CS514: Design and Analysis of Algorithms (Spring 2024) |
|||||||||
| This course will provide a basic understanding of problem solving strategies using computers. The course will focus mostly on the theoretical side. |
Class schedule |
|||||||||
| Monday — 1800-1900; Tuesday — 1800-1900; Thursday — 1800-1900; | |||||||||
| Venue — R107; |
Syllabus |
|||||||||
|
This is a 3-0-0-6 (L-T-P-C) course. Data structures: linked list, stack, queue, tree, balanced tree, graph; Complexity analysis: Big O, omega, theta notation, solving recurrence relation, master theorem Sorting and searching: Quick sort, merge sort, heap sort; Sorting in linear time; Ordered statistics; Problem solving strategies: recursion, dynamic programming, branch and bound, backtracking, greedy, divide conquer, Graph algorithms: BFS, DFS, Shortest path, MST, Network flow; NP-completeness Advanced topics: string matching, FFT-DFT, basics of approximation and randomized algorithms; |
Books |
|||||||||
|
Slides |
|||||||||
| Topic | Slides | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Introduction | |||||||||
| Recursion | |||||||||
| Recursion: Sorting | |||||||||
| K-th Largest | |||||||||
| Backtracking | |||||||||
| Dynamic Programming | |||||||||
| Design of Algorithms | |||||||||
| Polynomial multiplication, FFT | NA | ||||||||
| Heap sort | NA | ||||||||
| Sorting in linear time | NA | ||||||||
| DFS, SCC | NA | ||||||||
| BFS, Shortest path | NA | ||||||||
| All pair shortest paths | NA | ||||||||
| MST | NA | ||||||||
| Network Flow | |||||||||
| Intractability | |||||||||
| Tutorial | |||||||||