| 3 |
Course content |
Syllabus is divided roughly 8 modules; each module roughly takes two weeks.
Module 1: Introduction Examples and motivation. Asymptotic complexity: informal concepts, formal notation, examples
Module 2: Searching in list: binary search, Sorting: insertion sort, selection sort, merge sort, quicksort, stability and other issues.
Module 3: Divide and conquer: binary search, recurrence relations. nearest pair of points, merge sort, integer multiplication, matrix multiplication.
Module 4: Graphs: Motivation, BFS, DFS, DFS numbering and applications, directed acyclic graphs, directed acyclic graphs, Shortest paths: unweighted and weighted, Single source shortest paths: Dijkstra, Minimum cost spanning trees: Prim’s algorithm, Kruskal’s Algorithm.
Module 5: Union-Find data structure, Priority queues, heaps. Heap sort. Dijstra/Prims revisited using heaps, Search Trees: Introduction Traversals, insertions, deletions Balancing.
Module 6: Greedy algorithms: Greedy: Interval scheduling, Proof strategies, Huffman coding.
Module 7: Dynamic Programming: weighted interval scheduling, memoization, edit distance, longest ascending subsequence. matrix multiplication, shortest paths: Bellman Ford, shortest paths: Floyd Warshall.
Module 8: Intractability: NP completeness, reductions, examples, Misc topics.
|
| 4 |
Texts/References |
- Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, McGraw Hill Education, 2006.
- Introduction to Algorithms, 3rd edition, by Cormen, Leiserson, Rivest and Stein, PHI Learning Pvt. Ltd., 2010.
- Algorithm Design, 1st edition, by Kleniberg and Tardos, Pearson, 2014.
|