abdude824's blog

By abdude824, history, 3 years ago, In English

Hey all, thanks for the overwhelming response on our project: Codeblast. If you haven't seen yet, check it here.

kartik8800 has recently launched codeforces problemsets for us to practice and jump our codeforces rating to the moon.

Here is the youtube link for the same. He has awesome playlists on various topics ranging from CSES problemsets, to topic wise discussions.

As a less rated user of the almighty Codeforces, I really liked the idea of specific problems picked manually and with some backed up data. But doing it with friends doubles the fun. So, I have included to practice from Kartik Arora's sheet as well in our project, Codeblast. You can also schedule contests now!

See this for a quick 1 min tutorial on how to use the site(Well, actually you can skip it).

Thanks Lord_Invincible as always for working with me and kartik8800 for the awesome sheets and mighty Mike for making codeforces!

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it

By abdude824, history, 3 years ago, In English

OOPs are actually very simple but we can have some difficult questions on OOPs as well. We will first have short notes of theory(which can be asked in form of questions) and then shift to questions.

I am refering E balaguruswamy book for this. These are short notes and may miss something, if you think something is missing please comment. Also, we would be using this track:

  1. Introduction to classes and objects
  2. Constructors and Destructors
  3. Operator Overloading
  4. Inheritance
  5. Polymorphism

We will be discussing major topics here and actually difficult ones. You must know basic OOPs.

Introduction

C structures Vs C++ Classes
General structure of classes
Visibility labels(Public, private, protected
Some terms and their meaning
For CP lovers, here is class based implementation of segment trees and Euler tours, representing inheritance as well(although we don't actually need inheritance here)
Memory allocation of member variables and functions accross objects

Static Data members

As we saw in memory allocation diagram, copies of member variables are made for different objects. But if we want a common variable for all objects of class? For example in an employee class, we need to find the number of employees at a specific time. We can do it using a global variable but that variable can interfere in the whole working of program. We can use a static data member. Static members are initialized to 0 and one important thing to note is that type and scope of static variable is defined outside the class. This is because they are not of every object but are unique to a class. And where we have variables, we do have functions also. Static member functions are also specific to a class, and can access only static members. Please have a code for implementation of both(Here I have kept the static member function outside to generalize the concept that static members are specific to class but they can be defined and implemented inside the class as well)

Sample Code for static data members

All other operations like making an array, vector, or any other STL container works the same for classes(Although you have to make a custom comparator in case of sorting through STL) remains almost same. We can also pass objects as arguments which is self explanatory.

Friendly Functions

There can be a case when we want some function to access private members of a class. For example, suppose there are two classes, Software engineers and Software testers. We want to find maximum income between both of the classes(Although many testers may not be eligible to pay taxes in India(Minimum salary is 5LPA for tax payers)). But we don't want to use the private member "income" as we can't access private members using objects directly. So, what we do is we make a friend function which can access private members of both the classes outside of both of them. This way, it can access both the classes without actually being a part of the class. (Obviously, we have to define that a particular function is friend inside the class as it would be a security threat if any function can be friend)

Code for Friend Functions

If a member function do not alter any data, we put a const ahead of its definition: void changeNothing() const;

Pointers to members of a class

Suppose this is the class:

class A{
private:
    int x;
};

We define a pointer to X as: int A ::* it=&A :: m;

Now, it contains address of m and we can refer to m using *it.

Constructors and Destructors

Constructor

Special member functions having the same name as the class used to initialize objects. Whenever a new object is created, this member function is called.

Constructor example in segment tree implementation

Constructors can be parametrized or without any parameters as well. Constructors without any parameters are default constructors. Please note that if a parameterized constructor is present and no default constructor is present, this type of initialization will give you an error: segTree s; because compiler couldn't find any default constructor. But if no constructor is present, compiler supplies one.

Some properties of constructors:

The parameters of a constructor can be of any type except for that class only but it can accept a reference to the class. These constructors are called copy constructors. Copy Constructors can be used to create two objects with same member variables.

Example of Copy Constructors

We can also use constructors dynamically. That is, we can use them after initialization of objects also.

Code for Dynamic Initialization of Objects

Destructors

A destructor, as name suggests, is used to delete objects that have been created by a constructor. As we saw in memory allocation, each object has its own memory for its member variables. Suppose we have a vector and we are resizing it inside the constructor. Then we should use a destructor as well to free that memory. (Not in general, but in big firms, yes its necessary)

Destructor Example

Operator Overloading

This is perhaps the most interesting part of OOPs. As we saw initially, we can't do a (+) operation on structures, but we can do it in classes using operator overloading. For example, we can use a (+) operator for strings to concatenate them in C++. Similarly, we can modify the meaning of an operator for a class. The possibilities with this are immense. Just imagine, you can actually add maps, sets according to the meaning interpreted by you. You can practically create your own language with this feature. But there are some operators you can't overload.

List of operators you can't overload

Please note that the precedence of the operators don't change. Multiplication will have a higher precedence than addition.

Let's Overload some Unary and Binary Operators!

  1. Unary Operator:
Example of Unary operator, in a class complex, which is like an actual complex number

Now, you might be having a feel how all the STL containers are made. And that's why OOPs are hell awesome!

Now let's overload a binary operator.

Overloading subtraction operator

Left hand operand is used to invoke the operator and right hand operand is passed as an argument.

Diagram representing the operator overloading process

As we used a friend function in dealing with "<<" operator, we have to use a friend member for dealing with any operator in which any one operator is not of the same type.

Type Conversion

We all know type conversions very well (Assuming you are familiar with C++). We use type conversions to convert a double to int, or a character to integer. Although it's not extreme necessary, but it saves some time. These are the three cases we can have :

  1. Basic to User defined class.
  2. User defined class to Basic
  3. User defined to another user defined

To be updated

Inheritance

Here comes the interesting part of OOPs. With this we can actually support reusability. It's quite easy to understand as well.

1. Types of Inheritance
2. Access modifiers in Inheritance
3. Ambiguities in Inheritance
4. Virtual base classes and their applications
5. Abstract classes and real life application
6. Nesting classes

If you want to see the real life application of inheritance, see this code snippet and working here(links would be attached soon). (It was made by me so, maybe a bit clumsy at first look, but see the working, it's my new project(The full project will be uploaded soon))

Polymorphism

To be updated

Full text and comments »

  • Vote: I like it
  • +80
  • Vote: I do not like it

By abdude824, 3 years ago, In English

If you are struggling with the right track and a 10-min read for Operating systems from beginning to end, you're at the right place. Even I am not sure where to start, but we would figure it and if you are reading this, I have successfully completed these notes or at least am on right track.

Let's start our struggle for OS:

The Track

I found many resources to learn, let's just list all: (Galvin Concise PPTs)[https://www.os-book.com/OS9/slide-dir/index.html]: These were great but I felt that these are a little bit too much, so here are the chapters we would do:

  1. Processes
  2. Threads
  3. Process Synchronization
  4. CPU Scheduling Algorithms
  5. Deadlocks
  6. Main memory
  7. Virtual memory
  8. Virtual Machines

I am skipping the introduction of OS for now as it was not that important, this is going to be a fast article that works like a last night dose.

A simple introduction(May skip if you are already familiar)

Processes

Processes are a program in execution. It has its own memory which is divided into four parts: Text, Data, Heap, and Stack.

Brief explanation about these

Process, as the name suggests, have different states (just like making a joint). Here is a diagram which says it all:

Diagram

Process Control Block(PCB)

It is a data structure that stores all information about a process.

It contains these:

Process Scheduling Queues

This handles the order of execution of the process. We have different queues for different states. When the state of a process is changed, it is simply detached from the current queue and added to its new state's queue.

This says it all

Schedulers

There are three types of schedulers, long term, short term, and mid term schedulers.

Brief explanation

Interrupts and Context Switch

An interrupt is like a signal to stop the current process and allow the higher priority process(the process causing the interrupt) to execute. But what happens to the previous process which CPU was executing? It gets saved! When an interrupt occurs, the system needs to save the current context of the process currently running on the CPU so that it can restore that context. It's like a bookmark we have while reading novels. For example, if you are reading a book on data structures and algorithms and suddenly you realize that watching that Avengers 10 min scene would be far more interesting, you place a bookmark and return after 2 hours to resume the same.

The context is saved in the PCB

Also, please note that taking up a new process requires saving the context of the current process and restore the context of the incoming process. This is known as context switch.

Inter-Process Communication

Inter-Process Communication or IPC for short is used for transferring information from one process to another.

Why we need IPC?

We have studied PCBs. We know Process information is stored in PCBs. And we need some sort of a temporary variable to transfer information(like we do to swap two numbers). And we do have two types of mechanisms on this type of principle.

IPC different mechanisms

Scheduling Algorithms

Terminology

Let's start with algorithms.

First Come First Serve(FCFS)
Shortest Job First(SJS)
Round Robin Algorithm

Process synchronization

Processes categorized on basis of synchronization

Process synchronization problem arises in the case of Cooperative process also because resources are shared in Cooperative processes.

Race Condition

When more than one process is executing the same code or accessing the same memory or any shared variable in that condition there is a possibility that the output or the value of the shared variable is wrong so for that all the processes doing the race to say that my output is correct this condition known as a race condition. Several processes access and process the manipulations over the same data concurrently, then the outcome depends on the particular order in which the access takes place.

Example

Critical Section

A critical section is a code segment that can be accessed by only one process at a time. This code segment is common in many processes and if many processes run simultaneously, we would have a hard time finding the process containing the error, if it happens.

Any solution to the critical section must satisfy these rules.
Here is what critical section looks like

Different Solutions to synchronization problems

1) Disabling Interrupts

We know we can have a race condition if we have some interrupt in a preemptive scheduling algorithm(in a single processor system. In a multiprocessor system, we can have a race condition if two processes on different processors execute the critical section). A process can simply announce that it is entering a critical section and the processor should not interrupt it. Well, it works fine, doesn't it? NO, of course not. This can lead to a lot of problems. Firstly, it is not applicable for multiprocessor systems. Secondly, we cannot give a process the freedom to block the interrupts. It can go on indefinitely inside the critical section, disabling interrupts forever.

2) Locks (or Mutex)

Here we have a lock. We acquire the lock, run a process in the critical section and then release the lock. How it's different from Disabling Interrupts? Here only the process which wants to execute inside the critical section wait, all other processes can still interrupt.

There are two types of implementations:

  1. Software: Peterson solution for two processes and Bakery Algorithm for multiple processes.

  2. Hardware: Generally used, because it's faster. We have test and lock instructions and much more.

Peterson's Solution

As we saw earlier, we need a solution for the critical section of code, as it can lead to anomalies. This solution should satisfy the rules we mentioned before.

Simple Psuedo code
How it works

3) Semaphores

Semaphore is nothing but an integer variable, and this can be changed by using only these two operations:

  1. Wait: It is like a decrement operation.
wait(S){
   while(S<=0);
   S--;
} 
  1. Signal:
Signal(S){
   S++
} 

Semaphores can be counting or binary(0 or 1).

Binary Semaphores are generally called mutex locks as they provide mutual exclusion.

Counting Semaphores are used to control access to a given resource for multiple processes.

Use of semaphores in handling critical section of N processes
How does this work?

Busy Waiting problem's solution

problem with semaphores
How we achieve busy waiting problem

4) Monitors

Deadlocks

Perfect example for deadlock
Okay, a serious example for deadlock
Conditions for a deadlock

Methods for deadlock prevention

  1. Deadlock Prevention or Avoidance: We have to prevent any of the four conditions mentioned above.
Let's see which one we can avoid.

2) Deadlock detection and recovery

3) Ignore Deadlock and Reboot the system

Example of this prevention

Problems were some processes along with resources and you have to find the order of execution or which process to remove to avoid deadlocks can be solved by these deadlock resolving techniques. We will be discussing some problems also

Banker's algorithm for avoiding Deadlocks

See the below table: Here initially, we had total resources of type A=10, B=5, C=7. (See it as A printers, B keyboards, C CPUs)

alt text

Here is the terminology used here:

  1. Allocation: Resources already allocated by the system

  2. Max Need: Need of resources by processes. (although we saw in the deadlock avoidance that pre-computing how many resources are needed by a process is not possible but still, if we somehow know the maximum need)

  3. Available: Resources available at a particular time. Here initially we had 10 types of A resources but at the point, we came, the system had already allocated some resources leaving us the mentioned resources.

  4. Remaining Need: We already have allocated some resources. The remaining need is just the maximum need-Allocated.

There can be two things here: detection and sequence of processes. We have to output a sequence of processes where deadlock not happens or say it's impossible.

Now, it's very simple from here. We have the remaining need for every process. We just now have to iterate sequentially and see which process we can execute. If it's executable, we can just execute it and we have the allocated resources of that particular process and the process is executed completely. If we come in a situation where we can't execute any process, we welcome the deadlock.

I will be making a Codeforces problem also on it. You can visualize this as a completely greedy algorithm. But as far as the practical application of this algorithm goes, as we saw previously also, we cannot have the max need of processes. We don't know which process wants what resource and for how long and thus, it's not that practical.

Threads

We saw in types of OS(in the introduction at the start of the blog) that we have multithreading as well. We have multiple threads running in an interleaved fashion inside a process. The foremost advantage is the increased responsiveness of the CPU. A thread is the smallest unit assignable to the CPU.

Interesting thing about threads
Advantages and Disadvantages of threads

Types of Threads

  1. User Level Thread: A process is creating multiple threads and the kernel is not at all aware of these threads being created. Here we don't need to call the OS and there are no system calls involved making it much faster for context switching. But we have both advantages and certain disadvantages as well. We get fast context switching, and very fast creation and termination time because of no involvement of kernel. But if even a single threads make a call that waits, then all of the other threads in the process have to wait for that call to complete. This is because the call would be made to kernel obviously, and kernel considers the thread as the whole process and would not entertain another call of the same process thread.

  2. Kernel Level Threads: Kernel knows and manages the threads. OS kernel provides system calls to create and manage threads. Kernel Level threads require the involvement of the kernel, which means that you have to do a MOR switch(Google it), you need to go from User space to the kernel space, and then you need to do the switch. And then we have to schedule some other thread as well.

Difference between the two

Feature User Level Thread Kernel Level Threads
Management In User space In kernel space
Context Switching Fast Slow
Blocking One thread might block all other threads A thread block itself only
Multicore or Multiprocessor Cannot take advantage of multicore system. Only concurrent execution on single processor Take full advantage of the multicore system.
Creation/Termination Fast Slow

Mapping of User threads to Kernel threads

  1. One to One: Most common way, used in common Operating Systems like windows. Every user thread is mapped to one kernel thread. Very similar to a pure kernel thread. They are slower than many to one but we can use multicore systems efficiently here.
  1. Many to One: Many users are mapped to one kernel thread. They can be seen as pure user threads. They do provide fast context switching along with fast creation and termination but we cannot utilize multicore systems and all the threads can be blocked by one thread making a system call.

  2. Many to Many: Very rarely used. Many user threads are mapped to many kernel threads.

Memory Management

Full text and comments »

  • Vote: I like it
  • +160
  • Vote: I do not like it

By abdude824, history, 3 years ago, In English

Hey all!

Need Motivation for upsolving contests in codeforces? Or just want to do mashups with you friends but need a tool for getting problems/bugaboos? Or just want to practice random/upsolving problems/bugaboos in form of a contest?

We have a solution: Codeblast!

  • Head to https://codeblast.herokuapp.com ,

  • Create a blast.

  • Add handles or just give them the invite link for the contest.

  • After everyone clicks the ready button, you would have the given number of problems/bugaboos with the given time.

  • Enjoy the contest!

Thanks Lord_Invincible and naman114 for working with me on this project!

Please test it and if you face any errors, feel free to comment.

Update: Github Link: https://github.com/abhi-824/codeblast

Update: Site down due to Heroku monthly limit. UPD: Running now.

Full text and comments »

  • Vote: I like it
  • +123
  • Vote: I do not like it

By abdude824, history, 3 years ago, In English

Hey all, With ICPC coming, we have made a team contest feature in GOC(gameofcodes.herokuapp.com).

Now you can do a team contest with multiple teams and questions would be fetched from Codeforces. And also, those questions would be from Upsolve Section(Questions you don't do after the contest ends).

Giving codeblast not only gives you a peer group and common discussion place but also, as the questions are from you combined upsolve section, it also helps in upsolving which is quite important in Competitive Programming. It will also help keep your whatsapp/discord peer coding groups active.

See the 1 min tutorial and workflow of Contest here: https://www.youtube.com/watch?v=BfIeNC4PJsg

So please give it a try and leave your feedback wither in comments or form on the website itself.

Also, do see the video, it would help in understanding the workflow of codeblast. We are open to any suggestions or features.

Thanks Lord_Invincible for working with me along to build this feature.

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By abdude824, history, 3 years ago, In English

Here’s my Codeforces Year in Review 2021! Get a glimpse into my Competitiveprogramming journey over the last twelve months:

https://gameofcodes.herokuapp.com/annual-report/report.html?handle=abdude824

Go check yours here: https://gameofcodes.herokuapp.com/annual-report/index.html

I and Lord_Invincible have been working on this annual report of your progress on #codeforces which gives deep analysis and badges based on your performance in 2021.

I got these 3 badges:

  • Thor (1 star) (For the number of questions done)

  • The Hawkeye(1 star) (For the my accuracy)

  • Hulk (1 star) (For doing 11 questions in 1 day)

Mine are not that good, all the very best for yours!

Any suggestions for improving the tool would be appreciated.

Do share yours in the comments. :)

Do Share it if you like it!

Full text and comments »

  • Vote: I like it
  • +830
  • Vote: I do not like it

By abdude824, history, 3 years ago, In English

Hey Fellow Coders!

I am really excited to share that we have reached 1000+ members on Game Of Codes. Thanks for your overwhelming response!

I have added some new features listed here:

  • Bookmarks: Now you can bookmark questions and see them in bookmarks section.

  • Login as Guest: Now, you can login as guest, but when logged in as a guest, you won't be able to set targets, add bookmarks, play one v one coding fights in codeblast.

  • Visualizers: Added sorting visualizers and path finding visualizers with amazing theory on the side bar.

If you haven't registered yet, register here and make your competitive journey much more exciting: Game Of CODES

Once again thanks for the support and I am working on errors you all have reported. Also, there is a very big surprise waiting for you, so stay connected!

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By abdude824, 3 years ago, In English

Hey fellow Coders! Are you a fan of Codeforces and love to solve competitive programming questions? Or you are preparing for a FAANG interview? Nevertheless, you would need Competitive Coding and a good rating at Codeforces to show off. But this is a skill that requires speed, accuracy and a hell lot of practice to improve your rating. But a lot of times hardwork doesn't work here and here is what I made you to get cover:

The Game of CODES or simply GOC, is a tool which not only analyze your performance but also recommend you questions based on your weak and strong topics! You can train them, track your consistency, do one vs one coding fights with your friends, and much more.

You can also set daily targets on basis of the difficulty of the questions. As we all know that doing more number of questions is not perhaps the best strategy. Instead doing harder ones is a better strategy. Now you can add targets for sum of rating of questions you do in one day. For example if you do two questions of 800 and 1000 rating the sum would be 1800.

Excited? So head to beat yourselves on : https://gameofcodes.herokuapp.com.

Also, there are a ton of features like community support, visualizers, and a much more to be added, so stay tuned!

Please give it a try and your constructive criticism is highly appreciated.

P.S.: There is even much more to come. Please do not judge me on my rating, I am just a redskull, guiding others to a treasure I cannot possess...

Here is a video link of the tour of the site:https://www.youtube.com/watch?v=YuQeYr8NDRU

Some Screenshots:

screenshot screenshot2 screenshot3

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it