Description and plan

Instructors

1. Debarka Sengupta
<debarka@gmail.com>
<debarka@iiitd.ac.in>

2. Debajyoti Bera (Guest instructor)
<dbera@iiitd.ac.in>






 
Teaching Assistants

1. Rahul Gangopadhyay <rahulg@iiitd.ac.in> (lead) - Office hour: Wednesday 13:00 to 14:00
2. Kajal Kansal <kajalk@iiitd.ac.in> (lead- Office hour: Monday 13:00 to 14:00
3. Ashutosh Mittal <ashutosh16012@iiitd.ac.in>
4. Kanika Gautam <kanika15024@iiitd.ac.in>
5. Navya Vats <navya15122@iiitd.ac.in>
6. Sanket Jain <sanket16050@iiitd.ac.in>
7. Shanu IIITD <shanu16053@iiitd.ac.in>
8. Tarun Malhotra <tarun13112@iiitd.ac.in>
9. Vidhi Modi <vidhi16061@iiitd.ac.in>
10. Yash Sadana <yash16063@iiitd.ac.in>
Text Book

Algorithm Design by Jon Kleinberg, Éva Tardos

Reference Books

1. Introduction to Algorithms by Cormen et. al.

2. Introduction to Data Mining by Tan et. al.



 
Lecture Hours

Tuesday Lecture @ C01, 9:30--10:30

Thursday Lec @ C01, 9:00-10:00

Friday Lec @ C01, 13:00-14:00

Wednesday Lab @ L21, L22, L23, 15:00-17:30  


Thursday Tut @ LR1, LR2, LR3, 10:00-12:30       
Office Hours

Friday 16:00 to 17:00 or by appointment


 
Grading

Out of 100

A. Class tests 10
C. Lab 10
D. Assignment 5
E. Mid sem 30
F. Final 45


Computation of total

If (E + F >= 20):
    Total = A+B+C+D+E+F
else:
    Total = E+F+0.6*(A+B+C+D)


Note: Get in  touch with TAs if this is confusing.



Pre-requisite: Data structures and algorithms, Introduction to Programming, Discrete Mathematics

Post-Condition: At the end of this course, a student will gain the following: 
  • Knowledge about different paradigms of algorithm design, as well as some common algorithms. 
  • Ability to analyse algorithms with respect to correctness and computing resources like running time. 
  • Ability to design efficient algorithms for new problems, using the techniques learned as building block. 
  • Understand the limitation in algorithm design for solving certain problems. 
Specific skills to deliver post-condition: 
  • Know graph search algorithms, graph algorithms like connectivity, MST and shortest-path.
  • Be able to design algorithms using the fundamental design paradigms, prove correctness and analyze resource requirements.
  • Intractability of problems, reductions, the classes P and NP, NP-complete and NP-hard problems.
  • Ability to appreciate machine learning algorithms and preparedness for a elaborate ML course.
  • Ability of accurate implementation of algorithms, adhering to the programming best practices. 

Scheduled Lectures (No. of lectures)

Note: Watch here for material links.


- Orientation (6)
======================================
-- Solving recurrences (1)
-- Introductory graph theory (1)
-- Introduction to asymptotic analysis (2)
-- Refresher for Combinatorics, Sets Vectors and Matrices (2)



- Introduction (2)
======================================
-- Stable Marriage (2)


- Graph algorithms (4)
======================================
-- BFS (1)
-- DFS (1)
-- Strongly Connected Component - Kosaraju's algorithm (1)
-- Dijkstra (1)


- Divide and Conquer (4)
======================================
-- Introduction, Merge Sort (1)
-- Closest pair of points (1)
-- Convex Hull and Strassen's Efficient Matrix Multiplication (1)
-- O(n) Median finding algorithm, hint to MapReduce (1)



- Dynamic Programming (7)
======================================
-- Introduction, Fibonacci (1)
-- Chain matrix multiplication (1)
-- Knapsack problem DP solution (1)
-- Sequence alignment (2)
-- Bellman Ford (2)

- Greedy algorithms (5)
======================================
-- Introduction, Interval Scheduling (2)
-- MST - Prim, Kruskal (2)
-- Huffman's code (1)


- Data Mining and Machine Learning algorithm (5)
======================================
-- Introduction to machine learning and pattern recognition (1)
-- Apriori algorithm for frequent item set mining (1)
-- Clustering: K means and Expectation maximization (2)
-- Classification: KNN and its theory (1)


- Hardness and Approximation (5)
======================================
-- Reductions: introduction (1)
-- Reductions: basic examples - indep. set to vertex cover, etc. (1)
-- Reductions: SAT to Independent Set, NP-completeness. (1)
-- NP-completeness. (1)
-- TSP (1)