Dealing with Algorithms

This lecture is to show how a problem can be solved using many ways. When an unfamiliar problem is given to a set of people, everyone tries to solve it his/her own ways and will have multiple ways in which that problem is getting solved.

The example program that is taken here is to find the GCD (Greatest Common divisor) of two non negative non zero numbers.

Algorithm 1: Euclid's Algorithm:

gcd(m, n) = gcd(n, m mod n), where m mod n is the remainder of the division of m by n and is applied repeatedly until m mod n is equal to 0.Finally it becomes gcd(m, 0) = m which is nothing but gcd of the initial m and n

Algorithm 2:  Consecutive Integer Checking Algorithm

This algorithm works on the principle that the greatest common divisor of any non zero non negative integers is the largest integer that divides both numbers evenly.

Algorithm 3: Middle School Procedure (Note: Lecture for this algorithm is not present as it is middle school procedure. Program for the same is uploaded

Prime Factors of 64 is = 2 * 2 * 3 * 5 and Prime Factors of 24 is = 2 * 2 * 3 * 2

Common prime factors of 60 and 24 is = 2 * 2 * 3 , GCD = 12

Algorithm steps are:

if non zero non-negative numbers denoted as m, n

Step 1 Find the prime factors of m.  (prime factors can be found out using Sieve of Eratosthenes algorithm)

Step 2 Find the prime factors of n.

Step 3 Identify all the common factors in the two prime expansions found in Step 1 and Step 2.

Step 4 Compute the product of all the common factors and return it as the greatest common divisor of the numbers given.

Programs for all the three above algorithms are uploaded for your reference.

An example program for displaying power set is uploaded in the resource section. It has exponential time complexity.

Note: While referring the uploaded sources, The common inner classes like Graph, Edge, Node etc are used in the many example programs. Hence if they are in the same package, it gives conflict. You may need to change the name or comment out the lines of the programs whichever you are not using at the moment.

The travelling salesman problem using brute force approach is uploaded in the resource section. The permutation sequence of travelling cities have been found out by using the algorithm for finding the next permutation sequence.

The program for searching the pattern in a string is being uploaded in the resource section.

Here is external link for playing around with Tower of Hanoi puzzle: https://www.mathsisfun.com/games/towerofhanoi.html

The program for Tower of Hanoi puzzle is being uploaded in the resource section.

In this variation,  The problem keeps on divided into multiple sub problems until we get a solution. The popular Binary Search algorithm is an example of decrease and conquer approach.

The programs for binary search by iterative method and by using recursive method is being uploaded.

Three java programs are uploaded for quick sort. One by using recursive method and another  by using iteration method. In iteration method, one is by using array and another by using Stack class in java. Have a look on all these programs and try it yourself

The theorem suggests an easy and quick way to find  the asymptotic behaviour of the divide and conquer based algorithm by  solving its recurrence relation using the theorem. If we have the expression as form T(n) = a * T(n/b) + some f(n)  where a>= 1, b > 1, k >= 0 by looking at different cases mentioned in the theorem, the behaviour can be concluded.

We cannot use master theorem if T(n/b) is a monotone. For example, if it is of form sin(x) and also the function f(n) has to be polynomial function.

The program for merge sort is uploaded in resource section.

The program for heap sort is being uploaded in the resource section and it sorts elements in descending order. If you want it to be in ascending order instead of doing maxheapify operation, you can do minheapify operation.

Greedy Algorithm makes greedy choice at each step to find local optimal solution and finally find the global optimal solution. So we have to always make sure that the algorithm gives the required output for the entire problem at the end.

The program for Huffman coding is uploaded in resource section.

Some of the applications of minimum spanning tree are while design any network such as Road network, water supply network, Transportation network etc.

Main idea is to have tree call minimum spanning tree which has minimum weight by connecting all the vertices by passing to all the vertices exactly once. In order to have minimum spanning tree, one of the main operations is to detect cycle in a graph.  We can detect a cycle in a graph using union find algorithms.

This section mainly talks about  union find algorithms that can be used to detect a cycle in a graph.  We will be learning about  Union find algorithm in naive way

Programs for union find algorithm in naive way is uploaded in resource section for your reference

This section mainly talks about two ways in which ehe union find algorithm can be optimised and they are

2) By path compression (Optimising  find operation)

3) By ranking (Optimising union operation)

Once we have the algorithm ready for detecting cycle in the graph using these algotithms, implementing Kruskal's algorithm is really easy.

Programs for union find algorithm by path compression and ranking  as well as for finding Kruskal's minimum spanning tree are uploaded in resource section for your reference

Dijkstra's shortest path algorithm finds out the shortest path from a vertex to all the other vertices in a graph.Best example of Dijkstra's shortest path algorithm that can be stated is in maps. Using this algorithm, maps can easily trace out the shortest route for us.

The program for the same is uploaded in resource section.

Prim's minimum spanning tree is another algorithm like Kruskal's minimum spanning spanning tree to find the minimum spanning tree in a graph.  Due to the nature of each algorithm, in the case of a graph with moderate number of edges, you should use Kruskal's algorithm.

When you choose between these two algoithms though the running time of these two is almost same, you can choose Prim's algorithm when the graph is dense. It runs faster in a graph with many edges as it only compares limited number of edges per loop, whereas Kruskal's minimum spanning tree starts by sorting all the edges in the list and then going through them again to  check if the edge is part of the minimal spanning tree (MST) or not. If the graph is sparse, we can opt Kruskal's minimum spanning tree.

As we are learning Prim's algorithm soon after Dijkstra you will be able to follow very easily as implementation approach is similar.

The program for Prim's algorithm is uploaded in the resource section

Dynamic programming is the way of making algorithm more efficient by storing  the result of repetitive sub problems and reusing it for repetitive computation.

Dynamic programming can be done in two approaches.

1) Using Recursion and memoisation

2)  Using bottom up approach

This section is mainly for brushing up matrix multiplication that we learnt in school days and also it makes you aware of the major operation that is number of scalar multiplication involved in matrix multiplication.

If there are 3 matrices in matrix chain multiplication, the number of scalar multiplication involved will be equal to the number rows of first matrix * number of columns of first matrix or the number of rows of second matrix as both are same * number of columns of second matrix.

Another important thing is as the scalar multiplication impacts the program performance, it is also noted that according to the order in which we take sub matrices, the number of scalar matrix involved also will be varied. Hence our first task would be to find out the order which gives the minimum number of scalar multiplication.

This section introduces you to the formula for finding the order which gives the minimum number of scalar multiplications and also it tells about how we can implement matrix chain multiplication using dynamic programming approach. The approach introduces us to make use of the derived formula in an easy way.

This section walks you through the implementation by making use of the the formula and also explains how we can trace the order which has the minimum scalar multiplication.

The program for the same is uploaded in the resource section

This section talk about finding longest common subsequence from two sequences.

A sub-sequence is a sequence that can be derived from another sequence by removing some or no elements without changing the order. We can derive zero or more subsequences. For example,  the subsequence that we can derive from the sequence ABCDE are A,B,C,D,E

AB, AC, AD, AE,BC,BD,BE,CD,CE,DE

ABC,ABD,ABE,ACD,ACE,ADE,BCD,BDE,CDE

ABCD,ACDE,BCDE’

ABCDE

The problem here is to find the longest common subsequence when two sequences are given.

For example, given two sequences ABCDE and ADBC, the LCS is ABC.

Let us understand how to solve this using dynamic programming approach by listening this lecture.

This lecture explaining about the implementation of finding the LCS using dynamic programming.

The program for the same using top down and bottom up approach is uploaded in resource section

Floyd Warshall All pair Shortest Path Algorithm is to find the shortest path from all the vertices to all the other vertices in a directed weighted graph. How it is different from Dijkstra's Shortest Path Algorithm. Dijkstra's shortest path algorithm find the shortest distance from a vertex to all other vertices, but Floyd Warshall's shortest path finds the shortest path of each vertex to all other vertices.

Floys Warshall's algorithm does by using dynamic programming approach. So it find the solution to optimal substructure and memoise the value in order for it to use for finding final solution to the problem.

We have seen how we are addressing fractional knapsack problem in greedy algorithm section. Now in this section, let us learn how to solve 01 knapsack problem using dynamic programming. We can take the example of electronics items as example wherein the items cannot be fractionalised.

The source code for 01 knapsack problem using top down and bottom up approach has been uploaded in the resource section.

We have seen the Travelling Salesman problem in brute force approach and its complexity is n!. In this section let us see how we can improve its performance using dynamic programming approach.

This technique follows brute force approach and iterates through all possibilities. Then how it is different?  As the name as soon as problem constraints or conditions are not met it back tracks  and continues with other possibilities. It is suited for problem which has multiple solutions.

The program for N queen problem is being uploaded in resource section. It displays all combinations of position, the queens can have in 4 * 4 chess board.

Graph colouring too is implemented almost the same way as N-queen code. You can refer the program in resource section

A Hamiltonian path is a path in undirected graph that visits each vertex exactly once and Hamiltonian cycle is a cycle in a graph that visits all the vertices exactly once and terminates at starting node.

The algorithm finds out the hamiltonian cycles in a graph. The program for the same is uploaded in resource section