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
Recurrence relation & Masters Theorem
Mergesort
Medians
Matrix Multiplication, Polynomial Multiplication
Fast Fourier Transform
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
Minimum Spanning Trees
Kruskal’s Algorithm
Prim’s Algorithm
Set Cover
Huffman Encoding
Dynamic Programming
Shortest Path
Longest Increasing Subsequences
Edit Distance
Knapsack
Floyd-Warshall Algorithm
Travelling Salesman Problem
Linear Programming
Duality
The Simplex Algorithm
Flows in Networks
Bipartite Matching
Zero-sum Games
NP-Complete Problems
Search Problems
P and NP
Backtracking
Branch and Bound
Approximation Algorithms
Heuristics
Randomized Algorithms
Las Vegas
Monte Carlo
Hashing
Coding Tutorials:
Karatsuba's Algorithm, Mergesort
FFT, DFS for Connectivity
Strongly CC, BFS, DFS for Shortest Path
Dijkstra's Algorithm
Kruskal's Alogirthm, Set Cover
Edit Distance, Knapsack
LIS, Floyd-Warshall Algorithm
Simplex Algorithm
Network Flow, Quicksort
Lecture Resources:
- Through Google Classroom [invitation based, exclusive to those who officially register]