Description here

Time

From Mar 2024 to Oct 2024

Course Contents

Introduction - Algorithms, Analyzing & Designing Algorithms, Correctness ofAlgorithms; Greedy Algorithms - Introduction to Greedy Algorithms, Greedy Choice Property, Greedy vs. Dynamic Programming, Fractional Knapsack Problem, Activity Selection Problem, Huffman Encoding, Task Scheduling Problem, Coin Changing Problem, Kruskal’s and Prim’s Minimum Spanning Tree Algorithms; Divide and Conquer Algorithms - Introduction to Divide and Conquer Design Technique, Quick Sort, Merge Sort, Proof of Correctness, and Run Time Analysis; Dynamic Programming - Introduction to Dynamic Programming Technique, Principle of Optimality, Optimal Substructure Property, Assembly Line Scheduling, Matrix Chain Multiplication, LCS, Viterbi Algorithm, Bitonic Euclidean Traveling Salesperson Problem and Runtime Analysis; Graph Searching and Shortest Path Problems - Breadth First Search, Depth First Search, Flow Networks, Single Source and All Pair Shortest Path Algorithms; Linear Programming -Overview of Linear Programming, Formulating Problem as Linear Programs, Simplex Algorithm and Integer Linear Programming; Selected Topics - Computational Geometry, Number Theoretic and String Matching Algorithms; NP Completeness and Approximation Algorithms - NP Completeness, Polynomial Time Verification, NP Completeness and Reducibility, NP Complete Problems and Approximation Algorithms.

Reference Books:

1. Thomas Corman, Introduction to Algorithms, Stein Pub MIT Press, 3rd Ed.
   
2. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The Design and Analysis of ComputerAlgorithms, Addison Wesley Series, 1974 Ed.