DSA using C++

Chapter 1 - Flowchart & Pseudocode

• Flowchart
• Pseudocode
• C++ installation

Chapter 2 - Variable, Datatypes & Operators

Chapter 3 - Conditionals & Loops

Chapter 4 - Patterns

Chapter 5 - Functions

Chapter 6 - Binary Number System

How to convert Decimal to Binary?

1st Method:

• First you need to divide your decimal by 2 until it can't be divisible anymore.
• Second, you have to arrange the remainders from bottom to top, and it gives you the binary form of the decimal. For clarity, look at the bellow examples:

Decimal to binary from 1 - 10

2nd Method:

• For more clarity look at the bellow picture. just remember that we should always choose a limit which is less than our Decimal number, like I have choosen 32 or 2⁵, which is less than our Decimal number 37.

Decimal to binary - 37 & 17

How to convert Binary to Decimal?

• we have only have one way of doing it and that is the original mathematical way. Look at the bellow example for more clarity which converts binary (101010) to decimal.

Binary to Decimal conversion

Two's complement

we use Two's complement to store negative value to the memory. For calculating Two's complement of a number we do the following steps:

• Convert the number to Binary form.
• Prefix the Binary form with a zero (0).
• One's complement -> in the Binary, replace 0s with 1 and 1s with 0.
• Add 1 to the Binary.

Let's look this steps in an example

Two's complement of a number (-10)

Now, let's change the Two's complement of a number to it's original Decimal number.

• First, check the sign of a binary.
  • (-): If it starts with 1, it's negative in decimal.
  • (+): If it starts with 0, it's positive in decimal.
• Second, take out it's one's complement.
  • 0 ---> 1
  • 1 ---> 0
• Finally, add 1 to the binary.

- Change negative Binary (10110) to Decimal number

Now let's solve a question regarding Two's complement and it's vice versa.
Qs: Convert -8 to Binary and reverse.

// HomeWork
Qs: Convert -12 to binary & reverse ?

 -12

• 1100
• 01100
• 10011
• 10011 + 1 = 10100
  finally :   (-12)10 = (10100)2

Let's make it reverse:

• 10100
• 01011
• 01011 + 1 = 01100
• (1100)2 = (12)10
  Because, 10100 starts with 1 so it's decimal form has a negative sign (-12)10
(1100)2 = (-12)10

Chapter 7 - Bitwise operators, Scope, Datatype modifiers

Bitwise Operators

• AND ( & )
• OR ( | )
• XOR ( ^ ) --> (Exclusive OR)
• Left Shift operator (<<)
• Right Shift operator (>>)

Let's have a look to some examples:

Operators precedence

• look at the following chart:

• Let's have a look to an example of operator precedence:

Scope

Scope is the area in a program where a variable is accessible. It determines where the variable can be used, whether inside a function (local scope) or throughout the entire program (global scope).

• Local scope: Variables declared within a function or block can only be accessed within that specific function or block.
• Global scope: Variables declared outside of all functions or blocks can be accessed from anywhere in the program.

Examples for scope:

Datatype modifiers

Modifiers are used to alter the size or range of data types to suit different use cases.

• long (>= 4bytes) : Used to store values larger than the typical size for int. It guarantees at least 4 bytes of storage.

  long int population = 790000000;

• Short (<= 2bytes) : Used when you need to store small values and want to save memory. Common for values like age, where 2 bytes are sufficient.

  short int age = 21;

• long long (≥ 8 bytes) : Used to store very large values that exceed the range of long, like populations of entire countries or global figures.

  long long population = 7800000000;

• Signed : Specifies that a value can be either positive or negative. By default, int types are signed, so this is typically implicit unless you need to make it clear.

  signed int temperature = -5; // Allows negative values

• Unsigned - Used when a value can only be non-negative, like IDs or counts. It extends the range of positive numbers since no space is used for storing negative values.

  unsigned int customerId = 1202

Chapter 8 - Arrays

What is Local Array?

What is Dynamic Array?

Chapter 9 - Vectors

What is Vector?

A vector in C++ is a dynamic array from the Standard Template Library (STL) that can grow or shrink in size automatically, offering more flexibility than regular arrays.

Key Differences between Arrays and Vectors:

• Size:

  Array: Fixed size; defined at compile-time.
  Vector: Dynamic size; can grow or shrink at runtime.

• Memory:

  Array: Allocated on the stack (for local arrays), or heap (if dynamically allocated).
  Vector: Managed internally; automatically resizes and reallocates as needed.

• Initialization:

  Array: Must define size at declaration.
  Vector: No need to specify size; can initialize empty and add elements later.

• Bound Checking:

  Array: No automatic bounds checking.
  Vector: Provides bounds checking using .at() method (throws exceptions if out of range).

• Performance:

  Array: Faster for fixed-size data; no overhead from resizing.
  Vector: Slight overhead due to dynamic resizing but more flexible.

• Memory Reallocation:

  Array: No reallocation possible after declaration.
  Vector: Automatically reallocates and copies data when resized.

Memory Allocation in C++

1. Local Arrays (Stack Allocation)

Local arrays are fixed-size arrays that are stored on the stack. They are allocated when the function is called and automatically deallocated when the function ends. The size of local arrays must be known at compile-time.

• Pros:

  • Fast allocation and deallocation.
  • Simple to use.

• Cons:

  • Fixed size; cannot be resized at runtime.
  • Limited by stack size (typically small).

Example:

void localArrayExample() {
    int arr[5];  // A local array of size 5, allocated on the stack
    arr[0] = 10;
    arr[1] = 20;
    // The array is deallocated when the function ends
}

2. Dynamic Arrays (Heap Allocation)

Dynamic arrays are allocated on the heap using the new keyword, allowing their size to be determined at runtime. Unlike local arrays, dynamic arrays must be manually deallocated to prevent memory leaks.

• Pros:

  • Flexible size; can allocate as much memory as needed.
  • Large memory space compared to the stack.

• Cons:

  • Slower allocation and deallocation than the stack.
  • Requires manual deallocation using delete[].

Example:

void dynamicArrayExample() {
    int* arr = new int[5];  // A dynamic array of size 5, allocated on the heap
    arr[0] = 10;
    arr[1] = 20;
    delete[] arr;  // Deallocate the array to free memory
}

3. Vectors (Dynamic Size, Heap Allocation)

Vectors are part of the Standard Template Library (STL) and provide a dynamic array that can automatically grow or shrink as needed. Internally, vectors manage memory for you, and they are always allocated on the heap.

• Pros:

  • Dynamic size; automatically resizes as elements are added or removed.
  • Provides additional functionality like bounds checking with .at().
  • Handles memory allocation and deallocation automatically.

• Cons:

  • Slight overhead for resizing and memory management.
  • Slower than local arrays for fixed-size data.

Example:

#include <vector>
#include <iostream>

void vectorExample() {
    std::vector<int> vec;  // A vector, initially empty, allocated on the heap
    vec.push_back(10);     // Add elements to the vector
    vec.push_back(20);
    std::cout << "Vector size: " << vec.size() << std::endl;  // Output the size
    std::cout << "First element: " << vec[0] << std::endl;    // Access elements
    // No need for manual deallocation
}

Comparison Table