In this introductory instructional video on Programming with C++, the salient attributes and capabilities of C++ are elucidated, offering students an overarching view of the problem-solving potential inherent in this lower-level programming language.

The video effectively underscores certain noteworthy features, including:

• Its classification as a Low-Level Language, closely aligned with machine language intricacies.

• Profound Object-Oriented Support, facilitating structured programming paradigms.

• Lineage tracing back to the C programming language.

• Abundant and comprehensive built-in libraries such as <iostream>, <cmath>, <cstdlib>, and <fstream>.

• Evident High Execution Speed, contributing to expedient program performance.

The discourse culminates by delineating the domains in which C++ exhibits remarkable prowess, notably encompassing:

• Operating Systems

• Video Game Design

• Graphical User Interface (GUI) Development

• Web Browsing Applications

• Embedded Systems

Throughout the video, these concepts are expounded upon using numerous illustrative examples and thorough analytical dissections, ensuring optimal comprehension and assimilation.

In this instructional video centered on Programming with C++, the objective is to enhance one's grasp of C++ operators, cultivating a more refined comprehension of their functions and applications.

An operator, in its essence, represents a symbol employed to execute various operations, encompassing a broad spectrum including arithmetic, logical, and bitwise operations.

The C++ language accommodates a spectrum of operator categories designed to execute diverse operations, which encompass:

- Arithmetic Operators such as +, -, and *

- Relational Operators including <, >, <=, and >=

- Logical Operators represented by && and ||

- Bitwise Operators such as ^, |, and &

- Assignment Operator signified by =, =+, and =-

- Unary Operators in the forms of + and -

- Ternary or Conditional Operator recognized as ?:

- Miscellaneous Operator category

The precedence of operators determines the sequence in which they are evaluated, signifying which operator takes precedence over others. Associativity, on the other hand, denotes the direction of evaluation—whether proceeding from left to right or right to left.

Throughout the video presentation, these concepts are adeptly expounded upon, fortified by a profusion of illustrative examples and comprehensive analysis, thereby facilitating a more accessible and thorough assimilation of the subject matter.

"In this  Programming with C++ video, we will brush up on if-else conditionals and switch statements.

If statement is used to test the condition. There are various types of if statements in C++.

- if statement

- if-else statement

- nested if statement

- if-else-if ladder

The C++ if statement tests the condition. It is executed if condition is true.

#include <iostream>  

using namespace std;  

int main () {  

   int num = 10;    

            if (num % 2 == 0)    

            {    

                cout<<""It is even number"";    

            }   

   return 0;  

}    

#include <iostream>  

using namespace std;  

int main () {  

   int num = 11;    

            if (num % 2 == 0)    

            {    

                cout<<""It is even number"";    

            }   

            else  

            {    

                cout<<""It is odd number"";    

            }  

   return 0;  

}  

C++ If-else Ladder

if(condition1){    

//code to be executed if condition1 is true    

}else if(condition2){    

//code to be executed if condition2 is true    

}    

else if(condition3){    

//code to be executed if condition3 is true    

}    

...    

else{    

//code to be executed if all the conditions are false    

}  

Switch Statements - The C++ switch statement executes one statement from multiple conditions. It is like if-else-if ladder statement in C++.

int main () {  

       int num;  

       cout<<""Enter a number to check grade:"";    

       cin>>num;  

           switch (num)    

          {    

              case 10: cout<<""It is 10""; break;    

              case 20: cout<<""It is 20""; break;    

              case 30: cout<<""It is 30""; break;    

              default: cout<<""Not 10, 20 or 30""; break;    

          }    

    } 

Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding."

Within this educational presentation on Programming with C++, an in-depth exploration of loops is undertaken, aiming to provide a comprehensive grasp of fundamental concepts related to iteration in the C++ programming language.

The curriculum entails a thorough examination of diverse loop types, including the For loop, While loop, Do-While loop, and Nested loop, elucidated through practical and hands-on exemplifications.

For Loop: The For loop structure is expounded upon through the following illustration, demonstrating its application in generating sequential outputs:

for (int i = 0; i < 5; i++) {

    cout << i << "\n";

}

This example showcases the utilization of a For loop to print a table of numbers ranging from 1 to 10.

While Loop: The While loop is introduced, with the ensuing code snippet showcasing its employment to facilitate user input reception until a negative number is entered:

int i = 0;

while (i < 5) {

    cout << i << "\n";

    i++;

}

This illustration effectively conveys the utilization of a While loop to persistently solicit user input until a negative integer is provided.

Do-While Loop: The Do-While loop is thoroughly explicated, as demonstrated in the subsequent code excerpt that encapsulates its functionality:int i = 0;

do {

    cout << i << "\n";

    i++;

}

while (i < 5);

This exemplification underscores the characteristic of the Do-While loop, wherein the loop body is executed at least once. This is showcased through the creation of a menu-driven program, allowing users to make selections.

Throughout the presentation, these concepts are augmented with a plethora of practical examples and comprehensive analyses, affording a comprehensible and accessible understanding of the subject matter.

This educational segment on Programming with C++ elucidates three pivotal control flow keywords, unveiling their roles and functionalities.

Break Statement: The "break" keyword is employed to terminate the execution of a loop or switch statement. This abrupt termination occurs when a specified condition is met, disrupting the ongoing program flow. It's noteworthy that, within nested loops, "break" exclusively terminates the innermost loop.

int main() {

    for (int i = 1; i <= 10; i++) {

        if (i == 5) {

            break;

        }

        cout << i << "\n";

    }

}

Continue Statement: The "continue" statement serves to advance the flow of a loop, effectively skipping the remaining code within the loop body for a particular iteration. Similar to "break," in nested loops, "continue" pertains exclusively to the inner loop.for (int i = 1; i <= 10; i++) {

    if (i == 5) {

        continue;

    }

    cout << i << "\n";

}

Goto Statement: The "goto" keyword, functioning as a jump statement, is utilized to shift control to a designated section of the program. This unconditional jump entails transferring program execution to a specified label. "Goto" is particularly employed for navigating out of deeply nested loops or reaching specific switch case labels.int main() {

ineligible:

    cout << "You are not eligible to vote!\n";

    cout << "Enter your age:\n";

    int age;

    cin >> age;

    if (age < 18) {

        goto ineligible;

    } else {

        cout << "You are eligible to vote!";

    }

}

Throughout the instructional content, the material is accentuated through an assortment of illustrative examples and meticulous analysis, ensuring an accessible and comprehensive understanding of the concepts at hand.

This educational presentation on Programming with C++ delves into two important topics: writing comments in C++ and defining functions.

Comments in C++: Comments are statements that are not executed by the compiler but serve as explanatory annotations within the code. Comments can elucidate the purpose of code snippets, variables, methods, or classes. There are two categories of comments in C++:

• Single Line Comment:

  int x = 11; // x is a variable

• Multi-Line Comment:

  /* This is a multi-line comment

     used to declare and print variables in C++. */

  int x = 35;

These comment types are invaluable for enhancing code comprehension and can be used to both clarify the code's functionality and hide certain portions of it.

Functions: Functions are instrumental in executing tasks within a program and can be invoked multiple times, promoting modularity and code reusability. Two key categories of functions are discussed:

1. Library Functions: These functions are predefined in C++ header files and encompass operations such as ceil(x), cos(x), exp(x), among others.

2. User-defined Functions: Crafted by programmers to enhance code organization and optimize complexity in substantial programs.

An example of a user-defined function is provided:

void func() {

    static int i = 0;

    int j = 0;

    i++;

    j++;

    cout << "i=" << i << " and j=" << j << endl;

}

int main() {

    func();

}

Throughout the content, the presentation combines ample illustrative instances and thorough analyses to facilitate a comprehensive grasp of the material.

This instructional segment on Programming with C++ delves into two methodologies for passing parameters to functions: Call by Value and Call by Reference.

Call by Value: In this method, the value passed to a function is stored locally within the function parameter's stack memory location. Alterations made to the function parameter value solely affect the current function instance. The original value remains unaffected.

void change(int data);

int main() {

    int data = 3;

    change(data);

    cout << "Value of the data is: " << data << endl;

    return 0;

}

void change(int data) {

    data = 5;

}

// Output: Value of the data is: 3

Call by Reference: This approach entails passing the address of the value as a function parameter. Consequently, both the actual and formal arguments share the same memory address. Any changes made to the value via the formal parameter directly impact the actual parameter.

void swap(int *x, int *y);

int main() {

    int x = 500, y = 100;

    swap(&x, &y);

    cout << "Value of x is: " << x << endl;

    cout << "Value of y is: " << y << endl;

    return 0;

}

void swap(int *x, int *y) {

    int temp = *x;

    *x = *y;

    *y = temp;

}

// Output: Value of x is: 100

//         Value of y is: 500

Throughout the content, these concepts are elucidated using ample examples and comprehensive analyses, rendering the material accessible and deeply comprehensible.

This educational segment on Programming with C++ focuses on the concept of recursion, which is often considered challenging for beginners.

Recursion is a situation in which a function calls itself. The function that invokes itself is referred to as a recursive function.

An illustrative example of a recursive function calculates the factorial of a number:

#include <iostream>

using namespace std;

int factorial(int n) {

    if (n < 0)

        return -1;

    if (n == 0)

        return 1;

    else

        return n * factorial(n - 1);

}

int main() {

    int fact, value;

    cout << "Enter any number: ";

    cin >> value;

    fact = factorial(value);

    cout << "Factorial of a number is: " << fact << endl;

    return 0;

}

In this example, the factorial() function recursively calls itself with decreasing values of n. As n approaches 1, the recursive calls unravel, ultimately providing the final output.

Recursion is a crucial tool in solving problems related to data structures and advanced algorithms, particularly in scenarios like graph and tree traversal.

Throughout the content, the material is illuminated through comprehensive examples and in-depth analysis, facilitating a coherent and accessible understanding of the topic.

This instructional video on Programming with C++ delves into the subject of storage classes, which facilitate the declaration and management of variable types by defining their lifetime and visibility within the scope of a program.

C++ provides four primary storage classes:

1. Automatic: This is the default storage class for all local variables. The "auto" keyword is applied to local variables by default. These variables are automatically allocated memory when they come into scope and are deallocated when they go out of scope.

2. Register: A "register" variable is stored in a CPU register rather than in RAM memory. This allows for faster access compared to other variables. However, the size of a register variable is limited by the size of a CPU register.

3. Static: A "static" variable is initialized only once and retains its value between different function calls. It exists throughout the duration of the program and retains its value across multiple function calls. The default value for static variables is 0.

4. External: An "extern" variable is visible to all programs. It is used when multiple files need to share the same variable or function. An extern variable or function is declared in one file and can be accessed in other files that include its declaration.

Throughout the video, these storage class concepts are elucidated using a multitude of examples and comprehensive analyses, providing a thorough and accessible understanding of the topic.

In this instructive video on Programming with C++, we delve into a comprehensive exploration of arrays, which are fundamental linear data structures. An array in C++ constitutes a collection of elements of the same data type, residing in contiguous memory locations.

As detailed in the video, the following properties of arrays are highlighted:

Indexing Begins at 0: Array elements are accessed using indices, and the index count commences at 0. Arrays hold a predetermined number of elements in C++.

- **Random Access**: Elements within an array can be directly accessed using their respective indices.

- **Ease of Traversal, Manipulation, and Sorting**: Arrays facilitate convenient traversal, manipulation, and sorting operations.

This discussion encompasses two primary array types:

Single-Dimensional Array:

```cpp

int arr[5] = {10, 0, 20, 0, 30};

for (int i = 0; i < 5; i++) {

    cout << arr[i] << "\n";

}

```

Multidimensional Array: This category, including 2D and 3D arrays, will be expounded upon in a separate video.

Throughout the presentation, these concepts are fortified with a multitude of illustrative examples and in-depth analyses, facilitating a comprehensive and accessible understanding of the material.

In this comprehensive Programming with C++ video, we delve into performing operations on arrays by passing them as function arguments, as well as exploring the fundamentals of pointers in C++.

Passing Arrays to Functions: To pass an array to a function in C++, it is sufficient to provide the array name as an argument.

void printArray(int arr[5]);

int main() {

    int arr1[5] = { 10, 20, 30, 40, 50 };

    int arr2[5] = { 5, 15, 25, 35, 45 };

    printArray(arr1); // Passing array to function

    printArray(arr2);

}

void printArray(int arr[5]) {

    cout << "Printing array elements:" << endl;

    for (int i = 0; i < 5; i++) {

        cout << arr[i] << "\n";

    }

}

As showcased in the video, another approach is utilizing pointers to accomplish the same task. Pointers play a crucial role in Dynamic Memory Allocation.

Advantages of Pointers:

• Pointers enhance performance by enabling direct memory access.

• They allow functions to return multiple values through pointer references.

• Pointers enable access to any memory location within the computer's memory.

  
  

  int main() {

      int number = 30;

      int *p;

      p = &number;

      cout << "Address of number variable is: " << &number << endl;

      cout << "Address of p variable is: " << p << endl;

      cout << "Value of p variable is: " << *p << endl;

      return 0;

  }

Throughout the presentation, these concepts are elucidated using a multitude of illustrative examples and comprehensive analyses, rendering the material accessible and deeply comprehensible.

In this informative Programming with C++ video, we will delve into the intricacies of multidimensional arrays, a topic that has been previously mentioned in one of our earlier videos.

Multidimensional arrays, often referred to as rectangular arrays, can encompass two dimensions or even extend to three dimensions. The data within these arrays is arranged in a tabular form, resembling a matrix structure with rows and columns.

An illustrative example is provided to elucidate this concept:

int main() {

    int test[3][3] = {

        {2, 5, 5},

        {4, 0, 3},

        {9, 1, 8}

    };

    for (int i = 0; i < 3; ++i) {

        for (int j = 0; j < 3; ++j) {

            cout << test[i][j] << " ";

        }

        cout << "\n"; // New line at each row

    }

    return 0;

}

In this example, a 3x3 matrix named test is initialized with values. A nested loop structure iterates through the rows and columns, printing the array elements and creating a new line after each row.

Throughout the video, these concepts are illustrated using various examples and detailed analyses, providing a comprehensive and accessible understanding of the topic.

In this comprehensive Programming with C++ video, we will delve into three crucial concepts: pointers, the sizeof() operator, and the concept of void pointers.

Pointers in the C++ language are variables that serve as locators or indicators, pointing to the memory address of a value.

Advantages of Pointers:

• Enhances performance by enabling direct memory access.

• Facilitates returning multiple values from functions via pointers.

• Enables accessing any memory location in a computer's memory.

Address Operator (&): The ampersand sign is the address operator used to determine the memory address of a variable.

Indirection Operator (*): The asterisk sign represents the indirection operator, used to access the value stored at a particular memory address.

int main() {

    int number = 30;

    int *p;

    p = &number;

    cout << "Address of number variable is: " << &number << endl;

    cout << "Address of p variable is: " << p << endl;

    cout << "Value of p variable is: " << *p << endl;

    return 0;

}

sizeof() Operator: The sizeof() operator calculates the size of data types, constants, and variables.

std::cout << "Size of integer data type: " << sizeof(int) << std::endl;

std::cout << "Size of float data type: " << sizeof(float) << std::endl;

Void Pointers: A void pointer is a versatile pointer that can store the address of any data type. However, it is not associated with any specific data type.

void *ptr;          // void pointer declaration

int *ptr1;          // integer pointer declaration

int data = 10;      // integer variable initialization

ptr = &data;        // storing the address of data variable in void pointer variable

ptr1 = (int *)ptr;  // assigning void pointer to integer pointer

std::cout << "The value of *ptr1 is: " << *ptr1 << std::endl;

return 0;

Throughout the presentation, these concepts are reinforced with various illustrative examples and in-depth analyses, ensuring a comprehensive and accessible understanding of the material.

"In this Programming with C++ video, we will study about a variety of intermediate topics relating to pointers and references. In previous videos we have gone through standard variables and pointers but here you are being introduced to a new concept of references.

 It is a variable that behaves as an alias for another variable. They are created using the ampersand (&) operator. When we create a variable, then it occupies some memory location. We can create a reference of the variable; therefore, we can access the original variable by using either name of the variable or reference

CODE:

//Example 1

int a=10;  

int &ref=a;  

//Example 2

int a=10;   // 'a' is a variable.  

int &b=a; // 'b' reference to a.  

int &c=a; // 'c' reference to a.  

- Must be initialized during declaration.

- Cannot be reassigned

- Can also be passed as a function parameter.

Now we study references vs pointers:-

POINTERS

- A pointer can be initialized to any value anytime after it is declared.

- A pointer can be assigned to point to a NULL value.

- Pointers need to be dereferenced with a *

- A pointer can be changed to point to any variable of the same type.

REFERENCES

- A reference must be initialized when it is declared.

- References cannot be NULL.

- References can be used ,simply, by name.

- Once a reference is initialized to a variable, it cannot be changed to refer to a variable object.

In the final topic for this video, we will understand that function pointer is a pointer used to point functions. It is  used to store the address of a function. We can call the function by using the function pointer, or we can also pass the pointer to another function as a parameter.

They are mainly useful for event-driven applications, callbacks, and even for storing the functions in arrays.

void printname(char *name)  

{  

    std::cout << ""Name is :"" <<name<< std::endl;  

}  

int main()  

{  

    char s[20];  

    void (*ptr)(char*);  // function pointer declaration  

    ptr=printname;  // storing the address of printname in ptr.  

    std::cout << ""Enter the name of the person: "" << std::endl;  

    cin>>s;  

    cout<<s;  

    ptr(s); 

   return 0;  

}  

Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding."

"In this Programming with C++ video, we will do a deep-dive in memory management.

Memory Management:

As explained in the video, Memory management is a process of managing computer memory, assigning the memory space to the programs to improve the overall system performance. Sometimes, exact memory is not determined until runtime. To avoid such a situation, we declare an array with a maximum size, but some memory will be unused. To avoid the wastage of memory, we use the new operator to allocate the memory dynamically at the run time.

A new operator is used to create the object.

A delete operator is used to delete the object. 

CODE:

int main()  

{  

int size;  // variable declaration  

int *arr = new int[size];   // creating an array   

cout<<""Enter the size of the array : "";     

std::cin >> size;    //   

cout<<""\nEnter the element : "";  

for(int i=0;i<size;i++)   // for loop  

{  

cin>>arr[i];  

}  

cout<<""\nThe elements that you have entered are :"";  

for(int i=0;i<size;i++)    // for loop  

{  

cout<<arr[i]<<"","";  

}  

delete arr;  // deleting an existing array.  

return 0;  

Malloc() vs new

- The new operator constructs an object, i.e., it calls the constructor to initialize an object while malloc() function does not call the constructor. The new operator invokes the constructor.

- The new is an operator, while malloc() is a predefined function in the stdlib header file.

- In the new operator, we need to specify the number of objects to be allocated while in malloc() function, we need to specify the number of bytes to be allocated.

- For new operator, we have to use the delete operator to deallocate the memory. For malloc() function, we need the free() function.

Delete() vs free

- The delete is an operator that de-allocates the memory dynamically while the free() is a function that destroys the memory at the runtime.

- When the delete operator destroys the allocated memory, then it calls the destructor of the class in C++, whereas the free() function does not call the destructor; it only frees the memory from the heap.

- The delete() operator is faster than the free() function.

Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding."

"In this Programming with C++ video, we will study about concepts of Object Oriented Programming such as inheritance, data binding, polymorphism etc.

- Object - Any entity that has state and behavior is known. It is an instance of class.

- Class - Collection of objects is called class.

- Inheritance - When one object acquires all the properties and behaviors of parent object i.e. known as inheritance.

- Polymorphism - When one task is performed by different ways i.e. known as polymorphism.

- Abstraction - Hiding internal details and showing functionality is known as abstraction

- Encapsulation - Binding (or wrapping) code and data together into a single unit is known as encapsulation

Code for Creating Objects and Classes in C++:

class Student {  

   public:  

      int id;//data member (also instance variable)      

      string name;//data member(also instance variable)      

};  

int main() {  

    Student s1; //creating an object of Student   

    s1.id = 201;    

    s1.name = ""Board Infinity"";   

    cout<<s1.id<<endl;  

    cout<<s1.name<<endl;  

    return 0;  

}  

In future videos, we will explore all the OOP concepts in much more detail.  Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding."

"In this Programming with C++ video, we will study about constructors and destructors and how they make it easier to instantiate objects and assign them values rapidly.

Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

Constructor is a special method which is invoked automatically at the time of object creation and used to initialize the data members of new object generally.

There can be two types of constructors in C++.

- Default constructor

- Parameterized constructor

Example-

class Employee  

 {  

   public:  

        Employee()    

        {    

            cout<<""Default Constructor Invoked""<<endl;    

        }    

};  

int main(void)   

{  

    Employee e1; //creating an object of Employee   

    Employee e2;   

    return 0;  

}  

Copy Constructor:

A Copy constructor is an overloaded constructor used to declare and initialize an object from another object. It is useful when

we initialize the object with another existing object of the same class type. For example, Student s1 = s2, where Student is the class.

class A  

{  

   public:  

    int x;  

    A(int a)                // parameterized constructor.  

    {  

      x=a;  

    }  

    A(A &i)               // copy constructor  

    {  

        x = i.x;  

    }  

};  

int main()  

{  

 A a1(20);              

 A a2(a1);               

 cout<<a2.x;  

  return 0;  

}  

Destructors:

As explained in the video, A destructor works opposite to constructor; it destructs the objects of classes. It can be defined only once in a class. Like constructors, it is invoked automatically and prefixed with a tilde sign (~).

Example-

class Employee  

 {  

   public:  

        Employee()    

        {    

            cout<<""Constructor Invoked""<<endl;    

        }    

        ~Employee()    

        {    

            cout<<""Destructor Invoked""<<endl;    

        }  

};  

int main(void)   

{  

    Employee e1; //creating an object of Employee   

    Employee e2; //creating an object of Employee  

    return 0;  

}  "

"In this Programming with C++ video, we will study about more data types that make the object oriented programming reliable and easy to use like structs and enums along with studying class related concepts like this pointer and static keyword.

Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

THIS POINTER:

It is a keyword that refers to the current instance of the class. There can be 3 main usage of this keyword in C++.

- It can be used to pass current object as a parameter to another method.

- It can be used to refer current class instance variable.

- It can be used to declare indexers.

CODE:

class Employee {  

   public:  

       int id; //data member (also instance variable)      

       string name; //data member(also instance variable)  

       float salary;  

       Employee(int id, string name, float salary)    

        {    

             this->id = id;    

            this->name = name;    

            this->salary = salary;   

        }    

       void display()    

        {    

            cout<<id<<""  ""<<name<<""  ""<<salary<<endl;    

        }    

};  

int main(void) {  

    Employee e1 =Employee(101, ""abc"", 890000);

    Employee e2=Employee(102, ""xyz"", 59000); 

    e1.display();    

    e2.display();    

    return 0;  

}  

STATIC:

It is a is a keyword or modifier that belongs to the type not instance. So instance is not required to access the static members. In C++, static can be field, method, constructor, class, properties, operator and event. Useful when counting total number of objects created for a class.

Code Snippet -

class Account {  

   public:  

       int accno; 

       string name;   

       static int count;     

       Account(int accno, string name)   

        {    

             this->accno = accno;    

            this->name = name;    

            count++;  

        }    

       void display()    

        {    

            cout<<accno<<"" ""<<name<<endl;   

        }    

};  

Structs:

Structure is a collection of different data types. It is similar to the class that holds different types of data.

Structure variable can be defined as:

Student s;

Variables of structures can be accessed using dot operator just like classes.

 struct Rectangle      

{      

   int width, height;      

 };      

int main(void) {    

    struct Rectangle rec;    

    rec.width=8;    

    rec.height=5;    

   cout<<""Area of Rectangle is: ""<<(rec.width * rec.height)<<endl;    

 return 0;    

} 

Enum:

 It is a data type that contains fixed set of constants.  They are static and final implicitly.

enum week { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday };  

int main()  

{  

    week day;  

    day = Friday;  

    cout << ""Day: "" << day+1<<endl;  

    return 0;  

}     

This will output day as 5.

"

"In this Programming with C++ video, we will study about friend functions and classes and their use cases in great detail. Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

If a function is defined as a friend function in C++, then the protected and private data of a class can be accessed using the function. By using the keyword friend compiler knows the given function is a friend function. For accessing the data, the declaration of a friend function should be done inside the body of a class starting with the keyword friend.

As explained in the video, it has the following characteristics:-

- It cannot access the member names directly and has to use an object name and dot membership operator with the member name.

- It is not in the scope of the class to which it has been declared as a friend.

- It cannot be called using the object as it is not in the scope of that class.

- It can be invoked like a normal function without using the object.

- It can be declared either in the private or the public part.

CODE:

class Box    

{    

    private:    

        int length;    

    public:    

        Box(): length(0) { }    

        friend int printLength(Box); //friend function    

};    

int printLength(Box b)    

{    

   b.length += 10;    

    return b.length;    

}    

int main()    

{    

    Box b;    

    cout<<""Length of box: ""<< printLength(b)<<endl;    

    return 0;    

}    

Just like friend functions, we can also create friend classes. "

"In this Programming with C++  video we study about basic math functions which require the header file<math.h>

In the video, each of these functions is explained with a code example:-

- cos(x) - computes the cosine of x.

- sin(x) -  computes the sine of x.

- tan(x) - computes the tangent of x.

- pow(x,y) - computes x raised to the power y.

- sqrt(x) - computes the square root of x.

- ceil(x) - rounds up the value of x.

- floor(x) - rounds down the value of x.

- round(x) - rounds off the value of x."

"In this Programming with C++ video, we will study about more advanced OOP concepts like Inheritance, its extension called as Aggregation and Polymorphism. Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

INHERTIANCE:

The class which inherits the members of another class is called derived class and the class whose members are inherited is called base class. The derived class is the specialized class for the base class.

Inheritance is a process in which one object acquires all the properties and behaviors of its parent object automatically. In such way, you can reuse, extend or modify the attributes and behaviors which are defined in other class.

As demonstrated in the video, C++ offers 5 types of inheritance:

- Single inheritance - Where 'A' is the base class, and 'B' is the derived class.

- Multiple inheritance - class 'C' inherits two base classes 'A' and 'B'

- Hierarchical inheritance

- Multilevel inheritance - Class C inherits from Class B which in turn inherits from Class A

- Hybrid inheritance - Mixed inheritance from all the other types.

CODE:

class Shape                 

{  

    public:  

    int a;  

    int b;  

    void get_data(int n,int m)  

    {  

        a= n;  

        b = m;  

    }  

};  

class Rectangle : public Shape  

{  

    public:  

    int rect_area()  

    {  

        int result = a*b;  

        return result;  

    }  

};  

class Triangle : public Shape   

{  

    public:  

    int triangle_area()  

    {  

        float result = 0.5*a*b;  

        return result;  

    }  

};  

AGGREGATION:

As explained in the video, aggregation is a process in which one class defines another class as any entity reference. It is another way to reuse the class. It is a form of association that represents HAS-A relationship.

POLYMORPHISM:

When the same function demonstrates different behavior it is known as polymorphism and it is of two types:-

- Compile time polymorphism: The overloaded functions are invoked by matching the type and number of arguments.

- Run time polymorphism: Run time polymorphism is achieved when the object's method is invoked at the run time instead of compile time

We will be studying these in the following videos in greater detail.  "

"In this Programming with C++ video, we will study about two important concepts related to Classes and inheritance. Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

OVERLOADING:

Creating two or more members having the same name but different in number or type of parameter is known as overloading.

C++ allows the overloading of :-

- methods,

- constructors, and

- indexed properties

and is of two types:-

- Function overloading - having two or more function with the same name, but different in parameters.

CODE:

class Cal {    

    public:    

static int add(int a,int b){      

        return a + b;      

    }      

static int add(int a, int b, int c)      

    {      

        return a + b + c;      

    }      

};     

int main(void) {    

    Cal C;                                                    //     class object declaration.   

    cout<<C.add(10, 20)<<endl;      

    cout<<C.add(12, 20, 23);     

   return 0;    

}    

- Operator overloading - operator is overloaded to provide the special meaning to the user-defined data type. Operator overloading is used to overload or redefines most of the operators available in C++

Some exceptions to this are:-

Scope operator (::), Sizeof, member selector(.), member pointer, selector(*), ternary operator(?:)

There are also some norms associated with overloading operators:-

- Existing operators can only be overloaded.

- The overloaded operator contains at least one operand of the user-defined data type.

- When unary operators are overloaded through a member function take no explicit arguments, but, if they are overloaded by a friend function, takes one argument.

- When binary operators are overloaded through a member function takes one explicit argument, and if they are overloaded through a friend function takes two explicit arguments.

class Test    

{    

   private:    

      int num;    

   public:    

       Test(): num(8){}    

       void operator ++()         {     

          num = num+2;     

       }    

       void Print() {     

           cout<<""The Count is: ""<<num;     

       }    

};    

int main()    

{    

    Test tt;    

    ++tt;  // calling of a function ""void operator ++()""    

    tt.Print();    

    return 0;    

}    

OVERRIDING

If derived class defines same function as defined in its base class, it is known as function overriding and it  enables you to provide specific implementation of the function which is already provided by its base class.

class Animal {  

    public:  

void eat(){    

cout<<""Eating..."";    

    }      

};   

class Dog: public Animal    

{    

 public:  

 void eat()    

    {    

       cout<<""Eating bread..."";    

    }    

};  

int main(void) {  

   Dog d = Dog();    

   d.eat();  

   return 0;  

}  "

"In this Programming with C++ video, we will study about virtual functions and how to properly use them in the correct situation.

Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

A  virtual function is a member function in the base class that you redefine in a derived class. It is declared using the virtual keyword.

- Used to message compiler to perform dynamic linkage or late binding on the function.

- Must be members of some class.

- Cannot be static members.

- Accessed through object pointers.

- Can be a friend of another class.

- Must be defined in the base class, even though it is not used.

- We cannot have a virtual constructor, but we can have a virtual destructor.

CODE:

#include <iostream>    

{    

 public:    

 virtual void display()    

 {    

  cout << ""Base class is invoked""<<endl;    

 }    

};    

class B:public A    

{    

 public:    

 void display()    

 {    

  cout << ""Derived Class is invoked""<<endl;    

 }    

};    

int main()    

{    

 A* a;    //pointer of base class    

 B b;     //object of derived class    

 a = &b;    

 a->display();   

}    

Further, a ""do-nothing"" function is known as a pure virtual function. A pure virtual function is a function declared in the base class that has no definition relative to the base class.

virtual void display() = 0;   

"

"In this Programming with C++ video, we will study about Abstraction. Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

Abstraction is a process of providing only the essential details to the outside world and hiding the internal details, i.e., representing only the essential details in the program. It can be achieved in C++ using header files or wrapping program logic in classes.

As explained in the video, it should be employed when you want to:-

- Protect details of the class from user level errors.

- not need to write the low level code.

- avoid code duplication.

CODE:

#include <iostream>    

using namespace std;    

 class Sum    

{    

private: int x, y, z; 

public:    

void add()    

{    

cout<<""Enter two numbers: "";    

cin>>x>>y;    

z= x+y;    

cout<<""Sum of two number is: ""<<z<<endl;    

}    

};    

int main()    

{    

Sum sm;    

sm.add();    

return 0;    

}    

Another example would be in-built functions and how they simply allow the usage of a feature without having the programmer to know their implementation."

"In this Programming with C++ video, we will study about interfaces and use our knowledge from the previous video about abstraction. Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

An interface describes the behavior or capabilities of a C++ class without committing to a particular implementation of that class.

Interfaces are implemented using abstract classes.

As demonstrated in the video, a class is made abstract by declaring at least one of its functions as pure virtual function. A pure virtual function is specified by placing ""= 0"" in its declaration as follows −

CODE:

using namespace std;  

 class Shape    

{    

    public:   

    virtual void draw()=0;    

};    

 class Rectangle : Shape    

{    

    public:  

     void draw()    

    {    

        cout < <""drawing rectangle..."" < <endl;    

    }    

};    

class Circle : Shape    

{    

    public:  

     void draw()    

    {    

        cout <<""drawing circle..."" < <endl;    

    }    

};    

int main( ) {  

    Rectangle rec;  

    Circle cir;  

    rec.draw();    

    cir.draw();   

   return 0;  

}  "

"In this Programming with C++ video, we will study about namespaces. Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

Namespaces in C++ are used to organize too many classes so that it can be easy to handle the application.

For accessing the class of a namespace, we need to use namespacename::classname. Use using keyword so that we don't have to use complete name all the time.

Commonly addressed namespace is ""std"" provided by C++ Framework.

CODE:

using namespace std;  

namespace First{  

   void sayHello(){  

      cout << ""Hello First Namespace"" << endl;  

   }  

}  

namespace Second{  

   void sayHello(){  

      cout << ""Hello Second Namespace"" << endl;  

   }  

}  

using namespace First;  

int main () {  

   sayHello();  

   return 0;  

}  "

"In this Programming with C++ video, we will study about Strings and the functions associated with them.

As seen in the video, String is an object of std::string class that represents sequence of characters. We can perform many operations on strings such as concatenation, comparison, conversion etc.

The C++ compiler automatically places the '\0' at the end of the string when it initializes the array.

CODE:

 string s1 = ""Hello"";    

        char ch[] = { 'C', '+', '+'};    

        string s2 = string(ch);    

        cout<<s1<<endl;    

        cout<<s2<<endl;  

We see some commonly used functions related to strings in the video like:-

- strcpy(s1, s2) - Copies string s2 into string s1.

- strcat(s1, s2) - Concatenates string s2 onto the end of string s1.

- strlen(s1) - Returns the length of string s1.

- strcmp(s1, s2) - Returns 0 if s1 and s2 are the same; less than 0 if s1<s2; greater than 0 if s1>s2.

- strchr(s1, ch) -  Returns a pointer to the first occurrence of character ch in string s1.

- strstr(s1, s2) - Returns a pointer to the first occurrence of string s2 in string s1.

Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding. "

"In this Programming with C++ video, we will study about a new topic known as Exception Handlin which is a process to handle runtime errors.

Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

It is required so that the normal flow of the application can be maintained even after runtime errors. In C++, exception is an event or object which is thrown at runtime. All exceptions are derived from std::exception class. It is a runtime error which can be handled. If we don't handle the exception, it prints exception message and terminates the program.

Standard exceptions are defined in <exception> class that we can use inside our programs.

There are 3 keywords to perform exception handling:

- try

- catch, and

- throw

"In this Programming with C++ video, we will study about try/catch block and how they are useful to handle exceptions in C++. Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

try block is used to place the code that may occur exception.

catch block is used to handle the exception.

Example Code using try/catch -

#include <iostream>  

using namespace std;  

float division(int x, int y) {  

   if( y == 0 ) {  

      throw ""Attempted to divide by zero!"";  

   }  

   return (x/y);  

}  

int main () {  

   int i = 25;  

   int j = 0;  

   float k = 0;  

   try {  

      k = division(i, j);  

      cout << k << endl;  

   }catch (const char* e) {  

      cerr << e << endl;  

   }  

   return 0;  

}  

This will not throw an error and halt the program but show a user-defined error and continue the flow of the program. "

"In this Programming with C++ video, we will study about a new topic known as User Defined functions. Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

As explained via the video, C++ allows the programmer to define their own function.

A user-defined function groups code to perform a specific task and that group of code is given a name (identifier).

When the function is invoked from any part of the program, it all executes the codes defined in the body of the function.

CODE:

#include <iostream>

using namespace std;

// declaring a function

int add(int a, int b) {

    return (a + b);

}

int main() {

    int sum;

    sum = add(100, 78);

    cout << ""100 + 78 = "" << sum << endl;

    return 0;

}"

"In this Programming with C++ video, we will study about Templates in C++.  Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

As seen in the video, templates allow you to define the generic classes and generic functions and thus provides support for generic programming. Templates can make a function or class work for a variety of data types.

Templates can be:-

1. Function Templates -

- Generic functions use the concept of a function template. Generic functions define a set of operations that can be applied to the various types of data.

- The type of the data that the function will operate on depends on the type of the data passed as a parameter.

CODE:

template<class T> T add(T &a,T &b)  

{  

    T result = a+b;  

    return result;  

}  

OR

2. Class Templates - similar to the Function Template. When a class uses the concept of Template, then the class is known as generic class.

Ttype is a placeholder name which will be determined when the class is instantiated.

template<class T>  

class A   

{  

    public:  

    T num1 = 5;  

    T num2 = 6;  

    void add()  

    {  

        std::cout << ""Addition of num1 and num2 : "" << num1+num2<<std::endl;  

    }  

};  "

"In this Programming with C++ video, we will study about Signal Handling in C++.  Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

Signals are the interrupts which are delivered to a process by the operating system to stop its ongoing task and attend the task for which the interrupt has been generated.

- These signals are defined in <csingnal> header file.

- Signals can also be generated by the operating system on the basis of system or error condition.

void (*signal (int sig, void (*func)(int)))(int);  

As seen in the video, we go over some signals in C++ and learn their proper usage-

- SIGABRT (Signal Abort) Abnormal termination of the program, such as a call to abort.

- SIGFPE (Signal floating- point exception) An erroneous arithmetic operation, such as a divide by zero or an operation resulting in overflow.

- SIGILL (Signal Illegal Instruction) It is used for detecting an illegal instruction.

- SIGINT (Signal Interrupt) It is used to receipt an interactive program interrupt signal.

- SIGSEGV (Signal segmentation Violation) An invalid access to storage.

- SIGTERM (Signal Termination) A termination request sent to the program.

- SIGHUP (Signal Hang up) Hang Up, it reports that user's terminal is disconnected. It is used to report the termination of the controlling process."

"In this Programming with C++ video, we will study about Files and Streams which are useful for file handling operations in C++.  Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

Using the iostream standard library, we use cin and cout methods for reading from input and writing to output respectively.

To read and write from a file we are using the standard C++ library called fstream.

fstream library offers:

- fstream - To create files, write information to files, and read information from files.

- ifstream - To read information from files.

- ofstream - To create files and write information to the files.

Example of Reading and Writing to a file -

int main () {  

   char input[75];  

   ofstream os;  

   os.open(""testout.txt"");  

   cout <<""Writing to a text file:"" << endl;  

   cout << ""Please Enter your name: "";   

   cin.getline(input, 100);  

   os << input << endl;  

   cout << ""Please Enter your age: "";   

   cin >> input;  

   cin.ignore();  

   os << input << endl;  

   os.close();  

   ifstream is;   

   string line;  

   is.open(""testout.txt"");   

   cout << ""Reading from a text file:"" << endl;   

   while (getline (is,line))  

   {  

   cout << line << endl;  

   }      

   is.close();  

   return 0;  

}  "

"In this Programming with C++ video, we will study about getline() function in C++.  Concepts are explained with plenty of examples and in-depth analysis for your ease of understanding.

As seen in the video, to accept the multiple lines, we use the getline() function. It is a pre-defined <string.h> header file used to accept a line or a string from the input stream until the delimiting character is encountered.

Syntax-

istream& getline( istream& is, string& str, char delim );  

/*

is: object of the istream class that defines from where to read the input stream.

str: a string object in which string is stored.

delim: the delimiting character.

*/

In the following example we use we have used the getline() function to accept the character even when the space character is encountered.

CODE:

#include <iostream>  

#include<string.h>  

using namespace std;  

int main()  

{  

string name; // variable declaration.  

std::cout << ""Enter your name :"" << std::endl;  

getline(cin,name); 

cout<<""\nHello ""<<name;  

return 0;}  "

"In this video, you will learn about the array data structure, its declaration methods, syntax, implementation, and applications in DSA.  

This video will make it quite easy to understand, grasp, and master Arrays.  Arrays are required for almost all programming problems and hence it is a must-know data type for any DSA challenge.

- Arrays are used to store multiple values in a single variable, instead of declaring separate variables for each value.

- To declare an array, define the variable type, specify the name of the array followed by square brackets and specify the number of elements it should store.

- You access an array element by referring to the index number inside square brackets []

Syntax:

int arr[] = { 10, 20, 30, 40};

OR

int arr1[10];"

"In this video you will learn about the operations performed on array data structure, such as accessing array value using indexes, removing elements from an array, or adding elements to an array.

Here, we will compare arrays with mathematical matrices to spot the similarity and make it easier for you to grasp the concepts quickly.

An array supports the following operations:

- Traversal

- Insertion

- Deletion

- Search

Other operations include sorting ascending, sorting descending, etc. Let's follow up on these individually.

Traversal:

Visiting every element of an array once is known as traversing the array.

It is important for use cases like:

- Storing all elements – Using scanf()

- Printing all elements – Using printf()

- Updating elements.

An array can easily be traversed using a for loop in C++

Array Size:

If we create an array of length 100 using a[100]. It is possible for a program to use just 60 elements out of these 100. (But we cannot go beyond 100 elements).

Insertion:

An element can be inserted in an array at a specific position. For this operation to succeed, the array must have enough capacity.

Sorting:

Sorting means arranging an array in an orderly fashion (ascending or descending). We have different algorithms to sort arrays. In the upcoming videos, we will explore these in much more detail.

Also, you will learn how to debug possible errors related to arrays. This video will also revise for loops and iteration methods to dynamically determine array size during traversal.  

Syntax:

//Initialization Operation

Int Arr1;

Arr1[0] = -10;

// Access an Element

 printf(""%d\n"", arr[2]);

//Modify Operation

Arr1 [0] = 15; "

"In this video, you will learn about finding the largest element in an array using an application-based solution.

Given an array arr[] of size n, write a program to find the largest element in it.

Example 1:

Input: arr[] = [100, 50, 4]

Output: 100

Explanation: 100 is the largest element in the given array.

We accept the array elements from the user and run a for loop to check whether the next element in the unsorted array are of higher value compared to the previous elements.

If yes, we switch the element. We continue this algorithm until we reach the end of the array and store the max value in a variable that is outputted at the end.

Psuedo Code:

1. Take an array A and define its values

2. Declare largest as an integer

3. Set 'largest' to 0 

4. Loop for each value of A

5. If A[n] > largest, Assign A[n] to largest

6. After the loop finishes, Display largest as the largest element of an array."

"In this video, you will learn about the fundamentals of sorting algorithms and methods to sort an unsorted array of positive/negative elements in ascending order using concepts learned earlier.

Our problem: Given an array of size n, write a program to check if it is sorted in ascending order or not. Equal values are allowed in an array and two consecutive equal values are considered sorted.

Example:

Input : 20 20 45 89 89 90

Output : Yes

Input : 20 20 78 98 99 97

Output : No

- First, check if elements are already sorted or length of the array is greater than 1.

- If it is unsorted, implement a sorting algorithm like Bubble Sort or Selection sort and compare every element with the previous element for each iteration and switch the elements until the array gets sorted.

This video contains a practical hands-on explanation of basic sorting algorithms required for brute force approaches. "

"In this video, the problem of second largest element from an unsorted array will be explained. Some cases discussed are:-

Example 1: Given input array is {12, 35, 1, 10, 34, 1}

Output: The second largest element in array is 34.

The loop will find the largest element present in the array which is smaller than the largest element.

Start traversing the array from array[1],

- If the current element in array say arr[i] is greater than first. Then update first and second as, second = first & first= arr[i]

- If the current element is in between first and second Then update second to store the value of current variable as second = arr[i]

- Return the value stored in the second."

"In this video, you will be learning about a simple approach to reverse the array in-place. In place means, we will not be using some auxiliary space.

Our Problem Statement: Given an array (or string), the task is to reverse the array/string.

Example : 

Input  : arr[] = {1, 2, 3}

Output : arr[] = {3, 2, 1}

To reverse an array, we will use the concept of swapping. First, the problem strategy will be discussed followed by two approaches coded in C++.

In short, set two pointers at the start and end of the array and start iterating over it till the (length of array)/2. For every idx, swap array[idx] with array[length - idx]

Psuedo Code:

void reverseArray(int[] arr) {

   start = 0

   end = arr.length - 1

   while (start < end) {

       // swap arr[start] and arr[end]

       int temp = arr[start]

       arr[start] = arr[end]

       arr[end] = temp

       start = start + 1

       end = end - 1

   }

}"

"In this video, you learn how to make an array consisting of only unique elements by removing all the duplicates.

Our Problem Statement - Given a sorted array, the task is to remove the duplicate elements from the array.

Example -

Input  : arr[] = {2, 2, 2, 2, 2}

Output : arr[] = {2}

         new size = 1

Note that the array input will be sorted.

After iterating over the array elements, we will check if the previous element is not equal to the next element (because array is sorted) and if it is we will omit that element and store the rest of the elements in a new array that will be outputted to the user.

Pseudo Code:

- Input the number of elements of the array.

- Input the array elements.

- Repeat from i = 1 to n

    - if (arr[i] != arr[i+1])

    - temp[j++] = arr[i]

    - temp[j++] = arr[n-1]

- Repeat from i = 1 to j

    - arr[i] = temp[i]

  return j."

"In this video, the problem is to rotate the elements of an array towards the left by the specified number of times (D places).

Problem Statement:

Given an array of integers arr[] of size N and an integer, the task is to rotate the array elements to the left by d positions.

Example:  

Input: arr[] = {1, 2, 3, 4, 5, 6, 7}, d = 2

Output: 3 4 5 6 7 1 2

First, we will try out a strategy to do it for one index and then extend this knowledge to do it N times. In the left rotation, each element of the array will be shifted to its left by one position and the first element of the array will be added to end of the list.

This process will be followed for a specified number of times.

Steps:

1. Declare and initialize an array.

2. Variable n will denote the number of times an array should be rotated toward its left.

3. The array can be left rotated by shifting its elements to a position prior to them which can be accomplished by looping through the array and perform the operation arr[j] = arr[j+1].

4. The first element of the array will be added to the last of rotated array."

"In this video, the problem is to take all the zeros from an array and place at the rightmost end.

Problem Statement:

Given an array of random numbers, Push all the zero’s of a given array to the end of the array

Example: 

Input :  arr[] = {1, 2, 0, 4, 3, 0, 5, 0};

Output : arr[] = {1, 2, 4, 3, 5, 0, 0, 0};

Input : arr[]  = {1, 2, 0, 0, 0, 3, 6};

Output : arr[] = {1, 2, 3, 6, 0, 0, 0};

First, we discuss strategies and edge cases to handle then we study the approach that is:-

- if the current element is non-zero, place the element at the next available position in the array. After all elements in the array are processed, fill all remaining indices by 0.

Steps:

k = 0

for i in A:

   if I != 0:

      A[k] = i

      k = k + 1

for i in range(k, len(A)):

      A[i] = 0

 "

"In this video, we will shift our focus from Arrays to strings and learn about methods in C++ for dynamic creation, manipulation, deletion, and other operations performed on the String data type.

Topics covered are (with practical examples):

- char data type

//string s1 = ""Hello"";   

- strings from chars

//char ch[] = { 'C', '+', '+'};   

- calculating string sizes

// char ary[] = ""Board Infinity"";

// cout << ""Length of String = "" << strlen(ary)<<endl;

- updating string values

- appending/inserting in strings (str1 + str2)

- deletion from strings

- accepting string from console [cin>> or getline()]

- operations such as strcat(), strcpy(), strlen() and strcmp(), begin(), end()."

"In this video we will study more string manipulation methods such as converting to lowercase, uppercase and apply previously learned functions to check if string is an pangram (contains all English letter alphabets) as well as to reverse a given string.

Multiple approaches are discussed in the video for these problems.

Code:

- Reverse String: change the order of a given string so that the last character of the string becomes the first character of the string and so on

Enter a string to be reversed: AMBULANCE

After the reverse of a string: ECNALUBMA

Code:

int n = str.length();

// Swap character

for (int i = 0; i < n / 2; i++)

    swap(str[i], str[n - i - 1]);

- Check if Pangram:

A string is a Pangram if the string contains all the English alphabet letters.

Input: str = “We promptly judged antique ivory buckles for the next prize”

Output: Yes

Code:

for (int i = 0; i < str.length(); i++) {

       if ('A' <= str[i] && str[i] <= 'Z')

           index = str[i] - 'A';

       else if ('a' <= str[i] && str[i] <= 'z')

           index = str[i] - 'a';

       else

           continue;

       mark[index] = true;

   }

for (int i = 0; i <= 25; i++)

       if (mark[i] == false)

           return (false);

   // If all characters were present

   return (true);"

"In this video we will study more string methods useful for input validation.

Once we study the following functions, a program is written to display whether string input is valid/invalid based on assumptions.

Throughout the video logical operators such as || and && are also frequently used during conditional validation when more than two or more conditions are to be fulfilled.

1. isalpha(int ch); - Check for alphabet

2. isdigit(int ch); - Check for numbers

3. isalphanum(int ch); - Check for alphanumeric

4. strlen(string s) or string.length() – Calculate String Length"

"In this video we will understand palindromes and write a program to check whether a given string is a palindrome.

Problem Statement:

If the reversed integer is equal to the integer entered by user then, that number is a palindrome if not that number is not a palindrome. We need to check if a string passed is a palindrome.

Example -

“madam” is a palindromic string because it reads the same forwards and backward. Other palindromic strings are “anna,” “civic,” “level,”.

Using reverse() and strlen() this problem is simplified in the video.

Approach used is:

1. First, take a string as input.

2. Compare the first and the last character of the string. If they are equal, then compare the second and the second last character of the string, and so on, until we get to the middle of the string.

3. If the characters do not match at any iteration, then the string is not a palindrome."

"In this video, we are introducing you to string based patterns and algorithm/strategies used to determine whether a given pattern exists in a string (Similar to Regular Expressions).

 The most basic case of string searching involves one (often very long) string, sometimes called the haystack, and one (often very short) string, sometimes called the needle. The goal is to find one or more occurrences of the needle within the haystack. For example, one might search for to within:

“Some books are to be tasted, others to be swallowed, and some few to be chewed and digested.”

One might request the first occurrence of ""to"", which is the fourth word; or all occurrences, of which there are 3; or the last, which is the fifth word from the end.

Our video demonstrates multiple cases taken into consideration such as number of time pattern occurs, length of pattern, recurrence, numeric, alphabetic, and symbolic patterns.

In the video, we also cover all sorts of cases and brainstorm how to approach the problem during the theory part of the introduction."

"In this video, we implement a naïve Pattern Searching algorithm. Primary purpose is to find a pattern or substring from another bigger string.

We explore different methods to implement this algorithm. In the video, Naïve pattern searching is demonstrated which is the simplest method among other pattern searching algorithms. It checks for all characters of the main string to the pattern.

Pseudo Code:

for i := 0 to (lenStr - patLen), do

     for j := 0 to patLen, do

        if text[i+j] ≠ pattern[j], then

           break the loop

     done

     if j == patLen, then

        display the position i, as pattern found"

"In this video, we dive deeper and explore a more advanced and efficient pattern searching algorithm known as Rabin-Karp.

Problem Statement:

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m

Example:

Input:  txt[] =  ""AABAACAADAABAABA""

        pat[] =  ""AABA""

Output: Pattern found at index 0

        Pattern found at index 9

        Pattern found at index 12

Initially, we discuss the strategy which is checking the pattern by moving window one by one, but without checking all characters for all cases (finding the hash value).

- When the hash value is matched, then only it tries to check each character.

In the video, we also cover all sorts of cases and brainstorm how to approach the problem during the theory part of the introduction.

Pseudo Code:

   for i := 0 to (lenStr - patLen), do

      if patHash = strHash, then

         for charIndex := 0 to patLen -1, do

            if text[i+charIndex] ≠ pattern[charIndex], then

               break the loop

         if charIndex = patLen, then

            print the location i as pattern found at i position.

      if i < (lenStr - patLen), then

         strHash := (maxChar*(strHash – text[i]*h)+text[i+patLen]) mod prime, then

      if strHash < 0, then

         strHash := strHash + prime"

"In this video, we dive deeper and explore another pattern searching algorithm. We demonstrate an example by writing the KMP Algo in which we need to find a substring that is equivalent to our pattern.

Problem Statement:

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.

Example:

Input:  txt[] =  ""AABAACAADAABAABA""

        pat[] =  ""AABA""

Output: Pattern found at index 0

        Pattern found at index 9

        Pattern found at index 12

- The sliding window algorithm would have a window size equal to the length of the pattern.

- We would check substrings of length N starting from the left (0 index) to right.

As explained in the video, prefixes and suffixes are used to decrease time complexity. 

Psuedo Code:

while i < n do

    {if the characters match}

    if pattern[j] = string[i] then  do

        i ← i + 1

        j ← j + 1

      {j pointer reached end of pattern}

      if j = m then 

        {matched index}

        return i - j

            j ← LPS[j - 1]

    else if i<n && pattern[j] != string[i] then

           {no match}

            if j > 0

            j ← LPS[j - 1]

          else

            i ← i + 1

return -1 "

"In this video, we solve the String Rotation problem where the objective is to determine whether two given Strings have equal lengths and consist of the same characters. As discussed in the theory section, check for the second string by rotating the first String around a certain character. In the video, we also cover all sorts of cases and brainstorm how to approach the problem during the theory part of the introduction.

Problem Statement:

Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1

Example:

Valid example is two strings S1 = ""HELLO"", and S2 = ""LOHEL"".

The coding example can be simplified by the code snippet in a nutshell like so.

Pseudo Code:-

checkRotation(s1,s2)

    if s1.length != s2.length

        return False

    else

        temp = s1 + s1

        if s2 in temp

            return True

        else

            return False"

"In this video, we explain the concept of Anagrams, that is - both strings contain the same character set, only their order is different.

Problem Statement:

Therefore, in both strings, the frequency of each letter must be the same.

Example:

strings ""silent"" and ""listen"" are anagrams.

Then, we discuss all the possible valid test cases to write the algorithm such as length should match, duplicates are not allowed, and words should be only alphabetic in nature.

A detailed coded example is given at the end of the video with a thorough explanation and tips. 

Pseudo Code:

bool checkAnagram(string S1, int m, string S2, int n)

{

   if ( m != n )

        return False

   sort(S1, m)

   sort(S2, n)

   for ( i = 0 to n-1 )

      if ( S1[i] != S2[i] )

            return False

   return True

}"

"In this video, we will explore the Linked List Data Structure. A linked list is a linear data structure that includes a series of connected nodes. Here, each node stores the data and the address of the next node.

In the video, we also cover all sorts of cases and brainstorm how to approach the problem during the theory part of the introduction. Followed by an explanation of the need and use cases of linked lists.

Further, we discuss their 3 types:

- singly linked list

- doubly linked list

- circular linked list

Through examples, we talk about how they are different from arrays and their dynamic memory allocation, possible implementations in stack and queues.

PSEUDO CODE: -

struct node

{

  int data;

  struct node *next;

};

//traversing a linked list

  head = one;

  while (head != NULL) {

    cout << head->value;

    head = head->next;

  }"

"In this video, we discuss the three critical operations performed on Singly Linked lists. A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node. To perform any of these operations, a pointer reference to head is required.

Each node is traversed in a linear fashion and not randomly like arrays. The node->next and null properties are very common when performing these operations. Memory management is to be done manually in C++ while performing operations on the Singly Linked List data structure.

Each of these operations is discussed in detail with practical examples covering all possible cases. 

PSUEDO CODE:

-----Traversal - Iterating and Moving through all the elements of the linked list.

void traversal(Node* head) {

    Node* temp = head;

    while(temp != NULL)

    {

        cout<<(temp->data);

        temp = temp->next;

    }

}

-----Insertion - Either at the front or the back of the list. Can also be inserted at a specific position as explained in the video.

Node* insertAtBegin(Node* head, int x)

{

    Node* newNode = new Node(x)

    if(head == NULL)        

    return newNode;

    else     

    {

        newNode->next = head;

        return newNode;

    }

}

-----Deletion - Removing elements from either ends or from a specific position

Node deleteNode(Node* head, Node* toBeDeleted)

{

    if(head == toBeDeleted)

    {

        return head.next;

    }

    Node* temp = head;

    while( temp->next != NULL )

    {

        if(temp->next == toBeDeleted)

        {

            temp->next = temp->next->next;

            return head;

        }

        temp = temp->next;

    }

    return head;

}"

"In this video, we go over strategies and brainstorm ways to insert an element at the right position in a linked list so that list automatically appears as sorted.

So, basically finding the proper place such that the element fits perfectly in sorted order is the object. In the video, we have explained the example via which we iterate down the list looking for the place to insert the new node.

In the video, we also cover all sorts of cases and brainstorm how to approach the problem during the theory part of the introduction. That could be the end of the list or a point just before a larger node than the new node.

PSUEDO CODE:

void insertion_sort(struct Node** head, struct Node* newNode)

if (*head == NULL || (*head)->data >= newNode->data)

{

            newNode->next = *head;

            *head = newNode;

            return;

}

struct Node* current = *head;

while (current->next != NULL && current->next->data < newNode->data)

current = current->next;

newNode->next = current->next;

current->next = newNode;

}"

"In this video, we will discuss both the iterative and recursive ways in which you can solve the problem of Linked List reversal.

In the introduction, we see how we can make use of pointers to reverse the list by changing the links between nodes. 

Problem Statement:

We need to reverse the pointers such that the next element now points to the previous element.

Example:

Input: Head of following linked list

1->2->3->4->NULL

Output: Linked list should be changed to,

4->3->2->1->NULL

As explained in the video, for the iterative approach, we need to Create 3 instances: current, next, and previous. Loop the following till current is NOT null:

- Save the next Node of the current element in the next pointer.

- Set the next of the current Node to the previous. 

- Swap previous to current.

- Swap the current element to the next.

As explained in the video, for the recursive approach, we need to divide the LinkedList into two parts: head and remainder portion.

- Head points to the first element initially.

- Remaining points to the next element from the head.

We traverse the LinkedList recursively until the second last element.  Once we’ve reached the last element set that as the head.

From there we do the following until we reach the start of the LinkedList.

- node.next.next = node;

- node.next = null;

To not lose a track of the original head, we’ll save a copy of the head instance.

PSEUDO CODE:-

Using Iterative Method:

public class MyLinkedList {

            public Node head;

            public static class Node {

                        Node next;

                        Object data;

                        Node(Object data) {

                                 this.data = data;

                                 next = null;

                        }

            }

}

Using Recursive Method:

public  Node recursiveReverse(Node head) {

            Node first;

             if (head==null || head.next == null)

                 return head;

            first = recursiveReverse(head.next);

            head.next.next = head;

            head.next = null;

            return first;

}"

"In this video, we introduce you to a brand new data structure known as STACK that follows the LIFO rule (Last In First Out).

You can think of the stack data structure as a pile of plates on top of one another.

This means the last element inserted inside the stack is removed first. Then, we provide examples and give an overview of its use cases where Stack can be implemented to reverse a string, store browser history, and in parenthesis validators.

In the video, we also cover all sorts of cases and brainstorm how to approach the problem during the theory part of the introduction.

Next, we understand operations that can be performed on the stack such as (algorithms explain in detail):-

1. Push: Add an element to the top of a stack

2. Pop: Remove an element from the top of a stack

3. IsEmpty: Check if the stack is empty

4. IsFull: Check if the stack is full

5. Peek: Get the value of the top element without removing it"

"In this video, will help you to understand how a stack is implemented using an array as the data structure. and write all the operational functions.

Highlighted by properties, examples, and test cases you will be guided about implementing a stack with all the operations on the stack taking place using an array.

The primary advantage of using an array for implementing a stack is that it is more time-efficient than linked list implementation of the stack, which takes extra time in allocating pointers of nodes whenever there is a change in the size of the stack. All the operations in case of an array-based implementation of a stack are performed in O (1) time.

Operations performed in the video are:

1. Push: This operation adds an item to the stack; it will throw an exception if the stack’s capacity is full.

2. Pop: This removes the last inserted element from a stack that is removed in reverse order of their insertion; it will throw an underflow exception if the given stack is empty.

3. Peek: This operation returns the topmost element of the stack.

4. IsEmpty: Checks if a stack is empty or not. Returns true if the given stack is empty; otherwise, it returns false.

5. IsStackFull: Checks if a stack is full or not. Returns true if the given stack is full; otherwise, it returns false.

PSUEDO CODE:-

void push(int val) {

  if(top>=n-1)

  cout<<""Stack Overflow""<<endl;

  else {

     top++;

     stack[top]=val;

  }

}

void pop() {

  if(top<=-1)

  cout<<""Stack Underflow""<<endl;

  else {

     cout<<""The popped element is ""<< stack[top] <<endl;

     top--;

  }

}

void display() {

  if(top>=0) {

     cout<<""Stack elements are:"";

     for(int i=top; i>=0; i--)

     cout<<stack[i]<<"" "";

     cout<<endl;

  }else

  cout<<""Stack is empty"";

}"

"In this video, we will be using Linked List instead of Arrays to implement Stack. While the fundamentals will remain the same as in the previous video, we will now be introducing pointers yet again to traverse, remove and insert data at proper places using Linked Lists.

As we know, a stack is represented using nodes of a linked list. Each node consists of two parts:

- data - The data part of each node contains the assigned value

- next (storing address of next node) - next points to the node containing the next item in the stack

- top -  refers to the topmost node in the stack.

Both the push() and pop() operations are carried out at the front/top of the linked list and hence take O(1) time.

One noticeable difference from the previous video is that a stack can also be implemented using arrays but here we are going for the Linked List approach since arrays are of limited size and the size of the stack has to be predetermined whereas in a linked list implementation nodes can be added according to the user's requirements.

PSUEDO CODE: -

void push(int value) {

   struct Node *newNode;

   newNode = (struct Node *)malloc(sizeof(struct Node));

   newNode->data = value; // assign value to the node

   if (top == NULL) {

       newNode->next = NULL;

   } else {

       newNode->next = top; // Make the node as top

   }

   top = newNode; // top always points to the newly created node

   printf(""Node is Inserted\n\n"");

}

int pop() {

   if (top == NULL) {

       printf(""\nStack Underflow\n"");

   } else {

       struct Node *temp = top;

       int temp_data = top->data;

       top = top->next;

       free(temp);

       return temp_data;

   }

}

void display() {

   // Display the elements of the stack

   if (top == NULL) {

       printf(""\nStack Underflow\n"");

   } else {

       printf(""The stack is \n"");

       struct Node *temp = top;

       while (temp->next != NULL) {

           printf(""%d--->"", temp->data);

           temp = temp->next;

       }

       printf(""%d--->NULL\n\n"", temp->data);

   }

}"

"In this video, we do a deep dive into use-cases, applications, and programming problems where Stack data structure is very useful and efficient. Video highlights the top 3 uses of the stack such as:

1. Evaluation of Arithmetic Expressions

2. Backtracking

3. Delimiter Checking

4. Reverse a Data

5. Processing Function Calls

In the video, the approach to check for valid parenthesis is to first

- Declare an empty stack and then traverse the string and whenever an opening bracket is encountered, insert it into the stack.

- On the other hand, when a closing bracket is encountered, check if the last bracket in the stack matches the current closing bracket.

- If not, then return false otherwise remove the last bracket from the stack.

- After traversing the string, if the stack is empty return true otherwise return false.

In four such steps, the problem can be solved. Similar pattern problems can be tackled with the same approach. 

PSUEDO CODE:

bool isBalancedParentheses(string str) {

   int n = str.size();

   stack<char> openingBrackets;

   for (int i = 0; i < n; i++) {

   if (str[i] == '(' || str[i] == '{' || str[i] == '[') {

openingBrackets.push(str[i]);

} else {

   if (openingBrackets.empty()) {

     return false;

     }

   if (str[i] == ')') {

      char last = openingBrackets.top();

      openingBrackets.pop();

  if (last != '(') {      

   return false;

 }

 }

if (str[i] == '}') {

      char last = openingBrackets.top();

      openingBrackets.pop();

       if (last != '{')

           return false;

        }

           }

         if (str[i] == ']') {

     char last = openingBrackets.top();

    openingBrackets.pop();

      if (last != '[') {

 return false;

    }

  }

  }

 }

      return openingBrackets.empty();

}

"

"In this video, you will be introduced to yet another commonly used data structure known as a queue. A few highlights as discussed are:

The queue data structure follows the FIFO (First In First Out) principle where elements that are added first will be removed first.

After this, the video will demonstrate the types of operations associated with the Queue data structure used to manipulate the order of the elements and the elements themselves.

Operations highlighted are:

1.  enque(): inserts an element at the back of the queue

2. deque (): removes an element from the front of the queue

3. getFront(): returns the first element of the queue

4. getBack(): returns the last element of the queue

5. size(): returns the number of elements in the queue

6. empty(): returns true if the queue is empty"

"In this video, we will be doing a deep dive and understanding the concepts and operations associated with Queues in a better manner using the C++ STL Library for a more thorough understanding.

Some applications highlighted in the video are:

1. Managing requests on a single shared resource such as CPU scheduling and disk scheduling

2. Handling hardware or real-time systems interrupts

3. Handling website traffic

4. Routers and switches in networking

5. Maintaining the playlist in media players"

"Now that we have covered all the theories related to Queues, in this video, we will be writing the C++ code to implement the discussed operations of the Queue data structure using arrays.

We revise what the front and back values signify and dive right into the implementation. Each operation is successfully written in C++ with the help of functions.

Function Insert():

Inserts an element into the queue. If the rear is equal to n-1, then the queue is full, and overflow is displayed. If the front is -1, it is incremented by 1. The rear is incremented by 1 and the element is inserted in the index of the rear.

Code for Insertion:

void Insert() {

  int val;

  if (rear == n - 1)

  cout<<""Queue Overflow""<<endl;

  else {

     if (front == - 1)

     front = 0;

     cout<<""Insert the element in queue : ""<<endl;

     cin>>val;

     rear++;

     queue[rear] = val;

  }

}

Function Delete():

If there are no elements in the queue then it is underflow condition. Otherwise, the element at the front is displayed and the front is incremented by one.

Code for Deletion

 void Delete() {

  if (front == - 1 || front > rear) {

     cout<<""Queue Underflow "";

     return ;

  }

  else {

     cout<<""Element deleted from queue is : ""<< queue[front] <<endl;

     front++;;

  }

}

Function display(), if front is -1 then queue is empty. Otherwise, all the queue elements are displayed using a for loop

Code to display the queue:

void Display() {

   if (front == - 1)

   cout<<""Queue is empty""<<endl;

   else {

      cout<<""Queue elements are : "";

      for (int i = front; i <= rear; i++)

      cout<<queue[i]<<"" "";

      cout<<endl;

   }

}

"

"In this video, we will be writing the C++ code to implement the discussed operations of the Queue data structure using Linked Lists. Each operation is successfully written in C++ with the help of functions.

The primary difference from the array implementation is that Linked list Nodes are created dynamically and when required.

Function Insert():

- Inserts an element into the queue. If the rear is NULL, then the queue is empty and a single element is inserted. Otherwise, a node is inserted after the rear with the required element and then that node is set to the rear.

CODE IMPLEMENTATION:

void Insert() {

  int val;

  cout<<""Insert the element in queue : ""<<endl;

  cin>>val;

  if (rear == NULL) {

     rear = (struct node *)malloc(sizeof(struct node));

     rear->next = NULL;

     rear->data = val;

     front = rear;

  } else {

     temp=(struct node *)malloc(sizeof(struct node));

     rear->next = temp;

     temp->data = val;

     temp->next = NULL;

     rear = temp;

  }

}

Function Delete()

- If there are no elements in the queue then it is underflow condition. If there is only one element in the queue that is deleted and the front and rear are set to NULL.  Otherwise, the element at the front is deleted, and the front points to the next element.

CODE IMPLEMENTATION:

 void Delete() {

  temp = front;

  if (front == NULL) {

     cout<<""Underflow""<<endl;

     return;

  } else

  if (temp->next != NULL) {

     temp = temp->next;

     cout<<""Element deleted from queue is : ""<<front->data<<endl;

     free(front);

     front = temp

  } else{

     cout<<""Element deleted from queue is : ""<<front->data<<endl;

     free(front);

     front = NULL;

     rear = NULL;

  }

}"

"In this video, we start with a new topic – that of the Tree data structure. To clearly understand Trees, the video goes through the proper terminology used such as root node, children node, leaf nodes, height, levels, and depth of a tree, etc., and gives a basic overview of all the properties of all the nodes involved in the tree data structure.

In a nutshell, it can be covered by the following points: -

1. A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

2. The first node from where the tree originates is called as a root node.

3. The connecting link between any two nodes is called an edge.

4. The node which has a branch from it to any other node is called a parent node.

5. The node which is a descendant of some node is called a child node.

6. Nodes that belong to the same parent are called siblings.

7. The node which does not have any child is called a leaf node.

8. In a tree, each step from top to bottom is called as the level of a tree.

9. The total edges that lie on the longest path from any leaf node to a particular node is called the height of that node.

10. The total edges from the root node to a particular node are called the depth of that node.

Finally, after understanding the basics, in the video, we demonstrate the use-cases/applications of trees where they make it easy to solve problems with a repeating pattern such as: -

1. Binary Search Trees (BSTs) quickly check whether an element is present in a set or not.

2. Heap is a kind of tree that is used for heap sort.

3. Tries are used in modern routers to store routing information.

4. Most popular databases use B-Trees and T-Trees, which are variants of the tree structure.

5. Compilers use a syntax tree to validate the syntax of every program you write."

"In this video, we will be introducing you to Binary Trees data structure:

It has at most 2 children nodes. Since each element in a binary tree can have only 2 children, we name them the left and right child. It includes the following parts -

1. Data

2. Pointer to the left child

3. Pointer to the right child

Via the video, we also understand 3 traversal methods that are very important from an interview point of view.

1. PreOrder Traversal: root – left child – right child. It means that the root node is traversed first then its left child and finally the right child.

2. InOrder Traversal: left child – root – right child. It means that the left child is traversed first then its root node and finally the right child.

3. PostOrder Traversal: left child – right child – root. It means that the left child is traversed first then the right child and finally its root node.

CODE -

#include <stdlib.h>

#include <iostream>

using namespace std;

struct node {

  int data;

  struct node *left;

  struct node *right;

};

// New node creation

struct node *newNode(int data) {

  struct node *node = (struct node *)malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  return (node);

}

// Traverse Preorder

void traversePreOrder(struct node *temp) {

  if (temp != NULL) {

    cout << "" "" << temp->data;

    traversePreOrder(temp->left);

    traversePreOrder(temp->right);

  }

}

// Traverse Inorder

void traverseInOrder(struct node *temp) {

  if (temp != NULL) {

    traverseInOrder(temp->left);

    cout << "" "" << temp->data;

    traverseInOrder(temp->right);

  }

}

// Traverse Postorder

void traversePostOrder(struct node *temp) {

  if (temp != NULL) {

    traversePostOrder(temp->left);

    traversePostOrder(temp->right);

    cout << "" "" << temp->data;

  }

}

int main() {

  struct node *root = newNode(1);

  root->left = newNode(2);

  root->right = newNode(3);

  root->left->left = newNode(4);

  cout << ""preorder traversal: "";

  traversePreOrder(root);

  cout << ""\nInorder traversal: "";

  traverseInOrder(root);

  cout << ""\nPostorder traversal: "";

  traversePostOrder(root);

}

Applications, as demonstrated in the video, are:-

- For easy and quick access to data

- In router algorithms

- To construct or build a heap

- Syntax tree

"

"In this video, we see a Recursive way to implement Inorder Traversal in Binary Trees with a simple and lucid example with code demonstration.

We are making use of queues to make this possible. Recursively, until we encounter that node is none, in C++ we make a call to the Inorder() function and pass the nodes down the tree hierarchy.

The Algorithm from the video can be broken down into the following 3 steps:

Until all nodes are traversed:

- Step 1 − Recursively traverse the left subtree.

- Step 2 − Visit the root node.

- Step 3 − Recursively traverse the right subtree.

A detailed coded example is given at the end of the video with a thorough explanation and tips.

CODE:

void inorderTraversal(struct Node* node) {

 if (node == NULL)

   return;

 inorderTraversal(node->left);

 cout << node->data << ""->"";

 inorderTraversal(node->right);

}

"

"In this video, we see a Recursive way to implement Preorder Traversal in Binary Trees with a simple and lucid example with code demonstration.

We are making use of queues to make this possible. Recursively, until we encounter that node is none, in C++ we make a call to the Preorder() function and pass the nodes down the tree hierarchy.

The Algorithm from the video can be broken down into the following 3 steps: -

Until all nodes are traversed −

- Step 1 − Visit the root node.

- Step 2 − Recursively traverse the left subtree.

- Step 3 − Recursively traverse the right subtree.

A detailed coded example is given at the end of the video with a thorough explanation and tips.

PSUEDO CODE:

void preorderTraversal(struct Node* node) {

 if (node == NULL)

   return;

 cout << node->data << ""->"";

 preorderTraversal(node->left);

 preorderTraversal(node->right);

}

"

"In this video, we see a Recursive way to implement Postorder Traversal in Binary Trees with a simple and lucid example with code demonstration.

We are making use of queues to make this possible. Recursively, until we encounter that node is none, in C++ we make a call to the Postorder() function and pass the nodes down the tree hierarchy.

The Algorithm from the video can be broken down into the following 3 steps:

Until all nodes are traversed:

- Step 1 − Recursively traverse the left subtree.

- Step 2 − Recursively traverse the right subtree.

- Step 3 − Visit the root node.

A detailed coded example is given at the end of the video with a thorough explanation and tips.  

CODE: -

// Postorder traversal

void postorderTraversal(struct Node* node) {

 if (node == NULL)

   return;

 postorderTraversal(node->left);

 postorderTraversal(node->right);

 cout << node->data << ""->"";

}"

"In this video, we will be diving deeper and studying some advanced problems related to Trees to reinforce concepts we have understood from the previous sessions.

Level Order Traversal of Binary Tree

Given a binary tree, the objective is to print its nodes level by level, i.e., print all nodes of level 1 first, followed by nodes of level 2, and so on… Print nodes for any level from left to right.

This is also known as Breadth First search as the search tree is broadened as much as possible on each depth before going to the next depth.

bool printLevel(Node* root, int level)

{

    if (root == nullptr) {

        return false;

    }

    if (level == 1)

    {

        cout << root->key << "" "";

        // return true if at least one node is present at a given level

        return true;

    }

    bool left = printLevel(root->left, level - 1);

    bool right = printLevel(root->right, level - 1);

    return left || right;

}

void levelOrderTraversal(Node* root)

{

    // start from level 1 — till the height of the tree

    int level = 1;

    // run till printLevel() returns false

    while (printLevel(root, level)) {

        level++;

    }

}

Height of Binary Tree:

The objective is to find the maximum or the largest number of edges from a leaf node to the root node or root node to the leaf node. In the video, we have used a recursive approach as it is efficient and easy to understand.

int tree_height(Node* root) {

    if (root == NULL)

        return 0;

    else {

        // Find the height of left, right subtrees

        left_height = tree_height(root->left);

        right_height = tree_height(root->right);

        // Find max(subtree_height) + 1 to get the height of the tree

        return max(left_height, right_height) + 1;

}

Maximum Element from Binary Tree

int findMaxNode(Node* root) {

   if (root == NULL)

      return -100;

   int maxVal = root->data;

   int leftMaxVal = findMaxNode(root->left);

   int rightMaxVal = findMaxNode(root->right);

   if (leftMaxVal > maxVal)

      maxVal = leftMaxVal;

   if (rightMaxVal > maxVal)

      maxVal = rightMaxVal;

   return maxVal;

}

Print All Nodes at K distance from Binary Tree:

Using a Recursive approach, it can be done as demonstrated in the video.

public void findKDistanceFromNode(

TreeNode node,int dist, List<Integer> result,TreeNode blocker

) {

if (dist < 0 || node == null ||(blocker != null && node == blocker)) {

        return;

        }

        if (dist == 0) {

            result.add(node.val);

        }

findKDistanceFromNode(node.left, dist - 1, result, blocker);

findKDistanceFromNode(node.right, dist - 1, result, blocker);

}"

"In previous videos, we have studied this problem but we implemented the recursive solution. But instead, in this video, we will be trying out the iterative approach to print any Binary Tree in the Inorder fashion.

Since we are doing it iteratively, the stack is the preferred data structure to aid in the solution as seen in the video.

Important steps to remember are:-

- If the current node is NULL and the stack is not empty:

    a. Remove and print the last item from the stack.

    b. Set the current node to be the node to the right of the removed node.

    c. Repeat the second step of the algorithm.

- If the current node is NULL ​and the stack is empty, then the algorithm has finished.

PSUEDO CODE:

void inOrderTraversal(Node *root)

{

    stack<Node*> stack;

    Node *curr = root;

    while (!stack.empty() || curr != NULL)

    {

        if (curr != NULL)

        {

            stack.push(curr);

            curr = curr->left;

        }

        else

        {

            curr = stack.top();

            stack.pop(); // Pop the node on top of stack.

            cout << curr->data << "" ""; // Print it.

            curr = curr->right;

        }

    }

}"

"In previous videos, we have studied this problem but we implemented the recursive solution. But instead, in this video, we will be trying out the iterative approach to print any Binary Tree in the Preorder fashion.

Since we are doing it iteratively, the stack is the preferred data structure to aid in the solution as seen in the video.

Important steps to remember are:

- Pop and print an item from the stack.

- Push the right child of a popped item to stack.

- Push the left child of a popped item to stack.

PSUEDO CODE:-

void preorderIt(Node* root)

{

    if (root == nullptr)

    return;

    stack<Node*> s;

    s.push(root);

    while (!s.empty())

    {

        Node* curr = s.top();

        s.pop();

        cout << curr->data << "" "";

        if (curr->right) {

            s.push(curr->right);

        }

        if (curr->left) {

            s.push(curr->left);

        }

    }

}"

"Previously, we learned about trees. From this video onwards we are going to be studying an extension of the Tree Data structure known as the Binary Search Tree (BST).

It is a data structure that quickly allows us to maintain a sorted list of numbers.

- It is called a binary tree because each tree node has a maximum of two children.

- It is called a search tree because it can be used to search for the presence of a number in logN time.

In the video, we also see that the properties of a binary search tree are different from those a standard Tree in the following ways:-

1. All nodes of the left subtree are less than the root node

2. All nodes of the right subtree are more than the root node

3. Both subtrees of each node are also BSTs i.e. they have the above two properties

Since it is optimized for the search operation, from the video, we say that

- If the value is below the root, only search in the left subtree AND

- if the value is above the root, only search in the right subtree.

PSEUDO CODE:

If root == NULL

    return NULL;

If number == root->data

    return root->data;

If number < root->data

    return search(root->left)

If number > root->data

    return search(root->right)"

"In this video, we will study 4 problems and work out their C++ implementation.

INSERTION:

Insertion should take place in a BST such that the property of the BST should be maintained. All left children nodes should be lesser and all right children nodes should be greater than the parent node.

PSUEDO CODE:

public static TreeNode insertionRecursive(TreeNode root, int value) {

        if (root == null)

            return new TreeNode(value);

        if (value < (int) root.data) {

            root.left = insertionRecursive(root.left, value);

        } else if (value > (int) root.data) {

            root.right = insertionRecursive(root.right, value);

        }

        return root;

    }

DELETION:

For deletion operations, we must consider a few cases and write the logic for them individually.

- If no children - Just delete it.

- If a single child - Copy that child to the node.

- If two children - Determine the next highest element (in order successor) in the right subtree. Replace the node to be removed with the inorder successor. Delete the inorder successor duplicate.

PSUEDO CODE:

public static TreeNode deleteRecursively(TreeNode root, int value) {

        if (root == null)

            return root;

        if (value < (int) root.data) {

            root.left = deleteRecursively(root.left, value);

        } else if (value > (int) root.data) {

            root.right = deleteRecursively(root.right, value);

        } else {

            if (root.left == null) {

                return root.right;

            } else if (root.right == null)

                return root.left;

            root.data = inOrderSuccessor(root.right);

            root.right = deleteRecursively(root.right, (int) root.data);

        }

        return root;

    }

FLOOR OF BST:

It is the node with the greatest data lesser than or equal to the key value.

PSUEDO CODE:

int Floor(node *root, int input)

{

    if (root == NULL)

        return -1;

    if (root->key == input)

        return root->key;

    if (root->key > input)

        return Floor(root->left, input);

    else{

        int floor = Floor(root->right, input);

        return (floor<=input && floor!=-1)? floor : root->key; 

    }

} 

CEILING OF BST:

It is the node with the smallest data larger than or equal to the key value.

PSUEDO CODE:

int Ceil(node* root, int input) 

{ 

    if (root == NULL) 

        return -1; 

    if (root->key == input) 

        return root->key; 

    if (root->key < input) 

        return Ceil(root->right, input); 

    int ceil = Ceil(root->left, input); 

    return (ceil >= input) ? ceil : root->key; 

} "

"In this video, we will continue with the topic of BSTs and reinforce our learnings by studying the implementation of Self Balancing BSTs in C++.

Self-balancing binary search trees are an important type of data structure used in the underlying implementation of many containers, libraries, and algorithms. Usually, they achieve self-balancing through a certain sequence of rotations when there is a change in the tree while maintaining all BST properties.

During the introduction, it is explained that they are simply height-balanced binary search trees that automatically keep the height as small as possible when insertion and deletion operations are performed on the tree.

There are three major variants of self-balancing BSTs that we will consider using. They are AVL trees, red-black trees, and splay trees.

As seen from the video this is only possible by performing 4 types of rotations:-

- Left rotation

- Right Rotation

- Left-Right rotation

- Right-Left rotation

PSUEDO CODE FOR LEFT ROATATE OPERATION:

LEFT-ROTATE (T, x)

     y = x.right

     x.right = y.left

     if y.left != nil

         y.left.parent = x

     y.parent = x.parent

     if x.parent == nil

         T.root = y

     elseif x == x.parent.left

         x.parent.left = y

     else x.parent.right = y

     y.left = x

     x.parent = y

PSUEDO CODE FOR RIGHT ROTATE OPERATION:

RIGHT-ROTATE (T, x)

     y = x.left

     x.left = y.right

     if y.right != nil

         y.right.parent = x

     y.parent = x.parent

     if x.parent == nil

         T.root = y

     elseif x == x.parent.right

         x.parent.right = y

     else x.parent.left = y

     y.right = x

     x.parent = y"

"In this video, we continue from the point where we left off and study more issues that crop up with hashing and methods to handle them.

Topics explained in the videos are (with examples):-

Direct Address Table:

It is a data structure used for mapping records to their corresponding keys using arrays. In direct address tables, records are placed using their key values directly as indexes. They facilitate fast searching, insertion, and deletion operations.

Collision Handling:

Since a hash function gets us a small number for a big key, there is the possibility that two keys result in the same value. The situation where a newly inserted key maps to an already occupied slot in the hash table is called collision and must be handled using some collision handling technique.

Two methods discussed are Chaining and Open Addressing."

"In the previous videos, we have seen the side effects of hashing known as a collision. Now we will address this issue in this video by learning about Chaining which is a  technique used for avoiding collisions in Hash Tables.

After a theoretical explanation, the C++ solution is implemented for a thorough understanding.

In the chaining approach, the hash table is an array of linked lists. All key-value pairs mapping to the same index will be stored in the linked list of that index.

As we have understood from the previous videos

hashIndex = key % noOfBuckets

PSUEDO CODE:

class Hash{

   int BUCKET;

   list < int >*table;

   public:

   Hash (int V);

   void insertItem (int x);

   void deleteItem (int key);

   int hashFunction (int x){

      return (x % BUCKET);

   }

   void displayHash ();

};

Hash::Hash (int b){

   this->BUCKET = b;

   table = new list < int >[BUCKET];

}

void Hash::insertItem (int key){

   int index = hashFunction (key);

   table[index].push_back (key);

}

void Hash::deleteItem (int key){

   int index = hashFunction (key);

   list < int >::iterator i;

   for (i = table[index].begin (); i != table[index].end (); i++){

   if (*i == key)

      break;

   }

   if (i != table[index].end ())

      table[index].erase (i);

}

void Hash::displayHash (){

   for (int i = 0; i < BUCKET; i++){

      cout << i;

      for (auto x:table[i])

      cout << "" --> "" << x;

      cout << endl;

   }

}"

"In this video, we will get a brief overview of 3 topics:-

Open Addressing

Like separate chaining, open addressing is a method for handling collisions. In Open Addressing, all elements are stored in the hash table itself. So at any point, the size of the table must be greater than or equal to the total number of keys.

Operations involved are-

1. Insert(h)

2. Search(h)

3. Delete(h)

Double Hashing:

It is a technique to resolve collisions in Open Addressed Hash Tables. As we see in the video, this can be done by applying a second hash function to the o key when a collision occurs.

Implementation:

Delete Operation-

Declare Function Remove(int k)

      Declare hash_val, init of the integer datatype.

         initialize hash_val = HashFunc(k)

         initialize init = -1

      while (hash_val != init and (ht[hash_val]

         == DelNode::getNode() or ht[hash_val]

         != NULL and ht[hash_val]->k!= k))

            if (init == -1)

               init = hash_val

            hash_val = HashFunc(hash_val + 1)

         if (hash_val != init and ht[hash_val] != NULL)

            delete ht[hash_val]

            ht[hash_val] = DelNode::getNode()

Search Operation-

Declare Function SearchKey(int k)

      Declare hash_val, init of the integer datatype.

         initialize hash_val = HashFunc(k)

         intialize init = -1

      while (hash_val != init and (ht[hash_val]

         == DelNode::getNode() or ht[hash_val]

         != NULL and ht[hash_val]->k!= k

            if (init == -1)

               init = hash_val

            hash_val = HashFunc(hash_val + 1)

         if (ht[hash_val] == NULL or hash_val == init)

            return -1

         else

            return ht[hash_val]->v

"

"In this video, we will be studying 2 separate subarray based problems with an almost similar solution pattern. Firstly, we consider all the possible cases, brainstorm over the approach to the problem and then attempt to write an efficient C++ solution.

A subarray is a contiguous part of the array. An array that is inside another array

Problem Statement:

Given an array of positive and negative numbers, find if there is a subarray (of size at least one) with 0 sum.

Example:

Input: {4, 2, -3, 1, 6}

Output: true 

Explanation: There is a subarray with zero sum from index 1 to 3.

As shown in the video, we are using the following approach:

- Traverse the array from start to end.

- From every index start another loop from i to the end of the array to get all subarrays starting from i, and keep a variable currentSum to calculate the sum of every subarray.

- For every index in inner loop update currentSum = currentSum + arr[j]

- If the currentSum is equal to the given sum then print the subarray.

Code:

bool hasZeroSumSubarray(int nums[], int n)

{

    unordered_set<int> set;

    set.insert(0);

    int sum = 0;

    for (int i = 0; i < n; i++)

    {

        sum += nums[i];

        if (set.find(sum) != set.end()) 

            return true;

        else 

            set.insert(sum);

    }

    return false;

}

Subarray with Given Sum

Problem Statement:

Given an array arr[] of non-negative integers and an integer sum, find a continuous subarray that adds to a given sum.

Note: There may be more than one subarray with sum as the given sum, print the first such subarray. 

Examples: 

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33

Output: Sum found between indexes 2 and 4

Explanation: Sum of elements between indices 2 and 4 is 20 + 3 + 10 = 33

Code:

bool find_Subarray(int arr[], int N, int required) {

  int sum = 0;

  for (int i = 0; i < N; i++) {

    sum = arr[i];

    for (int j = i + 1; j < N + 1; j++) {

      if (sum == required) {

        // found subarray with given sum

        return true;

      } else if (sum > required) {

        break;

      }

      sum = sum + arr[j];

    }

  }

  return false;

}"

"In this video, we will be studying 2 separate subarray based problems with an almost similar solution pattern. We shall be making use of the Hashing Techniques that we studied in the previous videos to write an efficient C++ solution.

A subarray is a contiguous part of the array. An array that is inside another array

Longest subarray with given sum

Problem Statement:

Given an array arr[] of size n containing integers. The problem is to find the length of the longest sub-array having sum equal to the given value k.

Example: 

Input: arr[] = { 10, 5, 2, 7, 1, 9 }, k = 15

Output: 4

Explanation: The sub-array is {5, 2, 7, 1}.

Our approach as shown in the video will be to consider the sum of all the sub-arrays and return the length of the longest sub-array having the sum ‘k’. 

CODE -

int lenOfLongSubarr(int arr[], int n, int k)

{

    unordered_map<int, int> um;

    int sum = 0, maxLen = 0;

    for (int i = 0; i < n; i++) {

        sum += arr[i];

        if (sum == k)

            maxLen = i + 1;

        if (um.find(sum) == um.end())

            um[sum] = i;

        if (um.find(sum - k) != um.end()) {

            if (maxLen < (i - um[sum - k]))

                maxLen = i - um[sum - k];

        }

    }

    return maxLen;

}

Longest Subarray with an equal number of 0s and 1s

Problem Statement: Given an array containing only 0s and 1s, find the largest subarray which contains an equal no of 0s and 1s. The expected time complexity is O(n). 

Example:

Input: arr[] = {1, 0, 1, 1, 1, 0, 0}

Output: 1 to 6

(Starting and Ending indexes)

CODE -

Run a loop from i=0 to n-1

if (sumleft[i] == 0)

        {

           maxsize = i+1;

           startindex = 0;

        }

        if (hash[sumleft[i]-min] == -1)

            hash[sumleft[i]-min] = i;

        else

        {

if ((i - hash[sumleft[i]-min]) > maxsize)

            {

            maxsize = i - hash[sumleft[i]-min];

            startindex = hash[sumleft[i]-min] + 1;

            }

        }

return maxsize"

"In this video, we will be studying 2 separate problems with an almost similar solution pattern.

We shall be making use of the Hashing Techniques as well as the basic array properties that we studied in the previous videos to write an efficient C++ solution.

Count Distinct Elements

Problem Statement:

Given an unsorted array arr[] of length N, The task is to count all distinct elements in arr[].

Examples: 

Input :  arr[] = {10, 20, 20, 10, 30, 10}

Output : 3

Explanation: There are three distinct elements 10, 20, and 30.

To tackle the problem, as shown in the video we will be using the following approach:

- Create a count variable and run two loops, one with counter i from 0 to N-1 to traverse arr[] and the second with counter j from 0 to i-1 to check if ith element has appeared before. If yes, increment the count. 

Code:

int arr[] = {10, 30, 40, 20, 10, 20, 50, 10};

   int n = sizeof(arr)/sizeof(arr[0]);

   unordered_map <int, int>mp;

   int count_dis=0;

   for(int i=0; i<n; i++)

      mp[arr[i]]++;

   cout<<mp.size();

Count Frequency of Elements in Arrays:

Problem Statement:

Given an array which may contain duplicates, print all elements and their frequencies.

Examples: 

Input :  arr[] = {10, 20, 20, 10, 10, 20, 5, 20}

Output : 10 3

         20 4

         5  1

Code:

int frequency(int arr[], int size){

   bool check[size];

   for(int i=0;i<size;i++){

      check[i] = 0;

   }

   for(int i=0; i<size; i++){

      if(check[i]== 1){

         continue;

      }

      int count = 1;

      for(int j = i+1; j<size; j++){

         if (arr[i] == arr[j]){

            check[j] = 1;

            count++;

         }

      }

      cout<<""frequency of ""<<arr[i]<<"" is: "" << count << endl;

   }

}"

"In this video, we begin with a new data structure known as Binary Heap. Firstly, we understand the terminology involved during problem-solving as well as the properties that are discussed in the video.

- It’s a complete tree

i.e. All levels are completely filled except possibly the last level and the last level has all keys as left as possible. This property of Binary Heap makes them suitable to be stored in an array.

- A Binary Heap is either Min Heap or Max Heap.

In a Min Binary Heap, the key at the root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

Things to Remember:

- Arr[(i-1)/2] - Returns the parent node

- Arr[(2*i)+1] - Returns the left child node

- Arr[(2*i)+2] - Returns the right child node

class BHeap {

   private:

   vector <int> heap;

   int l(int parent);

   int r(int parent);

   int par(int child);

   void heapifyup(int index);

   void heapifydown(int index);

   public:

      BHeap() {}

      void Insert(int element);

      void DeleteMin();

      int ExtractMin();

      void showHeap();

      int Size();

};"

"In this video, we will continue with Binary Heap and dive deeper by understanding implementation details for 2 Operations in C++(Heapify and ExtractMax/ExtractMin).

Problem Statement:

Given an array of N elements. The task is to build a Binary Heap from the given array. The heap can be Min Heap or Max Heap

For Heapify operations, there are two possible strategies discussed in the video.

1. Build the heap from an array of n items using two methods. In the first method, we successively perform the insert operation on the heap. In n insert operations, we can build the heap from the array. Since each insert operation takes O(log n) time and there are n such operations, the complexity of this method is O(nlog n).

2. The internal node of the tree is max-heapified one at a time. If there are n items in the array, we start from the item at n/2 position and heapify it and we move to next item and do the same all the way down to the first item in the array. 

  void maxHeapify(int i){

        int left = BinaryHeap::leftChild(i);

        int right = BinaryHeap::rightChild(i);

        int largest = i;

        if (left <= size && heap[left] > heap[largest]) {

            largest = left;

        }

        if (right <= size && heap[right] > heap[largest]) {

            largest = right;

        }

        if (largest != i) {

            int temp = heap[i];

            heap[i] = heap[largest];

            heap[largest] = temp;

            maxHeapify(largest);

        }

    }

Extract operation can be done as demonstrated in the video in a much simpler manner.

Consider, extractMax():

int extractMax() {

        int maxItem = heap[0];

        heap[0] = heap[size - 1];

        size = size - 1;

        maxHeapify(0);

        return maxItem;

    }"

"In this video, we will cover some advanced topics like Decreasing a Key and Deleting and Building a Binary Heap.

In the previous video, we learnt about the Heapify operation. Building a binary heap is more or less the same.

Decreasing a Key:

To decrease the value of a certain key, we’ll use the map to locate its index. After we locate its index, we’ll change its value, and start moving it up the tree if needed.

1. Locate the index of the given key using the map.

2. Remove the old value of the key from the map, decrease it, and store the new value inside the map.

3. Perform multiple steps starting from the index of the key. In each step, we compare the value of the key with the value of its parent. If the value of the key is smaller than the value of its parent, we swap their values

4. Complexity is O(log N) where  is the number of keys inside the heap.

Deletion:

Since deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted by the last element and delete the last element of the Heap.

1. Replace the root or element to be deleted by the last element.

2. Delete the last element from the Heap.

3. Heapify the last node placed at the position of root.

As seen from the code in the video -

void deleteRoot(int arr[], int& n)

{

    int lastElement = arr[n - 1];

    arr[0] = lastElement;

    n = n - 1;

    heapify(arr, n, 0);

}"

"This is the introductory lecture of our Algorithms Module, after learning about Data Structures we will learn about Algorithm Analysis.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Characteristics of an Algorithm

Not all procedures can be called an algorithm. An algorithm should have the following characteristics −

- Unambiguous − The algorithm should be unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning.

- Input − An algorithm should have 0 or more well-defined inputs.

- Output − An algorithm should have 1 or more well-defined outputs and should match the desired output.

- Finiteness − Algorithms must terminate after a finite number of steps.

- Feasibility − This should be feasible with the available resources.

- Independent − An algorithm should have step-by-step directions, which should be independent of any programming code.

Example

Let's try to learn algorithm writing by using an example.

Problem − Design an algorithm to add two numbers and display the result.

Step 1 − START

Step 2 − declare three integers a, b & c

Step 3 − define values of a & b

Step 4 − add values of a & b

Step 5 − store output of step 4 to c

Step 6 − print c

Step 7 − STOP

Algorithms tell the programmers how to code the program. Alternatively, the algorithm can be written as −

Step 1 − START ADD

Step 2 − get values of a & b

Step 3 − c ← a + b

Step 4 − display c

Step 5 − STOP

Algorithm Analysis:

The efficiency of an algorithm can be analyzed at two different stages, before implementation, and after implementation. They are the following −

- A Priori Analysis 

- A Posterior Analysis 

Algorithm Complexity:

Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm X are the two main factors, which decide the efficiency of X.

- Time Factor − Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.

- Space Factor − Space is measured by counting the maximum memory space required by the algorithm.

The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data. In the lectures ahead we will learn bout the various Algorithms and their implementation.

"

"In this lecture of our Algorithm module, we will learn about Linear & Binary Search.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Linear Search:

A linear search is also known as a sequential search that simply scans each element at a time. Suppose we want to search for an element in an array or list; we simply calculate its length and do not jump at any item.

Below is the code syntax for the linear search.

// Linear Search in C++

#include <iostream>

using namespace std;

int search(int array[], int n, int x)

{

    // Going through array sequencially

    for (int i = 0; i < n; i++)

        if (array[i] == x)

            return i;

    return -1;

}

Binary Search:

A binary search is a search in which the middle element is calculated to check whether it is smaller or larger than the element which is to be searched. The main advantage of using binary search is that it does not scan each element in the list. Instead of scanning each element, it performs the search to half of the list. So, the binary search takes less time to search for an element as compared to a linear search.

Below is the code syntax for the binary search.

#include <iostream>

using namespace std;

int binarySearch(int array[], int x, int low, int high)

{

    // Repeat until the pointers low and high meet each

    // other

    while (low <= high) {

        int mid = low + (high - low) / 2;

        if (array[mid] == x)

            return mid;

        if (array[mid] < x)

            low = mid + 1;

        else

            high = mid - 1;

    }

    return -1;

}

"

"In this lecture of our Algorithm module, we will learn about Bubble Sort.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity is quite high.

How does Bubble Sort Work?

Input: arr[] = {5, 1, 4, 2, 8}

First Pass:

Bubble sort starts with the very first two elements, comparing them to check which one is greater.

- ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, the algorithm compares the first two elements and swaps since 5 > 1. 

- ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4 

- ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2 

- ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), the algorithm does not swap them.

Second Pass:

Now, during the second iteration it should look like this:

- ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) 

- ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2 

- ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

- ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

Third Pass:

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

- ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

- ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

- ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

- ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

Follow the below steps to solve the problem:

- Run a nested for loop to traverse the input array using two variables i and j, such that 0 ≤ i < n-1 and 0 ≤ j < n-i-1

- If arr[j] is greater than arr[j+1] then swap these adjacent elements, else move on

- Print the sorted array

Below is the implementation of the above approach:

#include <stdio.h>

void swap(int* xp, int* yp)

{

    int temp = *xp;

    *xp = *yp;

    *yp = temp;

}

// A function to implement bubble sort

void bubbleSort(int arr[], int n)

{

    int i, j;

    for (i = 0; i < n - 1; i++)

        // Last i elements are already in place

        for (j = 0; j < n - i - 1; j++)

            if (arr[j] > arr[j + 1])

                swap(&arr[j], &arr[j + 1]);

}

/* Function to print an array */

void printArray(int arr[], int size)

{

    int i;

    for (i = 0; i < size; i++)

        printf(""%d "", arr[i]);

    printf(""\n"");

}

// Driver program to test above functions

int main()

{

    int arr[] = { 64, 34, 25, 12, 22, 11, 90 };

    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    printf(""Sorted array: \n"");

    printArray(arr, n);

    return 0;

}

Output:

Sorted array:

1 2 4 5 8

//Time Complexity: O(N2)

//Auxiliary Space: O(1) 

"

"In this lecture of our Algorithm module, we will learn about Selection Sort.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning. 

The algorithm maintains two subarrays in a given array.

- The subarray which already sorted. 

- The remaining subarray was unsorted.

Below is the implementation of the above approach:

#include <bits/stdc++.h>

using namespace std;

//Swap function

void swap(int *xp, int *yp)

{

    int temp = *xp;

    *xp = *yp;

    *yp = temp;

}

void selectionSort(int arr[], int n)

{

    int i, j, min_idx;

    // One by one move boundary of

    // unsorted subarray

    for (i = 0; i < n-1; i++)

    {

        // Find the minimum element in

        // unsorted array

        min_idx = i;

        for (j = i+1; j < n; j++)

        if (arr[j] < arr[min_idx])

            min_idx = j;

        // Swap the found minimum element

        // with the first element

        if(min_idx!=i)

            swap(&arr[min_idx], &arr[i]);

    }

}

//Function to print an array

void printArray(int arr[], int size)

{

    int i;

    for (i=0; i < size; i++)

        cout << arr[i] << "" "";

    cout << endl;

}

// Driver program to test above functions

int main()

{

    int arr[] = {64, 25, 12, 22, 11};

    int n = sizeof(arr)/sizeof(arr[0]);

    selectionSort(arr, n);

    cout << ""Sorted array: \n"";

    printArray(arr, n);

    return 0;

}

Output

Sorted array:

11 12 22 25 64

Complexity Analysis of Selection Sort:

Time Complexity: The time complexity of Selection Sort is O(N2) as there are two nested loops:

- One loop to select an element of Array one by one = O(N)

- Another loop to compare that element with every other Array element = O(N)

Therefore overall complexity = O(N) * O(N) = O(N*N) = O(N2)

"

"In this lecture of our Algorithm module, we will learn about Insertion Sort.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part.

Characteristics of Insertion Sort:

- This algorithm is one of the simplest algorithms with simple implementation

- Basically, Insertion sort is efficient for small data values

- Insertion sort is adaptive in nature, i.e. it is appropriate for data sets that are already partially sorted.

Below is the implementation:

#include <bits/stdc++.h>

using namespace std;

// Function to sort an array using 

// insertion sort

void insertionSort(int arr[], int n) 

{ 

    int i, key, j; 

    for (i = 1; i < n; i++)

    { 

        key = arr[i]; 

        j = i - 1; 

        // Move elements of arr[0..i-1],  

        // that are greater than key, to one 

        // position ahead of their 

        // current position

        while (j >= 0 && arr[j] > key)

        { 

            arr[j + 1] = arr[j]; 

            j = j - 1; 

        } 

        arr[j + 1] = key; 

    } 

} 

// A utility function to print an array 

// of size n 

void printArray(int arr[], int n) 

{ 

    int i; 

    for (i = 0; i < n; i++) 

        cout << arr[i] << "" ""; 

    cout << endl;

} 

// Driver code

int main() 

{ 

    int arr[] = { 12, 11, 13, 5, 6 }; 

    int N = sizeof(arr) / sizeof(arr[0]); 

    insertionSort(arr, N); 

    printArray(arr, N); 

    return 0; 

} 

Output:

5 6 11 12 13

//Time Complexity: O(N^2) 

//Auxiliary Space: O(1)"

"In this lecture of our Algorithm module, we will learn about Quick Sort.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

QuickSort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. 

- Always pick the first element as a pivot.

- Always pick the last element as a pivot (implemented below)

- Pick a random element as a pivot.

- Pick median as the pivot.

The key process in quickSort is a partition(). The target of partitions is, given an array and an element x of an array as the pivot, put x at its correct position in a sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Following are the implementations of QuickSort:  

#include <bits/stdc++.h>

using namespace std; 

// A utility function to swap two elements 

void swap(int* a, int* b) 

{ 

    int t = *a; 

    *a = *b; 

    *b = t; 

} 

/* This function takes last element as pivot, places 

the pivot element at its correct position in sorted 

array, and places all smaller (smaller than pivot) 

to left of pivot and all greater elements to right 

of pivot */

int partition (int arr[], int low, int high) 

{ 

    int pivot = arr[high]; // pivot 

    int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far

    for (int j = low; j <= high - 1; j++) 

    { 

        // If current element is smaller than the pivot 

        if (arr[j] < pivot) 

        { 

            i++; // increment index of smaller element 

            swap(&arr[i], &arr[j]); 

        } 

    } 

    swap(&arr[i + 1], &arr[high]); 

    return (i + 1); 

} 

/* The main function that implements QuickSort 

arr[] --> Array to be sorted, 

low --> Starting index, 

high --> Ending index */

void quickSort(int arr[], int low, int high) 

{ 

    if (low < high) 

    { 

        /* pi is partitioning index, arr[p] is now 

        at right place */

        int pi = partition(arr, low, high); 

        // Separately sort elements before 

        // partition and after partition 

        quickSort(arr, low, pi - 1); 

        quickSort(arr, pi + 1, high); 

    } 

} 

/* Function to print an array */

void printArray(int arr[], int size) 

{ 

    int i; 

    for (i = 0; i < size; i++) 

        cout << arr[i] << "" ""; 

    cout << endl; 

} 

// Driver Code

int main() 

{ 

    int arr[] = {10, 7, 8, 9, 1, 5}; 

    int n = sizeof(arr) / sizeof(arr[0]); 

    quickSort(arr, 0, n - 1); 

    cout << ""Sorted array: \n""; 

    printArray(arr, n); 

    return 0; 

}

Output:

Sorted array:

1 5 7 8 9 10

//Time taken by QuickSort, in general, can be written as follows. 

// T(n) = T(k) + T(n-k-1) + (n)

"

"In this lecture of our Algorithm module, we will learn about Merge Sort.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

The Merge Sort algorithm is a sorting algorithm that is based on the Divide and Conquer paradigm. In this algorithm, the array is initially divided into two equal halves and then they are combined in a sorted manner.

Algorithm:

- step 1: start

- step 2: declare array and left, right, mid variable

- step 3: perform merge function.

  if left > right

    return

  mid= (left+right)/2

  mergesort(array, left, mid)

  mergesort(array, mid+1, right)

  merge(array, left, mid, right)

- step 4: Stop

Follow the steps below the solve the problem:

MergeSort(arr[], l, r)

If r > l

- Find the middle point to divide the array into two halves: 

    - middle m = l + (r – l)/2

- Call mergeSort for first half:  

    - Call mergeSort(arr, l, m)

- Call mergeSort for second half:

    - Call mergeSort(arr, m + 1, r)

- Merge the two halves sorted in steps 2 and 3:

    - Call merge(arr, l, m, r)

Time Complexity: O(N log(N)), Sorting arrays on different machines. Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation. 

T(n) = 2T(n/2) + θ(n)

"

"In this lecture of our Algorithm module, we will learn about Greedy Algorithms.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to the global solution is the best fit for Greedy.

- It is designed to achieve the optimum solution for a given problem. In the greedy algorithm approach, decisions are made from the given solution domain. As being greedy, the closest solution that seems to provide an optimum solution is chosen.

- It tries to find a localized optimum solution, which may eventually lead to globally optimized solutions. However, generally greedy algorithms do not provide globally optimized solutions.

Components of Greedy Algorithm

The components that can be used in the greedy algorithm are:

- Candidate set: A solution that is created from the set is known as a candidate set.

- Selection function: This function is used to choose the candidate or subset which can be added to the solution.

- Feasibility function: A function that is used to determine whether the candidate or subset can be used to contribute to the solution or not.

- Objective function: A function is used to assign the value to the solution or the partial solution.

- Solution function: This function is used to intimate whether the complete function has been reached or not.

Pseudo code of Greedy Algorithm:

Algorithm Greedy (a, n)  

{  

   Solution : = 0;  

  for i = 0 to n do  

  {  

      x: = select(a);  

     if feasible(solution, x)  

    {  

        Solution: = union(solution , x)  

    }  

       return solution;  

  } }  

"

"In this lecture of our Algorithm module, we will learn about Fractional Knapsack.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

The fractional knapsack problem is also one of the techniques which are used to solve the knapsack problem. In a fractional knapsack, the items are broken to maximize profit. The problem in which we break the item is known as a Fractional knapsack problem.

This problem can be solved with the help of using two techniques:

- Brute-force approach: The brute-force approach tries all the possible solutions with all the different fractions but it is a time-consuming approach.

- Greedy approach: In the Greedy approach, we calculate the ratio of profit/weight, and accordingly, we will select the item. The item with the highest ratio would be selected first.

There are three approaches to solving the problem:

- The first approach is to select the item based on the maximum profit.

- The second approach is to select the item based on the minimum weight.

- The third approach is to calculate the ratio of profit/weight.

Example:

#include <bits/stdc++.h>

using namespace std;

// Structure for an item which stores weight and

// corresponding value of Item

struct Item {

    int value, weight;

    // Constructor

    Item(int value, int weight)

    {

        this->value = value;

        this->weight = weight;

    }

};

// Comparison function to sort Item according to val/weight

// ratio

bool cmp(struct Item a, struct Item b)

{

    double r1 = (double)a.value / (double)a.weight;

    double r2 = (double)b.value / (double)b.weight;

    return r1 > r2;

}

// Main greedy function to solve problem

double fractionalKnapsack(int W, struct Item arr[], int N)

{

    //    sorting Item on basis of ratio

    sort(arr, arr + N, cmp);

    double finalvalue = 0.0; // Result (value in Knapsack)

    // Looping through all Items

    for (int i = 0; i < N; i++) {

        // If adding Item won't overflow, add it completely

        if (arr[i].weight <= W) {

            W -= arr[i].weight;

            finalvalue += arr[i].value;

        }

        // If we can't add current Item, add fractional part

        // of it

        else {

            finalvalue

                += arr[i].value

                   * ((double)W / (double)arr[i].weight);

            break;

        }

    }

    // Returning final value

    return finalvalue;

}

// Driver's code

int main()

{

    int W = 50; //    Weight of knapsack

    Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } };

    int N = sizeof(arr) / sizeof(arr[0]);

    // Function call

    cout << ""Maximum value we can obtain = ""

         << fractionalKnapsack(W, arr, N);

    return 0;

}

Output:

Maximum value we can obtain = 240

//Time Complexity: O(N log N)

//Auxiliary Space: O(N)

"

"In this lecture of our Algorithm module, we will learn about Job Sequencing Problem.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Problem Statement:

In job sequencing problem, the objective is to find a sequence of jobs, which is completed within their deadlines and gives maximum profit.

Solution:

Let us consider, a set of n given jobs that are associated with deadlines, and profit is earned, if a job is completed by its deadline. These jobs need to be ordered in such a way that there is maximum profit.

- It may happen that all of the given jobs may not be completed within their deadlines.

- Assume, the deadline of ith job Ji is di and the profit received from this job is pi. Hence, the optimal solution of this algorithm is a feasible solution with maximum profit.

- Thus, D(i)>0 for 1⩽i⩽n

- Initially, these jobs are ordered according to profit, i.e. p1⩾p2⩾p3⩾...⩾pn.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k)

D(0) := J(0) := 0

k := 1

J(1) := 1   // means first job is selected

for i = 2 … n do

   r := k

   while D(J(r)) > D(i) and D(J(r)) ≠ r do

      r := r – 1

   if D(J(r)) ≤ D(i) and D(i) > r then

      for l = k … r + 1 by -1 do

         J(l + 1) := J(l)

         J(r + 1) := i

         k := k + 1

Analysis:

In this algorithm, we are using two loops, one is within another. Hence, the complexity of this algorithm is O(n2).

Example:

Let us consider a set of given jobs as shown in the following table. We have to find a sequence of jobs, which will be completed within their deadlines and will give maximum profit. Each job is associated with a deadline and profit.

Job          J1     J2 J3  J4 J5

Deadline  2     1  3  2   1

Profit       60 100 20 40 20

Solution:

To solve this problem, the given jobs are sorted according to their profit in a descending order. Hence, after sorting, the jobs are ordered as shown in the following table.

Job               J2 J1 J4 J3 J5

Deadline      1    2   2   3   1

Profit         100 60 40 20 20

From this set of jobs, first we select J2, as it can be completed within its deadline and contributes maximum profit.

- Next, J1 is selected as it gives more profit compared to J4.

- In the next clock, J4 cannot be selected as its deadline is over, hence J3 is selected as it executes within its deadline.

- The job J5 is discarded as it cannot be executed within its deadline.

Thus, the solution is the sequence of jobs (J2, J1, J3), which are being executed within their deadline and gives maximum profit.

Total profit of this sequence is 100 + 60 + 20 = 180.

"

"In this lecture of our Algorithm module, we will learn about Huffman Coding & Huffman Algorithms.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Huffman coding is a lossless data compression algorithm. In this algorithm, a variable-length code is assigned to input different characters. The code length is related to how frequently characters are used. Most frequent characters have the smallest codes and longer codes for least frequent characters.

- There are mainly two parts. The first one is to create a Huffman tree, and another one is to traverse the tree to find codes.

- For example, consider some strings “YYYZXXYYX”, the frequency of character Y is larger than X and character Z has the least frequency. So the length of the code for Y is smaller than X, and the code for X will be smaller than Z.

- The complexity for assigning the code for each character according to their frequency is O(n log n)

Input and Output:

Input:

A string with different characters, say “ACCEBFFFFAAXXBLKE”

Output:

Code for different characters:

Data: K, Frequency: 1, Code: 0000

Data: L, Frequency: 1, Code: 0001

Data: E, Frequency: 2, Code: 001

Data: F, Frequency: 4, Code: 01

Data: B, Frequency: 2, Code: 100

Data: C, Frequency: 2, Code: 101

Data: X, Frequency: 2, Code: 110

Data: A, Frequency: 3, Code: 111

Algorithm: huffmanCoding(string)

- Input: A string with different characters.

- Output: The codes for each individual character.

Begin

   define a node with character, frequency, left and right child of the node for Huffman tree.

   create a list ‘freq’ to store frequency of each character, initially, all are 0

   for each character c in the string do

      increase the frequency for character ch in freq list.

   done

   for all type of character ch do

      if the frequency of ch is non zero then

         add ch and its frequency as a node of priority queue Q.

   done

   while Q is not empty do

      remove item from Q and assign it to left child of node

      remove item from Q and assign to the right child of node

      traverse the node to find the assigned code

   done

End

traverseNode(n: node, code)

- Input: The node n of the Huffman tree, and the code assigned from the previous call

- Output: Code assigned with each character

if a left child of node n ≠φ then

   traverseNode(leftChild(n), code+’0’)     //traverse through the left child

   traverseNode(rightChild(n), code+’1’)    //traverse through the right child

else

   display the character and data of current node.

"

"In this lecture of our Algorithm module, we will learn about Recursion Introduction.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

A recursive algorithm calls itself with smaller input values and returns the result for the current input by carrying out basic operations on the returned value for the smaller input. Generally, if a problem can be solved by applying solutions to smaller versions of the same problem, and the smaller versions shrink to readily solvable instances, then the problem can be solved using a recursive algorithm.

In general, recursive computer programs require more memory and computation compared with iterative algorithms, but they are simpler and for many cases a natural way of thinking about the problem.

Example − a function calling itself.

int function(int value) {

   if(value < 1)

      return;

   function(value - 1);

   printf(""%d "",value);   

}

Example − a function that calls another function which in turn calls it again.

int function1(int value1) {

   if(value1 < 1)

      return;

   function2(value1 - 1);

   printf(""%d "",value1);   

}

int function2(int value2) {

   function1(value2);

}

Properties:

A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have −

- Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.

- Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

- Time Complexity: In case of iterations, we take number of iterations to count the time complexity. Likewise, in case of recursion, assuming everything is constant, we try to figure out the number of times a recursive call is being made. A call made to a function is Ο(1), hence the (n) number of times a recursive call is made makes the recursive function Ο(n).

- Space Complexity: Space complexity is counted as what amount of extra space is required for a module to execute. In case of iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used in the iterations. But in case of recursion, the system needs to store an activation record each time a recursive call is made. Hence, it is considered that the space complexity of the recursive function may go higher than that of a function with iteration.

"

"In this lecture of our Algorithm module, we will learn about printing N to 1 & printing 1 to N using Recursion.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Previously we learned that A recursive algorithm is an algorithm which calls itself with ""smaller (or simpler)"" input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller (or simpler) input. Now we will learn about its implementation and will use it in an example to demonstrate the same.

Program to print numbers from N to 1 in reverse order:

Given a number N, the task is to print the numbers from N to 1.

Examples:

Input: N = 10 

Output: 10 9 8 7 6 5 4 3 2 1

Input: N = 7 

Output: 7 6 5 4 3 2 1  

Approach 1: We will use recursion to solve this problem.

1. Check for the base case. Here it is N<=0.

2. If base condition satisfied, return to the main function.

3. If base condition not satisfied, print N and call the function recursively with value (N – 1) until base condition satisfies.

Below is the implementation of the above approach. 

#include <bits/stdc++.h>

using namespace std;

// Recursive function to print from N to 1

void PrintReverseOrder(int N)

{

    // if N is less than 1

    // then return void function

    if (N <= 0) {

        return;

    }

    else {

        cout << N << "" "";

        // recursive call of the function

        PrintReverseOrder(N - 1);

    }

}

// Driven Code

int main()

{

    int N = 5;

    PrintReverseOrder(N);

    return 0;

}

Output: 

5 4 3 2 1

//Time Complexity: O(N)

//Auxiliary Space: O(N)

"

"In this lecture of our Algorithm module, we will learn about Natural Number Sum using Recursion.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Previously we learned that A recursive algorithm is an algorithm which calls itself with ""smaller (or simpler)"" input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller (or simpler) input. Now we will learn about its implementation and will use it in an example to demonstrate the same.

Given a number n, find sum of first n natural numbers. To calculate the sum, we will use a recursive function recur_sum().

Examples :

Input : 3

Output : 6

Explanation : 1 + 2 + 3 = 6

Input : 5

Output : 15

Explanation : 1 + 2 + 3 + 4 + 5 = 15

Below is code to find the sum of natural numbers up to n using recursion : 

#include <iostream>

using namespace std;

// Returns sum of first

// n natural numbers

int recurSum(int n)

{

    if (n <= 1)

        return n;

    return n + recurSum(n - 1);

}

// Driver code

int main()

{

    int n = 5;

    cout << recurSum(n);

    return 0;

}

Output : 

15

// Time complexity : O(n)

// Auxiliary space : O(n)

"

"In this lecture of our Algorithm module, we will learn about Sum of Digits Using Recursion.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Given a number, we need to find sum of its digits using recursion.

Examples:

Input : 12345

Output : 15

Input : 45632

Output :20

"

"In this lecture of our Algorithm module, we will learn about Rope Cutting Problem.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters. 

Examples: 

Input: n = 2

Output: 1 (Maximum obtainable product is 1*1)

Input: n = 3

Output: 2 (Maximum obtainable product is 1*2)

Input: n = 4

Output: 4 (Maximum obtainable product is 2*2)

Input: n = 5

Output: 6 (Maximum obtainable product is 2*3)

Input: n = 10

Output: 36 (Maximum obtainable product is 3*3*4)

int maxProd(int n)

{

   int val[n+1];

   val[0] = val[1] = 0;

   // Build the table val[] in bottom up manner and return

   // the last entry from the table

   for (int i = 1; i <= n; i++)

   {

      int max_val = 0;

      for (int j = 1; j <= i; j++)

         max_val = max(max_val, (i-j)*j, j*val[i-j]);

      val[i] = max_val;

   }

   return val[n];

}

Time Complexity of the Dynamic Programming solution is O(n^2) and it requires O(n) extra space. This is a hands on tutorial where we will discuss the algorithm using an example for clear understanding of the topic.

"

"In this lecture of our Algorithm module, we will learn about Generating Subsets.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Previously we learned that A recursive algorithm is an algorithm which calls itself with ""smaller (or simpler)"" input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller (or simpler) input. Now we will learn about its implementation and will use it in an example to demonstrate the same.

Given a set represented as a string, write a recursive code to print all subsets of it. The subsets can be printed in any order. 

Examples:  

Input :  set = ""abc""

Output : """", ""a"", ""b"", ""c"", ""ab"", ""ac"", ""bc"", ""abc""

Input : set = ""abcd""

Output : """" ""a"" ""ab"" ""abc"" ""abcd"" ""abd"" ""ac"" ""acd""

         ""ad"" ""b"" ""bc"" ""bcd"" ""bd"" ""c"" ""cd"" ""d""

Method: The idea is to pick each element one by one from the input set, then generate a subset for the same, and we follow this process recursively. 

We’ll use ArrayList for this purpose 

For ex, 

- f(0) = {a}, {} // {} when we don’t include any element from the set, it is null i.e {}. 

- f(1) = {a}, {}, {b}, {a, b} // We have to copy all the elements from f(0) and then include the very next element from the set i.e b. So f(1) = f(0) + 1; 

- f(2) = {a}, {}, {b}, {a, b}, {a, c}, {c}, {b, c}, {a, b, c}. So f(2) = f(1) +2;

The general form becomes f(n) = f(n-1) + n; 

"

"In this lecture of our Algorithm module, we will learn about Tower of Hanoi.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Tower of Hanoi is a mathematical puzzle where we have three rods (A, B, and C) and N disks. Initially, all the disks are stacked in decreasing value of diameter i.e., the smallest disk is placed on the top and they are on rod A. The objective of the puzzle is to move the entire stack to another rod (here considered C), obeying the following simple rules: 

- Only one disk can be moved at a time.

- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.

- No disk may be placed on top of a smaller disk.

Tower of Hanoi using Recursion:

The idea is to use the helper node to reach the destination using recursion. Below is the pattern for this problem:

- Shift ‘N-1’ disks from ‘A’ to ‘B’, using C.

- Shift last disk from ‘A’ to ‘C’.

- Shift ‘N-1’ disks from ‘B’ to ‘C’, using A.

Below is the implementation of the above approach.

#include <bits/stdc++.h>

using namespace std;

void towerOfHanoi(int n, char from_rod, char to_rod,

                  char aux_rod)

{

    if (n == 0) {

        return;

    }

    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);

    cout << ""Move disk "" << n << "" from rod "" << from_rod

         << "" to rod "" << to_rod << endl;

    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);

}

// Driver code

int main()

{

    int N = 3;

    // A, B and C are names of rods

    towerOfHanoi(N, 'A', 'C', 'B');

    return 0;

}

Output:

Move disk 1 from rod A to rod C

Move disk 2 from rod A to rod B

Move disk 1 from rod C to rod B

Move disk 3 from rod A to rod C

Move disk 1 from rod B to rod A

Move disk 2 from rod B to rod C

Move disk 1 from rod A to rod C

Time complexity: O(2N), There are two possibilities for every disk. Therefore, 2 * 2 * 2 * . . . * 2(N times) is 2N.

Auxiliary Space: O(N), Function call stack space.

"

"In this lecture of our Algorithm module, we will learn about Concepts of Backtracking.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time (by time, here, is referred to the time elapsed till reaching any level of the search tree).

There are three types of problems in backtracking –  

1. Decision Problem – In this, we search for a feasible solution.

2. Optimization Problem – In this, we search for the best solution.

3. Enumeration Problem – In this, we find all feasible solutions.

Pseudo Code for Backtracking:  

- Recursive backtracking solution. 

void findSolutions(n, other params) :

    if (found a solution) :

        solutionsFound = solutionsFound + 1;

        displaySolution();

        if (solutionsFound >= solutionTarget) :

            System.exit(0);

        return

    for (val = first to last) :

        if (isValid(val, n)) :

            applyValue(val, n);

            findSolutions(n+1, other params);

            removeValue(val, n);

- Finding whether a solution exists or not 

boolean findSolutions(n, other params) :

    if (found a solution) :

        displaySolution();

        return true;

    for (val = first to last) :

        if (isValid(val, n)) :

            applyValue(val, n);

            if (findSolutions(n+1, other params))

                return true;

            removeValue(val, n);

        return false;

"

"In this lecture of our Algorithm module, we will learn about N Queen Problem.

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Previously we learned that A backtracking algorithm is a problem-solving algorithm that uses a brute force approach for finding the desired output. The Brute force approach tries out all the possible solutions and chooses the desired/best solutions. Now we will learn about its implementation with help of an example.

#include <bits/stdc++.h>

#define N 4

using namespace std;

/* A utility function to print solution */

void printSolution(int board[N][N])

{

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++)

            cout << "" "" << board[i][j] << "" "";

        printf(""\n"");

    }

}

/* A utility function to check if a queen can

   be placed on board[row][col]. Note that this

   function is called when ""col"" queens are

   already placed in columns from 0 to col -1.

   So we need to check only left side for

   attacking queens */

bool isSafe(int board[N][N], int row, int col)

{

    int i, j;

    /* Check this row on left side */

    for (i = 0; i < col; i++)

        if (board[row][i])

            return false;

    /* Check upper diagonal on left side */

    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)

        if (board[i][j])

            return false;

    /* Check lower diagonal on left side */

    for (i = row, j = col; j >= 0 && i < N; i++, j--)

        if (board[i][j])

            return false;

    return true;

}

/* A recursive utility function to solve N

   Queen problem */

bool solveNQUtil(int board[N][N], int col)

{

    /* base case: If all queens are placed

      then return true */

    if (col >= N)

        return true;

    /* Consider this column and try placing

       this queen in all rows one by one */

    for (int i = 0; i < N; i++) {

        /* Check if the queen can be placed on

          board[i][col] */

        if (isSafe(board, i, col)) {

            /* Place this queen in board[i][col] */

            board[i][col] = 1;

            /* recur to place rest of the queens */

            if (solveNQUtil(board, col + 1))

                return true;

            /* If placing queen in board[i][col]

               doesn't lead to a solution, then

               remove queen from board[i][col] */

            board[i][col] = 0; // BACKTRACK

        }

    }

    /* If the queen cannot be placed in any row in

        this column col  then return false */

    return false;

}

/* This function solves the N Queen problem using

   Backtracking. It mainly uses solveNQUtil() to

   solve the problem. It returns false if queens

   cannot be placed, otherwise, return true and

   prints placement of queens in the form of 1s.

   Please note that there may be more than one

   solutions, this function prints one  of the

   feasible solutions.*/

bool solveNQ()

{

    int board[N][N] = { { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 } };

    if (solveNQUtil(board, 0) == false) {

        cout << ""Solution does not exist"";

        return false;

    }

    printSolution(board);

    return true;

}

// driver program to test above function

int main()

{

    solveNQ();

    return 0;

}

Output:

0  0  1  0

1  0  0  0

0  0  0  1

0  1  0  0

Time Complexity: O(N!)

Auxiliary Space: O(N2)

Optimization in is_safe() function

The idea is not to check every element in right and left diagonal, instead use the property of diagonals: 

1. The sum of i and j is constant and unique for each right diagonal, where i is the row of elements and j is the column of elements. 

2. The difference between i and j is constant and unique for each left diagonal, where i and j are row and column of element respectively."

"In this lecture of our Algorithm module, we will learn about Sudoku Problem.

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Previously we learned that A backtracking algorithm is a problem-solving algorithm that uses a brute force approach for finding the desired output. The Brute force approach tries out all the possible solutions and chooses the desired/best solutions. Now we will learn about its implementation with help of an example.

Problem Statement: Given a partially filled 9×9 2D array ‘grid[9][9]’, the goal is to assign digits (from 1 to 9) to the empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9.

Example: 

Input:

grid = { {3, 0, 6, 5, 0, 8, 4, 0, 0},

         {5, 2, 0, 0, 0, 0, 0, 0, 0},

         {0, 8, 7, 0, 0, 0, 0, 3, 1},

         {0, 0, 3, 0, 1, 0, 0, 8, 0},

         {9, 0, 0, 8, 6, 3, 0, 0, 5},

         {0, 5, 0, 0, 9, 0, 6, 0, 0},

         {1, 3, 0, 0, 0, 0, 2, 5, 0},

         {0, 0, 0, 0, 0, 0, 0, 7, 4},

         {0, 0, 5, 2, 0, 6, 3, 0, 0} }

Output:

          3 1 6 5 7 8 4 9 2

          5 2 9 1 3 4 7 6 8

          4 8 7 6 2 9 5 3 1

          2 6 3 4 1 5 9 8 7

          9 7 4 8 6 3 1 2 5

          8 5 1 7 9 2 6 4 3

          1 3 8 9 4 7 2 5 6

          6 9 2 3 5 1 8 7 4

          7 4 5 2 8 6 3 1 9

Explanation: Each row, column and 3*3 box of

the output matrix contains unique numbers.

Input:   

grid = { { 3, 1, 6, 5, 7, 8, 4, 9, 2 },

         { 5, 2, 9, 1, 3, 4, 7, 6, 8 },

         { 4, 8, 7, 6, 2, 9, 5, 3, 1 },

         { 2, 6, 3, 0, 1, 5, 9, 8, 7 },

         { 9, 7, 4, 8, 6, 0, 1, 2, 5 },

         { 8, 5, 1, 7, 9, 2, 6, 4, 3 },

         { 1, 3, 8, 0, 4, 7, 2, 0, 6 },

         { 6, 9, 2, 3, 5, 1, 8, 7, 4 },

         { 7, 4, 5, 0, 8, 6, 3, 1, 0 } };

Output:

           3 1 6 5 7 8 4 9 2

           5 2 9 1 3 4 7 6 8

           4 8 7 6 2 9 5 3 1

           2 6 3 4 1 5 9 8 7

           9 7 4 8 6 3 1 2 5

           8 5 1 7 9 2 6 4 3

           1 3 8 9 4 7 2 5 6

           6 9 2 3 5 1 8 7 4

           7 4 5 2 8 6 3 1 9

Explanation: Each row, column and 3*3 box of

the output matrix contains unique numbers.

Code Implementation:

#include <bits/stdc++.h>

using namespace std;

// UNASSIGNED is used for empty

// cells in sudoku grid

#define UNASSIGNED 0

// N is used for the size of Sudoku grid.

// Size will be NxN

#define N 9

// This function finds an entry in grid

// that is still unassigned

bool FindUnassignedLocation(int grid[N][N],

                            int& row, int& col);

// Checks whether it will be legal

// to assign num to the given row, col

bool isSafe(int grid[N][N], int row,

            int col, int num);

/* Takes a partially filled-in grid and attempts

to assign values to all unassigned locations in

such a way to meet the requirements for

Sudoku solution (non-duplication across rows,

columns, and boxes) */

bool SolveSudoku(int grid[N][N])

{

    int row, col;

    // If there is no unassigned location,

    // we are done

    if (!FindUnassignedLocation(grid, row, col))

        // success!

        return true;

    // Consider digits 1 to 9

    for (int num = 1; num <= 9; num++)

    {

        // Check if looks promising

        if (isSafe(grid, row, col, num))

        {

            // Make tentative assignment

            grid[row][col] = num;

            // Return, if success

            if (SolveSudoku(grid))

                return true;

            // Failure, unmake & try again

            grid[row][col] = UNASSIGNED;

        }

    }

    // This triggers backtracking

    return false;

}

/* Searches the grid to find an entry that is

still unassigned. If found, the reference

parameters row, col will be set the location

that is unassigned, and true is returned.

If no unassigned entries remain, false is returned. */

bool FindUnassignedLocation(int grid[N][N],

                            int& row, int& col)

{

    for (row = 0; row < N; row++)

        for (col = 0; col < N; col++)

            if (grid[row][col] == UNASSIGNED)

                return true;

    return false;

}

/* Returns a boolean which indicates whether

an assigned entry in the specified row matches

the given number. */

bool UsedInRow(int grid[N][N], int row, int num)

{

    for (int col = 0; col < N; col++)

        if (grid[row][col] == num)

            return true;

    return false;

}

/* Returns a boolean which indicates whether

an assigned entry in the specified column

matches the given number. */

bool UsedInCol(int grid[N][N], int col, int num)

{

    for (int row = 0; row < N; row++)

        if (grid[row][col] == num)

            return true;

    return false;

}

/* Returns a boolean which indicates whether

an assigned entry within the specified 3x3 box

matches the given number. */

bool UsedInBox(int grid[N][N], int boxStartRow,

               int boxStartCol, int num)

{

    for (int row = 0; row < 3; row++)

        for (int col = 0; col < 3; col++)

            if (grid[row + boxStartRow]

                    [col + boxStartCol] ==

                                       num)

                return true;

    return false;

}

/* Returns a boolean which indicates whether

it will be legal to assign num to the given

row, col location. */

bool isSafe(int grid[N][N], int row,

            int col, int num)

{

    /* Check if 'num' is not already placed in

    current row, current column

    and current 3x3 box */

    return !UsedInRow(grid, row, num)

           && !UsedInCol(grid, col, num)

           && !UsedInBox(grid, row - row % 3,

                         col - col % 3, num)

           && grid[row][col] == UNASSIGNED;

}

/* A utility function to print grid */

void printGrid(int grid[N][N])

{

    for (int row = 0; row < N; row++)

    {

        for (int col = 0; col < N; col++)

            cout << grid[row][col] << "" "";

        cout << endl;

    }

}

// Driver Code

int main()

{

    // 0 means unassigned cells

    int grid[N][N] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 },

                       { 5, 2, 0, 0, 0, 0, 0, 0, 0 },

                       { 0, 8, 7, 0, 0, 0, 0, 3, 1 },

                       { 0, 0, 3, 0, 1, 0, 0, 8, 0 },

                       { 9, 0, 0, 8, 6, 3, 0, 0, 5 },

                       { 0, 5, 0, 0, 9, 0, 6, 0, 0 },

                       { 1, 3, 0, 0, 0, 0, 2, 5, 0 },

                       { 0, 0, 0, 0, 0, 0, 0, 7, 4 },

                       { 0, 0, 5, 2, 0, 6, 3, 0, 0 } };

    if (SolveSudoku(grid) == true)

        printGrid(grid);

    else

        cout << ""No solution exists"";

    return 0;

}

"

"In this lecture of our Algorithm module, we will learn about Breadth First Search.

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(E, V).

Tree v/s Graph

Trees are the restricted types of graphs, just with some more rules. Every tree will always be a graph but not all graphs will be trees. Linked List, Trees, and Heaps all are special cases of graphs.

In the coming videos, we will be learning various types of Graphs like:

1. Undirected Graph: A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge. 

2. Directed Graph: A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.

3. Undirected Graph: A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge. 

4. Directed Graph: A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.

5. Cyclic Graph: A graph containing at least one cycle is known as a Cyclic graph.

6. Directed Acyclic Graph: A Directed Graph that does not contain any cycle. 

7. Weighted Graph

    - A graph in which the edges are already specified with suitable weight is known as a weighted graph. 

    - Weighted graphs can be further classified as directed weighted graphs and undirected weighted graphs. 

"

"In this lecture of our Algorithm module, we will learn about Breadth First Search.

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Breadth-first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes. While using BFS for traversal, any node in the graph can be considered as the root node.

Given below is the algorithm for BFS technique.

Consider G as a graph which we are going to traverse using the BFS algorithm.

Let S be the root/starting node of the graph.

- Step 1: Start with node S and enqueue it to the queue.

- Step 2: Repeat the following steps for all the nodes in the graph.

- Step 3: Dequeue S and process it.

- Step 4: Enqueue all the adjacent nodes of S and process them.

- [END OF LOOP]

- Step 6: EXIT

The pseudo-code for the BFS technique is given below.

Procedure BFS (G, s)

      G is the graph and s is the source node

begin

               let q be queue to store nodes

               q.enqueue(s) //insert source node in the queue

               mark s as visited.

               while (q is not empty)

               //remove the element from the queue whose adjacent nodes are to be processed

               n = q.dequeue( )

                //processing all the adjacent nodes of n

                for all neighbors m of n in Graph G if w is not visited

                q.enqueue (m)         //Stores m in Q to in turn visit its adjacent nodes

                mark m as visited.

end

"

"In this lecture of our Algorithm module, we will learn about Depth First Search Algorithm.

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, that, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than once, use a boolean visited array. A graph can have more than one DFS traversal.

Follow the below steps to solve the problem:

- Create a recursive function that takes the index of the node and a visited array.

- Mark the current node as visited and print the node.

- Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.

Below is the implementation of the above approach:

#include <bits/stdc++.h>

using namespace std;

// Graph class represents a directed graph

// using adjacency list representation

class Graph {

public:

    map<int, bool> visited;

    map<int, list<int> > adj;

    // function to add an edge to graph

    void addEdge(int v, int w);

    // DFS traversal of the vertices

    // reachable from v

    void DFS(int v);

};

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Add w to v’s list.

}

void Graph::DFS(int v)

{

    // Mark the current node as visited and

    // print it

    visited[v] = true;

    cout << v << "" "";

    // Recur for all the vertices adjacent

    // to this vertex

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

        if (!visited[*i])

            DFS(*i);

}

// Driver's code

int main()

{

    // Create a graph given in the above diagram

    Graph g;

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 2);

    g.addEdge(2, 0);

    g.addEdge(2, 3);

    g.addEdge(3, 3);

    cout << ""Following is Depth First Traversal""

            "" (starting from vertex 2) \n"";

    // Function call

    g.DFS(2);

    return 0;

}

Output:

Following is Depth First Traversal (starting from vertex 2)

2 0 1 3

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Auxiliary Space: O(V), since an extra visited array of size V is required."

"In this lecture of our Algorithm module, we will learn about Applications of DFS.

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Previously we learned that Depth-first search (DFS) is an algorithm (or technique) for traversing a graph. DFS uses a stack data structure for the traversal. A graph can have more than one DFS traversal.

Following is the problem that use DFS as a building block. 

Detecting cycle in a graph: A graph has cycle if and only if we see a back edge during DFS. So we can run DFS for the graph and check for back edges.

Follow the below steps to Implement the idea:

- Create the graph using the given number of edges and vertices.

- Create a recursive function that initializes the current vertex, visited array, and recursion stack.

- Mark the current node as visited and also mark the index in the recursion stack.

- Find all the vertices which are not visited and are adjacent to the current node and recursively call the function for those vertices

    - If the recursive function returns true, return true.

    - If the adjacent vertices are already marked in the recursion stack then return true.

- Create a wrapper function, that calls the recursive function for all the vertices, and

    - If any function returns true return true. 

    - Else if for all vertices the function returns false return false.

// A C++ Program to detect cycle in a graph

#include<bits/stdc++.h>

using namespace std;

class Graph

{

int V; // No. of vertices

list<int> *adj; // Pointer to an array containing adjacency lists

bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic()

public:

Graph(int V); // Constructor

void addEdge(int v, int w); // to add an edge to graph

bool isCyclic(); // returns true if there is a cycle in this graph

};

Graph::Graph(int V)

{

this->V = V;

adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

adj[v].push_back(w); // Add w to v’s list.

}

// This function is a variation of DFSUtil() in

// https://www.geeksforgeeks.org/archives/18212

bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)

{

if(visited[v] == false)

{

// Mark the current node as visited and part of recursion stack

visited[v] = true;

recStack[v] = true;

// Recur for all the vertices adjacent to this vertex

list<int>::iterator i;

for(i = adj[v].begin(); i != adj[v].end(); ++i)

{

if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )

return true;

else if (recStack[*i])

return true;

}

}

recStack[v] = false; // remove the vertex from recursion stack

return false;

}

// Returns true if the graph contains a cycle, else false.

// This function is a variation of DFS() in

// https://www.geeksforgeeks.org/archives/18212

bool Graph::isCyclic()

{

// Mark all the vertices as not visited and not part of recursion

// stack

bool *visited = new bool[V];

bool *recStack = new bool[V];

for(int i = 0; i < V; i++)

{

visited[i] = false;

recStack[i] = false;

}

// Call the recursive helper function to detect cycle in different

// DFS trees

for(int i = 0; i < V; i++)

if ( !visited[i] && isCyclicUtil(i, visited, recStack))

return true;

return false;

}

int main()

{

// Create a graph given in the above diagram

Graph g(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

if(g.isCyclic())

cout << ""Graph contains cycle"";

else

cout << ""Graph doesn't contain cycle"";

return 0;

}

"

"In this lecture of our Algorithm module, we will learn about Detect Cycle in Undirected Graph.

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Problem Statement: Given an undirected graph, how to check if there is a cycle in the graph?

Approach: Run a DFS from every unvisited node. Depth First Traversal can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is joining a node to itself (self-loop) or one of its ancestor in the tree produced by DFS. 

#include <iostream>

#include <limits.h>

#include <list>

using namespace std;

// Class for an undirected graph

class Graph {

    // No. of vertices

    int V;

    // Pointer to an array

    // containing adjacency lists

    list<int>* adj;

    bool isCyclicUtil(int v, bool visited[], int parent);

public:

    // Constructor

    Graph(int V);

    // To add an edge to graph

    void addEdge(int v, int w);

    // Returns true if there is a cycle

    bool isCyclic();

};

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

    // Add w to v’s list.

    adj[v].push_back(w);

    // Add v to w’s list.

    adj[w].push_back(v);

}

// A recursive function that

// uses visited[] and parent to detect

// cycle in subgraph reachable

// from vertex v.

bool Graph::isCyclicUtil(int v, bool visited[], int parent)

{

    // Mark the current node as visited

    visited[v] = true;

    // Recur for all the vertices

    // adjacent to this vertex

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i) {

        // If an adjacent vertex is not visited,

        // then recur for that adjacent

        if (!visited[*i]) {

            if (isCyclicUtil(*i, visited, v))

                return true;

        }

        // If an adjacent vertex is visited and

        // is not parent of current vertex,

        // then there exists a cycle in the graph.

        else if (*i != parent)

            return true;

    }

    return false;

}

// Returns true if the graph contains

// a cycle, else false.

bool Graph::isCyclic()

{

    // Mark all the vertices as not

    // visited and not part of recursion

    // stack

    bool* visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

    // Call the recursive helper

    // function to detect cycle in different

    // DFS trees

    for (int u = 0; u < V; u++) {

        // Don't recur for u if

        // it is already visited

        if (!visited[u])

            if (isCyclicUtil(u, visited, -1))

                return true;

    }

    return false;

}

// Driver program to test above functions

int main()

{

    Graph g1(5);

    g1.addEdge(1, 0);

    g1.addEdge(0, 2);

    g1.addEdge(2, 1);

    g1.addEdge(0, 3);

    g1.addEdge(3, 4);

    g1.isCyclic() ? cout << ""Graph contains cycle\n""

                  : cout << ""Graph doesn't contain cycle\n"";

    Graph g2(3);

    g2.addEdge(0, 1);

    g2.addEdge(1, 2);

    g2.isCyclic() ? cout << ""Graph contains cycle\n""

                  : cout << ""Graph doesn't contain cycle\n"";

    return 0;

}

Output:

Graph contains cycle

Graph doesn't contain cycle

Complexity Analysis: 

- Time Complexity: O(V+E). 

- The program does a simple DFS Traversal of the graph which is represented using adjacency list. So the time complexity is O(V+E).

- Space Complexity: O(V). 

- To store the visited array O(V) space is required.

"

"In this lecture of our Algorithm module, we will learn about Topological Sorting (DFS Based Algorithm).

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

Below is the implementation of DFS to print topological sorting of a DAG:

#include <iostream>

#include <list>

#include <stack>

using namespace std;

// Class to represent a graph

class Graph {

    // No. of vertices'

    int V;

    // Pointer to an array containing adjacency listsList

    list<int>* adj;

    // A function used by topologicalSort

    void topologicalSortUtil(int v, bool visited[],

                             stack<int>& Stack);

public:

    // Constructor

    Graph(int V);

    // function to add an edge to graph

    void addEdge(int v, int w);

    // prints a Topological Sort of

    // the complete graph

    void topologicalSort();

};

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

    // Add w to v’s list.

    adj[v].push_back(w);

}

// A recursive function used by topologicalSort

void Graph::topologicalSortUtil(int v, bool visited[],

                                stack<int>& Stack)

{

    // Mark the current node as visited.

    visited[v] = true;

    // Recur for all the vertices

    // adjacent to this vertex

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

        if (!visited[*i])

            topologicalSortUtil(*i, visited, Stack);

    // Push current vertex to stack

    // which stores result

    Stack.push(v);

}

// The function to do Topological Sort.

// It uses recursive topologicalSortUtil()

void Graph::topologicalSort()

{

    stack<int> Stack;

    // Mark all the vertices as not visited

    bool* visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

    // Call the recursive helper function

    // to store Topological

    // Sort starting from all

    // vertices one by one

    for (int i = 0; i < V; i++)

        if (visited[i] == false)

            topologicalSortUtil(i, visited, Stack);

    // Print contents of stack

    while (Stack.empty() == false) {

        cout << Stack.top() << "" "";

        Stack.pop();

    }

}

// Driver Code

int main()

{

    // Create a graph given in the above diagram

    Graph g(6);

    g.addEdge(5, 2);

    g.addEdge(5, 0);

    g.addEdge(4, 0);

    g.addEdge(4, 1);

    g.addEdge(2, 3);

    g.addEdge(3, 1);

    cout << ""Following is a Topological Sort of the given ""

            ""graph \n"";

    // Function Call

    g.topologicalSort();

    return 0;

}

Output:

Following is a Topological Sort of the given graph

5 4 2 3 1 0

Complexity Analysis:

- Time Complexity: O(V+E). 

- The above algorithm is simply DFS with an extra stack. So time complexity is the same as DFS which is.

- Auxiliary space: O(V). 

- The extra space is needed for the stack.

"

"In this lecture of our Algorithm module, we will learn about Topological Sorting (Kahn's BFS Based Algorithm).

An Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

The C++ code using a BFS traversal is given below:

vector<int> topological_sorting(vector<vector<int>> graph) {

    vector <int> indegree(graph.size(), 0);

    queue<int> q;

    vector<int> solution;

    for(int i = 0; i < graph.size(); i++) {

        for(int j = 0; j < graph[i].size(); j++)

        {

        //iterate over all edges

            indegree[ graph[i][j] ]++;

        }

    }

    //enqueue all nodes with indegree 0

    for(int i = 0; i < graph.size(); i++)

    {

        if(indegree[i] == 0) {

            q.push(i);

        }

    }

    //remove one node after the other

    while(q.size() > 0) {

        int currentNode = q.front();

        q.pop();

        solution.push_back(currentNode);

        for(int j = 0; j < graph[currentNode].size(); j++)

        {