This course is an advanced form of an introductory algorithms course, and is meant to have a thorough grounding in core Algorithms required for pursuing PG degree in Computer Science. The course covers topics such as asymptotic notation, recurrence relation, graph algorithms, heaps, dynamic programming, greedy algorithms, divide and conquer, NPcompleteness where the UG contents of each topic is first reviewed in a fastpaced manner, and is followed by some advanced content. Post Conditions Improve knowledge and understanding of material in a standard UG algorithms course
 Impart knowledge of essential algorithmic techniques in design and analysis to pursue PG level courses and projects
Course Material Video lectures of Tim Roughgarden: [C1] Course 1 [C2] Course 2
 C1i will denote lecture set i from C1, C2j will denote lecture set j from C2
 Lecture notes by Jeff Erickson
 JE will denote these material
Topics will be those covered by C1 and C2. If time permits, we will also cover additional topics like Generating Function for solving recurrences, Fast Fourier Transform, Matroids, and, Brute force search algorithms.
Lectures will follow inverted classroom approach A set of video lectures will be specified before every lecture. Students are supposed to study the video lecture before coming to class.
 Course lecture hours will be used primarily for clarification and problem solving.
HomeworksNot all problems of a homework may be graded, some of them are purely for your own practice. No late submission is allowed.
 Reading  JE Appendix I & II
Problems  HW1 Due: Friday 9th Saturday 10th August 5pm  Reading  JE Appendix II  Section 2.4
Problems  HW2 Due: Monday 19th August 1pm  Reading  JE1
Problems  HW3 Due: Friday 23rd August 5pm  See HW for reading sections and problems.
Due: Monday 9th Sept 1pm.  See HW for reading sections and problems.
Due: Friday 20th Sept 5pm.  See HW for reading sections and problems.
Due: Friday 11th Oct 5pm.  See HW for problems.
Due: Friday 25th Oct 5pm.  See HW8 for problems.
Due: Monday 11th Nov 5pm.

Teaching Assistants: Monalisa Jena (PhD Lab 2nd floor Bwing), Aniya Aggarwal, Shilpi Jain Lecture Venue: C11, Monday & Thursday 23:30
Office hours: Monalisa Jena  Wednesday 24pm Debajyoti Bera  Monday 3:305pm Thursday 3:304:00pm Prerequisites Undergraduate Algorithms course
Open only to M.Tech. students in Monsoon 2013 semester. (recommended for students with inadequate background in Algorithms) Lecturewise topics 1. 05/08
HW1
 Introduction to Algorithm Analysis [C11, JE0, JE1]
 Integer Multiplication digitbydigit, Karatsuba, Russian Peasant
 Integer exponentiation
 2. 08/08  Tools of Algorithm Analysis [C12, JE0, JE1]
 Analysis of few simple sorting
 Asymptotic Notation
 3. 12/08
HW2 HW3
  Divide and Conquer Algorithms [C13]
 4. 22/08
  Master Method [C14]
 Solving Recurrences [JE1]
 5. 26/08
  Probability in Algorithms [C17]
 Quicksort [C15,6]
 6. 29/08
Quiz1
  7. 02/09
HW4
  Selection Algorithms & Comparison Lower Bound [C18]
 8. 05/09
  Graphs and Contraction [C19]
 Graph Traversal & Search [C110, JE17]
 9. 09/09
  Graph Shortest Path [C111, JE19]
 10.12/09
HW5
  11.16/09
  Balanced Trees [C113, JE10]
 12.19/09
  Hashing, Universal Hashing & Bloom Filter [C114,15,16]

 Midsem Exam
 13.30/09   Greedy Algorithms [C23,4]
 14.03/10   MST (Prim & Kruskal) [C25,6]
 15.07/10   Clustering [C27]
 Huffman Codes [C29]
 16.10/10   17.14/10   18.17/10   UnionFind Log* and Inverted Ackermann Analysis [C28]
 19.21/10   Dynamic Programming [C210]
 20.24/10   Dynamic Programming on Trees [C213]
 Sequence Alignment [C212]
 21.28/10   22.31/10   BellmanFord [C214]
 AllPairs Shortest Path [C215]
 23.11/11   NPcomplete problems [C216]
 Exact Algorithms for NPcomplete problems [C217]
 24.14/11   Approximation Algorithms for NPcomplete problems [C218]
 25.18/11   Local Search Algorithms [C219]
 26.21/11   Matching, Flows, Optimization [C220]
  Endsem Exam

