Pre-requisites:
None
Text Book:
Algorithms by Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani, McGraw-Hill Education, 1st edition, 2006.
Course Syllabus Outline [Updated]:
Arithmetic, Fibonacci numbers, Asymptotic notations
Divide & Conquer
Multiplication
Recurrence relation & Masters Theorem
Mergesort
Quick Select & Sort
Median Computation
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
Flow in Networks
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
Chain Matrix Multiplication
Floyd-Warshall Algorithm
Travelling Salesman Problem (TSP)
NP-Complete Problems
Search Problems
P and NP
TSP Branch and Bound & Approximation
Coding Tutorials:
Karatsuba's Algorithm, Mergesort, Quicksort
FFT, DFS for Connectivity, DAG Validity, Topological Sorting
Strongly CC, BFS, DFS for Shortest Path
Dijkstra's and Bellman-Ford Algorithms
Kruskal's and Prim's Alogirthms, Set Cover
Longest Increasing Subsequence, Edit Distance, Knapsack
Travelling Salesman Problem, Floyd-Warshall Algorithm
Lecture Resources:
- Through Google Classroom [invitation based, exclusive to those who officially register]