Ilovepdf Merged
Ilovepdf Merged
INTRODUCTION
Here are the steps that may be followed to solve an algorithmic problem:
    ●   Analyzing the problem statement means making the objective of the program clear
        in our minds like what the input is and what is the required output.
    ●   Sometimes the problems are of complex nature, to make them easier to
        understand, we can break-down the problem into smaller sub-parts.
    ●   In order to save our time in debugging our code, we should first-of-all write down
        the solution on a paper with basic steps that would help us get a clear intuition of
        what we are going to do with the problem statement.
    ●   In order to make the solution error-free, the next step is to verify the solution by
        checking it with a bunch of test cases.
    ●   Now, we clearly know what we are going to do in the code. In this step we will start
        coding our solution on the compiler.
Flowcharts
Uses of Flowcharts
    ➔ Used in documentation.
    ➔ Used to communicate one’s solution with others, basically used for group projects.
    ➔ To check out at any step what we are going to do and get a clear explanation of the
        flow of statements.
Flowchart components
● Terminators
1
                       Mainly used to denote the start point of the program.
● Input/Output
Used for taking input from the user and store it in variable ‘var’.
● Process
● Decision
● Arrows
            Generally, used to show the flow of the program from one step to another. The
            head of the arrow shows the next step and the tail shows the previous one.
● Connector
2
                Used to connect different parts of the program and are used in case of
                break-through. Generally, used for functions(which we will study in our
                further sections).
Example 1:
Suppose we have to make a flowchart for adding 2 numbers a and b.
Solution:
Example 2:
Suppose we have to check if a number is even or odd.
Solution:
3
Note:  Operator % is used to find the remainder of a number with respect to another
number. F
         or example:
    ●   4%3=1
    ●   10 % 5 = 0
    ●   4%2=0
    ●   4%4=0
    ●   0%1=0
    ●   1 % 0 = undefined (as it leads to division by 0)
Example 3:
To print the numbers less than or equal to n where n is given by the user.
Solution:
4
Summary
5
    ●   Sometimes, it becomes a bulky process to represent any program using flowchart.
        In those cases, try to find out the optimal solution to the given problem.
Practice Problems
Till now in examples we learnt how to draw decision making blocks and how to manage
looping the same part again and again until the condition is not satisfied.
Using the concepts shown above, here are few tricky flowchart problems for your practice :
6
                         Java Foundation with Data Structures
                                  Lecture 2 : Getting Started
a) About Eclipse
      A new Java class can be created using the New Java Class wizard. The Java Class
      wizard can be invoked in different ways –
         1. By clicking on the File menu and selecting New → Class, or
         2. By right clicking in the package explorer and selecting New → Class, or
         3. By clicking on the class drop down button and selecting class.
Note : W e will understand what classes are when we will study Object Oriented
      Programming. For now you can assume them as a file. Also name of class and
      .java file inside which we have this class should be same.
b) About Main
             1. This is the line at which the program will begin executing. This statement
                is similar to start block in flowcharts. All Java programs begin execution
                by calling main()
             2. We will understand what public, static, void mean in subsequent
                lectures. For now we should assume that we have to write main as it is.
             3. The curly braces {} indicate start and end of main.
c) print / println
  Output:
  Hello World
  Programming is fun
Variables
a) Add two numbers
  Output:
  15
Here, we used variables to store values of two integers and their sum. Thus, a
variable is a basic unit of storage in a Java program.
Here, type is one of Java’s primitive datatypes. The variable_name is the name of
a variable. We can initialize the variable by specifying an equal sign and a value
(Initialization is optional). However, the compiler never assigns a default value to
an uninitialized local variable in Java.
While writing variable names you should be careful and follow the rules for
naming them. Following are the rules for writing variable names -
  1. All variable names may contain uppercase and lowercase letters (a-z, A-Z),
     underscore ( _ ), dollar sign ($) and the digits 0 to 9. The dollar sign character
     is not intended for general use. No spaces and no other special characters
     are allowed.
  2. The variable names must not begin with a number.
  3. Java is case-sensitive. Uppercase characters are distinct from lowercase
     characters.
  4. A Java keyword (reserved word) cannot be used as a variable name.
Based on the data type of a variable, the operating system allocates memory and
decides what can be stored in the reserved memory. Therefore, by assigning
different data types to variables, we can store integers, decimals, or characters in
these variables.
Example Code:
 Taking Input
 a) Scanner
The Java Scanner class breaks the input into tokens using a delimiter that is
     whitespace by default. It provides many ways to read and parse various
     primitive values.
In order to use scanner you have to write this import statement at the top –
      import java.util.Scanner;
Example Code:
      // Create a Scanner
                   Scanner s = new Scanner(System.in);
            a = s.nextInt();
            b = s.nextInt();
            c = a + b;
            System.out.println("Sum of entered integers = "+c);
      }
  }
   Sample Input:
   10 5
   Output:
   15
Here, s.nextInt() scans and returns the next token as int. A token is part of entered
line that is separated from other tokens by space, tab or newline. So when input
line is: “10 5” then s.nextInt() returns the first token i.e. “10” as int and s.nextInt()
again returns the next token i.e. “5” as int.
b) Code for calculating simple interest taking input from user
Example Code:
import java.util.Scanner;
Sample Input:
2500.0 6.0 5.0
Output:
750.0
import java.util.Scanner;
public class ScannerDemo1 {
       public static void main(String[] args) {
              Scanner s = new Scanner(System.in);
              char ch = s.next().charAt(0);      // character input
              System.out.println("input character = " +ch);
       }
 }
Sample Input:
k
Output:
input character = k
Sample Input:
Coding Ninjas
Output:
Coding
Here, s.next() returns the next token as String. A token is part of entered line that
is separated from other tokens by space, tab or newline. So when input line is -
“Coding Ninjas” then s.next() returns the first token i.e. “Coding”.
METHOD DESCRIPTION
public String next()         It returns the next token from the Scanner.
public String nextLine()     It moves the Scanner position to the next line
                             and returns the value as a string.
public byte nextByte()       It scans the next token as a byte.
public short nextShort()     It scans the next token as a short value.
public int nextInt()         It scans the next token as an int value.
public long nextLong()       It scans the next token as a long value.
public float nextFloat()     It scans the next token as a float value.
public double                It scans the next token as a double value.
nextDouble()
Example code:
Sample Input:
100 Hello World
Output:
100
Hello World
Here, s.nextInt() scans and returns the next token as int. A token is part of entered
line that is separated from other tokens by space, tab or newline. So when input
line is - “100 Hello World” then s.nextInt() returns the first token as int i.e. “100”
and s.nextLine() returns remaining part of line i.e “ (space)Hello World”
The most commonly used integer type is int which is a signed 32-bit type.
When you store an integer, its corresponding binary value is stored. The way
integers are stored differs for negative and positive numbers. For positive
numbers the integral value is simple converted into binary value and for negative
numbers their 2’s compliment form is stored.
Let’s discuss How are Negative Numbers Stored?
    1. There is only one representation for the number zero in 2's complement,
       instead of two representations in sign-magnitude and 1's complement.
Example:
int i = -4;
Steps to calculate Two’s Complement of -4 are as follows:
Thus, integer -4 is represented by the binary sequence (1111 1111 1111 1111
   1111 1111 1111 1100) in Java.
In Java, any value declared with decimal point is by default of type double (which
is of 8 bytes). If we want to assign a float value (which is of 4 bytes), then we must
use ‘f’ or ‘F’ literal to specify that current value is “float”.
Example:
float float_val = 10.4f;              //float value
double val = 10.4;               //double value
Example code:
When we add int to char, we are basically adding two numbers i.e. one
corresponding to the integer and other is corresponding code for the char.
Example code:
Output:
98
Here, we added a character and an int, so it added the ASCII value of char ‘a’ i.e
97 and int 1. So, answer will be 98.
Similar logic applies to adding two chars as well, when two chars are added their
codes are actually added i.e. ‘a’ + ‘b’ wil give 195.
Typecasting
Example code:
   double d = 100.04;
               long l2 = (long)d;      //explicit type casting
                      System.out.println(i);
               System.out.println(l1);
                     System.out.println(d);
                     System.out.println(l2);
}
Output:
100
100
100.04
100
Operators
a) Arithmetic operators
Arithmetic operators are used in mathematical expression in the same way that
are used in algebra.
          OPERATOR                         DESCRIPTION
              +           Adds two operands
              -           Subtracts second operand from first
              *           Multiplies two operands
              /           Divides numerator by denominator
             %            Calculates Remainder of division
b) Relational operators
Relational Operators are the operators that used to test some king of relation
between two entities. The following table lists the relation operators supported
by Java.
      OPERATOR                            DESCRIPTION
         ==         Check if two operands are equal
    !=              Check if two operands are not equal.
    >               Check if operand on the left is greater than operand on
                    the right
    <               Check if operand on the left is smaller than right
                    operand
    >=              Check if left operand is greater than or equal to right
                    operand
    <=              Check if operand on left is smaller than or equal to right
                    operand
 c) Logical operators
                        OPERATOR          DESCRIPTION
                           &&             al AND
                           ||             al OR
                            !             al NOT
      Example:
      Suppose a = true and b= false, then:
      (a && b) is false
      (a || b) is true
      (!a) is false
	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                                                 	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
                                   	
  
       Java	
  Foundation	
  with	
  Data	
  Structures	
  
         Lecture	
  3	
  :	
  Conditionals	
  and	
  Loops	
            	
  
	
  
	
  
Conditional	
  Statements	
  (if	
  else)	
  
Description	
  
	
  
Conditionals	
  are	
  used	
  to	
  execute	
  a	
  certain	
  section	
  of	
  code	
  only	
  if	
  some	
  
specific	
  condition	
  is	
  fulfilled,	
  and	
  optionally	
  execute	
  other	
  statements	
  if	
  
the	
  given	
  condition	
  is	
  false.	
  	
  The	
  result	
  of	
  given	
  conditional	
  expression	
  
must	
  be	
  either	
  true	
  or	
  false.	
  
                                                                                                                	
  
	
  
Different	
  variations	
  of	
  this	
  conditional	
  statement	
  are	
  –	
  	
  
       •   if	
  statement	
  
           if	
  statement	
  evaluates	
  the	
  given	
  test	
  expression.	
  If	
  it	
  is	
  evaluated	
  
           to	
  true,	
  then	
  statements	
  inside	
  the	
  if	
  block	
  will	
  be	
  executed.	
  
           Otherwise,	
  statements	
  inside	
  if	
  block	
  is	
  skipped.	
  
           	
  
           Syntax	
  
           	
  
                      if(test_expression)	
  {	
  
                      	
      //	
  Statements	
  to	
  be	
  executed	
  only	
  when	
  
                      test_expression	
  is	
  true	
  
                      }	
  
           	
  
           Example	
  Code	
  
           	
  
                      public	
  static	
  void	
  main(String	
  args[])	
  {	
  
                      	
      	
         int	
  n	
  =	
  5;	
  
	
  
	
  
                     	
       	
         if(	
  n	
  <	
  10	
  )	
  {	
  
                     	
       	
         	
               System.out.print("Inside	
  if	
  statement");	
  
                     	
       	
         }	
  
                     	
       	
         System.out.println("Outside	
  if	
  statement");	
  
                     }	
  
                     	
  
                     Output	
  
                     Inside	
  if	
  statement	
  
                     Outside	
  if	
  statement	
  
           	
  
           So	
  if	
  the	
  condition	
  given	
  inside	
  if	
  parenthesis	
  is	
  true,	
  then	
  
           statements	
  inside	
  if	
  block	
  are	
  executed	
  first	
  and	
  then	
  rest	
  of	
  the	
  
           code.	
  And	
  if	
  the	
  condition	
  evaluates	
  to	
  false,	
  then	
  statements	
  
           inside	
  if	
  block	
  will	
  be	
  skipped.	
  	
  
       •   If	
  –	
  else	
  statement	
  
           if	
  statement	
  evaluates	
  the	
  given	
  test	
  expression.	
  If	
  it	
  is	
  evaluated	
  
           to	
  true,	
  then	
  statements	
  inside	
  the	
  if	
  block	
  will	
  be	
  executed.	
  
           Otherwise,	
  statements	
  inside	
  else	
  	
  block	
  will	
  be	
  executed.	
  After	
  
           that,	
  rest	
  of	
  the	
  statements	
  will	
  be	
  executed	
  normally.	
  
           	
  
           Syntax	
  
           	
  
                         if(test_expression)	
  {	
  
                         	
            //	
  Statements	
  to	
  be	
  executed	
  when	
  test_expression	
  
                         is	
  true	
  
                         	
            	
  
                         }	
  
                         else	
  {	
  
                         	
            //	
  Statements	
  to	
  be	
  executed	
  when	
  test_expression	
  
                         is	
  false	
  
                         }	
  
           	
  
           Example	
  Code:	
  
           	
  
                         public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
                         	
            	
        int	
  a	
  =	
  10,	
  b	
  =	
  20;	
  
                         	
            	
        if(a	
  >	
  b)	
  {	
  
                         	
            	
        	
            System.out.println("a	
  is	
  bigger");	
  
                         	
            	
        }	
  
                         	
            	
        else	
  {	
  
                         	
            	
        	
            System.out.println("b	
  is	
  bigger");	
  
                         	
            	
        }	
  
	
  
	
  
                      }	
  
            	
  
                      Output	
  
                      b	
  is	
  bigger	
  
       •   if	
  –	
  else	
  –	
  if	
  
           Using	
  this	
  we	
  can	
  execute	
  statements	
  based	
  on	
  multiple	
  
           conditions.	
  	
  
           	
  
           Syntax	
  
           	
  
                         if(test_expression_1)	
  {	
  
                         	
               //	
  Statements	
  to	
  be	
  executed	
  only	
  when	
  
                         test_expression_1	
  is	
  true	
  
                         }	
  
                         else	
  if(test_expression_2)	
  {	
  
                         	
               //	
  Statements	
  to	
  be	
  executed	
  only	
  when	
  
                         test_expression_1	
  is	
  false	
  and	
  test_expression_2	
  is	
  true	
  
                         }	
  
                         else	
  if(test_expression_2)	
  {	
  
                         	
               //	
  Statements	
  to	
  be	
  executed	
  only	
  when	
  
                         test_expression_1	
  &	
  test_expression_2	
  are	
  false	
  and	
  
                         test_expression_3	
  is	
  true	
  
                         }	
  
                         ....	
  
                         ....	
  
                         else	
  {	
  
                         	
               //	
  Statements	
  to	
  be	
  executed	
  only	
  when	
  all	
  the	
  above	
  
                         test	
  expressions	
  are	
  false	
  
                         }	
  
           	
  
           Out	
  of	
  all	
  block	
  of	
  statements,	
  only	
  one	
  will	
  be	
  executed	
  based	
  on	
  
           the	
  given	
  test	
  expression,	
  all	
  others	
  will	
  be	
  skipped.	
  As	
  soon	
  as	
  
           any	
  expression	
  evaluates	
  to	
  ttue,	
  that	
  block	
  of	
  statement	
  will	
  be	
  
           executed	
  and	
  rest	
  will	
  be	
  skipped.	
  If	
  none	
  of	
  the	
  expression	
  
           evaluates	
  to	
  true,	
  then	
  the	
  statements	
  inside	
  else	
  will	
  be	
  
           executed.	
  	
  
           	
  
           Example	
  Code:	
  
           	
  
                         public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
                         	
               	
        int	
  a	
  =	
  5;	
  
                         	
               	
        if(a	
  <	
  3)	
  {	
  
	
  
	
  
                     	
      	
            	
            System.out.println("one");	
  
                     	
      	
            }	
  
                     	
      	
            else	
  if(a	
  <	
  10)	
  {	
  
                     	
      	
            	
            System.out.println("two");	
  
                     	
      	
            }	
  
                     	
      	
            else	
  if(a	
  <	
  20)	
  {	
  
                     	
      	
            	
            System.out.println("three");	
  
                     	
      	
            }	
  
                     	
      	
            else	
  {	
  
                     	
      	
            	
            System.out.println("four");	
  
                     	
      	
            }	
  
                     }	
  
                     Output	
  :	
  	
  
                     two	
  
	
  
       •   Nested	
  if	
  statament	
  
           We	
  can	
  put	
  another	
  if	
  –	
  else	
  statament	
  inside	
  an	
  if.	
  
           	
  
           Syntax	
  
           	
  
                   if(test_expression_1)	
  {	
  
                   	
           //	
  Statements	
  to	
  be	
  executed	
  when	
  
                   test_expression_1	
  is	
  true	
  
                   	
           if(test_expression_2)	
  {	
  
                   	
           	
            //	
  Statements	
  to	
  be	
  executed	
  when	
  
                   test_expression_2	
  is	
  true	
  
                   	
           }	
  
                   	
           else	
  {	
  
                   	
           	
            //	
  Statements	
  to	
  be	
  executed	
  when	
  
                   test_expression_2	
  is	
  false	
  
                   	
           }	
  
                   }	
  
                   	
  
           Example	
  Code:	
  	
  
           	
  
                   public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
                   	
           	
            int	
  a	
  =	
  15;	
  
                   	
           	
            if(a	
  >	
  10)	
  {	
  
                   	
           	
            	
            if(a	
  >	
  20)	
  {	
  
                   	
           	
            	
            	
            System.out.println("Hello");	
  
                   	
           	
            	
            }	
  
                   	
           	
            	
            else	
  {	
  
	
  
	
  
                   	
     	
             	
      	
       System.out.println("Hi");	
  
                   	
     	
             	
      }	
  
                   	
     	
             }	
  
                   }	
  
                   	
  
                   Output	
  :	
  	
  
                   Hi	
  
return	
  keyword	
  
return	
  is	
  a	
  special	
  keyword,	
  when	
  encountered	
  ends	
  the	
  main.	
  That	
  
means,	
  no	
  statament	
  will	
  be	
  executed	
  after	
  return	
  statament.	
  	
  We’ll	
  
study	
  in	
  more	
  detail	
  when	
  we’ll	
  study	
  functions.	
  
	
  
Example	
  Code:	
  
	
  
          public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
          	
           	
        int	
  a	
  =	
  10;	
  
          	
           	
        if(a	
  >	
  5)	
  {	
  
          	
           	
        	
            System.out.println("Hello");	
  
          	
           	
        	
            return;	
  
          	
           	
        }	
  
          	
           	
        System.out.println("Hi");	
  
          }	
  
          	
  
          Output	
  :	
  	
  
          Hello	
  
while	
  loop	
  
Loop	
  statements	
  allows	
  us	
  to	
  execute	
  a	
  block	
  of	
  statamenets	
  several	
  
number	
  of	
  times	
  depending	
  on	
  certain	
  condition.	
  while	
  is	
  one	
  kind	
  of	
  
loop	
  that	
  we	
  can	
  use.	
  	
  
When	
  executing,	
  if	
  the	
  test_expression	
  result	
  is	
  true,	
  then	
  the	
  actions	
  
inside	
  the	
  loop	
  will	
  be	
  executed.	
  This	
  will	
  continue	
  as	
  long	
  as	
  the	
  
expression	
  result	
  is	
  true.	
  
	
  
Syntax	
  
	
  
         while(test_expression)	
  {	
  
         	
        //	
  Statements	
  to	
  be	
  executed	
  till	
  test_expression	
  is	
  true	
  
         }	
  
         	
  
	
  
	
  
                                                                                                                    	
  
	
  
	
  
Example	
  Code:	
  
	
  
             public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
             	
        	
        int	
  i	
  =	
  1;	
  
             	
        	
        while(i	
  <=	
  5)	
  {	
  
             	
        	
        	
               System.out.println(i);	
  
             	
        	
        	
               i++;	
  
             	
        	
        }	
  
             }	
  
             	
  
             Output	
  :	
  	
  
             1	
  
             2	
  
             3	
  
             4	
  
             5	
  
	
  
In	
  while	
  loop,	
  first	
  given	
  test	
  expression	
  will	
  be	
  checked.	
  If	
  that	
  evaluates	
  
to	
  be	
  true,	
  then	
  the	
  statements	
  inside	
  while	
  will	
  be	
  executed.	
  After	
  that,	
  
the	
  condition	
  will	
  be	
  checked	
  again	
  and	
  the	
  process	
  continues	
  till	
  the	
  
given	
  condition	
  becomes	
  false.	
  	
  
	
  
	
  
	
  
	
  
Patterns
Introduction
Patterns are a handy application of loops and will provide you with better clarity
and understanding of the implementation of loops.
Before printing any pattern, you must consider the following three things:
    ● The first step in printing any pattern is to figure out the number of rows that
       the pattern requires.
    ● Next, you should know how many columns are there in the ith row.
    ● Once, you have figured out the number of rows and columns, then focus on
       the pattern to print.
For eg. We want to print the following pattern for N rows: ( Pattern 1.1)
// For N=4:
****
****
****
****
Approach:
From the above pattern, we can observe:
    ➔ Number of Rows: The pattern has 4 rows. We have to print the pattern for N
       rows.
    ➔ Number of Columns: All the rows have 4 columns. Thus, in a pattern of N
       rows, all the rows will have N columns.
    ➔ What to print: We have to print *
                                         4 times in all the 4 rows. Thus, in a pattern
       of N rows, we will have to print *
                                          N times in all the rows.
1
Java Implementation for Patterns
We generally need two loops to print patterns. The outer loop iterates over the rows,
while the inner nested loop is responsible for traversing the columns. The algorithm to
print any pattern can be described as follows:
          ● Accept the number of rows or size of the pattern from a user using the
             .nextInt() function.
          ● Iterate the rows using the outer loop.
          ● Use the nested inner loop to handle the column contents. The internal loop
             iteration depends on the values of the outer loop.
          ● Print the required pattern contents using the print function.
          ● Add a new line after each row.
Step 1: Let us first use a loop to traverse the rows. This loop will start at the first
row and go on till the Nth row. Below is the implementation of this loop:
2
Printing a New Line: S
                       ince we need to print the pattern in multiple lines, we will
have to add a new line after each row. Thus for this purpose, we use an empty
print statement. The print function in Java, can be written as
System.out.println(). ‘ln’ after print indicates a new line.
Step 2: Now, we need another loop to traverse the row during each iteration and
print the pattern; this can be done as follows:
3
There are two popular types of patterns-related questions that are usually posed:
Square Patterns
Pattern 1.2
// N = 5
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
Approach:
From the above pattern w
                        e can observe:
    ➔ Number of Rows: The pattern has 5 rows. We have to print the pattern for N
        rows.
    ➔ Number of Columns: All the rows have 5 columns. Thus, in a pattern of N
        rows, all the rows will have N columns.
    ➔ What to print: All the entries in any row are the same as the corresponding
        row numbers. Thus in a pattern of N rows, all the entries of the i
                                                                          th
                                                                            row are i
                                                                                      
        (1st row has all 1’s, 2nd row has all 2’s, and so on).
Java Implementation:
4
public static void main(String[] args) {
      Scanner s = new Scanner(System.in);
      int N = s.nextInt(); // Take user input, N= Number of Rows
      int row = 1; // The loop starts with the 1st row
      while (row <= N) { // Loop will on for N rows
          int col = 1; // loop starts with the first column in the
                          //current row
          while (col <= N) { //Loop will on for N columns
               System.out.print(row); // printing (*) in each column
               col = col+1; //Increment the current column (Inner Loop)
          }
          row = row+1; // Increment the current row (Outer Loop)
          System.out.println(); // Add a new Line after each row
      }
}
Pattern 1.3
// N = 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
Approach:
From the above pattern w
                        e can observe:
    ➔ Number of Rows: The pattern has 5 rows. We have to print the pattern for N
       rows.
    ➔ Number of Columns: All the rows have 5 columns. Thus, in a pattern of N
       rows, all the rows will have N columns.
5
    ➔ What to print: All the entries in any row are the same as the corresponding
       column numbers. Thus in a pattern of N rows, all the entries of the ith
                                                                             
       column are i
                    (1st column has all 1’s, 2nd column has all 2’s, and so on).
Java Implementation:
Pattern 1.4
// N = 5
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
6
Approach:
From the above pattern w
                        e can observe:
     ➔ Number of Rows: The pattern has 5 rows. We have to print the pattern for N
        rows.
     ➔ Number of Columns: All the rows have 5 columns. Thus, in a pattern of N
        rows, all the rows will have N columns.
     ➔ What to print: All the entries in any row are N-columnNumber+1. Thus in a
        pattern of N rows, all the entries of the ith
                                                     column are N
                                                                   -i+1 (1st column has
        all 5’s (5-1+1), 2nd column has all 4’s (
                                                         5-2+1), and so on).
Java Implementation:
This way there can be several other square patterns and you can easily print them using
this approach- B
                y finding the number of Rows, Columns and What to print.
7
Pattern 1.5
// N = 5
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
Approach:
From the above pattern w
                        e can observe:
    ➔ Number of Rows: The pattern has 5 rows. We have to print the pattern for N
       rows.
    ➔ Number of Columns: All the rows have 5 columns. Thus, in a pattern of N
       rows, all the rows will have N columns.
    ➔ What to print: The first entry in the 1st row is 1, the first entry in the 2nd row
       is 2, and so on. Further, these values are incremented continuously by 1 in
       the remaining entries of any particular row. Thus in a pattern of N rows, the
       first entry of the i
                           th
                             row is i
                                       . The remaining entries in the i
                                                                         th
                                                                           row are
       i+1,i+2, and so on. I t can be observed that any entry in this pattern can be
       written as row+col-1.
8
               }
               row = row+1; // Increment the current row (Outer Loop)
               System.out.println(); // Add a new Line after each row
       }
}
Triangular Patterns
Pattern 1.6
// N = 5
1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
Approach:
From the above pattern w
                        e can observe:
    ➔ Number of Rows: The pattern has 5 rows. We have to print the pattern for N
        rows.
    ➔ Number of Columns: The number of columns in any row is the same as the
        corresponding row number.1st row has 1 column, 2nd row has 2 columns, and
        so on. Thus, in a pattern of N rows, the i
                                                  th
                                                    row will have i
                                                                     columns.
    ➔ What to print: All the entries in any row are the same as the corresponding
        row numbers. Thus in a pattern of N rows, all the entries of the i
                                                                          th
                                                                            row are i
                                                                                      
        (1st row has all 1’s, 2nd row has all 2’s, and so on).
9
Java Implementation:
Pattern 1.7
// N = 5
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
Approach:
From the above pattern w
                        e can observe:
     ➔ Number of Rows: The pattern has 5 rows. We have to print the pattern for N
        rows.
10
     ➔ Number of Columns: The number of columns in any row is the same as the
        corresponding row number.1st row has 1 column, 2nd row has 2 columns, and
        so on. Thus, in a pattern of N rows, the i
                                                  th
                                                    row will have i
                                                                     columns.
     ➔ What to print: All the entries in any row are the same as the corresponding
        column numbers. Thus in a pattern of N rows, all the entries of the ith
                                                                              
        column are i
                     (1st column has all 1’s, 2nd column has all 2’s, and so on).
Java Implementation:
Pattern 1.8
// N = 5
1
2 3
4 5 6
7 8 9 10
11
11 12 13 14 15
Approach:
From the above pattern w
                        e can observe:
     ➔ Number of Rows: The pattern has 5 rows. We have to print the pattern for N
        rows.
     ➔ Number of Columns: The number of columns in any row is the same as the
        corresponding row number.1st row has 1 column, 2nd row has 2 columns, and
        so on. Thus, in a pattern of N rows, the i
                                                  th
                                                    row will have i
                                                                     columns.
     ➔ What to print: The pattern starts with 1 and then each column entry is
        incremented by 1. Thus, we will initialize a variable temp=1. We will keep
        printing the value of temp in the successive columns and upon printing, we
        will increment the value of temp by 1.
Java Implementation:
12
       }
}
Character Patterns
Pattern 1.9
// N = 4
ABCD
ABCD
ABCD
ABCD
Approach:
From the above pattern w
                        e can observe:
     ➔ Number of Rows: The pattern has 4 rows. We have to print the pattern for N
        rows.
     ➔ Number of Columns: All the rows have 4 columns. Thus, in a pattern of N
        rows, all the rows will have N columns.
     ➔ What to print: The 1st column has all A’s, 2nd column has all B’s, and so on.
        The ASCII value of A is 65. In the 1st column, the character corresponds to the
        ASCII value 65 (
                         64+1). In the 2nd column, the character corresponds to the
        ASCII value 66 (
                         64+2). Thus, all the entries in the i
                                                                    th
                                                                      column are equal to the
        character corresponding to the A
                                        SCII value 6
                                                      4+i. The c
                                                                   har() function gives
        the character associated with the integral ASCII value within the parentheses.
Java Implementation:
13
            int col = 1; // loop starts with the first column in the
                             //current row
            while (col <= N) { //Loop will on for N columns
                 System.out.print((char)(64+col)); //print in each column
                 col = col+1; //Increment the current column (Inner Loop)
            }
            row = row+1; // Increment the current row (Outer Loop)
            System.out.println(); // Add a new Line after each row
       }
}
Pattern 1.10
// N = 4
ABCD
BCDE
CDEF
DEFG
Approach:
From the above pattern w
                        e can observe:
     ➔ Number of Rows: The pattern has 4 rows. We have to print the pattern for N
        rows.
     ➔ Number of Columns: All the rows have 4 columns. Thus, in a pattern of N
        rows, all the rows will have N columns.
     ➔ What to print: This pattern is very similar to P
                                                        attern 1.5. We can implement
        this using a similar code with a minor change. Instead of integers, we need
        capital letters of the same order. Instead of 1, we need A, instead of 2, we
        need B and so on. A
                           SCII value of A is 65. Thus if we add 64 to all the entries
        in Pattern 1.5 a
                         nd find their ASCII v
                                                alues, we will get our result. The c
                                                                                     har()
        function gives the character associated with the integral ASCII v
                                                                          alue within
        the parentheses.
14
Java Implementation:
Practice Problems
Here are a few similar patterns problems for your practice. All the patterns have been
drawn for N=4.
 A
 AB
 ABC
 ABCD
 12344321
 123**321
 12****21
15
1******1
ABCD
ABC
AB
A
4555
3455
2345
1234
1
11
202
3003
A
BB
CCC
DDDD
16
Patterns
Some Advanced Patterns
// N = 3
* * *
* *
*
Approach:
From the above pattern, we can observe:
    ➔ Number of Rows: The pattern has 3 rows. We have to print the pattern for N
       rows.
    ➔ Number of Columns: The number of columns in any row is equal to
       N-rowNumber+1.1st row has 3 columns (
                                                3-1+1), 2nd row has 2 columns
       (3-2+1), and so on. Thus, in a pattern of N rows, the i
                                                                   th
                                                                     row will have N
                                                                                     -i+1
       columns.
    ➔ What to print: All the entries in any row are "*".
Java Implementation:
1
                col = col+1; //Increment the current column (Inner Loop)
           }
           row = row+1; // Increment the current row (Outer Loop)
           System.out.println(); // Add a new Line after each row
      }
}
// N = 3
    *
  * *
* * *
Approach:
From the above pattern, we can observe:
    ➔ Number of Rows: The pattern has 3 rows. We have to print the pattern for N
       rows.
    ➔ Number of Columns: The number of columns in any row is equal to N
                                                                        .
    ➔ What to print: In the 1st row, while columnNumber <= 2(3-1), we print a "
                                                                                      "
       in every column. Beyond the 2nd column, we print a "
                                                             *". Similarly, in the 2nd
       row, we print a " " till c
                                   olumnNumber <=1(3-2) and beyond the 1st column,
       we print a "*". We can easily notice that if col <= N-rowNumber, we are
       printing a "
                   " (Space). And if c
                                        ol > N-rowNumber, we are printing a "
                                                                               *".
Java Implementation:
2
           int col = 1; // loop starts with the first column in the
                             //current row
           while (col <= N) { //loop will on for N rows
                if(col<=N-row)
                        System.out.print(“ ”); // printing “ ”
                else
                        System.out.print(“*”); // printing “*”
                col = col+1; //Increment the current column
           }
           row = row+1; // Increment the current row (Outer Loop)
           System.out.println(); // Add a new Line after each row
      }
}
// N = 4
   1
  121
 12321
1234321
Approach:
From the above pattern w
                        e can observe:
    ➔ Number of Rows: The pattern has 3 rows. We have to print the pattern for N
       rows.
    ➔ Number of Columns: Similar to Pattern 2.2, we first have N
                                                                 -rowNumber
       columns of spaces. Following this, we have 2
                                                    *rowNumber-1 c olumns of
       numbers.
    ➔ What to print: We can notice that if c
                                             ol <= N-rowNumber, we are printing a
       " " (Space). Further, the pattern has two parts. First is the increasing part
       and second is the decreasing part. For the increasing part, we will initialise a
3
     variable n
               um=1. In each row we will keep printing n
                                                           um till its value becomes
     equal to the rowNumber . We will increment num by 1 after printing it; ;this will
     account for the first part of the pattern. We have num = rowNumber at this
     stage. The decreasing part starts with rowNumber - 1. Hence, we will
     initialise num with rowNumber - 1. Now, for the decreasing part, we will
     again start printing num till num>=1. After printing n
                                                                um we will decrement it by
     1.
Java Implementation:
4
                             num=num-1;
                         }
                         row = row+1; // Increment the current row (Outer Loop)
                         System.out.println(); // Add a new Line after each row
             }
 }
Practice Problems
Here are a few similar patterns problems for your practice. All the patterns have been
drawn for N=4.
    *
   ***
  *****
 *******
    1
   121
  12321
 1234321
  12321
   121
    1
 1                 1
    2         2
        3 3 
            4
         3 3
     2         2
5
1   1
   *
  ***
 *****
*******
 *****
  ***
   *
6
	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                                                          	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                                             	
  
                  Java	
  Foundation	
  with	
  Data	
  Structures	
  
Lecture	
  4	
  	
  :	
  Loops,	
  Keywords,	
  Associativity	
  and	
  Precedence	
  
	
                          	
  
	
  
	
  
for	
  loop	
  
	
  
Loop	
   statements	
   allows	
   us	
   to	
   execute	
   a	
   block	
   of	
   statements	
   several	
   number	
   of	
  
times	
   depending	
   on	
   certain	
   condition.	
   for	
   loop	
   is	
   kind	
   of	
   loop	
   in	
   which	
   we	
   give	
  
initialization	
   statement,	
   test	
   expression	
   and	
   update	
   statement	
   can	
   be	
   written	
   in	
  
one	
  line.	
  	
  
	
  
Inside	
  for,	
  three	
  statements	
  are	
  written	
  –	
  	
  
a.	
   Initialization	
   –	
   used	
   to	
   initialize	
   your	
   loop	
   control	
   variables.	
   This	
   statement	
   is	
  
executed	
  first	
  and	
  only	
  once.	
  
b.	
   Test	
   condition	
   –	
   this	
   condition	
   is	
   checked	
   everytime	
   we	
   enter	
   the	
   loop.	
  
Statements	
   inside	
   the	
   loop	
   are	
   executed	
   till	
   this	
   condition	
   evaluates	
   to	
   true.	
   As	
  
soon	
  as	
  condition	
  evaluates	
  to	
  false,	
  loop	
  terminates	
  and	
  then	
  first	
  statement	
  after	
  
for	
  loop	
  will	
  be	
  executed	
  next.	
  
c.	
   Updation	
   –	
   this	
   statement	
   updates	
   the	
   loop	
   control	
   variable	
   after	
   every	
  
execution	
  of	
  statements	
  inside	
  loop.	
  After	
  updation,	
  again	
  test	
  conditon	
  is	
  checked.	
  
If	
  that	
  comes	
  true,	
  the	
  loop	
  executes	
  and	
  process	
  repeats.	
  And	
  if	
  condition	
  is	
  false,	
  
the	
  loop	
  terminates.	
  	
  
	
  
                                              for	
  (initializationStatement;	
  test_expression;	
  updateStatement)	
  {	
  
                                              	
                                      //	
  Statements	
  to	
  be	
  executed	
  till	
  test_expression	
  is	
  true	
   	
  
                                              }	
  
                                              	
  
                                              Example	
  Code	
  :	
  
                                                                                                                                    	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
	
                                            	
                                      	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  for(int	
  i	
  =	
  0;	
  i	
  <	
  3;	
  i++)	
  {	
  
	
                                            	
                                      	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.print("Inside	
  for	
  loop	
  :	
  ");	
  
	
                                            	
                                      	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println(i);	
  
	
                                            	
                                      	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
	
                                            	
                                      	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println("Done");	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
                                                                                      	
  
                                                                                      Output:	
  
                                                                                      Inside	
  for	
  Loop	
  :	
  0	
  
                                                                                      Inside	
  for	
  Loop	
  :	
  1	
  
                                                                                      Inside	
  for	
  Loop	
  :	
  2	
  
                                                                                      Done	
  
	
  
	
  
	
  
In	
  for	
  loop	
  its	
  not	
  compulsory	
  to	
  write	
  all	
  three	
  statements	
  i.e.	
  
initializationStatement,	
  test_expression	
  and	
  updateStatement.	
  We	
  can	
  skip	
  one	
  
or	
  more	
  of	
  them	
  (even	
  all	
  three)	
  
	
  
Above	
  code	
  can	
  be	
  written	
  as:	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
	
                                            	
                                           	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  int	
  i	
  =	
  1;	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  //initialization	
  is	
  done	
  outside	
  the	
  for	
  loop	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  for(;	
  i	
  <	
  =5;	
  i++)	
  {	
  
	
                                            	
                                           	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println(i);	
  
	
                                            	
                                           	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
	
  
                                              	
  
                                              OR	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
	
                                            	
                                           	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  int	
  i	
  =	
  1;	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  //initialization	
  is	
  done	
  outside	
  the	
  for	
  loop	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  for(;	
  i	
  <	
  =5;	
  )	
  {	
  
	
                                            	
                                           	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println(i);	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  i++;	
  	
  	
  	
  	
  	
  	
  	
  //	
  update	
  Statement	
  written	
  here	
  
	
                                            	
                                           	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
	
  
We	
  can	
  also	
  skip	
  the	
  test_expression.	
  See	
  the	
  example	
  below	
  :	
  
	
  
Variations	
  of	
  for	
  loop	
  
	
  
•   The	
  three	
  expressions	
  inside	
  for	
  loop	
  are	
  optional.	
  That	
  means,	
  they	
  can	
  be	
  
    omitted	
  as	
  per	
  requirement.	
  	
  
    	
  
    Example	
  code	
  1:	
  Initialization	
  part	
  removed	
  –	
  
    	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
    	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
    	
   	
                                                             	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  int	
  i	
  =	
  0;	
  
    	
   	
                                                             	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  for(	
  ;	
  i	
  <	
  3;	
  i++)	
  {	
  
    	
   	
                                                             	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println(i);	
  
    	
   	
                                                             	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
    	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
                                                                        	
  
                                                                        	
  
	
  
	
  
                                                 	
  
                                                 Output:	
  
                                                 0	
  
                                                 1	
  
                                                 2	
  
	
  
                              Example	
  code	
  2:	
  Updation	
  part	
  removed	
  
       	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
       	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
       	
   	
                                                             	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  for(int	
  i	
  =	
  0;	
  i	
  <	
  3;	
  )	
  {	
  
       	
   	
                                                             	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println(i);	
  
       	
   	
                                                             	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  i++;	
  
       	
   	
                                                             	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
       	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
       	
   	
  
                                                                           Output:	
  
                                                                           0	
  
                                                                           1	
  
                                                                           2	
  
	
  
                              Example	
  code	
  3:	
  Condition	
  expression	
  removed	
  ,	
  thus	
  making	
  our	
  loop	
  
                              infinite	
  –	
  
                              	
  
       	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
       	
   	
                                                             	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  for(int	
  i	
  =	
  0;	
  ;	
  i++)	
  {	
  
       	
   	
                                                             	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println(i);	
  
       	
   	
                                                             	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
       	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
                              	
  
                              Example	
  code	
  4:	
  
                              We	
  can	
  remove	
  all	
  the	
  three	
  expression,	
  thus	
  forming	
  an	
  infinite	
  loop-‐	
  
                              	
  
       	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
       	
   	
                                                             	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  for(	
  ;	
  ;	
  )	
  {	
  
       	
   	
                                                             	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.print("Inside	
  for	
  loop");	
  
       	
   	
                                                             	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
       	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
                              	
  
	
  
	
  
	
  
•   Multiple	
  statements	
  inside	
  for	
  loop	
  
                       	
  
                       We	
  can	
  initialize	
  multiple	
  variables,	
  have	
  multiple	
  conditions	
  and	
  multiple	
  
                       update	
  statements	
  inside	
  a	
  for	
  loop.	
  	
  We	
  can	
  separate	
  multiple	
  statements	
  
                       using	
  comma,	
  but	
  not	
  for	
  conditions.	
  They	
  need	
  to	
  be	
  combined	
  using	
  logical	
  
                       operators.	
  
                       	
  
                                              Example	
  code:	
  
                                              	
  
                       	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  for(int	
  i	
  =	
  0,	
  j	
  =	
  4;	
  i	
  <	
  5	
  &&	
  j	
  >=	
  0;	
  i++,	
  j-‐-‐)	
  {	
  
	
                                            	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println(i	
  +	
  "	
  "	
  +	
  j);	
  
	
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  	
  	
  
                                              	
  
                                                                     Output:	
  
                                                                     	
  
                                                                     	
  	
  0	
  4	
  
                                                                     	
  	
  1	
  3	
  
                                                                     	
  	
  2	
  2	
  
                                                                     	
  	
  3	
  1	
  
                                                                     	
  	
  4	
  0	
  
	
  
	
  
	
  
                   	
        	
      }	
  
                   }	
  
	
  
                   Output:	
  	
  
                   	
  
                   1	
  
                   2	
  
                   3	
  
                   4	
  
                   5	
  
                   	
  
                   	
  
       •   Inner	
  loop	
  break:	
  
	
  
When	
  there	
  are	
  two	
  more	
  loops	
  inside	
  one	
  another.	
  Break	
  from	
  innermost	
  loop	
  
will	
  just	
  exit	
  that	
  loop.	
  
	
  
Example	
  Code	
  1:	
  
                        	
  
                        public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
                                  for	
  (int	
  i=1;	
  i	
  <=3;	
  i++)	
  {	
  
	
        	
            	
        	
        System.out.println(i);	
  
                                            for	
  (int	
  j=1;	
  j<=	
  5;	
  j++)	
  
                                            {	
  	
  
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println(“in”);	
  
                                            	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  if(j==1)	
  
                                                                                        {	
  
                                  	
        	
                                          	
     break;	
  
                                                                                        }	
  
	
  	
    	
            	
        	
        	
  }	
  
                                  }	
  
                        }	
  
                        Output:	
  
                        1	
  
                        in…	
  
                        2	
  
                        in…	
  
                        3	
  
                        in…	
  
	
  
	
  
	
  
Example	
  Code	
  2:	
  
	
  
              public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
              	
          int	
  i=1;	
  
                          while	
  (i	
  <=3)	
  {	
  
	
       	
   	
          	
        System.out.println(i);	
  
	
       	
   	
          	
        int	
  j=1;	
  
                                    while	
  (j	
  <=	
  5)	
  
                                    {	
  
                                              System.out.println(“in”);	
  
                          	
        	
        if(j==1)	
  
                                              {	
  
                          	
        	
        	
          break;	
  
                                              }	
  
                                              j++;	
  
	
  	
   	
   	
          	
        	
  }	
  
	
       	
   	
          	
        i++;	
  
                          }	
  
              }	
  
	
  
	
  
              Output:	
  
              1	
  
              in…	
  
              2	
  
              in…	
  
              3	
  
              in…	
  
              	
  
              	
  
v  Continue	
  
	
  
       The	
  continue	
  keyword	
  can	
  be	
  used	
  in	
  any	
  of	
  the	
  loop	
  control	
  structures.	
  It	
  
       causes	
  the	
  loop	
  to	
  immediately	
  jump	
  to	
  the	
  next	
  iteration	
  of	
  the	
  loop.	
  
	
  
       •   Example:	
  (using	
  for	
  loop)	
  
	
  
                     public	
  static	
  void	
  main(String[]	
  args){	
  
	
  
	
  
          	
      	
                 for	
  (int	
  i=1;	
  i	
  <=	
  5;	
  i++)	
  {	
  
                                               if(i==3)	
  
                                               {	
  
                                               	
             continue;	
  
                                               }	
  
                                               System.out.println(i);	
  
          	
      	
                 }	
  
                  }	
  
	
  
                  Output:	
  	
  
                  1	
  
                  2	
  
                  4	
  
                  5	
  
                  	
  
       •   Example:	
  (using	
  while	
  loop)	
  
                  	
  
                  public	
  static	
  void	
  main(String[]	
  args){	
  
          	
      	
     int	
  i=1;	
  
          	
      	
     while	
  (i	
  <=	
  5)	
  {	
  
                                     if(i==3)	
  
                                     {	
  
                                     	
                        i++;	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
                                     	
  	
  	
  	
  //	
  if	
  increment	
  isn’t	
  done	
  here	
  then	
  loop	
  	
  will	
  run	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
                         infinite	
  time	
  for	
  i=3	
  
                                     	
                        continue;	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
                                     }	
  
                                     System.out.println(i);	
  
                                     i++;	
  
          	
      	
     }	
  
                  }	
  
	
  
                  Output:	
  	
  
                  1	
  
                  2	
  
                  4	
  
                  5	
  
	
  
	
  
Scope	
  of	
  variables	
  
	
  
Scope	
  of	
  variables	
  is	
  the	
  curly	
  brackets	
  {}	
  inside	
  which	
  they	
  are	
  defined.	
  	
  Outside	
  
which	
   they	
   aren’t	
   known	
   to	
   the	
   compiler.	
   Same	
   is	
   for	
   all	
   loops	
   and	
   conditional	
  
statement	
  (if).	
  
	
  
v  Scope	
  of	
  variable	
  -‐	
  for	
  loop	
  
                   	
  
                          for	
  (initializationStatement;	
  test_expression;	
  updateStatement)	
  {	
  
                          	
        //	
  Scope	
  of	
  variable	
  defined	
  in	
  loop	
  
                          }	
  
	
  
                          	
  Example:	
  
                          public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
                                  for	
  (int	
  i=0;	
  i<5;	
  i++)	
  {	
  	
  	
  	
  	
  	
  	
  
                                             int	
  j=2;	
  	
  	
  	
  	
  	
  	
  	
  	
  //	
  Scope	
  of	
  i	
  and	
  j	
  are	
  both	
  inside	
  the	
  loop	
  they	
  
                                             can’t	
  be	
  used	
  outside	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
	
  	
  	
  	
            }	
  
	
  
	
  
v  Scope	
  of	
  variable	
  for	
  while	
  loop	
  
	
  
                          while(test_expression)	
  {	
  
                          	
    //	
  Scope	
  of	
  variable	
  defined	
  in	
  loop	
  	
  
                          }	
  
	
  
	
  
                          public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
	
                        	
     int	
  i=0;	
  
	
                        	
     while(i<5)	
  
	
                        	
     {	
  
                                             int	
  j=2;	
  	
  	
  //	
  Scope	
  of	
  i	
  is	
  main	
  and	
  scope	
  of	
  j	
  is	
  only	
  the	
  loop	
  
	
                        	
     	
          i++;	
  
	
                        	
     }	
  
                          }	
  
	
  
                   v   Scope	
  of	
  variable	
  for	
  conditional	
  statements	
  
	
  
	
  
	
  
            if(test_expression)	
  {	
  
            	
     //	
  Scope	
  of	
  variable	
  defined	
  in	
  the	
  conditional	
  statement	
  	
  
            }	
  
	
  
            public	
  static	
  void	
  main(String[]	
  args)	
  {	
  
	
          	
             int	
  i=0;	
  
	
          	
             if	
  (i<5)	
  
	
          	
             {	
  
	
          	
             	
            int	
  j=5;	
             	
  	
  	
  //	
  Scope	
  of	
  j	
  is	
  only	
  in	
  this	
  block	
  
	
          	
             }	
  
       	
             	
           //	
  cout<<j;	
  	
  à	
  	
  This	
  statement	
  if	
  written	
  will	
  give	
  an	
  error	
  because	
  	
  
                                                              scope	
  of	
  j	
  is	
  inside	
  if	
  and	
  is	
  not	
  accessible	
  outside	
  if.	
  
            }	
  	
  
	
  
	
  
	
  
                                                      	
                         int	
  I=1,	
  J=1,	
  K=1,	
  L=1;	
  
                                                      }	
  
                                                      Output:	
  
                                                      1	
  1	
  2	
  0	
  
                                                      2	
  0	
  2	
  0	
  
                                                      	
  
Bitwise	
  Operators	
  
	
  
Bitwise	
  operators	
  are	
  used	
  to	
  perform	
  operations	
  at	
  bit	
  level.	
  Following	
  is	
  the	
  
summary	
  of	
  various	
  bitwise	
  operations:	
  
	
  
       Operator	
   Name	
   Example	
   Result	
                                                                                                                                                         Description	
  
       a	
  &	
  b	
                          and	
                             4	
  &	
  6	
                                4	
                            1	
  if	
  both	
  bits	
  are	
  1.	
  
       a	
  |	
  b	
                          or	
                              4	
  |	
  6	
                                6	
                            1	
  if	
  either	
  bit	
  is	
  1.	
  
       a	
  ^	
  b	
                          xor	
                             4	
  ^	
  6	
                                2	
                            1	
  if	
  both	
  bits	
  are	
  different.	
  
       ~a	
                                   not	
                             ~4	
                                         -‐5	
                         Inverts	
  the	
  bits.	
  (Unary	
  bitwise	
  compliment)	
  
                                              left	
                                                                                                        Shifts	
  the	
  bits	
  of	
  n	
  left	
  p	
  positions.	
  Zero	
  bits	
  
       n	
  <<	
  p	
                                                           3	
  <<	
  2	
                               12	
  
                                              shift	
                                                                                                       are	
  shifted	
  into	
  the	
  low-‐order	
  positions.	
  
                                                                                                                                                            Shifts	
  the	
  bits	
  of	
  n	
  right	
  p	
  positions.	
  If	
  n	
  is	
  a	
  
                                              right	
  
       n	
  >>	
  p	
                                                           5	
  >>	
  2	
                               1	
                            2's	
  complement	
  signed	
  number,	
  the	
  sign	
  bit	
  
                                              shift	
  
                                                                                                                                                            is	
  shifted	
  into	
  the	
  high-‐order	
  positions.	
  
                                              right	
                                                                                                       Shifts	
  the	
  bits	
  of	
  n	
  right	
  p	
  positions.	
  Zeros	
  
       n	
  >>>	
  p	
                                                          -‐4	
  >>>	
  28	
   15	
  
                                              shift	
                                                                                                       are	
  shifted	
  into	
  the	
  high-‐order	
  positions.	
  
	
  
Example	
  Code:	
  
	
  	
  	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  public	
  static	
  void	
  main(String	
  args[])	
  {	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  int	
  a	
  =	
  19;	
   //	
  19	
  =	
  10011	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  int	
  b	
  =	
  28;	
   //	
  28	
  =	
  11100	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  int	
  c	
  =	
  0;	
  
	
  
	
  
	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  c	
  =	
  a	
  &	
  b;	
  	
  	
  	
  	
  	
  	
  	
  //	
  16	
  =	
  10000	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println("a	
  &	
  b	
  =	
  "	
  +	
  c	
  );	
  
	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  c	
  =	
  a	
  |	
  b;	
  	
  	
  	
  	
  	
  	
  	
  //	
  31	
  =	
  11111	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println("a	
  |	
  b	
  =	
  "	
  +	
  c	
  );	
  
	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  c	
  =	
  a	
  ^	
  b;	
  	
  	
  	
  	
  	
  	
  	
  //	
  15	
  =	
  01111	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println("a	
  ^	
  b	
  =	
  "	
  +	
  c	
  );	
  
	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  c	
  =	
  ~a;	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  //	
  	
  -‐20	
  =	
  01100	
  	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println("~a	
  =	
  "	
  +	
  c	
  );	
  
	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  c	
  =	
  a	
  <<	
  2;	
  	
  	
  	
  	
  	
  	
  //	
  76	
  =	
  1001100	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println("a	
  <<	
  2	
  =	
  "	
  +	
  c	
  );	
  
	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  c	
  =	
  a	
  >>	
  2;	
  	
  	
  	
  	
  	
  	
  //	
  4	
  =	
  00100	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println("a	
  >>	
  2	
  	
  =	
  "	
  +	
  c	
  );	
  
	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  c	
  =	
  a	
  >>>	
  2;	
  	
  	
  	
  	
  	
  //	
  4	
  =	
  00100	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  System.out.println("a	
  >>>	
  2	
  =	
  "	
  +	
  c	
  );	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  }	
  
	
  
                                              Output	
  	
  
                                              a	
  &	
  b	
  =	
  16	
  
                                              a	
  |	
  b	
  =	
  31	
  
                                              a	
  ^	
  b	
  =	
  15	
  
                                              ~a	
  =	
  -‐20	
  
                                              a	
  <<	
  2	
  =	
  76	
  
                                              a	
  >>	
  2	
  =	
  4	
  
                                              a	
  >>>	
  2	
  =	
  4	
  
	
  
	
  
	
  
	
  
	
  
Following	
  is	
  the	
  Precedence	
  table	
  along	
  with	
  associativity	
  for	
  different	
  operators.	
  
	
  
       OPERATOR	
                DESCRIPTION	
                                                  ASSOCIATIVITY	
  
       ++	
  —	
                 Prefix	
  increment/decrement	
  
       +	
  –	
                  Unary	
  plus/minus	
  
       !	
  ~	
                  Logical	
  negation/bitwise	
  
       (type)	
                  complement	
  
       	
                        Cast	
  (convert	
  value	
  to	
  temporary	
  
       	
                        value	
  of	
  type)	
                                         right-‐to-‐left	
  
* / % Multiplication/division/modulus left-‐to-‐right
+ – Addition/subtraction left-‐to-‐right
	
  
	
  
       =	
                  Assignment	
  
       +=	
  	
  -‐=	
     Addition/subtraction	
  assignment	
  
       *=	
  	
  /=	
       Multiplication/division	
  assignment	
  
       %=	
  	
  &=	
       Modulus/bitwise	
  AND	
  assignment	
  
       ^=	
  	
  |=	
       Bitwise	
  exclusive/inclusive	
  OR	
  
       <<=	
  	
  >>=	
     assignment	
  
       	
                   Bitwise	
  shift	
  left/right	
  assignment	
     right-‐to-‐left	
  
	
  
	
  
	
  
                Java Foundation with Data Structures
             Lecture 5 : Functions, Variables and Scope
sFunctions
Defining Function
return_type function_name(parameter 1, parameter 2, ………) {
        statements;
}
     ● return type: A function may return a value. The return type of the
       function is the data type of the value that function returns. Sometimes
       function is not required to return any value and still performs the
       desired task. The return type of such functions is void.
Example:
Following is the example of a function that sum of two numbers. Here input to
the function are the numbers and output is their sum.
   1. public static int findSum( int a, int b
                                                       ){
   2.        int sum = a + b;
   3.        return  sum;
   4. }
Function Calling
Now that we have read about how to create a function lets see how to call the
function. To call the function you need to know the name of the function and
number of parameters required and their data types and to collect the
returned value by the function you need to know the return type of the
function.
Example
Output:
30
IMPORTANT POINTS:
   ● Number of parameter and their data type while calling must match with
     function signature. Consider the above example, while calling function
     findSum () the number of parameters are two and both the parameter
     are of integer type.
   ● It is okay not to collect the return value of function. For example, in the
     above code to find the sum of two numbers it is right to print the return
     value directly.
“System.out. print(c);”
   ● void return type functions: These are the functions that do not return
     any value to calling function. These functions are created and used to
     perform specific task just like the normal function except they do not
     return a value after function executes.
Following are some more examples of functions and their use to give you a
better idea.
Consider the following code where there is a function called findsum which
calculates and returns sum of two numbers.
For Example: In above code entry point of the function findSum () is at line
number 3. So when at line number 9 the function call occurs the control goes
to line number 3, then after the statements in the function findSum () are
executed the programme control comes back to line number 9.
Benefits of functions
   ● Modularisation
   ● Easy Debugging: It is easy to find and correct the error in function as
     compared to raw code without function where you must correct the
     error (if there is any) everywhere the specific task of the function is
     performed.
   ● Neat code: A code created with function is easy to read and dry run.
Output
5
In the above code the variable a declared inside the block after if statement is
a local variable for this block.
Lifetime of a Variable
The lifetime of a variable is the time period for which the declared variable has
a valid memory. Scope and lifetime of a variable are two different concepts,
scope of a variable is part of a programme for which this variable is accessible
whereas lifetime is duration for which this variable has a valid memory.
Loop variable
Loop variable is a variable which defines the loop index for each iteration.
Example
“for (int i = 0; i < 3; i++) { // variable i i s the loop variable
                  …….;
                  ……..;
                  statements;
          } “
For this example, variable i is the loop variable.
Pass by value:
When the parameters are passed to a function by pass by value method, then
the formal parameters are allocated to a new memory. These parameters have
same value as that of actual parameters. Since the formal parameters are
allocated to new memory any changes in these parameters will not reflect to
actual parameters.
Example:
   //Function to increase the parameters value
         1. public static v oid increase(int x, int y){
         2.         x++;
         3.         y = y + 2;
         4.         System.out. println(x + ":" + y); // x and y are formal
             parameters
         5. }
         6. public static v oid main(String[] args) {
         7.         int a = 10;
         8.         int b = 20;
         9.         increase(a,b);
         10.        System.out. println(a + ":" + b);  // a and b are actual
             parameters
         11.
         12.}
Output:
11: 22
10: 20
For the above code, changes in the values of x and y are not reflected to a and
b because x and y are formal parameters and are local to function increment so
any changes in their values here won’t affect variables a and b inside main.
Arrays
Introduction
In cases where there is a need to use several variables of the same type, for storing,
example, names or marks of ‘n’ students we use a data structure called arrays.
Arrays are basically collections of fixed numbers of elements of a single type. Using
arrays saves us from the time and effort required to declare each of the elements
of the array individually.
The length of an array is established when the array is created. After creation, its
length is fixed. For example: {1,2,3,4,5} is an array of integers.
To use an array in a program, you must declare a variable to refer to the array, and
you must specify the type (which once specified can’t be changed) of the array the
variable can reference. Here is the syntax for declaring an array variable −
Syntax
1
datatype [] arrayRefVar;                             // preferred way. OR
Example:
    int [] arr;        OR
    int arr [];
Creating Array
Declaring an array variable does not create an array (i.e. no space is reserved for
array). Here is the syntax for creating an array –
Example:
Combining declaration of array variable, creating array and and assigning the
reference of the array to the variable can be combined in one statement, as shown
below –
2
Array Indexes
In order to access different elements in an array -‐ all elements in the array are
indexed and indexing starts from 0. So if there are 5 elements in the array then the
first index will be 0 and last one will be 4. Similarly, if we have to store n values in an
array, then indexes will range from 0 to n - 1.
int [] arr= { 1 , 2 , 3 , 4 , 5 };
Initialising an Array
In Single Line
Syntax of creating and initializing an array in single line ... dataType [] arrayRefVar =
{value0, value1, ..., value};
Using Loop
3
           arr[i]=Scan.nextInt();
This is a special type of loop to access array elements of array. But this loop can be
used only to traverse an array, nothing can be changed in the array using this loop.
System.out.print(i+" ");
4
int arr [] = new int [10]; //here arr is a reference to the array and not the name
of the array.
In Above example, we create two reference variables arr and arr1. So now there are
also 2 objects in the garbage collection heap.
If you assign arr1 reference variable to arr, then no reference will be present for the
20 integer space created earlier, so this block of memory can now be freed by
Garbage Collector.
Garbage Collector
Live objects(We can think of them as blocks of memory for now) are tracked and
everything else designated garbage. As you’ll see, this fundamental
misunderstanding can lead to many performance problems.
5
    1. When an object is no longer used, the garbage collector reclaims the
       underlying memory and reuses it for future object allocation.
    2. This means there is no explicit deletion and no memory is given back to the
       operating system.
New objects are simply allocated at the end of the used heap
System.out.print(arr[i]+" ");
6
     }
Similarly, when we pass an array to the increment function shown below then the
reference(address) to the array is passed and not the array itself.
arr[i]++;
increment(arr);
7
                       System.out.print(arr[i]+" ");
Output:
23456
Here reference to the array was passed. Thus inside increment function arr refers
to the same array which was created in main. Hence the changes by increment
function are performed on the same array and they will reflect in main.
Now, lets change code for increment function a little and make arr point to another
array as shown in example given below.
arr=arr1;
arr[i]++;
8
           int [] arr= {1,2,3,4,5};
increment(arr);
System.out.print(arr[i]+" ");
Output:
12345
Here the changes done in main didn’t reflect. Although here as well the reference to
the array was passed, but in the first line inside the function we created another arr
of size 5 and made arr refer to that array(without affecting the array created in
main). Thus the changes this time won’t reflect.
class ArrayUse{
int[] A = numbers();
9
         public static int[] numbers(){
             int[] A = new int[3];
             A[0] = 2;
             A[1] = 3;
             A[2] = 4;
             return A;
10
BufferedReader Class
So far we have learnt to take input with the help of Scanner class. There is another way
to take input: using BufferedReader class. Let us dive deep into it.
BufferedReader:
It can be used to read input from a file as well as a keyboard. Since, throughout our
course, since our source of input will be keyboard only, therefore, we will limit our
discussions to taking input from keyboard.
Using this method, we read characters from the input stream. As we know, we have
three streams:
    1. System.in
    2. System.out
    3. System.err
In this method, we will use a class called InputStreamReader, which takes input byte by
byte and decodes it into a character stream. After reading data from the source
keyboard, the decoded data (character stream) is stored in a buffer (storage meant for
temporary usage) and then the object of class BufferedReader reads from this buffer.
You will get to know about this in detail in the lecture of Object Oriented Programming
(OOP). It is explained in the OOP lecture that non-static functions or methods cannot be
accessed by class. For accessing and invoking non-static methods, we use objects of
class.
Note:-
Process
The complete can be divided into two steps:
1. In first step, we have to read the input or access the input using
   InputStreamReader
2. Now, in the second step, we have to read data from the buffer. This can be done
   using the object of the BufferedReader class. BufferedReader can read only
   characters or string. It does so using the following two methods:
      a. read(): reads only single character
      b. readLine(): reads multiple character or a string
We will static function parseInt for type casting character into integers and similarly,
parseFloat for floating point values.
Examples:
int a = Integer.parseInt(br.readLine());
float b = Float.parseFloat(br.readLine());
String str = br.readLine();
Before getting our hands dirty in a more complex input format, we have to discuss split
function. This function splits the given string on a certain delimiter. For example, if the
delimiter is space, then it will divide the string into smaller substrings, which are
separated by space. It will return an array of those substrings.
Example:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
Example Input:
11 12 13 14
Example Output:
11 12 13 14
More Examples
Let us suppose that we have to read input with the following input format:
“The first line contains an Integer 't' which denotes the number of test cases or queries
to be run. Then the test cases follow.
First line of each test case or query contains an integer 'N' representing the size of the
array/list.
Second line contains 'N' single space separated integers representing the elements in
the array/list.”
One Example of this input format is:
2
5
93620
4
2312
              if (size == 0) {
                    return input;
              }
              String[] strNums;
              strNums = br.readLine().split("\\s");
              return input;
       }
           System.out.println();
     }
while (t > 0) {
                 t -= 1;
           }
     }
}
Searching And Sorting
Searching
Searching means to find out whether a particular element is present in a given sequence or
not. There are commonly two types of searching techniques:
Binary Search
Binary Search is a searching algorithm for finding an element's position in a sorted array. In
a nutshell, this search algorithm takes advantage of a collection of elements being already
sorted by ignoring half of the elements after just one comparison.
Prerequisite: Binary search has one pre-requisite; unlike the linear search where elements
could be any order, the array in binary search must be sorted,
1
Example Run
2
Java Code
 // Function to implement Binary Search Algorithm
 public static int binarySearch(int arr[], int n, int x) {
       int start = 0, end = n - 1;
      // Repeat until the pointers start and end meet each other
       while(start <= end) {
             int mid = (start + end) / 2; // Middle Index
             if(arr[mid] == x) { // element found
                   return mid;
             }
             else if(x < arr[mid]) {    // x is on the left side
                   end = mid - 1;
             }
             else {                  // x is on the right side
                   start = mid + 1;
             }
       }
int x = 4;
3
Advantages of Binary search:
Sorting
Sorting is a permutation of a list of elements such that the elements are either i n increasing
(ascending) order or decreasing (descending) order.
There are many different sorting techniques. The major difference is the amount of space
and t ime they consume while being performed in the program.
    ●   Selection sort
    ●   Bubble sort
    ●   Insertion sort
Selection Sort
Selection sort is an algorithm that selects the smallest element from an unsorted list in
each iteration and places that element at the beginning of the unsorted list. The detailed
algorithm is given below.
4
    ●   Set the first element as m
                                  inimum.
    ●   Compare minimum with the second element. If the second element is smaller than
        minimum, assign the second element as minimum.
    ●   Compare minimum with the third element. Again, if the third element is smaller, then
        assign minimum to the third element otherwise do nothing. The process goes on until
        the last element.
    ●   For each iteration, indexing starts from the first unsorted element. These steps are
        repeated until all the elements are placed at their correct positions.
5
First Iteration
Second Iteration:
6
Third Iteration
Fourth Iteration
Java Code
public static void selectionSort(int input[], int n) {
     for(int i = 0; i < n-1; i++ ) {
          / / Find min element in the array
             int min = input[i], minIndex = i;
          for(int j = i+1; j < n; j++) {
                   // to sort in descending order, change < to > in this
                     // line select the minimum element in each loop
                 if(input[j] < min) {
                       min = input[j];
                       minIndex = j;
                  }
             }
           / / Swap
             int temp = input[i];
             input[i] = input[minIndex];
7
                input[minIndex] = temp;
          }
 }
          }
 }
 2 10 12 15 20                                            / sorted array
                                                        /
Bubble Sort
Bubble sort is an algorithm that compares the adjacent elements and swaps their positions
if they are not in the intended order. The order can be ascending or descending.
     ●   Starting from the first index, compare the first and the second elements. If the first
         element is greater than the second element, they are swapped.
     ●   Now, compare the second and third elements. Swap them if they are not in order.
     ●   The above process goes on until the last element.
     ●   The same process goes on for the remaining iterations. After each iteration, the
         largest element among the unsorted elements is placed at the end.
     ●   In each iteration, the comparison takes place up to the last unsorted element.
     ●   The array is sorted when all the unsorted elements are placed at their correct
         positions.
8
    First Iteration      Second Iteration
9
Java Code
 public static void bubbleSort(int array[], int size) {
     // run loops two times: one for walking through the array
       // and the other for comparison
      for (int step = 0; step < size - 1; ++step) {
         for (int i = 0; i < size - step - 1; ++i) {
 // driver code
 public static void main(String[] args) {
   int input[] = {-2, 45, 0, 11, -9};
      bubbleSort(input, 6);
      for(int i = 0; i < 6; i++) {
            System.out.print(input[i] + “ ”);
      }
 }
10
Insertion Sort
     ●   Insertion sort works similarly as we sort cards in our hand in a card game.
     ●   We assume that the first card is already sorted
     ●   Then, we select an unsorted card.
     ●   If the unsorted card is greater than the card in hand, it is placed on the right
         otherwise, to the left.
     ●   In the same way, other unsorted cards are taken and put in the right place. A similar
         approach is used by insertion sort.
     ●   Insertion sort is a sorting algorithm that places an unsorted element at its suitable
         place in each iteration
Algorithm
     ●   The first element in the array is assumed to be sorted. Take the second element and
         store it separately in key.
     ●   Compare the key with the first element. If the first element is greater than key, then
         key is placed in front of the first element.
     ●   If the first element is greater than key, then key is placed in front of the first
         element.
     ●   Now, the first two elements are sorted.
     ●   Take the third element and compare it with the elements on the left of it. Placed it
         just behind the element smaller than it. If there is no element smaller than it, then
         place it at the beginning of the array.
     ●   Similarly, place every unsorted element at its correct position.
11
The various iterations are depicted below:
12
Java Code
 public static void insertionSort(int array[], int size) {
    int key, j;
     for(int i = 1; i<size; i++) {
            key = array[i];                 //take value
            j = i;
          // Compare key with each element on the left of it until an
            // element smaller than it is found
           while(j > 0 && array[j-1]>key) {
               array[j] = array[j-1];
               j--;
            }
            array[j] = key;                   //insert in right place
      }
 }
 // driver code
 public static void main(String[] args) {
   int input[] = {9, 5, 1, 4, 3};
      insertionSort(input, 6);
      for(int i = 0; i < 6; i++) {
            System.out.print(input[i] + “ ”);
      }
 }
Now, practice different questions to get more familiar with the concepts. In the advanced
course, you will study more types of sorting techniques.
In this problem, you are given 2 sorted arrays, you need to return a new array including all
the elements of both given arrays in a sorted manner.
13
Algorithm
     1. Create an array arr3[] of size n1 + n2.
     2. Simultaneously traverse arr1[] and arr2[].
          ●   Pick a smaller of current elements in arr1[] and arr2[], copy this smaller
              element to the next position in arr3[] and move ahead in arr3[] as well as in the
              array whose element is picked.
          ● Keep reiterating the above step, till either one of arr1[] and arr2[] are
              completely traversed.
     3. Copy the remaining elements of the array which is left untraversed if there exists
        into the arr3, as the above loop breaks if any of the pointers exceeds their
        respective size.
Java Code
public static void mergeArrays(int arr1[], int[] arr2) {
   int n1 = arr1.length;
    int n2 = arr2.length;
      return arr3;
}
14
15
Strings
    ●   Strings in Java
    ●   String Objects
    ●   StringBuilder and StringBuffer
    ●   Important Functions of Java
Strings in Java
Strings, which are widely used in Java programming, are a sequence of characters.
In the Java programming language, strings are objects(we study about objects in
detail in OOPS lecture). The Java platform provides the String class to create and
manipulate strings. The most direct and easiest way to create a string is to write:
Note: Strings in Java are immutable, thus we cannot modify its value. If we want to
create a mutable string we can use StringBuffer and StringBuilder classes.
directly assigning a string literal to a String reference -‐ just like a primitive, or
1
via the "new" operator and constructor, similar to any other classes(like arrays and
scanner). However, this is not commonly-‐used and is not recommended.
For example,
In the first statement, str1 is declared as a String reference and initialized with a
string literal "Java is Amazing". In the second statement, str2 is declared as        a
String reference and initialized via the new operator to contain "Java is Cool".
String literals are stored in a common pool called String pool. This facilitates
sharing of storage for strings with the same contents to conserve storage. String
objects allocated via new operator are stored in the heap memory(all non
primitives created via new operator are stored in heap memory), and there is no
sharing of storage for the same contents.
For example,
2
    String s1 = "Hello";          // String literal
Java has provided a special mechanism for keeping the String literals -‐ in a
so-‐called string common pool. If two string literals have the same contents,
they will share the same storage inside the common pool. This approach is adopted
to conserve   storage for   frequently-‐used   strings.   On   the   other hand,
String objects created via the new operator and constructor are kept in the heap
memory. Each String object in the heap has its own storage just like any other
object. There is no sharing of storage in heap even if two String objects
have the same contents.
You can use the method equals() of the String class to compare the contents of two
Strings. You can use the relational equality operator '==' to compare the references
3
(or pointers) of two objects. Study the following codes for s1 and s2 defined in code
above:
2. String is Immutable
Since string literals with the same contents share storage in the common pool,
Java's String is designed to be immutable. That is, once a String is constructed, its
contents cannot be modified. Otherwise, the other String references sharing the
same storage location will be affected by the change, which can be unpredictable
and therefore is undesirable. Methods such as toUpperCase() might appear to
modify the contents of a String object. In fact, a completely new String object is
created and returned to the caller. The original String object will be deallocated,
once there are no more references, and subsequently garbage-‐collected.
Because String is immutable, it is not efficient to use String if you need to modify
your string frequently (that would create many new Strings occupying new storage
areas).
4
For example,
// inefficient code
str = str + i;
As explained earlier, Strings are immutable because String literals with the same
content share the same storage in the string common pool. Modifying the content
of one String directly may cause adverse side-‐effects to other Strings sharing the
same storage.
JDK provides two classes to support mutable strings: StringBuffer and StringBuilder
(in core package java.lang) . A StringBuffer or StringBuilder object is just like any
ordinary object, which are stored in the heap and not shared,and therefore, can
be modified without causing adverse side-‐effect to other objects.
The StringBuilder class was introduced in JDK 1.5. It is the same as the StringBuffer
class, except that StringBuilder is not synchronized for multi-‐thread
operations(you can read more about multi threading). However, for a
single-‐thread program, StringBuilder, without the synchronization overhead, is
more efficient.
5
Important Java Methods
String class provides an inbuilt method to get the index of a character in Java String.
For example:
Similar to the above question, given the index, how do I know the character at that
location? Simple one again!! Use the “charAt” method and provide the index whose
character you need to find.
6
 String str1 = "test string";
 System.out.println("char at index 3 : " + str.charAt());
 // output – ‘t’
Use “compareToIgnoreCase” in case you don’t want the result to be case sensitive.
The result will have the value 0 if the argument string is equal to this string; a value
less than 0 if this string is lexicographically less than the string argument; and a
value greater than 0 if this string is lexicographically greater than the string
argument.
Use the method “contains” to check if a string contains another string and specify the
characters you need to check.
Returns true if and only if this string contains the specified sequence of char values.
7
6. String "endsWith" Method
This method is used to find whether a string ends with a particular prefix or not.
Returns true if the character sequence represented by the argument is a suffix of the
character sequence represented by this object.
Java String Replace, replaceAll and replaceFirst methods. You can specify the part of the
String you want to replace and the replacement String in the arguments.
Use the “toLowercase()” or “ToUpperCase()” methods against the Strings that need to be
converted.
8
System.out.println("Convert to UpperCase: " + str.toUpperCase());
2      String substring(int beginIndex, int      returns substring for given begin index
       endIndex)                                 and end index
8      String[] split(String regex, int limit)   returns splitted string matching regex
                                                 and limit
10     int indexOf(int ch, int fromIndex)        returns specified char value index
                                                 starting with given index
9
11         int indexOf(String substring)          Returns specified substring index
     1. Strings are not NULL terminated in Java: Unlike C and C++, String in Java
        doesn't terminate with null character. Instead String is an Object in Java and
        backed by a character array. You can get the character array used to
        represent String in Java by calling toCharArray() method of java.lang.String
        class of JDK.
     2. Internally, String is stored as a character array only.
     3. String is a Immutable and Final class, that is, once created the value cannot
        be altered. Thus String objects are called immutable.
     4. The Java Virtual Machine(JVM) creates a memory location especially for
        Strings called String Constant Pool. That’s why String can be initialized
        without the ‘new’ keyword.
10
Object-Oriented Programming (OOPS-1)
Introduction to OOPS
Object-oriented programming System(OOPs) is a programming paradigm based
on the concept of “ objects” and “classes” that contain data and methods. The
primary purpose of OOP is to increase the flexibility and maintainability of
programs. It is used to structure a software program into simple, reusable pieces of
code b
      lueprints (called c lasses) which are used to create individual instances of
objects.
What is an Object?
The object is an entity that has a state and a behavior associated with it. It may be
any real-world object like the mouse, keyboard, chair, table, pen, etc.
Objects have states and behaviors. Arrays are objects. You've been using objects all
along and may not even realize it. Apart from primitive data types, objects are all
around in java.
What is a Class?
A class is a b
              lueprint that defines the variables and the methods (Characteristics)
common to all objects of a certain kind.
Example: If C
              ar is a class, then M
                                     aruti 800 is an object of the Car class. All cars share
similar features like 4 wheels, 1 steering wheel, windows, breaks etc. Maruti 800 (The C
                                                                                        ar
object) has all these features.
1
Classes vs Objects (Or Instances)
Classes are used to create user-defined data structures. Classes define functions
called m
        ethods, which identify the behaviors and actions that an object created
from the class can perform with its data.
In this module, you’ll create a Car class that stores some information about the
characteristics and behaviors that an individual C
                                                  ar c an have.
A class is a blueprint for how something should be defined. It doesn’t contain any
data. The C
           ar class specifies that a name and a top-speed are necessary for
defining a C
            ar, but it doesn’t contain the name or top-speed of any specific Car.
While the class is the blueprint, an instance is an object that is built from a class and
contains real data. An instance of the Car class is not a blueprint anymore. It’s an
actual car with a name, like Creta, and with a t op speed of 200 Km/Hr.
Put another way, a class is like a form or questionnaire. An instance is like a form
that has been filled out with information. Just like many people can fill out the same
form with their unique information, many instances can be created from a single
class.
class Car{
2
Note: J ava class names are written in CapitalizedWords notation by convention. For
example, a class for a specific model of Car like the Bugatti Veyron would be
written as BugattiVeyron. The first letter is capitalized. This is just a good
programming practice.
The Car c lass isn’t very interesting right now, so let’s spruce it up a bit by defining
some properties that all Car objects should have. There are several properties that
we can choose from, including c
                               olor, brand, and t op-speed. To keep things simple,
we’ll just use c
                olor and top-speed.
Constructor
    ● Constructors are generally used for instantiating an object.
    ● The task of a constructor is to initialize(assign values) to the data members of
       the class when an object of the class is created.
    ● In Java, constructor for a class must be of the same name as of class.
    ● In Java, constructors don't have a return type.
Types of constructors
    ● Default Constructor: The default constructor is a simple constructor that
       doesn’t accept any arguments.
    ● Parameterized Constructor: A constructor with parameters is known as a
       parameterized constructor. The parameterized constructor takes its
       arguments provided by the programmer.
3
Class Attributes or Data Members
Class attributes are attributes that may or may not have the same value for all class
instances. You can define a class attribute by assigning a value to a variable name
outside of constructor.
For example, t he following Car class has a class attribute called n
                                                                       ame and
topSpeed with the value "
                          Black":
 class Car{
     String name;
     int topSpeed;
     ● Class attributes are defined directly beneath the first line of the class name.
     ● When an instance of the class is created, the class attributes are
        automatically created.
The t
     his Parameter
     ● The this parameter is a reference to the current instance of the class and is
        used to access variables that belong to the class.
     ● We can use this every time but the main use of t
                                                         his comes in picture when
        the attributes and data members share the same name.
class Car{
4
       String name;
       int topSpeed;
In the body of constructor, two statements are using the self variable:
     1. this.name = name assigns the value of the n
                                                    ame parameter to name attribute.
     2. this.topSpeed= topSpeed assigns the value of the t
                                                           opSpeed parameter to
        topSpeed attribute.
All C
     ar objects have a n
                          ame and a topSpeed, but the values for the n
                                                                          ame and
topSpeed attributes will vary depending on the C
                                                 ar instance. Different objects of
the Car class will have different names and top speeds.
5
The new C
         ar instance is located at a different memory address. That’s because it’s
an entirely new instance and is completely different from the first Car object that
you instantiated.
Even though c
             1 and c
                      2 are both instances of the C
                                                     ar class, they represent two
distinct objects in memory. So they are not equal.
 System.out.println(c1.name);
 System.out.println(c2.topSpeed);
One of the biggest advantages of using classes to organize data is that instances
are guaranteed to have the attributes you expect. The values of these attributes
can b
      e changed dynamically:
 c1.topSpeed= 250
 c2.name = "Jeep"
In this example, you change the topSpeed attribute of the c1 object to 2
                                                                            50. Then
you change the name attribute of the c2 object to "
                                                       Jeep".
Note:
    ● The key takeaway here is such custom objects are m
                                                        utable by default i.e.
        their states can be modified.
6
Access Modifiers
     1. Private: The access level of a private modifier is only within the class. It
        cannot be accessed from outside the class.
     2. Default: The access level of a default modifier is only within the package. It
        cannot be accessed from outside the package. If you do not specify any
        access level, it will be the default.
     3. Protected: The access level of a protected modifier is within the package and
        outside the package through child class. If you do not make the child class, it
        cannot be accessed from outside the package.
     4. Public: The access level of a public modifier is everywhere. It can be accessed
        from within the class, outside the class, within the package and outside the
        package
Final Keyword
If you make any variable final, you cannot change the value of the final variable (It
will be constant).
 class Pen{
     final int price = 15;
 }
7
There is a final variable price, we are going to change the value of this variable, but
it can't be changed because the final variable once assigned a value can never be
changed. Therefore this will give a compile time error.
Static Keyword
The static variable gets memory only once in the class area at the time of class
loading.
The static keyword in J ava is used for memory management mainly. We can apply
static keyword with variables, methods, blocks and nested classes. The static
keyword belongs to the class rather than an instance of the class.
class Car{
    static int year;
    String company_name;
class NewCar{
    public static void main (String[] args) {
         Car c=new Car();
         Car.year=2018;
         c.company_name="KIA";
         Car d=new Car();
         System.out.print(d.year);
Now in this code, when we look carefully, even when the new instance of Car is
created, the year is defined by the first instance of the Car and it tends to remain
8
the same for all instances of the object. But here’s the catch, we can change the
value of this static variable from any instance. Here the output will be 2018 for
every instance as long as it is not changed.
Static Functions
If you apply a static keyword with any method, it is known as static method.
● A static method belongs to the class rather than the object of a class.
     ● A static method can be invoked without the need for creating an instance of
        a class.
     ● A static method can access static data members and can change the value of
        it.
 class Test{
     static int a = 10;
     static int b;
     static void fun(){
          b = a * 4;
     }
 }
 class NewCar{
     public static void main(String[] args) {
        Test t=new Test();
        t.fun();
        System.out.print(t.a + t.b);
      }
9
Object-Oriented Programming (OOPS-2)
    ●   Components of OOPs.
    ●   Access modifiers with inheritance and protected modifiers.
    ●   All about exception handling.
Encapsulation
Encapsulation is defined as the wrapping up of data under a single unit. It is the
mechanism that binds together code and the data it manipulates. Another way to
think about encapsulation is, it is a protective shield that prevents the data from
being accessed by the code outside this shield.
1
       ● Encapsulation can be achieved by: Declaring all the variables in the class
          as private and writing public methods in the class to set and get the
          values of variables.
Inheritance
    ● Inheritance is a powerful feature in Object-Oriented Programming.
    ● Inheritance can be defined as the process where one class acquires the
       properties (methods and fields) of another. With the use of inheritance, the
       information is made manageable in a hierarchical order.
    ● The class which inherits the properties of the other is known as subclass
       (derived class or child class) and the class whose properties are inherited is
       known as superclass (base class, parent class).
Super Keyword:
Let us take a real-life example to understand inheritance. Let’s assume that Human
is a class that has properties such as height, weight, age, etc and functionalities (or
methods) such as eating(), sleeping(), dreaming(), working(), etc.
2
Now we want to create Male and Female classes. Both males and females are
humans and they share some common properties (like height, weight, age, etc)
and behaviors (or functionalities like eating(), sleeping(), etc), so they can inherit
these properties and functionalities from the Human class. Both males and
females also have some characteristics specific to them (like men have short hair
and females have long hair). Such properties can be added to the Male and Female
classes separately.
This approach makes us write less code as both the classes inherited several
properties and functions from the superclass, thus we didn’t have to re-write them.
Also, this makes it easier to read the code.
To inherit properties of the parent class, extends keyword is used followed by the
name of the parent class.
A polygon is a closed figure with 3 or more sides. Say, we have a class called
Polygon defined as follows.
 class Polygon{
     int n;
     int[] sides;
3
         public Polygon(int no_of_sides){ //Constructor
             this.n = no_of_sides;
             this.sides = new int[no_of_sides];
         }
This class has data attributes to store the number of sides n and magnitude of
each side as a list called sides.
The inputSides() method takes in the magnitude of each side and dispSides()
displays these side lengths.
Now, a triangle is a polygon with 3 sides. So, we can create a class called Triangle
which inherits from Polygon. In other words, we can say that every triangle is a
polygon. This makes all the attributes of the Polygon class available to the Triangle
class.
Constructor in Subclass
The constructor of the subclass must call the constructor of the superclass using
super keyword:
4
super.Polygon(<Parameter1>,<Parameter2>,...)
Note: The parameters being passed in this call must be the same as the
parameters being passed in the superclass’ constructor/ function, otherwise it will
throw an error.
     void findArea(){
         int a = super.sides[0];
         int b = super.sides[1];
         int c = super.sides[2];
         // calculate the semi-perimeter
         int s = (a + b + c) / 2;
         int area = Math.sqrt(s*(s-a)*(s-b)*(s-c));
         print('The area of the triangle is ' + area);
     }
}
However, the class Triangle has a new method findArea() to find and print the
area of the triangle. This method is only specific to the Triangle class and not
Polygon class.
5
Access Modifiers
Various object-oriented languages like C++, Java, Python control access
modifications which are used to restrict access to the variables and methods of the
class. There are four types of access modifiers available in java, which are Public,
Private, and Protected in a class, then there is a default case (we don't write any
keyword in this case), which lies somewhere in between public and private.
Public Modifier
      ● The public access modifier has the widest scope among all other access
          modifiers.
      ● Classes, methods, or data members that are declared as public are
          accessible from everywhere in the program. There is no restriction on the
          scope of public data members.
// Package 1
public class Student{
    public String name; // public member
    public int age; // public member
      // constructor
     public void Student(String name, int age){
         this.name = name;
         this.age = age;
     }
}
---------------------------------------------------------------------
// Package 2
6
class Test{
    public static void main(String[] args) {
        Student obj = Student("Boy", 15)
        System.out.println(obj.age); //calling public member of class
        System.out.println(obj.name); //calling public member
    }
}
10
Boy
We will be able to access both name and age of the object from outside the class
and package as they are public. However, this is not a good practice due to security
concerns.
Private Modifier
The members of a class that are declared private are accessible within the class
only. A private access modifier is the most secure access modifier. Data members
of a class are declared private by adding a private keyword before the data member
of that class. Consider the given example:
// Package 1
public class Student{
    private String name; // private member
    public int age; // public member
       // constructor
      public void Student(String name, int age){
          this.name = name;
          this.age = age;
      }
}
---------------------------------------------------------------------
7
 // Package 2
 class Test{
     public static void main(String[] args) {
         Student obj = Student("Boy", 15)
         System.out.println(obj.age); //calling public member of class
         System.out.println(obj.name); //calling private member
     }
 }
 10
 AttributeError: 'Student' object has no attribute 'name'
We will get an AttributeError when we try to access the name attribute. This is
because name is a private attribute and hence it cannot be accessed from outside
the class.
Note: We can even have public and private methods.
Protected Modifier
The members of a class that are declared protected are only accessible to a class
derived from it. Data members of a class are declared protected by adding a
protected keyword before the data member of that class.
The given example will help you get a better understanding:
8
// superclass
public class Student{
    protected String name; // private member
      // constructor
     public void Student(String name){
         this.name = name;
     }
}
This is the parent class Student with a protected instance attribute name. Now
consider a subclass of this class:
class Test{
    public static void main(String[] args) {
        Display obj = Student("Boy");   // creating objects of the
                                        // derived class
        obj.displayDetails();     // calling public member functions
                                  // of the class
        System.out.println(obj.name);    // trying to access
                                         // protected attribute
    }
}
9
This class Display inherits the Student class. The method displayDetails()
accesses the protected attribute _name. Further, we try to access it again outside
this class.
Output:
 Name: Boy
 AttributeError: 'Display' object has no attribute 'name'
You can observe that we were able to access the protected attribute _name from
inside the displayDetails() method in the subclass. However, we were not able
to access it outside the subclass and we got an AttributeError. This justifies the
definition of the protected modifier.
Polymorphism
Polymorphism is considered one of the important features of Object-Oriented
Programming. Polymorphism allows us to perform a single action in different ways.
In other words, polymorphism allows you to define one interface and have multiple
implementations. The word “poly” means many and “morphs” means forms, So it
means many forms.
10
      Function/ Method Overloading: When there are multiple functions with the
      same name but different parameters then these functions are said to be
      overloaded. Functions can be overloaded by change in number of arguments
      or/and change in type of arguments.
We know that the + operator is used extensively in Java programs. But, it does not
have a single usage. For integer data types, the + operator is used to perform
arithmetic addition operation.
int num1 = 1;
int num2 = 2;
System.out.println(num1+num2);
Similarly, for string data types, the + operator is used to perform concatenation.
Here, we can see that a single operator + has been used to carry out different
operations for distinct data types. This is one of the most simple occurrences of
polymorphism in Python.
11
class MultiplyFun {
    // Method with 2 parameter
    static int Multiply(int a, int b){
        return a * b;
    }
    // Method with the same name but 3 parameter
    static int Multiply(int a, int b, int c){
        return a * b * c;
    }
}
class Test{
    public static void main(String[] args) {
        System.out.println(MultiplyFun.Multiply(2, 4));
        System.out.println(MultiplyFun.Multiply(2, 7, 3));
    }
}
Output
8
42
        It occurs when a derived class has a definition for one of the member
        functions of the base class. That base function is said to be overridden.
class Parent {
      void Print() {
            System.out.println("parent class");
      }
12
}
class TestPolymorphism3 {
      public static void main(String[] args) {
            Parent a;
            a = new subclass1();
            a.Print();
            a = new subclass2();
            a.Print();
     }
}
Output
subclass1
subclass2
13
Exception Handling
Error in Java can be of two types i.e. normal unavoidable errors and Exceptions.
     ● Errors are the problems in a program due to which the program will stop the
        execution.
     ● On the other hand, exceptions are raised when some internal events occur
        which changes the normal flow of the program.
14
Exceptions: Exceptions are raised when the program is syntactically correct but the
code resulted in an error. This error does not stop the execution of the program,
however, it changes the normal flow of the program.
Example:
Output:
Exceptions in Java
     ● Java has many built-in exceptions that are raised when your program
        encounters an error (something in the program goes wrong).
     ● When these exceptions occur, the Java interpreter stops the current process
        and passes it to the calling process until it is handled.
     ● If not handled, the program will crash.
     ● For example, let us consider a program where we have a function A that calls
        function B, which in turn calls function C. If an exception occurs in function C
        but is not handled in C, the exception passes to B and then to A.
     ● If never handled, an error message is displayed and the program comes to a
        sudden unexpected halt.
15
Some Common Exceptions
A list of common exceptions that can be thrown from a standard Java program is
given below.
     ● ArithmeticException
       It is thrown when an exceptional condition has occurred in an arithmetic
       operation.
     ● ArrayIndexOutOfBoundsException
       It is thrown to indicate that an array has been accessed with an illegal index.
       The index is either negative or greater than or equal to the size of the array.
     ● ClassNotFoundException
       This Exception is raised when we try to access a class whose definition is not
       found
     ● FileNotFoundException
       This Exception is raised when a file is not accessible or does not open.
     ● IOException
       It is thrown when an input-output operation failed or interrupted
     ● InterruptedException
       It is thrown when a thread is waiting , sleeping , or doing some processing,
       and it is interrupted.
     ● NoSuchFieldException
       It is thrown when a class does not contain the field (or variable) specified
     ● NoSuchMethodException
       It is thrown when accessing a method which is not found.
     ● NullPointerException
       This exception is raised when referring to the members of a null object. Null
       represents nothing
16
     ● NumberFormatException
       This exception is raised when a method could not convert a string into a
       numeric format.
     ● RuntimeException
       This represents any exception which occurs during runtime.
     ● StringIndexOutOfBoundsException
       It is thrown by String class methods to indicate that an index is either negative
       than the size of the string
Catching Exceptions
In Java, exceptions can be handled using try-catch blocks.
     ● If the Java program contains suspicious code that may throw the exception,
        we must place that code in the try block.
     ● The try block must be followed by the catch statement, which contains a
        block of code that will be executed in case there is some exception in the try
        block.
     ● We can thus choose what operations to perform once we have caught the
        exception.
17
     ● Here is a simple example:
The entry is 1
The entry is 0
Oops! An error occurred: java.lang.ArithmeticException: / by zero
The entry is 2
18
Catching Specific Exceptions in Java
     ● In the above example, we did not mention any specific exception in the
        catch clause.
     ● This is not a good programming practice as it will catch all exceptions and
        handle every case in the same way.
     ● We can specify which exceptions a catch clause should catch.
     ● A try clause can have any number of catch clauses to handle different
        exceptions, however, only one will be executed in case an exception occurs.
     ● You can use multiple catch blocks for different types of exceptions.
try{
    a=10/0;
}
catch(ArithmeticError e){
    System.out.println("Arithmetic Exception");
}
catch(IOException e){
    System.out.println("input output Exception");
}
Output:
Arithmetic Exception
19
finally Statement
The try statement in Java can have an optional finally clause. This clause is
executed no matter what and is generally used to release external resources.
Here is an example of file read and close to illustrate this:
 FileReader f = null;
 try{
     f = new FileReader(file);
     BufferedReader br = new BufferedReader(f);
     String line = null;
 }
 catch (FileNotFoundException fnf) {
     fnf.printStackTrace();
 }
 finally {
     if( f != null)
         f.close();
 }
This type of construct makes sure that the file is closed even if an exception occurs
during the program execution.
20
Recursion-1
Introduction
The process in which a function calls itself is called r ecursion and the
corresponding function is called a r ecursive function.
In general, we all are aware of the concept of functions. In a nutshell, functions are
mathematical equations that produce an output on providing input. F
                                                                   or example:
Suppose the function F
                      (x) is a function defined by:
F(x) = x2 + 4
Now, we can pass different values of x to this function and receive our output
accordingly.
Before moving onto the recursion, let's try to understand another mathematical
concept known as the Principle of Mathematical Induction (PMI).
1
    1. Step of the trivial case: In this step, we will prove the desired statement for
         a base case like n = 0 or n
                                      = 1.
    2. Step of assumption: In this step, we will assume that the desired statement
         is valid for n = k.
    3. To prove step: From the results of the assumption step, we will prove that,
         n = k + 1 is also true for the desired equation whenever n
                                                                    = k is true.
For Example: L
               et’s prove using the Principle of Mathematical Induction that:
Proof:
Step 1: F
         or N = 1, S(1) = 1 is true.
Step 2: A
         ssume, the given statement is true for N = k, i.e.,
Step 3: L
         et’s prove the statement for N = k + 1 using step 2.
To Prove: 1
             + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
Proof:
Adding (k+1) to both LHS and RHS in the result obtained on step 2:
 1 + 2 + 3 + ... + (k+1) = (k*(k+1))/2 + (k+1)
Hence proved.
2
One can think, why are we discussing these over here. To answer this question, we
need to know that these three steps of PMI are related to the three steps of
recursion, which are as follows:
    1. Induction Step and Induction Hypothesis: Here, the Induction Step is the
       main problem which we are trying to solve using recursion, whereas the
       Induction Hypothesis is the sub-problem, using which we’ll solve the
       induction step. Let’s define the Induction Step and Induction Hypothesis for
       our running example:
       Induction Step: Sum of first n natural numbers - F(n)
       Induction Hypothesis: T
                              his gives us the sum of the first n-1 natural
       numbers - F(n-1)
    2. Express F(n) in terms of F(n-1) and write code:
F(N) = F(N-1)+ N
    3. The code is still not complete. The missing part is the base case. Now we will
       dry run to find the case where the recursion needs to stop.
3
    4. After the dry run, we can conclude that for N equals 1, the answer is 1, which
       we already know. So we'll use this as our base case. Hence the final code
       becomes:
This is the main idea to solve recursive problems. To summarize, we will always
focus on finding the solution to our starting problem and tell the function to
compute the rest for us using the particular hypothesis. This idea will be studied in
detail in further sections with more examples.
Now, we’ll learn more about recursion by solving problems which contain smaller
subproblems of the same kind. Recursion in computer science is a method where
the solution to the question depends on solutions to smaller instances of the same
problem. By the exact nature, it means that the approach that we use to solve the
original problem can be used to solve smaller problems as well. So, in other words,
in recursion, a function calls itself to solve smaller problems. R
                                                                  ecursion is a popular
approach for solving problems because recursive solutions are generally easier to
think than their iterative counterparts, and the code is also shorter and easier to
understand.
4
Working of recursion
We can define the steps of the recursive approach by summarizing the above three
steps:
    ● Base case: A recursive function must have a terminating condition at which
         the process will stop calling itself. Such a case is known as the base case. In
         the absence of a base case, it will keep calling itself and get stuck in an
         infinite loop. Soon, the recursion depth* will be exceeded and it will throw
         an error.
    ● Recursive call: T
                       he recursive function will invoke itself on a smaller version
         of the main problem. We need to be careful while writing this step as it is
         crucial to correctly figure out what your smaller problem is.
    ● Small calculation: Generally, we perform a calculation step in each recursive
         call. We can achieve this calculation step before or after the recursive call
         depending upon the nature of the problem.
Note*: R
        ecursion uses an in-built stack which stores recursive calls. Hence, the
number of recursive calls must be as small as possible to avoid memory-overflow. If
the number of recursion calls exceeded the maximum permissible amount, the
recursion depth* will be exceeded.
Now, let us see how to solve a few common problems using Recursion.
Approach: Figuring out the three steps of PMI and then relating the same using
recursion.
5
       Induction Hypothesis: W
                              e have already obtained the factorial of n-1 - F(n-1)
    3. The code is still not complete. The missing part is the base case. Now we will
       dry run to find the case where the recursion needs to stop. Consider n = 5:
6
Problem Statement - Fibonacci Number
Write a function int fib(int n) that returns nth fibonacci number. For example, if n =
0, then fib(int n) should return 0. If n = 1, then it should return 1. For n > 1, it should
return F(n-1) + F(n-2), i.e., fibonacci of n-1 + fibonacci of n-2.
Approach: F
            iguring out the three steps of PMI and then relating the same using
recursion.
    1. Induction Step: Calculating the nth Fibonacci
                                             
                                                       number n.
       Induction Hypothesis: W
                              e have already obtained the (n-1)th a
                                                                      nd (n-2)th
       Fibonacci numbers.
3. Let’s dry run the code for achieving the base case: (Consider n= 6)
7
From here we can see that every recursive call either ends at 0 or 1 for which we
already know the answer: F(0) = 0 and F(1) = 1. Hence using this as our base case in
the code below:
We have to tell whether the given array is sorted or not using recursion.
For example:
    ● If the array is {2, 4, 8, 9, 9, 15}, then the output should be Y
                                                                      ES.
    ● If the array is {5, 8, 2, 9, 3}, then the output should be N
                                                                  O.
Approach: Figuring out the three steps of PMI and then relating the same using
recursion.
8
       two elements. Find if the first two elements are sorted or not. If the elements
       are not in sorted order, then we can directly return false. If the first two
       elements are in sorted order, then we will check for the remaining array
       through recursion.
    3. We can see that in the case when there is only a single element left or no
       element left in our array, the array is always sorted. Let’s check the final code
       now:
// driver code
public static void main(String[] args) {
    int arr[] = {2, 3, 6, 10, 11};
      if(isSorted(arr, 5))
           System.out.println("Yes");
     else
           System.out.println("No");
}
9
Problem Statement - First Index of Number
To get a better understanding of the problem statement, consider the given cases:
Case 1: Array = {1,4,5,7,2}, Integer = 4
Output: 1
Explanation: 4 is present at 1st position in the array.
Case 2: A
          rray = {1,3,5,7,2}, Integer = 4
Output: -1
Explanation: 4
              is not present in the array
Case 3: A
          rray = {1,3,4,4,4}, Integer = 4
Output: 2
Explanation: 4
              is present at 3 positions in the array; i.e., [2, 3, 4]. But as the
question says, we have to find out the first occurrence of the target value, so the
answer should be 2.
Approach:
Now, to solve the question, we have to figure out the following three elements of
the solution:
10
     1. Base case
     2. Recursive call
     3. Small calculation
 if(arr[sI] == x)
     return sI;
11
     ● The base case for this question can be identified by dry running the case
        when you are trying to find an element that is not present in the array.
     ● For example: Consider the array [ 5, 5, 6, 2, 5] and x = 10. On dry running, we
        can conclude that the base case will be the one when the startIndex exceeds
        size of the array.
     ● Therefore , then we will return -1. This is because if the base case is reached,
        then this means that the element is not present in the entire array.
     ● We can write the base case as:
Note: The code written from the above insights can be accessed in the solution tab
in the question itself.
Case 1: A
          rray = {1,4,5,7,2}, Integer = 4
Output: 1 (Explanation: 4
                           is present at 1st position in the array, which is the last
and the only place where 4 is present in the given array.)
Case 2: A
          rray = {1,3,5,7,2}, Integer = 4
Output: -1 (Explanation: 4
                            is not present in the array.)
12
Approach:
Now, to solve the question, we have to figure out the following three elements of
the solution.
     1. Base case
     2. Recursive call
     3. Small calculation
Let the array be: [5, 5, 6, 2, 5] and x = 6. Now, if we want to find 6 in the array, then
first we have to check with the first index. This is the small calculation part.
Code:
 if(arr[sI] == x)
      return sI;
Since, in the running example, the 0th index element is not equal to 6, so we will
have to make a recursive call for the remaining array: [5, 6, 2, 5] and x = 6. This is
the recursive call step. We will start with startIndex from the last index of the
array.
Base Case:
     ● The base case for this question can be identified by dry running the case
         when you are trying to find an element that is not present in the array.
     ● For example: [5, 5, 6, 2, 5] and x = 10. On dry running, we can conclude that
         the base case will be the one when the startIndex passes beyond left of index
         0 as we started from the rightmost index.
13
     ● When startIndex becomes -1, then we will return -1.
     ● This is because if the startIndex reaches -1, then this means that we have
        traversed the entire array and we were not able to find the target element.
Note: The code written from the above insights can be accessed in the solution tab
in the question itself.
Approach:
Now, to solve the question, we have to figure out the following three elements of
the solution:
     1. Base case
     2. Recursive call
     3. Small calculation
14
Let us assume the given array is: [5, 6, 5, 5, 6] and the target element is 5, then the
output array should be [0, 2, 3] and for the same array, let’s suppose the target
element is 6
            , then the output array should be [ 1, 4].
To solve this question, the base case should be the case when the startIndex
reaches the size of the array. In this case, we should simply return an empty array,
i.e., an array of size 0, since there are no elements left.
The next two components of the solution are Recursive call and Small calculation.
Let us try to figure them out using the following images:
So, the following are the recursive call and small calculation components of the
solution:
Recursive Call
Small Calculation:
     1. If the element at startIndex of array is equal to the x, then create a new array
        of size of output+1. Now copy paste all the elements of the output array to
        the new array starting from 1st index and at the 0th index add the element
        of startIndex in original array. Finally return this new output.
     2. Else is the case when element at startIndex do not match with x. So simply
        return the output.
Note: The code written from the above insights can be accessed in the solution tab
in the question itself.
Using the same concept, other problems can be solved using recursion, just
remember to apply PMI and three steps of recursion intelligently.
15
Recursion 2
In this module, we are going to understand how to solve different kinds of
problems using recursion.
Recursion in strings is not a very different logic, it is the same as we apply in arrays,
in fact it becomes more easy to pass a complete new string using substring
method.
 You are given a string of size n containing characters a-z. The task is to write
 a recursive function to replace all occurrences of pi with 3.14 in the given
 string and print the modified string.
Approach
    1. Step of the trivial case: In this step, we will prove the desired statement for
       a base case like size of string = 0 or  1.
    2. Small calculation and recursive part interlinked: In this step, you will first
       check character at 0th index and character at 1st index of the string.
          -   If it comes out to be ‘p’ and ‘i’ then we make a recursive call passing the
              string from index 2. And thereafter “3.14” needs to be concatenated
              with the recursive answer and return this new result.
1
          -   Else we will just make a recursive call passing the string from index 1.
              Thereafter the character at 0th index needs to be concatenated with a
              recursive answer and return the same.
are already sorted by ignoring half of the elements after just one comparison.
You are given a target element X and a sorted array. You need to check if X is
2
 }
Pseudo-Code
 public static void mergeSort(arr[], l, r){
    if (r > l){
        1. Find the middle point to divide the array into two halves:
                     middle m = (l+r)/2
         2. Call mergeSort for the first half:
                     Call mergeSort(arr, l, m)
          3. Call mergeSort for the second half:
                     Call mergeSort(arr, m+1, r)
           4. Merge the two halves sorted in step 2 and 3
                                                                 :
                     Call merge(arr, l, m, r)
     }
 }
The following diagram shows the complete merge sort process for an example
array [
       38,27,43,3,9,82,10]. If we take a closer look at the diagram, we can see
3
that the array is recursively divided into two halves till the size becomes 1. Once the
size becomes 1, the merge processes come into action and start merging arrays
back till the complete array is merged.
Quick Sort
Quick-sort is based on the d
                            ivide-and-conquer approach. It works along the lines
of choosing one element as a pivot element and partitioning the array around it
such that:
    ● The left side of the pivot contains all the elements that are less than the pivot
       element
4
    ● The right side contains all elements greater than the pivot.
    ● Divide: T
               he array is divided into subparts taking pivot as the partitioning
         point. The elements smaller than the pivot are placed to the left of the pivot
         and the elements greater than the pivot are placed to the right side.
    ● Conquer: T
                he left and right sub-parts are again partitioned using the by
         selecting pivot elements for them. This can be achieved by recursively
         passing the subparts into the algorithm.
    ● Combine: T
                his part does not play a significant role in quicksort. The array is
         already sorted at the end of the conquer step.
The advantage of quicksort over merge sort is that it does not require any extra
space to sort the given array, that it is an in-place sorting technique.
[8,1,5,14,4,15,12,6,2,11,10,7,9]
5
    ● In s tep 1, 8 is taken as the pivot.
    ● In s tep 2, 6 and 12 are taken as pivots.
    ● In s tep 3, 4, and 10 are taken as pivots.
    ● We keep dividing the list about pivots till there are only 2 elements left in a
       sublist.
6
Problem Statement - Tower Of Hanoi
Tower of Hanoi is a m
                      athematical puzzle where we have 3
                                                           rods and N
                                                                        disks. The
objective of the puzzle is to move all disks from source rod to d
                                                                   estination rod
using a t hird rod (say auxiliary). The rules are :
    ● Only one disk can be moved at a time.
    ● A disk can be moved only if it is on the top of a rod.
    ● No disk can be placed on the top of a smaller disk.
Print the steps required to move N
                                   disks from source rod to destination rod.
Source Rod is named as ' A', the destination rod as ' B', and the auxiliary rod as ' C'.
Let's see how to solve the problem recursively. We'll start with a really easy case
N=1. We just need to move one disk from source to destination.
    ● You can always move disk 1 from peg A to peg B because you know that any
       disks below it must be larger.
    ● There's nothing special about pegs A and B. You can move disk 1 from peg B
                                                                                   
       to peg C if you like, or from peg C to peg A
                                                       , or from any peg to any peg.
    ● Solving the Towers of Hanoi problem with one disk is trivial as it requires
       moving only the one disk one time.
Now consider the case N=2. Here's what it looks like at the start:
7
First, move disk 1 from peg A to peg C
                                          :
8
Now let us solve this problem for 3 disks. You need to expose the bottom disk (disk
3) so that you could move it from peg A to peg B. To expose disk 3, you needed to
move disks 1 and 2 from peg A to the spare peg, which is peg C
                                                                :
Wait a minute—it looks like two disks moved in one step, violating the first rule. But
they did not move in one step. You agreed that you can move disks 1 and 2 from
any peg to any peg, using three steps. The situation above represents what you
have after three steps. (Move disk 1 from peg A to peg B; move d
                                                                      isk 2 from peg A
                                                                                       
to peg C
        ; move d
                  isk 1 from peg B
                                     to peg C. )
9
from peg A to peg C
                     . Once you've solved this subproblem, you can move disk 3
from peg A to peg B
                     :
Now, to finish up, you need to recursively solve the subproblem of moving disks
1 through n-1, from peg C
                           to peg B
                                     . Again, you agreed that you can do so in three
steps. (Move d
              isk 1 from peg C
                                 to peg A
                                           ; move disk 2 from peg C to peg B; move
disk 1 from peg A
                   to peg B.) And you're done:
At this point, you might have picked up the pattern. The algorithm can be
summarised as:
10
     ● Recursively solve the subproblem of moving disks 1
                                                         through n-1 from
         whichever peg they start on, to the spare peg.
     ● Move disk N from the peg it starts on, to the peg it's supposed to end up on.
     ● Recursively solve the subproblem of moving disks 1
                                                         through n-1, from the
         spare peg to the peg they're supposed to end up on.
Practice Problems
11
Time Complexity
    ●   Algorithm Analysis
    ●   Type of Analysis
    ●   Big O Notation
    ●   Determining Time Complexities Theoretically
    ●   Time complexity of some common algorithms
Introduction
All are important but we are mostly concerned about CPU time. Be careful to
differentiate between:
1
    1. Performance: how much time/memory/disk/etc. is actually used when a
       program is run. This depends on the machine, compiler, etc. as well as the
       code we write.
    2. Complexity: how do the resource requirements of a program or algorithm
       scale, i.e. what happens as the size of the problem being solved by the code
       gets larger. Complexity affects performance but not vice-versa. The time
       required by a function/method is proportional to the number of "basic
       operations" that it performs.
Algorithm Analysis
Algorithm analysis is an important part of computational complexity theory, which
2
Types of Analysis
To analyze a given algorithm, we need to know, with which inputs the algorithm
takes less time (i.e. the algorithm performs well) and with which inputs the
• Worst-Case Analysis: The worst-case consists of the input for which the
• Best Case Analysis: The best case consists of the input for which the algorithm
• Average case: The average case gives an idea about the average running time of
Big-O notation
We can express algorithmic complexity using the big-O notation. For a problem of
size N:
3
Definition: Let g and f be functions from the set of natural numbers to itself. The
function f is said to be O(g) (read big-oh of g), if there is a constant c and a natural
Examples:
Note: The big-O expressions do not have constants or low-order terms. This is
because, when N gets large enough, constants and low-order terms don't matter (a
1. Sequence of statements
 statement 1;
 statement 2;
 ...
 statement k;
4
The total time is found by adding the times for all statements:
2. if-else statements
if (condition):
     #sequence of statements 1
else:
     #sequence of statements 2
Here, either sequence 1 will execute, or sequence 2 will execute. Therefore, the
For example, if sequence 1 is O(N) and sequence 2 is O(1) the worst-case time for
3. for loops
for i in range N:
     #sequence of
statements
Here, the loop executes N times, so the sequence of statements also executes N
times. Now, assume that all the statements are of the order of O(1), then the total
4. Nested loops
5
for i in range N:
      for i in range
M:
            #statements
The outer loop executes N times. Every time the outer loop executes, the inner loop
executes M times. As a result, the statements in the inner loop execute a total of N
* M times. Assuming the complexity of the statement inside the inner loop to be
Sample Problem:
What will be the Time Complexity of following while loop in terms of ‘N’ ?
while N>0:
      N =
N//8
Iteration Value of N
Number
1 N
2 N//8
3 N//64
... ...
k N//8k
6
We know, that in the last i.e. the kth iteration, the value of N would become 1, thus,
we can write:
N//8k = 1
=> N = 8k
=> log(N) = log(8k)
=> k*log(8) =
log(N)
=> k =
log(N)/log(8)
=> k = log8(N)
Now, clearly the number of iterations in this example is coming out to be of the
order of log8(N). Thus, the time complexity of the above while loop will be
O(log8(N)).
Qualitatively, we can say that after every iteration, we divide the given number by 8,
and we go on dividing like that, till the number remains greater than 0. This gives
Linear Search
Linear Search time complexity analysis is done below-
7
    ● In this case, the search terminates in success with just one comparison.
    ● Thus in the best case, the linear search algorithm takes O(1) operations.
Worst Case- In the worst possible case:
    ● The element being searched may be present in the last position or may not
       present in the array at all.
    ● In the former case, the search terminates in success with N comparisons.
    ● In the latter case, the search terminates in failure with N comparisons.
    ● Thus in the worst case, the linear search algorithm takes O(N) operations.
Binary Search
Binary Search time complexity analysis is done below-
    ● In each iteration or each recursive call, the search gets reduced to half of the
       array.
    ● So for N elements in the array, there are log2N iterations or recursive calls.
Thus, we have-
8
Example-2 Find upper bound for f(n) = n2 + 1
9
Space Complexity Analysis
Introduction
    ● The space complexity of an algorithm represents the amount of extra
       memory space needed by the algorithm in its life cycle.
    ● Space needed by an algorithm is equal to the sum of the following two
       components:
           ○ A fixed part is a space required to store certain data and variables (i.e.
              simple variables and constants, program size, etc.), that are not
              dependent on the size of the problem.
           ○ A variable part is a space required by variables, whose size is
              dependent on the size of the problem. For example, recursion stack
              space, dynamic memory allocation, etc.
In this particular method, three variables are used and allocated in memory:
1
The first integer argument, a; the second integer argument, b; and the returned
sum which is also an integer.
In Java, these three variables point to three different memory locations. We can see
that the space complexity is constant, so it can be expressed in big-O notation as
O(1).
Next, let’s determine the space complexity of a program that sums all integer
elements in an array:
    ● array
    ● size
    ● sum
    ● iterator
2
    ● Case 1: The case when the sizes of the sublist on either side of the pivot
       become equal occurs when the subarray has an odd number of elements
       and the pivot is right in the middle after partitioning. Each partition will have
       (n-1)/2 elements.
    ● Case 2: The size difference of 1 between the two sublists on either side of
       pivot happens if the subarray has an even number, n, of elements. One
       partition will have n
                            /2 e
                                 lements with the other having ( n/2)-1.
    ● In either of these cases, each partition will have at most n
                                                                  /2 elements, and
       the tree representation of the subproblem sizes will be as below:
3
Practice Problems
Problem 1: What is the time & space complexity of the following code:
int a =    0
int b =      0
for(int      i=0; i<n; i++){
     a =      a + i;
}
Problem 2: What is the time & space complexity of the following code:
int a = 0;
int b = 0;
for(int i=0; i<n; i++){
     for(int j=0; j<n; j++){
           a = a + j;
      }
}
Problem 3: What is the time and space complexity of the following code:
int a = 0;
for(int i=0; i<n; i++){
      int j = n;
     while (j>i){
          a = a + i + j;
          j = j-1;
      }
}
4
Linked-List 2
Now moving further with the topic, let’s try to solve some problems now...
1
Java Code
public static Node returnMiddle(Node headNode){
    if (headNode == null || headNode.next == null)
           return head;
     Node slow = headNode; //Slow pointer
     Node fast = headNode.next; //Fast Pointer
     while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
      }
      return slow; // Slow pointer shall point to our middle element
}
Note:
    ● For odd length there will be only one middle element, but for the even length
        there will be two middle elements.
    ● In case of an even length LL, both these approaches will return the first
        middle element and the other one will be the direct n
                                                              ext o
                                                                    f the first middle
        element.
    ● We will be merging the linked list, similar to the way we performed merge
        over two sorted arrays.
    ●   We will be using the two h
                                  ead pointers, compare their data and the one
        found smaller will be directed to the new linked list, and increase the head
        pointer of the corresponding linked list.
    ●   Just remember to maintain the h
                                       ead pointer separately for the new sorted
        list.
    ●   And also if one of the linked list’s length ends and the other one’s not, then
        the remaining linked list will directly be appended to the final list.
    ● Try to implement this approach on your own.
2
Mergesort over a linked list
    ● Like the merge sort algorithm is applied over the arrays, the same way we
       will be applying it over the linked list.
    ● Just the difference is that in the case of arrays, the middle element could be
       easily figured out, but here you have to find the middle element, each time
       you send the linked list to split into two halves using the above approach.
    ● The merging part of the divided lists can also be done using the merge
       sorted linked lists code a
                                 s discussed above.
    ● The functionalities of this code have already been implemented by you, just
       use them directly in your functions at the specified places.
    ● Try to implement this approach on your own.
Recursive approach:
    ● In this approach, we will store the last element of the list in the small answer,
       and then update that by adding the next last node and so on.
    ● Finally, when we will be reaching the first element, we will assign the n
                                                                               ext to
       null.
    ● Follow the Java code below, for better understanding.
3
        head.next = null;
       return smallHead;
 }
After calculation, you can see that this code has a time complexity of O
                                                                        (n2). Now
let’s think about how to improve it.
 class Pair{
     Node head;
     Node tail;
     public Pair(Node head, Node tail){
         this.head = head;
          this.tail = tail;
     }
 }
 class main{
     private static Pair reverse2Helper(Node head){
          if (head == null || head.next == null)
                 return new Pair(head, head);
              Pair p = reverse2Helper(head.next);
              p.tail.next= head;
              head.next = null;
             return new Pair(p.head,head);
       }
4
       // Main driver function can be written by yourself
 }
         smallHead = reverse3(head.next);
         tail = head.next;
         tail.next = head;
         head.next = null;
         return smallHead;
 }
Iterative approach:
5
public static Node reverse(Node head){
     if (head == null || head.next == null)
           return head;
6
Linked-List 1
Data Structures
Data structures are just a way to store and organize our data so that it can be used and
retrieved as per our requirements. Using these can affect the efficiency of our algorithms
to a greater extent. There are many data structures that we will be going through
throughout the course, linked-lists are a part of them.
Introduction
AL
  inked List is a data structure used for storing collections of data. A linked list has the
following properties:
    ●   Successive elements are connected by pointers.
    ●   Can grow or shrink in size during the execution of a program.
    ●   Can be made just as long as required (until systems memory exhausts).
    ●   Does not waste memory space (but takes some extra memory for pointers). It
        allocates memory as the list grows.
Basic Properties:
    ●   Each element or node of a list is comprising of two items:
           ○   Data
           ○   Pointer(reference) to the next node.
    ●   In a Linked List, the elements are not stored at contiguous memory locations.
    ●   The first node of a linked list is known as Head.
    ●   The last node of a linked list is known as Tail.
    ●   The last node has a reference to null.
1
Types of A Linked List
    ●   Doubly-Linked List: I t’s a two-way linked list as each node points not only to the
        next pointer but also to the previous pointer.
    ●   Circular-Linked List: There is no tail node i.e., the next field is never null and the
        next field for the last node points to the head node.
    ●   Circular Doubly-Linked List: Combination of both Doubly linked list and circular
        linked list.
2
Node Class (Singly Linked List)
 // Node class
 class Node{
       int data;
       Node next;
     // Function to initialize the node object
      Node(int data){
            this.data = data; // Data that the node contains
            this.next = null; // Next node that this node points to
       }
 }
Note: T
        he first node in the linked list is known as Head pointer and the last node is
referenced as T
               ail pointer. We must never lose the address of the head pointer as it
references the starting address of the linked list and if lost, would lead to loss of the list.
3
Insertion of A Node in a Singly Linked List
There are 3 possible cases:
    ●   Inserting a new node before the head (at the beginning).
    ●   Inserting a new node after the tail (at the end of the list).
    ●   Inserting a new node in the middle of the list (random location).
In this case, a new node is inserted before the current head node. Only one next pointer
needs to be modified (new node’s next pointer) and it can be done in two steps:
• Update h
          ead pointer to point to the new node.
Java Code:
4
Case 2: Insert node at the ending:
In this case, we need to modify two next pointers (last nodes next pointer and new nodes
next pointer).
• New node’s n
              ext pointer points to n
                                       ull.
• Last node’s n
               ext pointer points to the new node.
Java Code:
5
Case 3: Insert node anywhere in the middle: (At any specified Index)
Let us assume that we are given a position where we want to insert the new node. In this
case, also, we need to modify two next pointers.
• For simplicity let us assume that the second node is called the position node. The new
node points to the next node of the position where we want to add this node.
• Position node’s n
                   ext pointer now points to the new node.
6
Java Code:
 public static Node insertAtIndex (int head, int index, int data){
         if (index == 1) // Insert at beginning
                  insertAtStart(head, data);
             int i = 1;
             Node n = head;
          while (i < index-1 && n != null){
                  n = n.next;
                  i = i+1;
             }
           if (n == null)
                  print("Index out of bound");
            else{
                  Node newNode = new Node(data);
                  newNode.next = n.next;
                  n.next = newNode;
             }
 }
7
• Now, move the head nodes pointer to the next node and dispose of the temporary node.
In this case, the last node is removed from the list. This operation is a bit trickier than
removing the first node because the algorithm should find a node, which is previous to the
tail. It can be done in three steps:
• Traverse the list and while traversing maintain the previous node address also. By the
time we reach the end of the list, we will have two pointers, one pointing to the tail node
and the other pointing to the node before the tail node.
8
• Dispose of the tail node.
In this case, the node to be removed is always located between two nodes. Head and tail
links are not updated in this case. Such removal can be done in two steps:
• Similar to the previous case, maintain the previous node while traversing the list. Once we
find the node to be deleted, change the previous node’s next pointer to the next pointer of
the node to be deleted.
9
Insert node recursively
     ●   If Head is n
                       ull and position is not 0. Then exit it.
     ●   If Head is n
                       ull and position is 0. Then insert a new Node to the H
                                                                                 ead and exit it.
     ●   If Head is not n
                           ull a
                                 nd position is 0. Then the Head reference set to the new Node.
         Finally, a new Node set to the Head and exit it.
     ●   If not, iterate until finding the Nth position or end.
10
Stacks
    ●   Operations on stack.
    ●   Implementation of stack.
    ●   Use of inbuilt stack.
Introduction
    ● Stacks are simple data structures that allow us to store and retrieve data
        sequentially.
    ● A stack is a linear data structure like arrays and linked lists.
    ● It is an abstract data type(ADT).
    ● In a stack, the order in which the data arrives is essential. It follows the LIFO
        order of data insertion/abstraction. LIFO stands for Last In First Out.
    ● Consider the example of a pile of books:
1
       Here, unless the book at the topmost position is removed from the pile, we
       can’t have access to the second book from the top and similarly, for the
       books below the second one. When we apply the same technique over the
       data in our program then, this pile-type structure is said to be a stack.
       Like deletion, we can only insert the book at the top of the pile rather than at
       any other position. This means that the object/data that made its entry at the
       last would be one to come out first, hence known as LIFO.
• int pop(): Removes and returns the last inserted element from the stack.
2
• int top(): Returns the last inserted element without removing it.
• boolean isEmpty(): Indicates whether any elements are stored in the stack or
not.
Performance
Let n be the number of elements in the stack. The complexities of stack operations
with this representation can be given as:
Exceptions
    ● Attempting the execution of an operation may sometimes cause an error
       condition, called an exception.
    ● Exceptions are said to be “thrown” by an operation that cannot be executed.
    ● Attempting the execution of pop() on an empty stack throws an exception
       called Stack Underflow.
    ● Trying to push an element in a full-stack throws an exception called Stack
       Overflow.
3
Implementing stack- Simple Array Implementation
This implementation of stack ADT uses an array. In the array, we add elements
from left to right and use a variable to keep track of the index of the top element.
class StackUsingArray{
       int[] data;                     // Dynamic array created serving as stack
       int nextIndex                  // To keep the track of current top index
       int capacity;               // To keep the track of total size of stack
// insert element
4
       public void push(int element) {
             if(nextIndex == capacity) {
                   System.out.println("Stack full");
                   return;
             }
             data[nextIndex] = element;
             nextIndex++;                            //Size incremented
       }
       // delete element
       public int pop() {
          //Before deletion check for empty to prevent underflow
             if(isEmpty()) {
                   System.out.println("Stack is empty");
                   return Integer.MIN_VALUE;
             }
             nextIndex--;               //Conditioned satisfied so deleted
             return data[nextIndex];
       }
Dynamic Stack
There is one limitation to the above approach, which is the size of the stack is fixed.
In order to overcome this limitation, whenever the size of the stack reaches its limit
5
we will simply double its size. To get the better understanding of this approach,
look at the code below…
class StackUsingArray{
       int[] data;                     // Dynamic array created serving as stack
       int nextIndex                  // To keep the track of current top index
       int capacity;               // To keep the track of total size of stack
       // insert element
       public void push(int element) {
             if(nextIndex == capacity) {
                   int newData[] = new int[2 * capacity]; //Capacity doubled
                   for(int i = 0; i < capacity; i++) {
                         newData[i] = data[i];            //Elements copied
                   }
                   capacity *= 2;
                   data = newData;
             }
             data[nextIndex] = element;
             nextIndex++;                           //Size incremented
       }
6
       // delete element
       public int pop() {
          //Before deletion check for empty to prevent underflow
             if(isEmpty()) {
                   System.out.println("Stack is empty");
                   return Integer.MIN_VALUE;
             }
             nextIndex--;               //Conditioned satisfied so deleted
             return data[nextIndex];
       }
While implementing the dynamic stack, we kept ourselves limited to the data of
type integer only, but what if we want a generic stack(something that works for
every other data type as well). For this we will be using templates. Refer the code
below(based on the similar approach as used while creating dynamic stack):
7
    public int size() {
          return nextIndex;
    }
    // insert element
    public void push(T element) {
          if(nextIndex == capacity) {
                T newData[] = new T[2 * capacity]; //Capacity doubled
                for(int i = 0; i < capacity; i++) {
                      newData[i] = data[i];            //Elements copied
                }
                capacity *= 2;
                data = newData;
          }
          data[nextIndex] = element;
          nextIndex++;                           //Size incremented
    }
    // delete element
    public T pop() {
       //Before deletion check for empty to prevent underflow
          if(isEmpty()) {
                System.out.println("Stack is empty");
                return Integer.MIN_VALUE;
          }
          nextIndex--;               //Conditioned satisfied so deleted
          return data[nextIndex];
    }
8
               }
               return data[nextIndex - 1];
        }
 }
You can see that every function whose return type was int initially now returns T
type (i.e., template-type).
Generally, the template approach of stack is preferred as it can be used for any
data type irrespective of it being int, char, float, etc.
        Node(T data) {
              this.data = data;
              next = NULL;
        }
        Node() {
              next = null;
        }
 }
 class Stack {
        Node<T> head;
        Node<T> tail;
        int size;             // number of elements present in stack
9
         public int getSize() {      // traverse the LL and return its length
public boolean isEmpty() {// check if the head pointer is NULL or not
         public T pop() {    // remove the tail node and then update the tail
                             // pointer to the previous position
         }
Java provides the in-built stack in it’s library which can be used instead of
creating/writing a stack class each time. To use this stack, we need to use the
import following file:
import java.util.Stacks;
10
     ● st.isEmpty() : Returns a boolean value (True for empty stack and vice versa).
Approach:
     ● We will use stacks.
     ● Each time, when an open parenthesis is encountered, push it in the stack,
        and when closed parenthesis is encountered, match it with the top of the
        stack and pop it.
     ● If the stack is empty at the end, return Balanced otherwise, Unbalanced.
Java Code:
public String checkBalanced(inputStr){//Function to check parentheses
    Stack<Character> s = new Stack<>(); //The stack
    for(char i : inputStr.toCharArray){
        if (i==’[’ || i==’{’ || i==’(’)
            s.push(i);
        else if (i==’]’ || i==’}’ || i==’)’)
            if (s.size()>0 && s.top()==i)
                s.pop();
            else
                return "Unbalanced";
    }
    if (s.size() == 0)
        return "Balanced";
    else
        return "Unbalanced";
}
11
Queues
     ●   Operations on queue.
     ●   Implementation of queue.
     ●   Use of inbuilt queue.
Introduction
     ● Like stack, the queue is also an abstract data type.
     ● As the name suggests, in queue elements are inserted at one end while
         deletion takes place at the other end.
     ● Queues are open at both ends, unlike stacks that are open at only one
         end(the top).
12
     ● Here, the person who comes first in the queue is served first with the ticket
        while the new seekers of tickets are added back in the line.
     ● This order is known as First In First Out (FIFO).
     ● In programming terminology, the operation to add an item to the queue is
        called "enqueue", whereas removing an item from the queue is known as
        "dequeue".
Working of A Queue
     1. Two pointers called FRONT and REAR are used to keep track of the first and
        last elements in the queue.
     2. When initializing the queue, we set the value of FRONT and REAR to -1.
     3. On enqueuing an element, we increase the value of the REAR index and
        place the new element in the position pointed to by REAR.
     4. On dequeuing an element, we return the value pointed to by FRONT and
        increase the FRONT index.
     5. Before enqueuing, we check if the queue is already full.
     6. Before dequeuing, we check if the queue is already empty.
     7. When enqueuing the first element, we set the value of FRONT to 0.
     8. When dequeuing the last element, we reset the values of FRONT and REAR to
        -1.
13
14
15
Applications of queue
16
          size = 0;
          capacity = s;
     }
17
              }
              return ans;
       }
}
Dynamic queue
In the dynamic queue. we will be preventing the condition where the queue
becomes full and we were not able to insert any further elements in that.
As we all know that when the queue is full it means the internal array that we are
using in the form of queue has become full, we can resolve this problem by creating
a new array of double the size of previous one and copy pasting the elements of
previous array to the new one. Now this new array which has the double size will be
considered as our queue. We will do this in insert function when we check for
queue full (size==capacity), when this happens we will discard the previous array
and create a new array of double size, copy pasting all the elements so that we
don't lose the data. Let’s now check the implementation of the same.
18
     }
19
              return data[firstIndex];        // otherwise returned the element
       }
Given below is an implementation of Queue using Linked List. This is similar to the
way we wrote the LL Implementation for a Stack:
class Node <T> {       // Node class for linked list, no change needed
      T data;
      Node<T> next;
      Node(T data) {
            this -> data = data;
            next = NULL;
      }
}
20
         }
Java provides the in-built queue in it’s library which can be used instead of
creating/writing a queue class each time. To use this queue, we need to use the
import following file:
 import java.util.Queues;
 import java.util.LinkedList;
21
     ● .size() : Returns the total number of elements present in the queue
     ● .isEmpty() : Returns TRUE if the queue is empty and vice versa
     1. Declare a queue of integers and insert the following elements in the same
        order as mentioned: 10, 20, 30, 40, 50, 60.
2. Now tell the element that is present at the front position of the queue
     3. Now delete an element from the front side of the queue and again tell the
        element present at the front position of the queue.
4. Print the size of the queue and also tell if the queue is empty or not.
5. Now, print all the elements that are present in the queue.
import java.util.Queues;
import java.util.LinkedList;
Class QueueTesting{
    public static void main(String[] args) {
             Queue<Integer> q = new LinkedList<>();
              q.push(10);      // part 1
              q.push(20);
              q.push(30);
              q.push(40);
              q.push(50);
              q.push(60);
              System.out.println(q.front());     // Part 2
              q.pop();                           // Part 3
              System.out.println(q.front());     // Part 3
              System.out.println(q.size());      // Part 4
              System.out.println(q.isEmpty()); // prints 1 for TRUE and 0 for
                                                // FALSE(Part 4)
22
           }
     }
}
10
20
5
0
20
30
40
50
60
23
Queues
Introduction
    ● Like stack, the queue is also an abstract data type.
    ● As the name suggests, in queue elements are inserted at one end while
       deletion takes place at the other end.
    ● Queues are open at both ends, unlike stacks that are open at only one
       end(the top).
    ● Here, the person who comes first in the queue is served first with the ticket
       while the new seekers of tickets are added back in the line.
    ● This order is known as F
                              irst In First Out (FIFO).
    ● In programming terminology, the operation to add an item to the queue is
       called "enqueue", whereas removing an item from the queue is known as
       "dequeue".
1
Working of A Queue
2
3
Applications of queue
NOTE: W
       e will be using templates in the implementation, so that it can be
generalised.
4
          size = 0;
          capacity = s;
    }
5
              }
              return ans;
       }
}
Dynamic queue
In the dynamic queue. we will be preventing the condition where the queue
becomes full and we were not able to insert any further elements in that.
As we all know that when the queue is full it means the internal array that we are
using in the form of a queue has become full, we can resolve this problem by
creating a new array of double the size of the previous one and copy pasting the
elements of the previous array to the new one. Now this new array which has the
double size will be considered as our queue. We will do this in insert function when
we check for queue full (size==capacity), when this happens we will discard the
previous array and create a new array of double size, copy pasting all the elements
so that we don't lose the data. Let’s now check the implementation of the same.
6
    }
7
              return data[firstIndex];        // otherwise returned the element
       }
Given below is an implementation of Queue using Linked List. This is similar to the
way we wrote the LL Implementation for a Stack:
       ode <T> {
class N                 // Node class for linked list, no change needed
      T data;
      Node<T> next;
      Node(T data) {
             this -> data = data;
             next = NULL;
      }
}
       ueue <T> {
class Q
      Node<T> head;                        // for storing front of queue
      Node<T> tail;                        // for storing tail of queue
      int size;                             // number of elements in queue
public int getSize() { // just return the size of linked list
8
         }
         public void enqueue(T element) {     // Simply insert the new node
                                                  //at the tail of LL
         public T dequeue() {     // moves the head pointer one position ahead
                                      // and deletes the head pointer.
         }                          // Also decrease the size by 1
 }
         ava.util.Queues;
 import j
 import j ava.util.LinkedList;
9
     ● .size() : Returns the total number of elements present in the queue
     ● .isEmpty() : Returns TRUE if the queue is empty and vice versa
     1. Declare a queue of integers and insert the following elements in the same
        order as mentioned: 10, 20, 30, 40, 50, 60.
2. Now tell the element that is present at the front position of the queue
     3. Now delete an element from the front side of the queue and again tell the
        element present at the front position of the queue.
4. Print the size of the queue and also tell if the queue is empty or not.
5. Now, print all the elements that are present in the queue.
        ava.util.Queues;
import j
import j ava.util.LinkedList;
Class QueueTesting{
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
           .push(10);
           q               // part 1
             q.push(20);
             q.push(30);
             q.push(40);
             q.push(50);
             q.push(60);
             System.out.println(q.front());                // Part 2
             q.pop();                                    // Part 3
             System.out.println(q.front());               // Part 3
             System.out.println(q.size());             // Part 4
             System.out.println(q.isEmpty());          // prints 1 for TRUE and 0 for
                                                        // FALSE(Part 4)
10
           }
     }
}
10
20
5
0
20
30
40
50
60
11
Trees
Introduction
    ● In the previous modules, we discussed binary trees where each node can
       have a maximum of two children and these can be represented easily with
       two pointers i.e right child and left child.
    ● But suppose, we have a tree with many children for each node.
    ● If we do not know how many children a node can have, how do we represent
       such a tree?
    ● For example, consider the tree shown below.
1
Generic Tree Node
    ● Implementation of a generic tree node in Java is quite simple.
    ● The node class will contain two attributes:
          ○ The node data
          ○ Since there can be a variable number of children nodes, thus the
             second attribute will be a list of its children nodes. Each child is an
             instance of the same node class. This is a general n-nary tree.
    ● Consider the given implementation of the Tree Node class:
2
Consider the given Java code:
 // Create nodes
 TreeNode<Integer>        n1= TreeNode<>(5);
 TreeNode<Integer>        n2 =TreeNode<>(2);
 TreeNode<Integer>        n3 =TreeNode<>(9);
 TreeNode<Integer>        n4 =TreeNode<>(8);
 TreeNode<Integer>        n5 =TreeNode<>(7);
 TreeNode<Integer>        n6 =TreeNode<>(15);
 TreeNode<Integer>        n7 =TreeNode<>(1);
3
Take Generic Tree Input (Recursively)
Go through the given Java code for better understanding:
4
              int numChild = s.nextInt();// get the number of child nodes
              for (int i=0; i<numChild; i++) { // iterated over each
                                                 //child node to input it
                     System.out.println("Enter "+i+"th child of "+front.data);
                     int childData = s.nextInt();
                     TreeNode<Integer> child = new TreeNode<>(childData);
                     front.children.add(child);    //Each child node is pushed
                                //into the queue as well as the list of child
                                //nodes as it is taken input so that next
                               // time we can take its children as input while
                              //we kept moving in the level-wise fashion
                     pendingNodes.push(child);
              }
       }
                        / Finally returns the root node
       return root;  /
}
Similarly, we can also print the child nodes using a queue itself. Now, try doing the
same yourselves and for solution refer to the solution tab of the respective
question.
To count the total number of nodes in the tree, we will just traverse the tree
recursively starting from the root node until we reach the leaf node by iterating
over the vector of child nodes. As the size of the child nodes vector becomes 0, we
will simply return. Kindly check the code below:
5
        return ans;      // ultimately returning the final answer
 }
Height of a tree is defined as the length of the path from the tree’s root node to any
of its leaf nodes. Just think what should be the height of a tree with just one node?
Well, there are a couple of conventions; we can define the height of a tree with just
one node to be either 1 or zero. We will be following the convention where the
height of a null tree is zero and that with only one node is one. This has been left
as an exercise for you, if need be you may follow the code provided in the solution
tab of the topic corresponding to the same question.
Approach: Consider the height of the root node as 1 instead of 0. Now, traverse
each child of the root node and recursively traverse over each one of them also and
the one with the maximum height is added to the final answer along by adding 1
(this 1 is for the current node itself).
Depth of a node
Depth of a node is defined as it’s distance from the root node. For example, the
depth of the root node is 0, depth of a node directly connected to root node is 1
and so on. Now we will write the code to find the same… (Below is the pictorial
representation of the depth of a node)
6
If you observe carefully, then the depth of the node is just equal to the level in
which it resides. We have already figured out how to calculate the level of any
node,using a similar approach we will find the depth of the node as well. Suppose,
we want to find all the nodes at level 3, then from the root node we will tell its
children to find the node that is at level 3 - 1 = 2, and similarly keep this up
recursively until we reach the depth = 0. Look at the code below for better
understanding…
7
Count Leaf nodes
To count the number of leaves, we can simply traverse the nodes recursively until
we reach the leaf nodes (the size of the children vector becomes zero). Following
recursion, this is very similar to finding the height of the tree. Try to code it yourself
and for the solution refer to the solution tab of the same.
Traversals
Traversing the tree is the manner in which we move on the tree in order to access
all its nodes. There are generally 4 types of traversals in a tree:
We have already discussed level order traversal. Now let’s discuss the other
traversals.
In Preorder traversal, we visit the current node first(starting with root) and then
traverse the left sub-tree. After covering all nodes there, we will move towards the
right subtree and visit in a similar manner. Refer the code below:
8
Binary Trees
What is A Tree?
    ● A tree is a data structure similar to a linked list but instead of each node
       pointing simply to the next node in a linear fashion, each node points to
       several nodes.
    ● A tree is an example of a non- linear data structure.
    ● A tree structure is a way of representing the hierarchical nature of a
       structure in a graphical form.
Terminology Of Trees
    ● The root of a tree is the node with no parents. There can be at most one root
       node in a tree ( node A in the above example).
    ● An edge refers to the link from a parent to a child ( all links in the figure).
    ● A node with no children is called a l eaf node ( E, J, K, H, and I).
    ● The children nodes of the same parent are called siblings ( B, C, D are
       siblings of parent A, and E, F are siblings of parent B).
1
    ● The set of all nodes at a given depth is called the level of the tree ( B, C, and
       D are the same level). The root node is at level zero.
    ● The depth of a node is the length of the path from the root to the node
       (depth of G is 2, A
                          -> C –> G).
    ● The height of a node is the length of the path from that node to the deepest
       node.
    ● The height of a tree is the length of the path from the root to the deepest
       node in the tree.
    ● A (rooted) tree with only one node (the root) has a height of zero.
Binary Trees
    ● A generic tree with at most two child nodes for each parent node is known as
       a binary tree.
    ● A binary tree is made of nodes that constitute a left pointer, a r ight pointer,
       and a data element. The r oot pointer is the topmost node in the tree.
    ● The left and right pointers recursively point to smaller subtrees on either
       side.
    ● An empty tree is also a valid binary tree.
    ● A formal definition is: A b
                                  inary tree i s either empty (represented by a null
       pointer), or is made of a single node, where the left and right pointers
       (recursive definition ahead) each point to a b
                                                     inary tree.
2
Types of binary trees:
3
Complete binary tree: A
                        complete binary tree has all the levels filled except for
the last level, which has all its nodes as much as to the left.
A degenerate tree: I n a degenerate tree, each internal node has only one child.
The tree shown above is degenerate. These trees are very similar to linked-lists.
4
Balanced binary tree: A binary tree in which the difference between the depth
of the two subtrees of every node is at most one is called a balanced binary tree.
Sequential representation
    ● This is the most straightforward technique to store a tree data structure. An
       array is used to store the tree nodes.
    ● The number of nodes in a tree defines the size of the array.
    ● The root node of the tree is held at the first index in the array.
    ● In general, if a node is stored at the i th
                                                 location, then its l eft and r ight child
       are kept at ( 2i)th a
                               nd (2i+1)th l ocations in the array, respectively.
5
The array representation of the above binary tree is as follows:
As discussed above, we see that the left and right child of each node is stored at
locations 2*(nodePosition) and 2*(nodePosition)+1, respectively.
For Example, The location of node 3 in the array is 3. So its left child will be placed
at 2*3 = 6. Its right child will be at the location 2
                                                       *3 +1 = 7. As we can see in the
array, children of 3, which are 6 and 7, are placed at locations 6 and 7 in the array.
Note: The sequential representation of the tree is not preferred due to the massive
amount of memory consumption by the array.
6
In this type of model, a linked list is used to store the tree nodes. The nodes are
connected using the parent-child relationship like a tree. The following diagram
shows a linked list representation for a tree.
As shown in the above representation, each linked list node has three components:
 class BinaryTreeNode<T> {
        T data;                    // To store data
        BinaryTreeNode left; // for storing the reference to left pointer
        BinaryTreeNode right; // for storing the reference to right pointer
               // Constructor
        BinaryTreeNode(T data) {
               this.data = data;        // Initializes data of the node
7
              this.left = null;// initializes left and right pointers to null
              this.right = null;
        }
}
8
Input Binary Tree
We will be following the level-wise order for taking input and -1 denotes the n
                                                                               ull
pointer.
Count nodes
    ● Unlike the Generic trees, where we need to traverse the children vector of
       each node, in binary trees, we just have at most left and right children for
       each node.
    ● Here, we just need to recursively call on the right and left subtrees
       independently with the condition that the node pointer is not null.
    ● Follow the comments in the upcoming code for better understanding:
9
Binary tree traversal
Following are the ways to traverse a binary tree and their orders of traversal:
     ● Preorder traversal : ROOT -> LEFT -> RIGHT
     ● Postorder traversal : LEFT -> RIGHT-> ROOT
     ● Inorder traversal : LEFT -> ROOT -> RIGHT
Some examples of the above-stated traversal methods:
     ❖ Preorder traversal: 1
                            , 2, 4, 5, 3, 6, 7
     ❖ Postorder traversal:  4, 5, 2, 6, 7, 3, 1
     ❖ Inorder traversal:  4, 2, 5, 1, 6, 3, 7
Now, from this inorder traversal code, try to code preorder and postorder traversal
yourselves. If you get stuck, refer to the solution tab for the same.
10
Node with the Largest Data
In a Binary Tree, we must visit every node to figure out the maximum. So the idea is
to traverse the given tree and for every node return the maximum of 3 values:
     ● Node’s data.
     ● Maximum in node’s left subtree.
     ● Maximum in node’s right subtree.
11
Construct a binary tree from preorder and inorder
traversal
Input:
Preorder traversal : { 1, 2, 4, 3, 5, 7, 8, 6}
The idea is to start with the root node, which would be the first item in the preorder
sequence and find the boundary of its left and right subtree in the inorder array.
Now all keys before the root node in the inorder array become part of the left
12
subtree, and all the indices after the root node become part of the right subtree.
We repeat this recursively for all nodes in the tree and construct the tree in the
process.
Inorder: { 4, 2, 1, 7, 5, 8, 3, 6}
Preorder: {1, 2, 4, 3, 5, 7, 8, 6}
The root will be the first element in the preorder sequence, i.e. 1. Next, we locate
the index of the root node in the inorder sequence. Since 1 is the root node, all
nodes before 1 must be included in the left subtree, i.e., {4, 2}, and all the nodes
after one must be included in the right subtree, i.e. {7, 5, 8, 3, 6}. Now the problem
is reduced to building the left and right subtrees and linking them to the root node.
Preorder : { 2, 4} Preorder : { 3, 5, 7, 8, 6}
Using the above explanation you can easily create logic and code this. Refer
solution tab for solution code for this problem.
Now, try to construct the binary tree when inorder and postorder traversals are
given…
13
The diameter of a binary tree
The diameter of a tree (sometimes called the width) is the number of nodes on the
longest path between two child nodes. The diameter of the binary tree may pass
through the root (not necessary).
For example, the Below figure shows two binary trees having diameters 6 and 5,
respectively (nodes highlighted in blue color). The diameter of the binary tree
shown on the left side passes through the root node while on the right side, it
doesn't.
     1. The diameter could be the sum of the left height and the right height.
     2. It could be the left subtree’s diameter.
     3. It could be the right subtree’s diameter.
14
Now let’s check the code for this...
     ● Height function traverses each node once; hence time complexity will be
        O(n).
     ● Option2 and Option3 also traverse on each node, but for each node, we are
        calculating the height of the tree considering that node as the root node,
        which makes time complexity equal to O(n*h). (worst case with skewed trees,
        i.e., a type of binary tree in which all the nodes have only either one child or
        no child.) Here, h is the height of the tree, which could be O(n2).
This could be reduced if the height and diameter are obtained simultaneously,
which could prevent extra n traversals for each node. To achieve this, move
towards the other sections…
15
The Diameter of a Binary tree: Better Approach
In the previous approach, for each node, we were finding the height and diameter
independently, which was increasing the time complexity. In this approach, we will
find height and diameter for each node at the same time, i.e., we will store the
height and diameter using a pair class where the f irst pointer will be storing the
height of that node and the s econd pointer will be storing the diameter. Here, also
we will be using recursion.
Let’s focus on the base case: For a null tree, height and diameter both are equal to
0. Hence, pair class will store both of its values as zero.
Now, moving to H
                ypothesis: We will get the height and diameter for both left and
right subtrees, which could be directly used.
Finally, the induction step: Using the result of the Hypothesis, we will find the
height and diameter of the current node:
Now we will create a Pair class which will help us do this problem in better
complexity.
 class Pair {
     int first;
     int second;
     public Pair(int first, int second){
          this.first = first;
          this.second = second;
     }
 }
16
To access this pair class, we will use . first and .second pointers.
Follow the code below along with the comments to get a better grip on it...
Now, talking about the time complexity of this method, it can be observed that we
are just traversing each node once while making recursive calls and rest all other
operations are performed in constant time, hence the time complexity of this
program is O(n), where n is the number of nodes.
17
Binary Search Trees
Introduction
    ● These are the specific types of binary trees.
    ● These are inspired by the binary search algorithm.
    ● Time complexity on insertion, deletion, and searching reduces significantly as
       it works on the principle of binary search rather than linear search, as in the
       case of normal binary trees (will discuss it further).
1
Example: T
           he left tree is a binary search tree and the right tree is not a binary
search tree (This because the BST property is not satisfied at node 6. Its child with key 2,
is less than its parent with key 3, which is a violation, as all the nodes on the right
subtree of root node 3, must have keys greater than or equal to 3).
Example: Insert {45, 68, 35, 42, 15, 64, 78} in a BST in the order they are given.
1. Since the tree is empty, so the first node will automatically be the root node.
    2. Now, we have to insert 68, which is greater than 45, so it will go on the right
       side of the root node.
2
    3. To insert 35, we will start from the root node. Since 35 is smaller than 45, it
       will be inserted on the left side.
    4. Moving on to inserting 42. We can see that 42 < 45, so it will be placed on the
       left side of the root node. Now, we will check the same on the left subtree.
       We can see that 42 > 35 means 42 will be the right child of 35, which is still a
       part of the left subtree of the root node.
3
    5. Now, to insert 15, we will follow the same approach starting from the root
       node. Here, 15 < 45, which means 15 will be a part of the left subtree. As 15 <
       35, we will continue to move towards the left. As the left subtree of 35 is
       empty, so 15 will be the left child of 35.
    6. Continuing further, to insert 64, we know that 64 > root node’s data, but less
       than 68, hence 64 will be the left child of 68.
    7. Finally, we have to insert 78. We can see that 78 > 45 and 78 > 68, so 78 will
       be the right child of 68.
4
In this way, the data is stored in a BST.
Note:
    ● If we follow the i norder traversal of the final BST, we will get the sorted
        array.
    ● As seen above, to insert an element in the BST, we will be traversing till either
        the left subtree’s leaf node or right subtree’s leaf node, in the worst-case
        scenario.
    ● Hence, the t ime complexity of insertion for each node is O
                                                                   (log(H)) (where
        H is the height of the tree).
    ● For inserting N nodes, complexity will be O(N*log(H)).
Base Case:
    ● If the tree is empty, it means that the root node is NULL, then we will simply
        return NULL as the node is not present.
    ● Suppose if root’s data is equal to x
                                          , we don’t need to traverse forward in this
        tree as the target value has been found out, so we will simply return the r oot
        from here.
Small Calculation:
    ● In the case of BST, we’ll only check for the condition of binary search, i.e., if x
        is greater than the root’s data, then we will make a recursive call over the
        right subtree; otherwise, the recursive call will be made on the left subtree.
5
    ● This way, we are entirely discarding half the tree to be searched as done in
       case of a binary search. Therefore, the time complexity of searching is
       O(log(H)) (where H is the height of BST).
Recursive call: A
                 fter figuring out which way to move, we can make recursive calls
on either left or right subtree. This way, we will be able to search the given element
in a BST.
Note: The code written from the above insights can be accessed in the solution tab
in the question itself.
Approach: We will be using recursion and binary searching for the same.
Base case: If the root is NULL, it means we don’t have any tree to check upon, and
we can simply return.
Recursive call: R
                 ecursive call will be made as per the small calculation part onto
the left and right subtrees. In this way, we will be able to figure out all the elements
in the range.
Note: T
       ry to code this yourself, and refer to the solution tab in case of any doubts.
6
Problem Statement: Check BST
Given a binary tree, we have to check if it is a BST or not.
Approach: We will simply traverse the binary tree and check if the nodes satisfy the
BST Property. Thus we will check the following cases:
    ● If the node’s value is greater than the value of the node on it’s left.
    ● If the node’s value is smaller than the value of the node on its right.
Important Case: D
                  on’t just compare the direct left and right children of the node;
instead, we need to compare every node in the left and right subtree with the
node’s value. Consider the following case:
    ● Here, it can be seen that for root, the left subtree is a BST, and the right
       subtree is also a BST (individually).
    ● But the complete tree is not a BST. This is because a node with value 5 lies on
       the right side of the root node with value 20, whereas it should be on the left
       side of the root node.
    ● Hence, even though the individual subtrees are BSTs, it is also possible that
       the complete binary tree is not a BST. Hence, this third condition must also
       be checked.
To check over this condition, we will keep track of the minimum and maximum
values of the right and left subtrees correspondingly, and at last, we will simply
compare them with root.
7
    ● The left subtree’s maximum value should be less than the root’s data.
    ● The right subtree’s minimum value should be greater than the root’s data.
Now, let’s look at the Python code for this approach using this approach.
8
traversing that complete subtree’s height. Hence, if there are N nodes in total and
the height of the tree is H, then the time complexity will be O
                                                                 (N*H).
 class IsBSTReturn {     // Class to store data for each node of tree
       bool isBST;
       int minimum;
       int maximum;
 }
 ---------------------------------------------------------------------------
        // Small Calculation
        // Minimum and maximum values figured out side-by-side preventing
        //extra traversals
        int minimum = Math.min(root.data, Math.min(leftOutput.minimum,
                                                       rightOutput.minimum));
        int maximum = max(root.data, max(leftOutput.maximum,
                                                       rightOutput.maximum));
9
       // Checking out for the subtree if it’s a BST or not
       bool isBSTFinal = (root.data > leftOutput.maximum) && (root.data <=
                                 rightOutput.minimum) && leftOutput.isBST &&
                                                          rightOutput.isBST;
Time Complexity: Here, we are going to each node and doing a constant amount
of work. Hence, the time complexity for N
                                         n
                                           odes will be of O(N).
Approach: We will be checking on the left subtree, right subtree, and combined
tree without returning a tuple of maximum and minimum values. We will be using
the concept of default arguments over here. Check the code below:
// This time function is using default arguments for storing minimum and
// maximum value for each node
private bool isBST3Helper(BinaryTreeNode<Integer> root, int min, int max) {
      if (root == NULL) {        // Base case: Empty tree
             return true;
      }
// checking out the special condition first and returning false if not
satisfied
      if (root->data < min || root->data > max) {
             return false;
      }
// Checking out left and right subtrees
      bool isLeftOk = isBST3(root.left, min, root.data - 1);
      bool isRightOk = isBST3(root.right, root.data, max);
// Returning true if both are BST and false otherwise.
      return isLeftOk && isRightOk;
}
10
public bool isBST3(BinaryTreeNode<Integer> root) {
      return isBST3Helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
Time Complexity: Here also, we are just traversing each node and doing constant
work on each of them; hence time complexity remains the same, i.e. O(n).
Approach:
     ● Suppose we take the first element as the root node, then the tree will be
        skewed as the array is sorted.
     ● To get a balanced tree (so that searching and other operations can be
        performed in O(log(n)) time), we will be using the binary search technique.
     ● Figure out the middle element and mark it as the root.
     ● This is done so that the tree can be divided into almost 2 equal parts, as half
        the elements which will be greater than the root, will form the right subtree
        (These elements are present to its right).
     ● The elements in the other half, which are less than the root, will form the left
        subtree (These elements are present to its left).
     ● Just put root’s left child to be the recursive call made on the left portion of
        the array and root’s right child to be the recursive call made on the right
        portion of the array.
     ● Try it yourself and refer to the solution tab for code.
11
BST to Sorted LL
Problem statement: G
                    iven a BST, we have to construct a sorted linked list out of it.
Approach: As discussed earlier, the inorder traversal of the BST, provides elements
in a sorted fashion, so while creating the linked list, we will be traversing the tree in
inorder style.
     ● Base case: If the root is NULL, it means the head of the linked list is NULL;
        hence we return NULL.
     ● Small calculation: Left subtree will provide us the head of LL, and the right
        subtree will provide the tail of LL; hence root node will be placed after the LL
        obtained from the left subtree and right LL will be connected after the root.
Try it yourselves, and for code, refer to the solution tab of the corresponding
question.
Problem statement: G
                    iven a Binary tree, we have to return the path of the root
node to the given node.
For Example: R
              efer to the image below...
12
Approach:
     1. Start from the root node and compare it with the target value. If matched,
        then simply return, otherwise, recursively call over left and right subtrees.
     2. Continue this process until the target node is found and return if found.
     3. While returning, you need to store all the nodes that you have traversed on
        the path from the root to the target node in a vector.
     4. Now, in the end, you will be having your solution vector.
Now try to create logic and code the same problem with BST instead of a binary
tree.
BST Class
Here, we will be creating our own BST class to perform operations like insertion,
deletion, etc…
13
       ST {
class B
      BinaryTreeNode<Integer> root;          // root node
               if (node->data == data) {
                      return true;
               } else if (data < node->data) {
                      return hasData(data, node->left);
               } else {
                      return hasData(data, node->right);
               }
       }
You can observe that hasData() function has been declared under the private
section to prevent it from being manipulated, presenting the concept of data
abstraction.
Try insertion and deletion on your own, and in case of any difficulty, refer to the
hints and solution code below…
Insertion in BST:
We are given the root of the tree and the data to be inserted. Follow the same
approach to insert the data as discussed above using Binary search algorithm.
Check the code below for insertion:
14
public BinaryTreeNode<Integer> insert(int data, BinaryTreeNode<Integer> node){
      // Using Binary Search algorithm
      if (node == null) {
             BinaryTreeNode<Integer> newNode = new BinaryTreeNode<>(data);
             return newNode;
      }
Deletion in BST:
     ● Case 1: If the node to be deleted is the leaf node, then simply delete that
         node with no further changes and return NULL.
     ● Case 2: If the node to be deleted has only one child, then delete that node
         and return the child node.
     ●   Case 3: If the node to be deleted has both the child nodes, then we have to
         delete the node such that the properties of BST remain unchanged. For this,
         we will replace the node’s data with either the left child’s largest node or right
         child’s smallest node and then simply delete the replaced node.
15
     if (data > node.data) {
            node.right = deleteData(data, node.right);
            return node;
     } else if (data < node.data) {
            node.left = deleteData(data, node.left);
            return node;
     } else {      //found the node
            if (node.left == NULL && node.right == NULL) { //Leaf node
                   delete node;
                   return NULL;
            } else if (node.left == NULL) { //node having only left child
                   BinaryTreeNode<Integer> temp = node.right;
                   node.right = NULL;
                   delete node;
                   return temp;
            } else if (node.right == NULL) {//node having only right child
                   BinaryTreeNode<Integer> temp = node.left;
                   node.left = NULL;
                   delete node;
                   return temp;
            } else {      //node having both the childs
                   BinaryTreeNode<Integer> minNode = node.right;
                   while (minNode.left != NULL) { // replacing node with
                           minNode = minNode.left; // right subtree’s min
                   }
                   int rightMin = minNode.data;
                   node.data = rightMin;
     // now simply deleting that replaced node using recursion
                   node.right = deleteData(rightMin, node.right);
                   return node;
            }
     }
}
16
Hashmaps
Introduction to Hashmaps
Suppose we are given a string or a character array and asked to find the maximum
occurring character. It could be quickly done using arrays. We can simply create an
array of size 256, initialize this array to zero, and then, simply traverse the array to
increase the count of each character against its ASCII value in the frequency array.
In this way, we will be able to figure out the maximum occurring character in the
given string.
The above method will work fine for all the 256 characters whose ASCII values are
known. But what if we want to store the maximum frequency string out of a given
array of strings? It can’t be done using a simple frequency array, as the strings do
not possess any specific identification value like the ASCII values. For this, we will be
using a different data structure called hashmaps.
In hashmaps, the data is stored in the form of keys against which some value is
assigned. Keys and values don’t need to be of the same data type.
If we consider the above example in which we were trying to find the maximum
occurring string, using hashmaps, the individual strings will be regarded as keys,
and the value stored against them will be considered as their respective frequency.
1
 Key (datatype             Value
   = string)            (datatype =
                            int)
“abc” 3
“def” 2
“ab” 1
From here, we can directly check for the frequency of each string and hence figure
out the most frequent string among them all.
Note: O
        ne more limitation of arrays is that the indices could only be whole numbers but
this limitation does not hold for hashmaps.
The values are stored corresponding to their respective keys and can be invoked
using these keys. To insert, we can do the following:
● hashmap.put(key, value)
The functions that are required for the hashmaps are(using templates):
    ●   insert(k key, v value): To insert the value of type v against the key of type k.
    ●   get(k key): To get the value stored against the key of type k.
    ●   remove(k key): T
                        o delete the key of type k, and hence the value
        corresponding to it.
    1. Linked Lists: To perform insertion, deletion, and search operations in the
        linked list, the time complexity will be O(n) for each as:
            ○   For insertion, we will first have to check if the key already exists or not,
                if it exists, then we just have to update the value stored corresponding
                to that key.
            ○   For search and deletion, we will be traversing the length of the linked
                list.
2
    2. BST: We will be using some kind of a balanced BST so that the height remains
       of the order O(logN). For using a BST, we will need some sort of comparison
       between the keys. In the case of strings, we can do the same. Hence,
       insertion, search, and deletion operations are directly proportional to the
       height of the BST. Thus the time complexity reduces to O(logN) for each.
    3. Hash table: U
                    sing a hash table, the time complexity of insertion, deletion,
       and search operations, could be improved to O(1) (same as that of arrays).
       We will study this in further sections.
Inbuilt Hashmap
Note: B
       oth have similar functions and similar ways to use, differing only in the time
complexities. The time complexity of each of the operations(insertion, deletion, and
searching) in the T
                   reemap is O(logN), while in the case of Hashmap, they are O(1).
Hashmap:
       import java.util.HashMap;
    ● Syntax to declare:
3
                      ourmap.put(“abc”, 1);
          2. Searching: S
                         uppose we want to find the value stored in the hashmap
              against key “abc”, there are two ways to do so:
                 ○ As did in insertion like arrays, the same way we can figure out
                     the value stored against the corresponding key. Syntax:
Note: I f we try to access a key that is not present in the unordered_map, then there
are two different outcomes:
    ➢ If we are accessing the value using .get() function, then we will get an error
       specifying that we are trying to access the value that is not present in the
       map.
But what if we want to check if the key is present or not on the map? For that, we
will be using the .count() function, which tells if the key is present in the map or not.
It returns false, if not present, and true, if present
Syntax:
Note: W
       e can also check the size of the map by using .size() function, which returns the
number of key-value pairs present on the map.
Syntax:
       3. Deletion: Suppose we want to delete the key “ abc” f rom the map,
       we will be using .remove() function.
4
       Syntax:
ourmap.remove(“abc”);
Remove Duplicates
Problem statement: G
                    iven an array of integers, we need to remove the duplicate
values from that array, and the values should be in the same order as present in
the array.
For example: Suppose the given array is arr = {1, 3, 6, 2, 4, 1, 4, 2, 3, 2, 4, 6}, answer
should be {1, 3, 6, 2, 4}.
Approach: We will add unique values to the vector and then return it. To check for
unique values, start traversing the array, and for each array element, check if the
value is already present in the map or not. If not, then we will insert that value in
the vector and update the map; otherwise, we will proceed to the next index of the
array without making any changes.
5
Bucket Array and Hash function
Now, let’s see how to perform insertion, deletion, and search operations using hash
tables. Till now, we have seen that arrays are the fastest way to extract data as
compared to other data structures as the time complexity of accessing the data in
the array is O(1). So we will try to use them in implementing the hashmaps.
For example: Suppose, we want to store some names from the contact list in the
hash table, check out the following the image:
6
Suppose we want to store a string in a hash table, and after passing the string
through the hash function, the integer we obtain is equal to 10593, but the bucket
array’s size is only 20. So, we can’t store that string in the array as 10593, as this
index does not exist in the array of size 20.
To overcome this problem, we will divide the hashmap into two parts:
    ● Hash code
    ● Compression function
The first step to store a value into the bucket array is to convert the key into an
integer (this could be any integer irrespective of the size of the bucket array). This
part is achieved by using hashcode. For different types of keys, we will be having
different kinds of hash codes. Now we will pass this value through the compression
function, which will convert that value within the range of our bucket array’s size.
Now, we can directly store that key against the index obtained after passing
through the compression function.
But, there is still a possibility that after passing the key through from hash code,
when we give the same through the compression function, we can get the same
values of indices. For example, let s1 = “ab” and s2 = “cd”. Now using the above hash
function for p = 2, h1 = 292 and h2 = 298. Let the bucket size be equal to 2. Now, if
we pass the hash codes through the compression function, we will get:
7
Compression_function1 = 292 % 2 = 0
Compression_function2 = 298 % 2 = 0
Collision Handling
In closed hashing, each entry of the array will be a linked list. This means it should
be able to store every value that corresponds to this index. The array position holds
the address to the head of the linked list, and we can traverse the linked list by
using the head pointer for the same and add the new element at the end of that
linked list. This is also known as separate chaining.
On the other hand, in open addressing, we will check for the index in the bucket
array if it is empty or not. If it is empty, then we will directly insert the key-value pair
over that index. If not, then will we find an alternate position for the same. To find
the alternate position, we can use the following:
Where hf(a) is the original hash function, and f(i) is the i-th try over the hash
function to obtain the final position hi(a).
    1. Linear probing: In this method, we will linearly probe to the next slot until
        we find the empty index. Here, f(i) = i.
8
    2. Quadratic probing: A
                           s the name suggests, we will look for alternate i2
       positions ahead of the filled ones, i.e., f(i) = i2.
    3. Double hashing: A
                        ccording to this method, f(i) = i * H(a), where H(a) is some
       other hash function.
       ap <K, V> {
class M
      ArrayList<MapNode<K, V>> buckets;
      int size;
      int numBuckets;
      public Map() {
              numBuckets = 5;
              buckets = new ArrayList<>();
              for (int i = 0; i < numBuckets; i++) {
                     buckets.add(null);
              }
      }
9
       private int getBucketIndex(K key) {
             int hashCode = key.hashCode();
             return hashCode % numBuckets;
       }
10
               head = head.next;
         }
         return null;
}
         (n/b) < 0.7, this will ensure that each bucket does not contain too
         many entries in it.
     4. To make sure that load factor < 0.7, we can’t reduce the number of entries,
        but we can increase the bucket size comparatively to maintain the ratio. This
        process is known as R
                             ehashing.
This ensures that time complexity is on an average O(1) for insertion, deletion, and
search operations each.
11
Rehashing
Now, we will try to implement the rehashing in our map. After inserting each
element into the map, we will check the load factor. If the load factor’s value is
greater than 0.7, then we will rehash.
Note: W
       hile solving the problems, use the in-built hashmap only.
12
Tries and Huffman Coding
Introduction to Tries
To search a word in the hashmap, we again have to calculate the hashcode of the
string to be searched, and for that also, it would require O(string_length) time.
Similarly, for removing a word from the hashmap, we would have to calculate the
hashcode for that string. It would again require O(string_length) time.
For the same purpose, we can use another data structure known as tries.
1
Below is the visual representation of the trie:
Here, the node at the top named as the start is the root node of our n
                                                                        -ary tree.
Suppose we want to insert the word ARE i n the trie. We will begin from the root,
search for the first word A and then insert R
                                                as its child and similarly insert the
letter E
        . You can see it as the left-most path in the above trie.
2
Moving on to searching a word in the trie, for that also, we would have to traverse
the complete length of the string, which would take O(word_length) time.
Let us take an example. Suppose we want to search for the word DOT i n the above
trie, we will first-of-all search for the letter D
                                                   as the direct child of the start node and
then search for O and T and, then we will return true as the word is present in the
trie.
Consider another example AR, which we want to search for in the given trie.
Following the above approach, we would return true as the given word is present in
it. However ideally, we should return false as the actual word was ARE  and not A
                                                                                   R.
To overcome this, it can be observed that in the above trie, some of the letters are
marked with a bolder circle, and others are not. This boldness represents the
termination of a word starting from the root node. Hence, while searching for a
word, we will always be careful about the last letter that it should be bolded to
represent the termination.
Note: W
       hile insertion in a trie, the last letter of the word should be bolded as a
mark of termination of a word.
In the above trie, the following are all possibilities that can occur:
    ● ARE, AS
    ● DO, DOT
    ● NEW, NEWS, NOT
    ● ZEN
Here, to remove the word, we will simply unbold the terminating letter as it will
make that word invalid. For example: If you want to remove the string D
                                                                       O f rom the
above trie by preserving the occurrence of string DOT, then we will reach O
                                                                            and
then unbolden it. This way the word D
                                     O i s removed but at the same time, another
3
word DOT w
           hich was on the same path as that of word DO was still preserved in the
trie structure.
For removal of a word from trie, the time complexity is still O(word_length) as we
are traversing the complete length of the word to reach the last letter to unbold it.
It can be observed that using tries, we can improve the space complexity.
        rieNode {
 class T
       char data;       // To store data (character value: ‘A’ - ‘Z’)
       TreeNode[] children;  // To store the address of each child
       boolean isTerminal;       // it will be TRUE if the word terminates
                                  // at this character
4
       public TrieNode(char data) { // Constructor for values initialization
             this.data = data;
             children = new TrieNode[26];
             for(int i = 0; i < 26; i++) {
                  children[i] = null;
             }
             isTerminal = false;
       }
 }
Insert Function
To insert a word in a trie, we will use recursion. Suppose we have the following trie:
Recursion says that we need to work on a smaller problem, and the rest it will
handle itself. So, we will do it on the root node.
5
Note: P
       ractically, the functionality of bolding the terminal character is achieved
using the boolean i sTerminal v
                                ariable for that particular node. If this value is true
means that the node is the terminal value of the string, otherwise not.
Approach:
    ● Small Calculation: We will check if the root node has the first character of
         the string as one of its children or not. If not, then we will create one.
    ● Recursive call: W
                       e will tell the recursion to insert the remaining string in the
         subtree of our trie.
    ● Base Case: As the length of the string becomes zero, or in other words, we
         reach the NULL character, then we need to mark the isTerminal f or the last
         character as True.
6
        rie {
 class T
       TrieNode root;
        public Trie() {
              root = new TrieNode();
        }
                // Recursive call
                insertWord(child, word.substring(1));
        }
        // For user
        public void insertWord(String word) {
              insertWord(root, word);
        }
 }
Search in Tries
Objective: Create a search function which will get a string as its argument to be
searched in the trie and returns a boolean value. True if the string is present in the
trie and False if not.
7
Approach: We will be using the same process as that used during insertion. We will
call recursion over the root node after searching for the first character as its child. If
the first character is not present as one of the children of the root node, then we
will simply return false; otherwise, we will send the remaining string to the
recursion. When we reach the empty string, then check for the last character’s
isTerminal v
            alue; if it is true, m
                                    eans that word exists in our trie, and we will return
true from there otherwise, return false.
Try to code it yourselves, and for the code, refer to the solution tab of the same.
Approach: First-of-all we need to search for the word in the trie, and if found, then
we simply need to mark the i sTerminal value of the last character of the word to
false as that will simply denote that the word does not exist in our trie.
Check out the code below: (Nearly same as that of insertion, just a minor changes
which are explained along side)
8
       }
      removeWord(child, word.substring(1));
// Suppose if the character of the string doesn’t have any child and is a
part of the word to be deleted, then we can simply delete that node also as
it is not referencing to any other word in the trie
             / For user
             /
void removeWord(string word) {
       removeWord(root, word);
}
Types of Tries
    ● Compressed tries:
           ○ Majorly, used for space optimization.
           ○ We generally club the characters if they have at most one child.
           ○ General rule: Every node has at least two child nodes.
9
                                          Figure - 1
     ● Pattern matching:
          ○ Used to match patterns in the trie.
10
           ■ Example: In the figure-1 (shown above), if we want to search for
               pattern ben i n the trie, but the word b
                                                         end was present instead,
               using the normal search function, we would return false, as the
               last character n’ s isTerminal property was false, but in this trie,
               we would return true.
     ○ To overcome this problem of the last character’s identification, just
        remove the isTerminal property of the node.
     ○ In the figure-1, instead of searching for the pattern ben, we now want
        to search for the pattern en. Our trie would return false if e
                                                                        n is not
        directly connected to the root. But as the pattern is present in the
        word b
              en, it should return true. To overcome this problem, we need to
        attach each of the prefix strings to the root node so that every pattern
        is encountered.
           ■ For example: for the string b
                                           en, we would store b
                                                                 en, e
                                                                        n, n in
               the trie as the direct children of the root node.
11
Huffman Coding
Introduction
Huffman Coding is one approach followed for T
                                             ext Compression. Text
compression means reducing the space requirement for saving a particular text.
Here, each of the characters of the string takes 8 bits of memory. Since there are a
total of 15 characters in the string so the total memory consumption will be 15*8 =
120 bits. Let’s try to compress its size using the Huffman Algorithm.
12
     1. Begin with calculating the frequency of each character value in the given
        string.
     2. Sort the characters in ascending order concerning their frequency and store
        them in a priority queue, say Q
                                       .
     3. Each character should be considered as a different leaf node.
     4. Make an empty node, say z . The left child of z is marked as the minimum
        frequency and the right child, the second minimum frequency. The value of z
        is calculated by summing up the first two frequencies.
13
        Here, “.” denote the internal nodes.
     5. Now, remove the two characters with the lowest frequencies from the
        priority queue Q a
                           nd append their sum to the same.
     6. Simply insert the above node z to the tree.
     7. For every character in the string, repeat steps 3 to 5.
14
     8. Assign 0 to the left side and 1 to the right side except for the leaf nodes.
15
     The size table is given below:
A 5 11 5*2 = 10
B 1 100 1*3 = 3
C 6 0 6*1 = 6
D 3 101 3*3 = 9
     To decode the code, simply traverse through the tree (starting from the root)
     to find the character. Suppose we want to decode 101, then:
16
Time Complexity:
In the case of encoding, inserting each character into the priority queue takes
O(log n) time. Therefore, for the complete array, the time complexity becomes
O(nlog(n)).
17
Dynamic Programming - 1
Introduction
Suppose we need to find the nth Fibonacci number using recursion that we have
already found out in our previous sections. Let’s directly look at its code:
    ● Here, for every n, we need to make a recursive call to f (n-1) and f(n-2).
    ● For f(n-1), we will again make the recursive call to f (n-2) and f(n-3).
    ● Similarly, for f (n-2), recursive calls are made on f(n-3) and f(n-4) until we
       reach the base case.
    ● The recursive call diagram will look something like shown below:
1
(20 + 21 + 22 + ... + 2n -1) * k   ≃   2n k
    ● Hence, it means time complexity will be O(2n).
    ● We need to improve this complexity. Let’s look at the example below for
       finding the 6th F
                          ibonacci number.
Important Observation:
    ● We can observe that there are repeating recursive calls made over the entire
       program.
    ● As in the above figure, for calculating f(5), we need the value of f(4) (first
       recursive call over f(4)), and for calculating f(6), we again need the value of
       f(4)(second similar recursive call over f(4)).
    ● Both of these recursive calls are shown above in the outlining circle.
    ● Similarly, there are many other values for which we are repeating the
       recursive calls.
    ● Generally, while recursing, there are repeated recursion calls, which
       increases the time complexity of the program.
To overcome this problem, we will store the output of previously encountered
values(preferably in arrays as these are most efficient to traverse and extract data).
Next time whenever we will be making the recursive calls over these values, we will
2
directly consider their already stored outputs and then use these in our calculations
instead of calculating them over again.
This way, we can improve the running time of our code. This process of storing
each recursive call’s output and then using them for further calculations preventing
the code from calculating these again is called M
                                                 emoization.
    ● To achieve this in our example we will simply take an answer array, initialized
       to -1.
    ● Now while making a recursive call, we will first check if the value stored in
       this answer array corresponding to that position is -1 or not.
    ● If it is -1, it means we haven’t calculated the value yet and need to proceed
       further by making recursive calls for the respective value.
    ● After obtaining the output, we need to store this in the answer array so that
       next time, if the same value is encountered, it can be directly used from this
       answer array.
3
        // save the output for future use
         ans[n] = a + b;
4
Again, if we observe carefully, we can see that for any number, we are not able to
make a recursive call on the right side of it. This means that we can make at most
5+1 = 6 (n+1) unique recursive calls which reduce the time complexity to O(n) which
is highly optimized as compared to simple recursion.
Summary
    ● Memoization is a t op-down approach, w
                                             here we save the previous answers
       so that they can be used to calculate future answers and improve the time
       complexity to a greater extent.
    ● Finally, what we are doing is making a recursive call to every index of the
       answer array and calculating the value for it using previous outputs stored.
    ● Recursive calls terminate over the base case, which means we are already
       aware of the answers that should be stored in the base case’s indexes.
    ● In cases of Fibonacci numbers, these indexes are 0 and 1 as f(0) = 0 and f(1) =
       1. So we can directly allot these two values to our answer array and then use
       these to calculate f(2), which is f(1) + f(0), and so on for every other index.
    ● This can be simply done iteratively by running a loop from i = (2 to n).
    ● Finally, we will get our answer at the 5th i ndex of the answer array as we
       already know that the i-th index contains the answer to the i-th value.
We are first trying to figure out the dependency of the current value on the
previous values and then using them calculating our new value. Now, we are
looking for those values which do not depend on other values, which means they
are independent (the base case’s values as these are the smallest problems about
which we are already aware of). Finally, we will follow a bottom-up approach t o
reach the desired index. This approach of converting recursion into iteration is
known as Dynamic programming(DP).
5
Let us now look at the DP code for calculating the nth Fibonacci number:
        eturn ans[n];
       r                        // final answer
}
Note: G
       enerally, memoization is a recursive approach, and DP is an iterative
approach.
6
    3. If its divisible by 3, divide by 3. (if n%3 == 0, then n = n / 3 ).
Example 1: F
             or n = 4:
STEP-1: n = 4/2 = 2
STEP-2: n = 2/2 = 1
Example 2: F
             or n = 7:
STEP-1: n = 7 - 1 = 6
STEP-2: n = 6/3 = 2
STEP-3: n = 2/2 = 1
Approach: We are only allowed to perform the above three mentioned ways to
reduce any number to 1.
Let’s start thinking about the brute-force approach first, i.e., recursion.
We will make a recursive call to each of the three steps keeping in mind that for
dividing by 2, the number should be divisible by 2 and similarly for 3 as given in the
question statement. After that take the minimum value out of the three obtained
and simply add 1 to the answer for the current step itself. Thinking about the base
case, we can see that on reaching 1, simply we have to return 0 as it is our
destination value. Let’s now look at the code:
7
 public static int minSteps(int n){
      // base case
       if (n <= 1)
             return 0;
                nteger.MAX_VALUE;
       int y = I                            / Initialise to infinity to check
                                            /
       nt z = I
      i          nteger.MAX_VALUE;      // divisibility by 2 or 3
Now, we have to check if we can optimize the code that we have written. It can be
done using memoization. But, for memoization to apply, we need to check if there
are any overlapping sub-problems so that we can store the previous values to
obtain the new ones. To check this let’s dry run the problem for n = 12:
(Here X represents that the calls are not feasible as the number is not divisible by
either of 2 or 3)
8
Here, if we blindly make three recursive calls at each step, then the time complexity
will approximately be O(3n).
From the above, it is visible that there are repeating sub-problems. Hence, this
problem can be optimized using memoization.
Now, we need to figure out the number of unique calls, i.e., how many answers we
are required to save. It is clear that we need at most n+1 responses to be saved,
starting from n = 0, and the final answer will be present at index n.
The code will be nearly the same as the recursive approach; just we will not be
making recursive calls for already stored outputs. Follow the code and comments
below:
9
      if (memo[n] != -1)
            return memo[n];
 Given an integer N, find and return the count of minimum numbers, the
 sum of whose squares is equal to N.
10
 That is, if N is 4, then we can represent it as : {1^2 + 1^2 + 1^2 + 1^2} and {2^2}.
 The output will be 1, as 1 is the minimum count of numbers required. (x^y
 represents x raised to the power y.)
     ● 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1
     ● 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 1^1 + 2^2
     ● 1^1 + 1^1 + 1^1 + 1^1 + 2^2 + 2^2
     ● 2^2 + 2^2 + 2^2
Hence, the minimum count is obtained from the 4-th option. Therefore, the answer
is equal to 3.
Approach: First-of-all, we need to think about breaking the problems into two
parts, one of which will be handled by recursion and the other one will be handled
by us(smaller sub-problem). We can break the problem as follows:
And so on…
     ● In the above figure, it is clear that in the left subtree we are making ourselves
        try over a variety of values that can be included as a part of our solution.
     ● The right subtree’s calculation will be done by recursion.
     ● Hence, we will just handle the i2 part,
                                           
                                                 and (n-i2) will be handled by recursion.
     ● By now, we have got ourselves an idea of solving this problem, the only
        thinking left is the loop’s range on which we will be iterating, i.e., the values
        of i f or which we will be deciding to consider while solving or not.
11
     ● As the maximum value up to which i can be pushed, to reach n is √n as
        (√n*√n = n). Hence, we will be iterating over the range ( 1 to √n) and do
        consider each possible way by sending ( n-i2) over the recursion.
     ● This way we will get different subsequences and as per the question, we will
        simply return the minimum out of it.
This problem is left for you to try out using all the three approaches and for code,
refer to the solution tab of the same.
For Example: I n the figure below, the left side represents the height h, and the
right side represents the possible binary trees along with the count.
Here for h = 1, the answer is 1. For h = 2, the answer is 3. For h = 3, the answer is 15.
Approach: Suppose we have h = 3, so at level 3 there are four nodes and each
node has two options, either it can be included or excluded from the binary tree,
12
hence in total, we have 24 =
                              16 possibilities. Here, we need to exclude the possibility
of the case when none out of 4 is present. Hence, the remaining options are 16-1 =
15. We can think that this approach could be efficient as we just need to know the
number of nodes at the last level, and then we can simply apply the above formula.
Now, consider for h = 4, where the last level has got eight nodes, so according to
the above approach, the answer could be 28 - 1 = 255 ways, but the solution for h =
4 is 315. Let’s look at the cases which we missed. One of the examples could be:
Till now, we were only working over the last level, but in the above example, if we
remove the nodes from upper levels, then also the binary tree could remain
balanced.
Let’s now think about implementing it using recursion on trees. If the height of the
complete binary tree is h, that means the height of its left and right subtrees
individually is at most h-1. So if the height of the left subtree is h-1, then the height
of the right subtree could be any among {h-1, h-2} and vise versa.
13
Initially, we were given the problem of finding the output for height h. Now we have
reduced the same to tell the output of height h-1 and h-2. Finally, we just need to
figure out these counts, add them, and return.
          Possible Cases:
     ●   Both h-1                =        x*x
     ●   h-1 and h-2         =          x*y
     ●   h-2 and h-1         =          y*x
14
       int temp1 = (int)(((long)(x)*x) % mod);
       int temp2 = (int)((2* (long)(x) * y) % mod);
       int ans = (temp1 + temp2) % mod;
       return ans;
}
Time Complexity: If we observe this function, then we can find it very similar to the
pattern of the Fibonacci number. Hence, the time complexity is O(2h).
Now, try to reduce the time complexity of the code using memoization and DP by
yourselves and for solution refer to the solution tab of the problem.
15
Dynamic Programming- 2
Let us now move to some advanced-level DP questions, which deal with 2D arrays.
For example, T
              he given input is as follows-
 3   4
 3    4 1   2 
 2     1 8   9  
 4      7 8   1   
The path that should be followed is 3
                                     -> 1 -> 8 -> 1. Hence the output is 13.
Approach:
      ● Thinking about the r ecursive approach to reach from the cell ( 0, 0) to ( m-1,
               n-1), we need to decide for every cell about the direction to proceed out of
               three.
      ● We will simply call recursion over all the three choices available to us, and
               finally, we will be considering the one with minimum cost and add the
               current cell’s value to it.
      ● Let’s now look at the recursive code for this problem:
1
public int minCostPath(int[][] input, int m, int n, int i, int j) {
      // Base case: reaching out to the destination cell
      if(i == m- 1 && j == n- 1) {
              return input[i][j];
      }
       if(i >= m || j >= n) { // checking for within the constraints or not
              return Integer.MAX_VALUE; //if not, returning +infinity so that
       }                            // it will not be considered as the answer
       // Recursive calls
       int x = minCostPath(input, m, n, i, j+1); // Towards right direction
       int y = minCostPath(input, m, n, i+1, j+1);// Towards diagonal
       int z = minCostPath(input, m, n, i+1, j); // Towards down direction
       // Small Calculation: figuring out the minimum value and then adding
      // current cells value to it
       int ans = Math.min(x, Math.min(y, z)) + input[i][j];
       return ans;
}
Let’s dry run the approach to see the code flow. Suppose, m = 4 and n = 5; then the
recursive call flow looks something like below:
2
Here, we can see that there are many repeated/overlapping recursive calls(for
example: ( 1,1) is one of them), leading to exponential time complexity, i.e., O(3n). If
we store the output for each recursive call after their first occurrence, we can easily
avoid the repetition. It means that we can improve this using memoization.
      // Small Calculation
      int a = Math.min(x, Math.min(y, z)) + input[i][j];
3
     return a;
 }
Here, we can observe that as we move from the cell (0,0) to (m-1, n-1), in general,
the i-th row varies from 0 to m-1, and the j-th column runs from 0 to n-1. Hence, the
unique recursive calls will be a maximum of (m-1) * (n-1), which leads to the time
complexity of O
               (m*n).
To get rid of the recursion, we will now proceed towards the DP approach.
The DP approach is simple. We just need to create a solution array (lets name that
as ans), where:
ans[i][j] = minimum cost to reach from (i, j) to (m-1, n-1)
Now, initialize the last row and last column of the matrix with the sum of their
values and the value, just after it. This is because, in the last row or column, we can
reach there from their forward cell only (You can manually check it), except the cell
(m-1, n-1), which is the value itself.
 ans[m-1][n-1] = cost[m-1][n-1]
 ans[m-1][j] = ans[m-1][j+1] + cost[m-1][j] (for 0 < j < n)
 ans[i][n-1] = ans[i+1][n-1] + cost[i][m-1] (for 0 < i < m)
4
Next, we will simply fill the rest of our answer matrix by checking out the minimum
among values from where we could reach them. For this, we will use the same
formula as used in the recursive approach:
Finally, we will get our answer at the cell (0, 0), which we will return.
The code looks as follows:
ans[m-1][n-1] = input[m-1][n-1];
        // Last row
        for(int j = n - 2; j >= 0; j--) {
               ans[m-1][j] = input[m-1][j] + ans[m-1][j+1];
        }
        // Last col
        for(int i = m-2; i >= 0; i--) {
               ans[i][n-1] = input[i][n-1] + ans[i+1][n-1];
        }
Note: T
       his is the bottom-up approach to solve the question using DP.
5
Problem Statement: LCS (Longest Common Subsequence)
 The longest common subsequence (LCS) is defined as the longest
 subsequence that is common to all the given sequences, provided that the
 elements of the subsequence are not required to occupy consecutive
 positions within the original sequences.
Note: S
       ubsequence is a part of the string which can be made by omitting none or
some of the characters from that string while maintaining the order of the
characters.
If s1 and s2 are two given strings then z is the common subsequence of s1 and s2, if
z is a subsequence of both of them.
Example 1:
 s1 = "abcdef"
 s2 = " xyczef"
Here, the longest common subsequence is "cef"; hence the answer is 3 (the length
of LCS).
Example 2:
 s1 = "ahkolp"
 s2 = " ehyozp"
Approach: Let’s first think of a brute-force approach using r ecursion. For LCS, we
have to match the starting characters of both strings. If they match, then simply we
can break the problem as shown below:
 s1 = "x|yzar"
 s2 = " x|qwea"
6
The rest of the LCS will be handled by recursion. But, if the first characters do not
match, then we have to figure out that by traversing which of the following strings,
we will get our answer. This can’t be directly predicted by just looking at them, so
we will be traversing over both of them one-by-one and check for the maximum
value of LCS obtained among them to be considered for our answer.
For example:
Suppose, string s
                 = "xyz" and string t
                                        = "zxay".
We can see that their first characters do not match so that we can call recursion
over it in either of the following ways:
A=
B=
C=
LCS = max(A, B, C)
Check the code below and follow the comments for a better understanding.
7
 public int lcs(string s, string t) {
       // Base case
       if(s.size() == 0 || t.size() == 0) {
                return 0;
       }
       // Recursive calls
       if(s[0] == t[0]) {
                 return 1 + lcs(s.substr(1), t.substr(1));
       }
       else {
                 int a = lcs(s.substring(1), t); // discarding the first
                                                 // character of string s
                 int b = lcs(s, t.substring(1));// discarding the first
                                                 // character of string t
                 int c = lcs(s.substring(1), t.substring(1));// discarding the
                                                    // first character of both
                return Math.max(a, Math.max(b, c)); // Small calculation
       }
 }
Here, as for each node, we will be making three recursive calls, so the time
complexity will be exponential and is represented as O
                                                      (2m+n), where m and n are
8
the lengths of both strings. This is because, if we carefully observe the above code,
then we can skip the third recursive call as it will be covered by the two others.
Consider the diagram below, where we are representing the dry run in terms of its
length taken at each recursive call:
As we can see there are multiple overlapping recursive calls, the solution can be
optimized using m
                 emoization followed by DP. So, beginning with the memoization
approach, as we want to match all the subsequences of the given two strings, we
have to figure out the number of unique recursive calls. For string s, we can make
at most l ength(s) recursive calls, and similarly, for string t, we can make at most
length(t) recursive calls, which are also dependent on each other’s solution. Hence,
our result can be directly stored in the form of a 2-dimensional array of size
(length(s)+1) * (length(t) + 1) as for string s, we have 0 to length(s) possible
combinations, and the same goes for string t.
So for every index ‘i’ in string s and ‘j’ in string t , we will choose one of the following
two options:
9
     1. If the character s[i] matches t [j], the length of the common subsequence
        would be one plus the length of the common subsequence till the i-1 and j-1
        indexes in the two respective strings.
     2. If the character s[i] does not match t[j], we will take the longest subsequence
        by either skipping i-th or j-th character f rom the respective strings.
Hence, the answer stored in the matrix will be the LCS of both strings when the
length of string s will be ‘i’ and the length of string t will be ‘j’.
         // Base case
         if(m == 0 || n == 0) {
                return 0;
         }
         int ans;
         // Recursive calls
         if(s[0] == t[0]) {
                ans = 1 + lcs_mem(s.substring(1), t.substring(1), output);
         }
         else {
                int a = lcs_mem(s.substring(1), t, output);
                int b = lcs_mem(s, t.substring(1), output);
                int c = lcs_mem(s.substring(1), t.substring(1), output);
                ans = Math.max(a, Math.max(b, c));
         }
// Return ans
10
       return ans;
}
11
                            int c = output[i-1][j-1];
                            output[i][j] = Math.max(a, Math.max(b, c));
                     }
              }
        }
        return output[m][n];        // final answer
}
Time Complexity: We can see that the time complexity of the DP and memoization
approach is reduced to O
                        (m*n) where m
                                        and n
                                                are the lengths of the given strings.
Edit Distance
Problem statement: G
                    iven two strings s and t of lengths m and n respectively,
find the Edit Distance between the strings. Edit Distance of two strings is the
minimum number of steps required to make one string equal to another. To do
so, you can perform the following three operations only :
     ● Delete a character
     ● Replace a character with another one
     ● Insert a character
Example 1:
s1 =
      “but”
s2 = “bat”
Answer: 1
Explanation: W e just need to replace ‘a’ with ‘u’ to transform s2 to s1.
Example 2:
s1 = “cbda”
s2 = “abdca”
Answer: 2
Explanation: W e just need to replace the first ‘a’ with ‘c’ and delete the second ‘c’.
12
Example 3:
s1 = “ppsspqrt”
s2 = “passpot”
Answer: 3
Explanation: W  e just need to replace first ‘a’ with ‘p’, ‘o’ with ‘q’, and insert ‘r’.
Approach: Let’s think about this problem using r ecursion first. We need to apply
each of the three operations on each character of s2 to make it similar to s1 and
then find the minimum among them.
Let’s assume index1 and index2 point to the current indexes of s1 and s2
respectively, so we have two options at every step:
     1. If the strings have the same character, we can recursively match for the
        remaining lengths of the strings.
     2. If the strings do not match, we start three new recursive calls representing
        the three edit operations, as mentioned in the problem statement. Consider
        the minimum count of operations among the three recursive calls.
13
From here, it is clear that the time complexity is again exponential, which is O(3m+n),
where m and n are the lengths of the given strings.
Also, we can see the overlapping/repeated recursive calls(for example: (2,2) is one
of them), which means this problem can be further solved using memoization.
This problem is somehow similar to the LCS problem. We will be using a similar
approach to solve this problem too. The answer to each recursive call will be stored
in a 2-Dimensional array of size (m+1)*(n+1), and the final solution will be obtained
at index (m,n) as each cell will be storing the answer for the given m length of s1
and n length of s2. Try to code it yourself.
Time Complexity: As there are (m+1)*(n+1) number of unique calls, hence the time
complexity becomes O(m*n), which is better than the recursive approach.
We have already discussed the basic requirements like output array size, final
output’s position, and the value stored at each position of the output array in the
memoization approach. We have already figured out that this problem is similar to
the LCS question. So try to code it yourself. Refer to the solution tab for the same.
14
Problem Statement: Knapsack
 Given the weights and values of ‘N’ items, we are asked to put these items
 in a knapsack, which has a capacity ‘C’. The goal is to get the maximum
 value from the items in the knapsack. Each item can only be selected once,
 as we don’t have multiple quantities of any item.
For example:
If we consider a particular weight ‘w’ from the array of weights with value ‘v’ and the
total capacity was ‘C’ with initial value ‘Val’, then the remaining capacity of the
knapsack becomes ‘C-w’, and the value becomes ‘Val + v’.
15
Let’s look at the recursive code for the same:
       // Recursive calls
       //1. Considering the weight
       int x = knapsack(weight, values, i+1, n, maxWeight - weight[i]) +
                                                                  values[i];
       // 2. Skipping the weight and moving forward
       int y = knapsack(weight, values, i+1, n, maxWeight) + values[i];
Now, the memoization and DP approach is left for you to solve. For the code, refer
to the solution tab of the same. Also, figure out the time complexity for the same by
running the code over some examples and by dry running it.
16
Graphs- 1
Introduction
Ag
  raph is a p
               air G
                       = (V, E), where V
                                               is a set whose elements are called v
                                                                                     ertices, and
E is a set of two sets of vertices, whose elements are called e dges.
For example: Suppose there is a road network in a country, where we have many
cities, and roads are connecting these cities. There could be some cities that are not
connected by some other cities like an island. This structure seems to be
non-uniform, and hence, we can’t use trees to store it. In such cases, we will be
using graphs. Refer to the figure for better understanding.
1
Relationship between trees and graphs:
    ● A tree is a special type of graph in which we can reach any node to any other
       node using some path, unlike the graphs where this condition may or may
       not hold.
    ● A tree does not have any cycles in it whereas a graph may or may not contain
       a cycle.
Graphs Terminology
    ● Nodes are named vertices, and the connections between them are called
       edges.
    ● Two vertices are said to be a
                                   djacent if there exists a direct edge connecting
       them.
    ● The degree o
                   f a node is defined as the number of edges that are incident to
       it.
    ● Ap
        ath i s a collection of edges through which we can reach from one node to
       the other node in a graph.
    ● A graph is said to be c
                             onnected if there is a path between every pair of
       vertices.
    ● If the graph is not connected, then all the connected subsets of the graphs
       are called connected components. Each component is connected within the
       self, but two different components of a graph are never connected.
    ● The minimum number of edges in a graph can be zero, which means a graph
       could have no edges as well.
    ● The minimum number of edges in a connected graph will be ( N-1), where N
                                                                               
       is the number of nodes.
2
    ● In a complete graph (where each node is connected to every other node by a
       direct edge), there are N C2 n
                                         umber of edges means (N * (N-1)) / 2 edges,
       where n is the number of nodes.
    ● This is the maximum number of edges that a graph can have.
    ● Hence, if an algorithm works on the terms of edges, let’s say O(E), where E
                                                                                    is
       the number of edges, then in the worst case, the algorithm will take O
                                                                             (N2)
       time, where N
                     is the number of nodes.
Graphs Implementation
Suppose the graph is as follows:
    2. Adjacency list: We will create an array of vertices, but this time, each vertex
       will have its list of edges connecting this vertex to another vertex. Now to
       check for a particular edge, we can take any one of the nodes and then check
3
       in its list if the target node is present or not. This will take O(n) work to figure
       out a particular edge.
    3. Adjacency matrix: Here, we will create a 2D array where the cell (i, j) will
       denote an edge between node i and node j. It is the most reliable method to
       implement a graph in terms of ease of implementation. We will be using the
       same throughout the session. The major disadvantage of using the adjacency
       matrix is vast space consumption compared to the adjacency list, where each
       node stores only those nodes that are directly connected to them. For the
       above graph, the adjacency matrix looks as follows:
4
DFS - Adjacency matrix
Here, if we have n vertices(labelled: 0 to n-1). Then we will be asking the user for the
number of edges. We will run the loop from 0 to the number of edges, and at each
iteration, we will take input for the two connected nodes and correspondingly
update the adjacency matrix. Let’s look at the code for better understanding.
public static void print(int[][] edges, int n, int sv, boolean[] visited){
  System.out.println(sv);
  visited[sv] = true;          // marked the starting vertex true
  for(int i=0; i<n; i++){// Running the loop over all n nodes and checking
                              // if there is an edge between sv and i
     if(i==sv){
          continue;
      }
      if(edges[sv][i]==1){ // As the edge is found, we then checked if the
                              // node i was visited or not
          if(visited[i]){
              continue;
           }
           print(edges, n, i, visited); // Otherwise, recursively called over
                                         // node i taking it as starting vertex
       }
   }
}
5
        int s = s.nextInt();   // Nodes f and s having edges between them
        edges[f][s]=1;                             // marking f to s as 1
        edges[s][f]=1;                           // also, marking s to f as 1
    }
    boolean[] visited = new bool[n]; // this is used to keep the track
                                    // of nodes if we have visited them or not.
    for(int i=0; i<n; i++){
       visited[i]=false; // Marking all nodes as false which means not visited
     }
Here, we are starting from a node, going in one direction as far as we can, and then
we return and do the same on the previous nodes. This method of graph traversal
is known as the depth-first search (DFS). As the name suggests, this algorithm
6
goes into the depth first and then recursively does the same in other directions.
Follow the figure below, for step-by-step traversal using DFS.
BFS Traversal
Breadth-first search(BFS) is an algorithm where we start from the selected node
and traverse the graph level-wise or layer-wise, thus exploring the neighbor nodes
(which are directly connected to the starting node), and then moving on to the next
level neighbor nodes.
    ● We first move horizontally and visit all the nodes of the current layer.
    ● Then move to the next layer.
7
This is an iterative approach. We will use the queue data structure to store the child
nodes of the current node and then pop out the current node. This process will
continue until we have covered all the nodes. Remember to put only those nodes in
the queue which have not been visited.
8
public void BFS(int[][] edges, int n) {
      boolean[] visited = new boolean[n]; // visited array
      for (int i = 0; i < n; i++) {
             visited[i] = false;
      }
Consider the dry run over the example graph below for a better understanding of
the same:
9
BFS & DFS for Disconnected Graph
Till now, we have assumed that the graph is connected. For the disconnected graph,
there will be a minor change in the above codes. Just before calling out the print
functions, we will run a loop over each node and check if that node is visited or not.
If not visited, then we will call a print function over that node, considering it as the
starting vertex. In this way, we will be able to cover up all the nodes of the graph.
Consider the same for the BFS function. Just replace this function in the above code
to make it work for the disconnected graph too.
       for (int i = 0; i < n; i++) {         // run a loop over each node
               if (!visited[i]) {   // if a node is not visited, then called print()
                     printBFS(edges, n, i, visited); //on it taking it as starting vtx
                }
       }
 }
10
Has Path
Problem statement: G
                    iven an undirected graph G(V, E) and two vertices v1 and
v2(as integers), check if there exists any path between them or not. Print true or
false. V is the number of vertices present in graph G, and vertices are numbered
from 0 to V-1. E is the number of edges present in graph G.
Approach: This can be simply solved by considering the vertex v1 as the starting
vertex and then run either BFS or DFS as per your choice, and while traversing if we
reach the vertex v2, then we will simply return true, otherwise return false.
This problem has been left for you to try yourself. For code, refer to the solution tab
of the same.
4   4
0     1
0       3
1         2
2           3
1             3
11
The output should be:
3 0 1
Explanation: H
              ere, v1 = 1 and v2 = 3. The connected vertex pairs are (0, 1), (0, 3), (1,
2) and (2, 3). So, according to the question, we have to print the path from vertex v1
to v2 in reverse order using DFS only; hence the path comes out to be {3, 0, 1}.
Approach: We have to solve this problem by using DFS. Suppose, if the start and
end vertex are the same, then we simply need to put the start in the solution array
and return the solution array. If this is not the case, then from the start vertex, we
will call DFS on the direct connections of the same. If none of the paths leads to the
end vertex, then we do not need to push the start vertex as it is neither directly nor
indirectly connected to the end vertex, hence we will simply return NULL. In case
any of the neighbors return a non-null entry, it means that we have a path from
that neighbor to the end vertex, hence we can now insert the start vertex into the
solution array.
Try to code it yourself, and for the answer, refer to the solution tab of the same.
 Problem: It is the same problem as the above, just we have to code the same
 using BFS.
Approach: Using BFS will provide us the shortest path between the two vertices.
We will use the queue over here and do the same until the end vertex gets inserted
into the queue. Here, the problem is how to figure out the node, which led us to the
end vertex. To overcome this, we will be using a map. In the map, we will store the
resultant node as the index, and its key will be the node that led it into the queue.
12
For example: If the graph was such that 0 was connected to 1 and 0 was connected
to 2, and currently, we are on node 0 such that node 1 and node 2 are not visited.
So our map will look as follows:
1 0
2 0
This way, as soon as we reach the end vertex, we can figure out the nodes by
running the loop until we reach the start vertex as the key value of any node.
Try to code it yourselves, and for the solution, refer to the specific tab of the same.
Is connected?
Problem statement: G
                    iven an undirected graph G(V, E), check if the graph G is a
connected graph or not. V is the number of vertices present in graph G, and
vertices are numbered from 0 to V-1. E is the number of edges present in graph
G.
13
Example 1: Suppose the given input is:
 4   4
 0     1
 0       3
 1         2
 2           3
 1             3
 4   3
 0     1
 1       3
 0         3
14
Problem statement: Return all Connected Components
Given an undirected graph G(V, E), find and print all the connected components of
the given graph G. V is the number of vertices present in graph G, and vertices are
numbered from 0 to V-1. E is the number of edges present in graph G.
You need to take input in the main and create a function that should return all
the connected components. And then print them in the main, not inside a
function.
Print different components in a new line. And each component should be printed
in increasing order (separated by space). The order of different components
doesn't matter.
4   3
0     1
1       3
0         3
The output should be:
0 1 3
2
Explanation:  As we can see that {0, 1, 3} is one connected component, and {2} is
the other one. So, according to the question, we just have to print the same.
Approach: For this problem, start from vertex 0 and traverse until vertex n-1. If the
vertex is not visited, then run DFS/BFS on it and keep track of all the connected
vertices through that node. This way, we will get all the distinct connected
components, and we can print them at last.
This problem is left for you to solve. For the code, refer to the solution tab of the
same.
15
Weighted and Directed Graphs
Directed graphs:  These are generally required when we have one-way routes.
Suppose you can go from node A to node B, but you cannot go from node B to
node A. Another example could be social media (like Twitter) if you are following
someone, it does not mean that they are following you too.
edges[i][j] = 1;
edges[j][i] = 1 ;
But, in the case of a directed graph, we will just do the following:
edges[i][j] = 1;
16
Weighted graphs: T
                  hese generally mean that all the edges are not equal, which
means somehow, each edge has some weight assigned to it. This weight can be the
length of the road connecting the cities or many more.
To implement this, in the edges matrix, we will assign a weight to connected nodes
instead of putting it 1 at that position. For example: If node i and j are connected,
and the weight of the edge connecting them is 5, then e
                                                        dges[i][j] = 5.
17
Graphs- 2
MST(Minimum Spanning Tree) & Kruskal’s Algorithm
As discussed earlier, a tree is a graph, which:
    ● Is always connected.
    ● Contains no cycle.
If there are n vertices and e  edges in the graph, then any spanning tree
corresponding to that graph contains n
                                       vertices and n
                                                       -1 edges.
1
Properties of spanning trees:
    ● A connected and undirected graph can have more than one spanning tree.
    ● The spanning tree is free of loops, i.e., it is acyclic.
    ● Removing any one of the edges will make the graph disconnected.
    ● Adding an extra edge to the spanning tree will create a loop in the graph.
In a weighted graph, the MST is a spanning tree with minimum weight than all other
spanning trees of that graph. Refer to the image below for better understanding.
2
Kruskal’s Algorithm:
This algorithm is used to find MST for the given graph. It builds the spanning tree by
adding edges one at a time. We start by picking the edge with minimum weight,
adding that edge into the MST, and increasing the count of edges in the spanning
tree by one. Now, we will be picking the minimum weighted edge by excluding the
already chosen ones and correspondingly increasing the count. While choosing the
edge, we will also make sure that the graph remains acyclic after including the
same. This process will continue until the count of edges in the MST reaches n
                                                                              -1.
Ultimately, the graph obtained will be MST.
3
This is the final MST obtained using Kruskal’s algorithm. It can be checked manually
that the final graph is the MST for the given graph.
Cycle Detection
While inserting a new edge in the MST, we have to check if introducing that edge
makes the MST cyclic or not. If not, then we can include that edge, otherwise not.
Now, let’s figure out a way to detect the cycle in a graph. The following are the
possible cases:
    ● By including an edge between the nodes A and B, if both nodes A and B are
       not present in the graph, then it is safe to include that edge as including it,
       will not bring a cycle to the graph.
    ● Out of two vertices, if any one of them has not been visited (or not present in
       the MST), then that vertex can also be included in the MST.
    ● If both the vertices are already present in the graph, they can introduce a
       cycle in the MST. It means we can’t use this method to detect the presence of
       the cycle.
Let’s think of a better approach. We have already solved the h
                                                              asPath question in
the previous module, which returns true if there is a path present between two
vertices v1 and v2, otherwise false.
4
Now, before adding an edge to the MST, we will check if a path between two
vertices of that edge already exists in the MST or not. If not, then it is safe to add
that edge to the MST.
Union-Find Algorithm:
Before adding any edge to the graph, we will check if the two vertices of the edge lie
in the same component of MST or not. If not, then it is safe to add that edge to the
MST.
5
6
7
Note: W
       hile finding the parent of the vertex, we will be finding the topmost parent
(Oldest Ancestor). For example: suppose, the vertex 0 and the vertex 1 were
connected, where the parent of 0 is 1, and the parent of 1 is 1. Now, while
determining the parent of the vertex 0, we will visit the parent array and check the
vertex at index 0. In our case, it is 1. Now we will go to index 1 and check the parent
of index 1, which is also 1. Hence, we can’t go any further as the index is the parent
of itself. This way, we will be determining the parent of any vertex.
The time complexity of the union-find algorithm becomes O(V) for each vertex in
the worst case due to skewed-tree formation, where V is the number of vertices in
the graph. Here, we can see that time complexity for cycle detection has
significantly improved compared to the previous approach.
8
Kruskal’s Algorithm: Implementation
Till now, we have studied the logic behind Kruskal’s algorithm for finding MST. Now,
let’s discuss how to implement it in code.
Consider the code below and follow the comments for a better understanding.
class Edge {       // Class that store values for each vertex
    int source;
    int dest;
    int weight;
}
class Main{
     public static v
                     oid kruskals(Edge[] input, int n, int E) {
        sort(input, new Sortbyweight());       // In-built sort function:
       // Sorts the edges in increasing order of their weights
       Edge[] output = new Edge[n-1];        // Array to store final edges of MST
       int[] parent = new int[n];
       int count = 0; //To maintain the count of number of edges in the MST
       int i = 0;           // Index to traverse over the input array
       while (count != n - 1) {      // As the MST contains n-1 edges.
             Edge currentEdge = input[i];
9
               // Figuring out the parent of each edge’s vertices
               int sourceParent = findParent(currentEdge.source, parent);
               int destParent = findParent(currentEdge.dest, parent);
             // If their parents not equal, then we added that edge to output
               if(sourceParent != destParent) {
                      output[count] = currentEdge;
                      count++;               // Increased the count
                      parent[sourceParent] = destParent;//Updated parent array
               }
               i++;
       }
       // Finally, printing the MST obtained.
       for (int i = 0; i < n-1; i++) {
              if(output[i].source < output[i].dest) {
                      System.out.println(output[i].source + “ ” +
                                      output[i].dest + “ ” + output[i].weight);
              }
              else {
                      System.out.println(output[i].dest + “ ” +
                                    output[i].source + “ ” + output[i].weight);
              }
       }
}
       kruskals(input, n, E);
}
10
Time Complexity of Kruskal’s Algorithm:
In our code, we have the following three steps: (Here, the total number of vertices is
n, and the total number of edges is E)
     ● Take input in the array of size E.
     ● Sort the input array based on edge-weight. This step has the time complexity
        of O(E log(E)).
     ● Pick (n-1) edges and put them in MST one-by-one. Also, before adding the
        edge to the MST, we checked for cycle detection for each edge. For cycle
        detection, in the worst-case time complexity of E edges will be O(E.n), as
        discussed earlier.
Hence, the total time complexity of Kruskal’s algorithm becomes O(E log(E) + n.E).
This time complexity is bad and needs to be improved.
We can’t reduce the time taken for sorting, but the time taken for cycle detection
can be improved using another algorithm named U
                                               nion by Rank and Path
Compression. You need to explore this on yourselves. The basic idea in these
algorithms is that we will be avoiding the formation of skewed-tree structure, which
reduces the time complexity for each vertex to O(log(E)).
Prim’s Algorithm
This algorithm is used to find MST for a given undirected-weighted graph (which
can also be achieved using Kruskal’s Algorithm).
In this algorithm, the MST is built by adding one edge at a time. In the beginning,
the spanning tree consists of only one vertex, which is chosen arbitrarily from the
set of all vertices of the graph. Then the minimum weighted edge, outgoing from
this vertex, is selected and simultaneously inserted into the MST. Now, the tree
contains two edges. Further, we will be selecting the edge with the minimum weight
such that one end is already present there in the MST and the other one from the
11
unselected set of vertices. This process is repeated until we have inserted a total of
(n-1) edges in the MST.
Implementation:
     ● We are considering the starting vertex to be 0 with a parent equal to -1, and
        weight is equal to 0 (The weight of the edge from vertex 0 to vertex 0 itself).
     ● The parent of all other vertices is assumed to be NIL, and the weight will be
        equal to infinity, which means that the vertex has not been visited yet.
     ● We will mark the vertex 0 as visited and the rest as unvisited. If we add any
        vertex to the MST, then that vertex will be shifted from the unvisited section
        to the visited section.
12
     ● Now, we will update the weights of direct neighbors of vertex 0 with the edge
        weights as these are smaller than infinity. We will also update the parent of
        these vertices and assign them 0 as we reached these vertices from vertex 0.
     ● This way, we will keep updating the weights and parents, according to the
        edge, which has the minimum weight connected to the respective vertex.
Let’s look at the code now:
13
                       if(edges[minVertex][j] != 0 && !visited[j]) {
                              if(edges[minVertex][j] < weights[j]) {
                                     // updating weight array and parent array
                                     weights[j] = edges[minVertex][j];
                                     parent[j] = minVertex;
                              }
                       }
              }
       }
       // Final MST printed
       for (int i = 0; i < n; i++) {
              if (parent[i] < i) {
                   System.out.println(parent[i] + “ ” + i + “ ” + weights[i]);
              }
              else {
                   System.out.println(i + “ ” + parent[i] + “ ” + weights[i]);
              }
       }
}
       prims(edges, n);
}
14
     ● The time complexity for finding the minimum weighted vertex is O(n) for
        each iteration. So for (n-1) edges, it becomes O(n2).
     ● Similarly, for exploring the neighbor vertices, the time taken is O(n2).
It means the time complexity of Prim’s algorithm is O(n2). We can improve this in
the following ways:
     ● For exploring neighbors, we are required to visit every vertex because of the
        adjacency matrix. We can improve this by using an adjacency list instead of a
        matrix.
     ● Now, the second important thing is the time taken to find the minimum
        weight vertex, which is also taking a time of O(n2). Here, out of the available
        list, we are trying to figure out the one with minimum weight. This can be
        optimally achieved using a priority queue where the priority will be taken as
        weights of the vertices. This will take O(log(n)) time complexity to remove a
        vertex from the priority queue.
Dijkstra’s Algorithm
This algorithm is used to find the shortest distance between any two vertices in a
weighted non-cyclic graph.
     1. We want to calculate the shortest path between the source vertex C and all
        other vertices in the following graph.
15
     2. While executing the algorithm, we will mark every node with its minimum
        distance to the selected node, which is C in our case. Obviously, for node C
        itself, this distance will be 0, and for the rest of the nodes, we will assume
        that the distance is infinity, which also denotes that these vertices have not
        been visited till now.
16
     3. Now, we will check for the neighbors of the current node, which are A, B, and
        D. Now, we will add the minimum cost of the current node to the weight of
        the edge connecting the current node and the particular neighbor node. For
        example, for node B, it’s weight will become minimum(infinity, 0+7) = 7. This
        same process is repeated for other neighbor nodes.
     4. Now, as we have updated the distance of all the neighbor nodes of the
        current node, we will mark the current node as visited.
17
     5. After this, we will be selecting the minimum weighted node among the
        remaining vertices. In this case, it is node A. Take this node as the current
        node.
     6. Now, we will repeat the above steps for the rest of the vertices. The pictorial
        representation of the same is shown below:
18
     7. Finally, we will get the graph as follows:
19
The distances finally marked at each node are minimum from node C.
20
Implementation:
Let’s look at the code below for a better explanation:(Code is nearly same as that of
Prim’s algorithm, just a change while updating the distance)
21
              System.out.println(i + “ ” + distance[i]);
       }
}
       dijkstra(edges, n);
}
22
OOPs - 4
Introduction
In this lecture we will try to create game logics by playing around different classes.
We will create a Tic-Tac-Toe game and we will discuss Othello game. It will be a java
console application. You can refer to course videos to understand the game rules.
Tic-Tac-Toe
In this game, two players will be played and you have one print board on the screen
where from 1 to 9 numbers will be displayed or you can say it box number. Now,
you have to choose X or O for the specific box number. For example, if you have to
select any number then for X or O will be shown on the print board, and turn for
next will be there. The task is to create a Java program to implement a 3×3
Tic-Tac-Toe game for two players.
      ● Both the players choose either X or O to mark their cells.
      ● There will be a 3×3 grid with numbers assigned to each of the 9 cells.
      ● The player who chose X begins to play first.
      ● He enters the cell number where he wishes to place X
                                                            .
      ● Now, both O
                   and X
                           play alternatively until any one of the two wins.
      ● Winning criteria: Whenever any of the two players has fully filled one
          row/ column/ diagonal with his symbol (X/ O), he wins and the game ends.
1
      ● If neither of the two players wins, the game is said to have ended in a
         draw.
Board class
public class Board {
      private char board[][];
      private int boardSize = 3;
      private char p1Symbol, p2Symbol;
      private int count;
      public final static int PLAYER_1_WINS = 1;
      public final static int PLAYER_2_WINS = 2;
      public final static int DRAW = 3;
      public final static int INCOMPLETE = 4;
      public final static int INVALID = 5;
              board[x][y] = symbol;
              count++;
              // Check Row
              if(board[x][0] == board[x][1] && board[x][0] == board[x][2]){
2
                return symbol == p1Symbol ? PLAYER_1_WINS :PLAYER_2_WINS;
          }
          // Check Col
          if(board[0][y] == board[1][y] && board[0][y] == board[2][y]){
                 return symbol == p1Symbol ? PLAYER_1_WINS :PLAYER_2_WINS;
          }
          // First Diagonal
          if(board[0][0] != ' ' && board[0][0] == board[1][1] &&
                                               board[0][0] == board[2][2]){
                 return symbol == p1Symbol ? PLAYER_1_WINS :PLAYER_2_WINS;
          }
          // Second Diagonal
          if(board[0][2] != ' ' && board[0][2] == board[1][1] &&
                                               board[0][2] == board[2][0]){
                 return symbol == p1Symbol ? PLAYER_1_WINS :PLAYER_2_WINS;
          }
          if(count == boardSize * boardSize){
                 return DRAW;
          }
          return  INCOMPLETE;
    }
    public void print() {
          System.out.println("---------------");
          for(int i =0; i < boardSize; i++){
                 for(int j =0; j < boardSize; j++){
                         System.out.print("| " + board[i][j] + " |");
                 }
                 System.out.println();
          }
          System.out.println();
          System.out.println("---------------");
    }
}
3
Player class
public class Player {
               if(!name.isEmpty()) {
                      this.name = name;
               }
       }
4
TicTacToe class (Main class)
import java.util.Scanner;
5
                       }
               }else{
                       System.out.println("Player 2 - " +
                                            player2.getName() + "'s turn");
                       System.out.println("Enter x: ");
                       int x = s.nextInt();
                       System.out.println("Enter y: ");
                       int y = s.nextInt();
                       status = board.move(player2.getSymbol(), x, y);
                       if(status != Board.INVALID){
                               player1Turn = true;
                               board.print();
                       }else{
                              System.out.println("Invalid Move! Try Again");
                       }
               }
         }
         if(status == Board.PLAYER_1_WINS){
                 System.out.println("Player 1 - " + player1.getName() +"
                                                                wins !!");
         }else if(status == Board.PLAYER_2_WINS){
                 System.out.println("Player 2 - " + player2.getName() +"
                                                                wins !!");
         }else{
                 System.out.println("Draw !!");
         }
    }
6
Othello
Approach: We have eight different directions to explore before we make a move
(before we make changes to the board) to ensure which all boxes will toggle. We
will move in every direction one by one and check for the player’s value who just
made his turn. We will then toggle the desired boxes, which the current player
secured by playing in that position. To explore all eight directions we can create
arrays for different directions and looping in the board we can increment or
decrement in respective value to move in the particular direction, like we explore
ways in backtracking lecture for rat in a maze game.
Now this code can be written on your own. Refer to the solution tab for the
solution.
7
Backtracking
Introduction
    ● Ab
        acktracking 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.
    ● The term backtracking suggests that if the current solution is not suitable,
       then backtrack and try other solutions. Thus, recursion is used in this
       approach.
    ● This approach is used to solve problems that have multiple solutions.
    ● Backtracking is thus a form of recursion.
    ● We begin by choosing an option and backtrack from it, if we reach a state
       where we conclude that this specified option does not give the required
       solution.
    ● We repeat these steps by going across each available option until we get the
       desired solution.
1
Problem Statement: N-Queen
One of the most common examples of the backtracking is to arrange N queens on
an NxN chessboard such that no queen can strike down any other queen. A queen
can attack horizontally, vertically, or diagonally.
The solution to this problem is also attempted using Backtracking.
    ● We first place the first queen anywhere arbitrarily and then place the next
       queen in any of the safe places.
    ● We continue this process until the number of unplaced queens becomes
       zero (a solution is found) or no safe place is left.
    ● If no safe place is left, then we change the position of the previously placed
       queen.
    ● The above picture shows an NxN chessboard and we have to place N queens
       on it. So, we will start by placing the first queen.
2
    ● Now, the second step is to place the second queen in a safe position and
       then the third queen.
    ● Now, you can see that there is no safe place where we can put the last
       queen. So, we will just change the position of the previous queen. And this is
       backtracking.
    ● Also, there is no other position where we can place the third queen so we will
       go back one more step and change the position of the second queen.
3
    ● And now we will place the third queen again in a safe position until we find a
       solution.
    ● We will continue this process and finally, we will get the solution as shown
       below.
4
As now you have understood backtracking, let us now code the above problem of
placing N queens on an NxN chessboard using the backtracking method.
5
                  }
       eturn f
       r        alse;
}
https://www.codingninjas.com/blog/2020/09/02/backtracking-rat-in-a-maze/
6
Object-Oriented Programming (OOPS-3)
Final Keyword
    ● When a variable is declared with a final keyword, its value can’t be modified,
        essentially, a constant. This also means that you must initialize a final
        variable.
    ● If the final variable is a reference, this means that the variable cannot be
        re-bound to reference another object, but the internal state of the object
        pointed by that reference variable can be changed i.e. you can add or
        remove elements from the final array or final list.
Example:
1
Refer to the course videos to see the use case and more about the final keyword.
Abstract Classes
An abstract class can be considered as a blueprint for other classes. Abstract
classes are classes that contain one or more abstract methods. An abstract method
is a method that has a declaration but does not have an implementation. This set of
methods must be created within any child classes which inherit from the abstract
class. A class that contains one or more abstract methods is called an a
                                                                         bstract class.
The given Java code uses the ABC class and defines an abstract base class:
2
We will do it in the following example, in which we define two classes inheriting
from our abstract class:
class Test{
    public static void main(String[] args) {
          add x = new add(10);
          mul y = new mul(10);
          System.out.println(x.do_something());
          System.out.println(y.do_something());
      }
}
52
420
Thus, we can observe that a class that is derived from an abstract class cannot be
instantiated unless all of its abstract methods are overridden.
Note: C
       oncrete classes contain only concrete (normal) methods whereas abstract
classes may contain both concrete methods and abstract methods.
3
    ● However, even if they are implemented, this implementation shall be
       overridden in the subclasses.
    ● If you wish to invoke the method definition from the abstract superclass, the
       abstract method can be invoked with s
                                            uper() call mechanism. (Similar to
       cases of “normal” inheritance).
    ● Similarly, we can even have concrete methods in the abstract class that can
       be invoked using s
                         uper() call. Since these methods are not abstract it is not
       necessary to provide their implementation in the subclasses.
    ● Consider the given example:
class Test{
    public static void main(String[] args) {
          AnotherSubclass x = new AnotherSubclass()
          x.do_something() //calling abstract method
          x.do_something2() //Calling concrete method
4
     }
}
Another Example
The given code shows another implementation of an abstract class.
// Driver code
5
 class Test{
     public static void main(String[] args) {
           Animal R = new Human();
           R.move();
           Animal K = Snake();
           K.move();
           R = Dog();
           R.move();
      }
 }
Interfaces
Writing an interface is similar to writing a class. But a class describes the attributes
and behaviors of an object. And an interface contains behaviors that a class
implements.
6
    ● An interface is not extended by a class; it is implemented by a class.
    ● An interface can extend multiple interfaces.
Declaring Interface
Example:
Now we need to implement this interface using a different class. A class uses the
implements keyword to implement an interface. The i mplements k
                                                                eyword appears
in the class declaration following the extends portion of the declaration.
        @Override
        public void print() {
             // TODO Auto-generated method stub
             // We can implement this function further.
        }
        @Override
        public int getMaxSpeed() {
7
                 // TODO Auto-generated method stub
                 return 0;
       }
       @Override
       public String getCompany() {
            // TODO Auto-generated method stub
            return null;
       }
 }
@Override annotation informs the compiler that the element is meant to override
an element declared in an interface.