Graduate Algorithms

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, NP-completeness where the UG contents of each topic is first reviewed in a fast-paced 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
    • C1-i will denote lecture set i from C1, C2-j 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.

Homeworks

Not all problems of a homework may be graded, some of them are purely for your own practice. No late submission is allowed.

  1. Reading - JE Appendix I & II
    Problems - HW1
    Due: Friday 9th Saturday 10th August 5pm
  2. Reading - JE Appendix II - Section 2.4
    Problems - HW2
    Due: Monday 19th August 1pm
  3. Reading - JE-1
    Problems - HW3
    Due: Friday 23rd August 5pm
  4. See HW for reading sections and problems.
    Due: Monday 9th Sept 1pm.
  5. See HW for reading sections and problems.
    Due: Friday 20th Sept 5pm.
  6. See HW for reading sections and problems.
    Due: Friday 11th Oct 5pm.
  7. See HW for problems.
    Due: Friday 25th Oct 5pm.
  8. See HW8 for problems.
    Due: Monday 11th Nov 5pm.

Instructor: Debajyoti Bera (B204, Academic Office)
Teaching Assistants: Monalisa Jena (PhD Lab 2nd floor B-wing), Aniya Aggarwal, Shilpi Jain
Lecture Venue: C11, Monday & Thursday 2-3:30

Office hours:
Monalisa Jena - Wednesday 2-4pm
Debajyoti Bera - Monday 3:30-5pm    Thursday 3:30-4:00pm

Pre-requisites

  • Undergraduate Algorithms course
Open only to M.Tech. students in Monsoon 2013 semester.
(recommended for students with inadequate background in Algorithms)

Lecture-wise topics

 1. 05/08

HW1
Introduction to Algorithm Analysis [C1-1, JE0, JE1]
  • Integer Multiplication digit-by-digit, Karatsuba, Russian Peasant
  • Integer exponentiation
 2. 08/08Tools of Algorithm Analysis [C1-2, JE0, JE1]
  • Analysis of few simple sorting
  • Asymptotic Notation
 3. 12/08
HW2
HW3
  • Divide and Conquer Algorithms [C1-3]
 4. 22/08

  • Master Method [C1-4]
  • Solving Recurrences [JE-1]
 5. 26/08

  • Probability in Algorithms [C1-7]
  • Quicksort [C1-5,6]
 6. 29/08
Quiz1
  • Recap
 7. 02/09
HW4
  • Selection Algorithms & Comparison Lower Bound [C1-8]
 8. 05/09

  • Graphs and Contraction [C1-9]
  • Graph Traversal & Search [C1-10, JE-17]
 9. 09/09

  • Graph Shortest Path [C1-11, JE-19]
10.12/09
HW5
  • Heaps [C1-12]
11.16/09

  • Balanced Trees [C1-13, JE-10]
12.19/09
  • Hashing, Universal Hashing & Bloom Filter [C1-14,15,16]

Mid-sem Exam
13.30/09
  • Greedy Algorithms [C2-3,4]
14.03/10
  • MST (Prim & Kruskal) [C2-5,6]
15.07/10
  • Clustering [C2-7]
  • Huffman Codes [C2-9]
16.10/10
  • Greedy Algorithms
17.14/10
  • Union-Find [C2-8]
18.17/10
  • Union-Find Log* and Inverted Ackermann Analysis [C2-8]
19.21/10
  • Dynamic Programming [C2-10]
20.24/10 
  • Dynamic Programming on Trees [C2-13]
  • Sequence Alignment [C2-12]
21.28/10
  •  Knapsack [C2-11]
22.31/10
  • Bellman-Ford [C2-14]
  • All-Pairs Shortest Path [C2-15]
23.11/11
  • NP-complete problems [C2-16]
  • Exact Algorithms for NP-complete problems [C2-17]
24.14/11
  •  Approximation Algorithms for NP-complete problems [C2-18]
25.18/11
  •  Local Search Algorithms [C2-19]
26.21/11
  •  Matching, Flows, Optimization [C2-20]
 End-sem Exam


Subpages (1): Homeworks