Course Objectives

• The objective of this course is to study paradigms and approaches used to analyze and design algorithms and to appreciate the impact of algorithm design in practice. It also ensures that students understand how the worst-case time complexity of an algorithm is defined
• How asymptotic notation is used to provide a rough classification of algorithms,
• how a number of algorithms for fundamental problems in computer science and engineering work and compare with one another, and how there are still some problems for which it is unknown whether there exist
  efficient algorithms, and how to design efficient algorithms.

Learning Outcomes

• Introduction, algorithm, pseudo code for expressing algorithms, performance analysis, space
  complexity, time complexity, asymptotic notation, big oh notation, omega notation, theta notation,
  and little oh notation, probabilistic analysis, amortized analysis.
• Disjoint sets, disjoint set operations, union and find algorithms, spanning trees, connected components, biconnected components Divide and conquer: general method, applications, binary search, quick sort, merge sort,  matrix multiplication.Greedy method: general method, applications, job sequencing with deadlines, 0/1 knapsack
  problem, minimum cost spanning trees, single source shortest path problem.Dynamic programming: general method, applications, matrix chain multiplication, optimal binary
  search trees, 0/1 knapsack problem, all pairs shortest path problem, travelling sales person
  problem, reliability design.Backtracking: general method, applications, n-queen problem, sum of subsets problem, graph
  coloring, Hamiltonian cycles.Branch and Bound: general method, applications, travelling sales person problem, 0/1 knapsack
  problem. LC branch and bound solution, FIFO branch and bound solution.NP-hard and NP-complete problems: basic concepts, non deterministic algorithms, NP-hard and
  NP-complete classes.

Course Syllabus

Module I: Introduction to analysis and design of algorithm (4 Hrs)

Introduction to analysis and design of algorithm, Growth of functions, Asymptotic notations,
Recurrences, Solution of recurrences by substitution, Recurrence tree and the master method.

Assignment 1:  Examples on Recurrences (Substitution Method, Recursion Tree Method, Master's Method)

Module II: Divide and conquer algorithms (4 Hrs)

Worst case analysis of merge sort, quick sort and heap sort
algorithms, Priority queue, Data structure for disjoint sets (Disjoint set operations, linked list
representation, disjoint set forests)

Assignment 2: Example of Merge sort, Quick sort, Heap sort Techniques

Practice:

1.  Implement Insertion Sort (The program should report the number of comparisons)
2. . Implement Merge Sort(The program should report the number of comparisons)
3. Implement Heap Sort(The program should report the number of comparisons)
4. Implement Randomized Quick sort (The program should report the number of comparisons
5. Implement Radix Sort

Module III: Dynamic programming approach (4 Hrs)

Matrix chain multiplication, longest common subsequence.

Assignment 3: Example on Matrix chain Multiplication. Finding LCS among two strings

Practice :

6. Write a program to determine the LCS of two given sequences 

Module IV: Greedy method (5 Hrs)

Fractional knapsack problem Greedy verses dynamic programming, Huffman codes. Concept of backtracking, branch & bound design techniques.

Assignment 4: Example on 0/1 Knapsack problem. Huffman coding.

Module V: Single source shortest paths (5 Hrs)

Graph algorithms: Minimal spanning tree (Kruskal's and
Prim’s algorithms), Single source shortest paths (Bellman-Ford and Dijkstra’s algorithm), Floyd’s algorithm.

Practice:

7. Implement Breadth-First Search in a graph 

8. Implement Depth-First Search in a graph.

9. Write a program to determine the minimum spanning tree of a graph 

Assignment 5:  Examples on Kruskal's and Prim's Algorithm. Bellman-Ford and Dijkstra's Algorithm

Module VI: Flow Network (4 Hrs)

Ford-Fulkerson method, Fast Fourier Transform, Rabin-Karp string matching algorithm.

Assignment 6: 4 point & 8 point DIF and DIT FFT

Assignment 7: Example on Robin-Karp String matching Algorithm.

Module VII: NP-Completeness (4 Hrs)

NP Completeness, Polynomial time solvability, Verification and Reducibility, NP complete problems (without
proof), Approximation algorithm for the traveling salesman problem

Assignment 8:  Example on Travelling Salesman Problem

I am text block. Click edit button to change this text. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.