COL351, Fall Semester 2024

Analysis and Design of Algorithms

Instructor: Rohit Vaish ()

Teaching Assistants:
Lakshay Saggi (),
Pratikkumar Sureshkumar Bulani (),
Gaurav Rajput (),
Adithya R Narayan (),
Shivansh Garg (),
Vaibhav Katendra (),
Ramanuj Goel (),
Geetansh Juneja (),
Samyak Jain (),
Mayank Mangla ()


Course Information

What this course is about

This course will provide an introduction to the fascinating field of algorithms. Participants will learn various techniques for designing algorithms and formally reasoning about their correctness and resource requirements.

Who is this course aimed at

The course is designed for third-year undergraduate students. This offering of COL351 is for CS students; non-CS students should sign up for the Spring semester offering.

Prerequisites

This is a theoretical course that will require familiarity with Data Structures (COL106) and Discrete Mathematical Structures (COL202).

References
  • [DPV] Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms. First Edition.
  • [KT] Jon Kleinberg and Éva Tardos. Algorithm Design. First Edition
  • [R] Tim Roughgarden. Algorithms Illuminated, Parts 1-4. [Website]
  • A Second Course in Algorithms at Stanford
Other resources


Admin

Lecture and tutorial timings

Lectures: TWF 10-11 AM. Venue: LH 121.

Tutorials: M/T/Th/F 1-2 PM. Venue: LH 408. (Tutorial Groups).

Sign up on the Microsoft Teams channel of the course for announcements.

Evaluation policy

Tutorial quizzes: 24% (best eight x 3%)
In-class quizzes: 36% (best three x 12%)
Minor: 20%
Major: 20%

  • For missed minor and/or major exams due to a medical reason, a single exam will be held after the regular major exam (date will be announced later), for which the syllabus will be the entire course. The weightage of this make-up exam will be 20%.

    Only those who obtain prior approval from the instructor (before the date of the missed regular minor and/or regular major exam) and have at least 75% attendance will qualify for this exam. In particular, if you miss both the regular minor and the regular major exam, there will still be only one make-up exam (worth 20%).

  • For students with an E grade, a remajor exam will be held at the start of the next semester. Again, at least 75% attendance will be required.

  • Audit policy: No audits allowed.
 
Date and Lecture Topic Tutorials
Week 1
July 22 (Mon)
    No tutorial
July 23 (Tue)
Lecture 1
Introduction to Algorithms

  • Slides
  • Additional reading: [R] Part 1 Chapter 1
    • No tutorial
    July 24 (Wed)
    Lecture 2
    Divide and Conquer I: Integer Multiplication and Merge Sort

  • Slides
  • Additional reading: [R] Part 1, Chapter 1
  • Communicating algorithms
    July 25 (Thurs)
      No tutorial
    July 26 (Fri)
    Lecture 3
    Divide and Conquer II: Merge Sort (Contd.) and Asymptotic Analysis

  • Slides
  • Additional reading: [R] Part 1, Chapters 1 and 2
  • Understanding (log) scale: Powers of Ten
    • No tutorial
    Week 2
    July 29 (Mon)
    July 30 (Tue)
    Lecture 4
    Divide and Conquer III: Asymptotic Analysis (Contd.) and Counting Inversions

  • Slides
  • Additional reading: [R] Part 1, Chapters 2 and 3
  • July 31 (Wed)
    Lecture 5
    Divide and Conquer IV: Counting Inversions (Contd.), Matrix Multiplication and Master Theorem

  • Slides
  • Additional reading: [R] Part 1, Chapters 3 and 4
  • Timeline of matrix multiplication exponent
  • Quanta article on matrix multiplication
    Aug 01 (Thurs)
    Aug 02 (Fri)
    Lecture 6
    Divide and Conquer V: Proof and Applications of Master Theorem

  • Slides
  • Additional reading: [R] Part 2, Chapters 4
  • The "grandmaster" theorem
  • Slides by Rohit Gurjar
  • Quanta article on integer multiplication
  • Week 3
    Aug 05 (Mon) Last date for course drop
    Aug 06 (Tue)
    Lecture 7
    Quiz 1

  • Solutions
  • Aug 07 (Wed)
    Lecture 8
    Graph Algorithms I: Basic Definitions

  • Slides
  • Additional reading: [R] Part 2, Chapter 7

  • Last date for adding courses in lieu of dropped courses
    Finalization of roll lists
    Aug 08 (Thurs)
    Aug 09 (Fri)
    Lecture 9
    Graph Algorithms II: Representation and Search

  • Slides
  • Additional reading: [R] Part 2, Chapter 8
  • Week 4
    Aug 12 (Mon)
    Aug 13 (Tue)
    Thursday timetable
    No lecture
    Aug 14 (Wed)
    Lecture 10
    Graph Algorithms III: BFS, DFS, and Applications

  • Slides
  • Additional reading: [R] Part 2, Chapter 8
    Aug 15 (Thurs)
    Independence Day

      No tutorial
    Aug 16 (Fri)
    No Class Day
    No lecture
      No tutorial
    Week 5
    Aug 19 (Mon)
    Rakshabandhan

      No tutorial
    Aug 20 (Tue)
    Lecture 11
    Graph Algorithms IV: Topological Ordering and Strongly Connected Components

  • Slides
  • Additional reading: [R] Part 2, Chapter 8
  • Aug 21 (Wed)
    Lecture 12
    Graph Algorithms V: Kosaraju's Algorithm

  • Slides
  • Additional reading: [R] Part 2, Chapter 8
    Aug 22 (Thurs)

    Aug 23 (Fri)
    Lecture 13
    Graph Algorithms VI: Dijkstra's Algorithm

  • Slides
  • Additional reading: [R] Part 2, Chapters 9 and 10 (for Heaps)
  • Paper on bow tie structure of the web
  • Small-world experiment and Six degrees of separation
  • Dijkstra's Turing Award Lecture
  • Week 6
    Aug 26 (Mon)
    Janmashtami

      No tutorial
    Aug 27 (Tue)
    Lecture 14
    Greedy Algorithms I: Job Scheduling

  • Slides
  • Additional reading: [R] Part 3, Chapter 13
  • Aug 28 (Wed)
    Lecture 15
    Greedy Algorithms II: Job Scheduling (Contd.) and Huffman Coding

  • Slides
  • Additional reading: [R] Part 3, Chapter 14, [KT] Chapter 4.8
    Aug 29 (Thurs)
    Aug 30 (Fri)
    Lecture 16
    Quiz 2

  • Solutions
  • Aug 31 (Sat)
    Monday timetable

    Week 7
    Sep 02 (Mon)
    Sep 03 (Tue)
    Lecture 17
    Greedy Algorithms III: Huffman Coding (Contd.)

  • Slides
  • Additional reading: [R] Part 3, Chapter 14, [KT] Chapter 4.8
  • Sep 04 (Wed)
    Lecture 18
    Greedy Algorithms IV: Huffman's Algorithm

  • Slides
  • How Computers Compress Text
  • Additional reading: [R] Part 3, Chapter 14, [KT] Chapter 4.8
    Sep 05 (Thurs)

    Sep 06 (Fri)
    Lecture 19
    Greedy Algorithms V: Minimum Spanning Trees

  • Slides
  • On the History of MST Problem
  • Additional reading: [R] Part 3, Chapter 15
  • Week 8
    Sep 09 (Mon)
    Sep 10 (Tue)
    Lecture 20
    Greedy Algorithms VI: Minimum Spanning Trees (Contd.)

  • Slides
  • Additional reading: [R] Part 3, Chapter 15
  • Sep 11 (Wed)
    Lecture 21
    Friday timetable
    Mid-Term Review and Introduction to Dynamic Programming

  • Slides
  • Additional reading: [R] Part 3, Chapter 16

  • Weeks 8 and 9 (Sept 12-18)
    Sep 17 (Tue) Mid-Semester Examination (8 AM-10 AM) at LH 121 and LH 325
  • Solutions
    • Week 9
      Sept 19 (Thurs)
      Sept 20 (Fri)
      Lecture 22
      Dynamic Programming I: Weighted Independent Set

    • Slides
    • Additional reading: [R] Part 3, Chapter 16
    • Week 10
      Sep 23 (Mon)

      Sep 24 (Tue)
      Lecture 23
      Dynamic Programming II: Weighted Independent Set (Contd.) and Knapsack

    • Slides
    • Additional reading: [R] Part 3, Chapter 16
    • Sep 25 (Wed)
      Lecture 24
      Dynamic Programming III: Knapsack (Contd.) and Sequence Alignment

    • Slides
    • Additional reading: [R] Part 3, Chapters 16 and 17
      Sep 26 (Thurs)

      Sep 27 (Fri) No lecture
      Mid-term evaluation of projects
        No tutorial
      Week 11
      Sep 30 (Mon)
      Oct 01 (Tue)
      Lecture 25
      No lecture

      Oct 02 (Wed)
      Gandhi Jayanti
      No lecture
      Oct 03 (Thurs)

      Oct 04 (Fri)
      Lecture 26
      Dynamic Programming IV: Sequence Alignment (Contd.) and Bellman-Ford Algorithm

    • Slides
    • Additional reading: [R] Part 3, Chapters 17 and 18
    • Week 12 (Mid-Semester Break)
      Oct 07-11 No Lectures
        No tutorials
      Week 13
      Oct 14 (Mon)
      Oct 15 (Tue)
      Lecture 27
      Dynamic Programming V: Bellman-Ford Algorithm (Contd.)

    • Slides
    • Additional reading: [R] Part 3, Chapter 18
    • Oct 16 (Wed)
      Lecture 28
      Quiz 3
    • Solutions
      Oct 17 (Thurs)
      Oct 18 (Fri)
      Lecture 29
      Dynamic Programming VI: All Pairs Shortest Paths Problem

    • Slides
    • Additional reading: [R] Part 3, Chapter 18
    • Oct 19 (Sat)
      Lecture 30
      Wednesday timetable
      All Pairs Shortest Paths Problem (Contd.) and Introduction to Network Flows

    • Slides
    • Additional reading: Notes by Roughgarden
    • Lectures [1, 2, 3, 4, 5] by David Karger
      Week 14
      Oct 21 (Mon)
      Oct 22 (Tue)
      Lecture 31
      Network Flow II: Ford-Fulkerson Algorithm

    • Slides
    • Additional reading: Notes by Roughgarden
    • Oct 23 (Wed)
      Lecture 32
      Network Flow III: Maximum Flows and Minimum Cuts

    • Slides
    • Additional reading: Notes by Roughgarden
      Oct 24 (Thurs)

      Oct 25 (Fri)
      Lecture 33
      Network Flow IV: Edmonds-Karp Algorithm

    • Slides
    • Additional reading: Notes by Roughgarden
    • Oct 26 (Sat)
      Lecture 34
      Friday timetable
      Network Flow V: Edmonds-Karp Algorithm (Contd.) and Applications

    • Slides
    • Additional reading: Notes by Roughgarden
      • No tutorial
      Week 15
      Oct 28 (Mon)
      Oct 29 (Tue)
      Lecture 35
      Quiz 4

    • Solutions
    • Oct 30 (Wed)
      Lecture 36
      Network Flow VI: Edmonds-Karp Runtime Analysis (Contd.)

    • Slides
    • Additional reading: Notes by Roughgarden
      Oct 31 (Thurs)
      Diwali
        No tutorial
      Nov 01 (Fri)
      Lecture 37
      Maximum Flow Applications (Contd.)

    • Slides
    • Additional reading: Notes by Roughgarden
    • Week 16
      Nov 04 (Mon)
      Nov 05 (Tue)
      Lecture 38
      NP-completeness I: Introduction

    • Slides
    • Additional reading: [R] Part 4, Chapters 19 and 23
    • Fun with Hardness Proofs
    • Nov 06 (Wed)
      Lecture 39
      NP-completeness II: The Class NP

    • Slides
    • Additional reading: [R] Part 4, Chapter 23
      Nov 07 (Thurs)
      Nov 08 (Fri)
      Lecture 40
      NP-completeness III: More Reductions

    • Additional reading: [R] Part 4, Chapter 22
    • Week 17
      Nov 11 (Mon)
        No tutorial
      Nov 12 (Tue)
      Lecture 41
      NP-completeness IV: Even More Reductions

    • Additional reading: [R] Part 4, Chapter 22
      • No tutorial
      Nov 13 (Wed)
      Lecture 42
      NP-completeness V: P vs NP, ETH, SETH and Wrap-Up

    • Additional reading: [R] Part 4, Chapter 23
      Week 18
      Nov 22 (Fri) End-Semester Examination
      TBA Make-Up Exam