Algorithms-1 - CS21003
Autumn Semester - 2017
Course Timings
Lectures
Wednesday - 10:00 - 11:00 (NR223)
Thursday - 09:00 - 10:00 (NR223)
Friday - 11:00 - 12:00 (NR223)
Tutorial: Friday - 12:00 - 13:00 (NR223)
Office Hours: Tuesday - 18:00 - 19:00 (CSE-308)
Teaching Assistants
Mayank Singh, Abhik Jana, Suman Kalyan Maity
Reference Books
- Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Third Edition, MIT Press, 2009.
- Udi Manber, Algorithms -- A Creative Approach, Addison-Wesley,
Reading, MA, 1989.
- Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
Topics Covered
| July 19th, 2017 |
Introduction: What is an algorithm? |
| July 20th, 2017 |
Asymptotic notations and their significance, complexity analysis
of algorithms |
| July 21st, 2017 |
Worst case and average case, divide and conquer algorithms |
| July 26th, 2017 |
Divide and conquer algorithms: polynomial multiplication |
| July 27th, 2017 |
Divide and conquer: matrix multiplication, greedy algorithms |
| July 28th, 2017 |
Greedy algorithms: coin change problem, interval scheduling problem |
| August 2nd, 2017 |
Interval scheduling problem: Optimality Proof |
| August 3rd, 2017 |
Interval Partitioning problem: Optimality Proof |
| August 4th, 2017 |
Dynamic Programming: Coin Change, Weighted Interval Scheduling |
| August 9th, 2017 |
Weighted Interval Scheduling Contd ... |
| August 10th, 2017 |
Knapsack Problem, Longest Common subsequence |
| August 11th, 2017 |
Proofs for Greedy Algorithms |
| August 16th, 2017 |
Graphs and Trees: Basic Notions and Definitions |
| August 17th, 2017 |
Representation of graphs and rooted trees, binary trees |
| August 23rd, 2017 |
Heaps |
| August 24th, 2017 |
Priority Queues, HeapSort |
| August 25th, 2017 |
Binary Search Trees - Operations |
| August 30th, 2017 |
Traversal, Binary Search Trees - Operations, BST sort |
| August 31st, 2017 |
AVL Trees: Height balancing property |
| September 1st, 2017 |
AVL Trees: Insertion and Deletion |
| September 6th-8th, 2017 |
Revision: BST, AVL Trees |
| October 4th, 2017 |
HashTable: Chaining |
| October 5-6th, 2017 |
HashTable: Open Addressing |
| October 11th, 2017 |
Algorithms on Arrays: Linear Time Sorting |
| October 12th, 2017 |
Algorithms on Arrays: Counting Sort, Radix Sort |
| October 13th, 2017 |
Algorithms on Arrays: Bucket Sort, Order Statistics |
| October 18th, 2017 |
String Matching: Rabin-Karp Algorithm |
| October 20th, 2017 |
String Matching: KMP Algorithm |
| October 25th, 2017 |
String Matching: KMP Algorithm Contd.. |
| October 26th, 2017 |
Graph Algorithms: Breadth-First-Traversal |
| October 26th, 2017 |
BFS Contd.. |
| November 1st, 2017 |
DFS |
| November 2nd, 2017 |
DFS, Edge Classification |
| November 3rd, 2017 |
Topological Sort, Minimum Spanning Tree |
| November 9th, 2017 |
Minimum Spanning Tree - Kruskal's Algorithm |
| November 10th, 2017 |
SSSP - Dijkstra's Algorithm |
| November 15th, 2017 |
APSP - Floyd Warshall's Algorithm |
| November 16th, 2017 |
Shortest path - generalizations |
Announcements
Algo Class Test-1 will be on August 25th, 6:00 - 7:00 PM in CSE 107,
108, 119 and 120. The seating arrangement will follow shortly.
First Algo-1 class will be on July 19th, 10:00 - 11:00 AM
(NR223). First Algo Lab will be on July 20th, 2:00 - 5:00 PM at CIC
(PC_Lab II and PC_Lab V).
|