CS514: Design and Analysis of Algorithms
This course will provide a basic understanding of problem solving strategies using computers. The course will focus mostly on the theoretical side.
Class timings
- Monday - 1600-1700
- Tuesday - 1700-1800
- Friday - 1500-1600
TAs
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
- Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Third Edition, MIT Press/McGraw-Hill
- Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh V. Vazirani, Algorithms, Tata McGraw-Hill, 2008.
- Steven Skiena, The Algorithm Design Manual, Springer
- Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
- Robert Sedgewick and Kevin Wayne, Algorithms, fourth edition, Addison Wesley, 2011.
- Udi Manber, Algorithms – A Creative Approach, Addison-Wesley, Reading, MA, 1989.
- Jeff Erickson, Algorithms, Link