The course studies techniques for designing and analyzing algorithms and data structures. The course concentrates on the logical process that leads to the creation of the algorithm, rather than the algorithm itself, and the techniques for evaluating the performance of algorithms. The central idea is that Computer Science is more than mere recipes; it is about computational thinking.
The topics are drawn from the following lists:
- algorithm design basics: algorithm design with mathematical induction, asymptotic notation, and solving recurrence relations
- algorithm design techniques: divide and conquer, dynamic programming, greedy algorithms, and backtracking
- searching, sorting, and union-find
- trees and red-black trees
- string matching, sequence comparison, and Huffman codes
- graph algorithms
- NP-completeness
- Assignment 1: A recursive function to compute the Fibonacci numbers F(n) with time complexity O(n).
- Assignment 2: Finding connected components in a binary image by implementing a Disjoint-Set data structure.
- Assignment 3: Implement the Dijkstra's single source shortest path algorithm for a weighted directed graph using a heap data structure. The time complexity of the algorithm should be O((|V|+|E|)log|V|).