Pre-requisites:
None
Text Book:
Algorithms by Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani, McGraw-Hill Education, 1st edition, 2006.
Course Syllabus Outline:
Arithmetic
Fibonacci numbers*
Asymptotic notations*
Divide & Conquer
Multiplication*
Matrix Multiplication
Recurrence relation & Masters Theorem
Sorting by comparison, Mergesort*
Quick Select & Sort*
Median Computation
Fast Fourier Transform*
Polynomial Multiplication
Graphs
Elementary Concepts
Directed Acylic Graph (DAG)*
Depth-first Search*
Breadth-first Search*
Dijkstra’s Algorithm*
Bellman-Ford Algorithm*
Shortest Path in DAG
Greedy Algorithms
Scheduling
Set Cover*
Minimum Spanning Trees
Kruskal’s & Prim’s Algorithms*
Huffman Encoding
Dynamic Programming
Shortest Path
Longest Increasing Subsequence*
Edit Distance*
Knapsack*
Floyd-Warshall Algorithm*
Chain Matrix Multiplication
Travelling Salesman Problem (TSP)*
More on Complexity
Search Problems
P and NP
* Coding tutorials will be conducted
Lecture Resources:
- Through Google Classroom [invitation based, exclusive to those who officially register]