COL351, Fall Semester 2026

Analysis and Design of Algorithms

Instructor: Rohit Vaish ()

Teaching Assistants:
Abhishek Tiwari (),
Sanchita Saha (),
Anshul Vijayvergiya (),
Nayan Rabadiya (),
Yash Bansal (),
Satwik (),
Omar Islam Laskar (),
Sharayu Shivajirao Deshmukh (),
Kalavala Navya ()


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.
  • [GM] Bernd Gärtner and Jiří Matoušek. Understanding and Using Linear Programming. First Edition
  • [KT] Jon Kleinberg and Éva Tardos. Algorithm Design. First Edition
  • [R] Tim Roughgarden. Algorithms Illuminated, Parts 1-4.
  • A Second Course in Algorithms at Stanford
Other resources


Admin

Lecture and tutorial timings

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

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

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

Office hours

With TAs: Tuesday 6-7 PM. Venue: Bharti 408.

With Instructor: Via Email. Venue: Bharti 428.

Evaluation policy

Tutorial quizzes: 30% (best ten x 3%)
In-class quizzes: 45% (best three x 15%)
Assignments: 25% (best one x 25%)

  • There are no minor or major exams in this course; therefore, there will be no opportunity for a repeat minor or repeat major exam, except possibly for an E-grade remajor in January 2027. Additionally, there will be no make-up tutorial quiz, in-class quiz, or assignment.

  • All evaluations will take place under invigilation.

  • The use of any electronic devices during lectures, tutorials, or course evaluations is prohibited.

  • The submissions from tutorial quizzes will count towards the attendance.

  • Audits are not allowed.

Date and Lecture Topic Tutorials
Week 1
July 24 (Fri)
Lecture 1		 Introduction to Algorithms

  • Slides
  • Additional reading: [R] Part 1 Chapter 1
    		•
      No tutorial
    Week 2
    July 27 (Mon)
    July 28 (Tue)
    Lecture 2    		 Divide and Conquer I: Integer Multiplication and Merge Sort

  • Slides
  • Additional reading: [R] Part 1, Chapter 1
  • Communicating algorithms
    		•
    July 29 (Wed)
    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
    		•
    Jul 30 (Thurs)
    July 31 (Fri)
    Lecture 4    		 Divide and Conquer III: Asymptotic Analysis (Contd.)

  • Slides
  • Additional reading: [R] Part 1, Chapter 2
    		•
    Week 3
    Aug 03 (Mon)
    Aug 04 (Tue)
    Lecture 5    		 Divide and Conquer IV: Counting Inversions and Matrix Multiplication

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

  • Slides
  • Additional reading: [R] Part 2, Chapter 4
  • The "grandmaster" theorem
  • Slides by Rohit Gurjar
  • Quanta article on integer multiplication
    		•
    Aug 06 (Thurs)
    Aug 07 (Fri)
    Lecture 7    		 Quiz 1 (LH 121)

    Last date for course drop
    Week 4
    Aug 10 (Mon)
    Aug 11 (Tue)
    Lecture 8    		 Graph Algorithms I: Basic Definitions and Representation

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

    • Last date for adding courses in lieu of dropped courses
    Finalization of roll lists
    Aug 12 (Wed)
    Lecture 9    		 Graph Algorithms II: Representation (Contd.) and Search

  • Slides
  • Additional reading: [R] Part 2, Chapter 8
  • Rubik's cube graph
    		•
    Aug 13 (Thurs)
    Aug 14 (Fri)
    Lecture 10    		 Graph Algorithms III: BFS, DFS, and Applications

  • Slides
  • Additional reading: [R] Part 2, Chapter 8
    		•
    Week 5
    Aug 17 (Mon)
    Aug 18 (Tue)
    Lecture 11    		 Graph Algorithms IV: Topological Ordering and Strongly Connected Components

  • Slides
  • Additional reading: [R] Part 2, Chapter 8
    		•
    Aug 19 (Wed)
    Lecture 12    		 Graph Algorithms V: Strongly Connected Components (Contd.)

  • Slides
  • Additional reading: [R] Part 2, Chapter 8
  • Paper on bow tie structure of the web
  • Small-world experiment and Six degrees of separation
    		•
    Aug 20 (Thurs)
    Aug 21 (Fri)
    Lecture 13    		 Graph Algorithms V: Dijkstra's Algorithm

  • Slides
  • Additional reading: [R] Part 2, Chapters 9 and 10 (for Heaps)
  • Dijkstra's Turing Award Lecture
  • How Google Maps finds shortest paths by Veritasium
    		•
    Week 6
    Aug 24 (Mon)
    Aug 25 (Tue)
    Lecture 14    		 Greedy Algorithms I: Job Scheduling

  • Slides
  • Additional reading: [R] Part 3, Chapter 13
    		•
    Aug 26 (Wed)
    Milad-un-Nabi    		 No Lecture
    Aug 27 (Thurs)
    Aug 28 (Fri)
    Lecture 15    		 Greedy Algorithms II: Job Scheduling (Contd.)

  • Slides
  • Additional reading on Huffman Coding: [R] Part 3, Chapter 14, [KT] Chapter 4.8
  • How Computers Compress Text
    		•
    Week 7
    Aug 31 (Mon)
    Sep 01 (Tue)
    Lecture 16    		 Quiz 2 (LH 121)
    Sep 02 (Wed)
    Lecture 17    		 Greedy Algorithms III: Minimum Spanning Trees

  • Slides
  • On the History of MST Problem
  • Additional reading: [R] Part 3, Chapter 15
    		•
    Sep 03 (Thurs)
    Lecture 18
    Friday timetable    		 Greedy Algorithms IV: Minimum Spanning Trees (Contd.)

  • Slides
  • Additional reading: [R] Part 3, Chapter 15
    		•
    Sep 04 (Fri)
    Janmashtami
    		 No Lecture
      Group 3: Tutorial Sheet 6
      Rescheduled to Sep 02 (Wed), 5:30-6:30 PM, Bharti 501
    Week 8
    Sep 07 (Mon)
    Sep 08 (Tue)
    Lecture 19    		 Greedy Algorithms V: Kruskal's Algorithm

  • Slides
  • Additional reading: [R] Part 3, Chapter 15
    		•
    Sep 09 (Wed)
    Lecture 20    		 Dynamic Programming I: Weighted Independent Set

  • Slides
  • Additional reading: [R] Part 3, Chapter 16
    		•
    Sep 10 (Thurs)
    Sep 11 (Fri)

    		 No Lecture
    BRICS Summit
    Week 9 (Sept 12-18)
    Sep 19 (Sat) Assignment 1 (9 AM-1 PM, LH 121)
      Week 10
      Sept 21 (Mon)
      Sept 22 (Tue)
      Lecture 21      		 Dynamic Programming II: Knapsack

    • Slides
    • Additional reading: [R] Part 3, Chapter 16
      • Sep 23 (Wed)
      Lecture 22      		 Dynamic Programming III: Knapsack (Contd.)

    • Slides
    • Additional reading: [R] Part 3, Chapter 16
      		•
      Sep 24 (Thurs)
      Sep 25 (Fri) No lecture
      Mid-term evaluation of projects
      Week 11 (Mid-Semester Break)
      Sep 28-Oct 04 No Lectures
        No tutorials
      Week 12
      Oct 05 (Mon)
      Oct 06 (Tue)
      Lecture 23      		 Dynamic Programming IV: Sequence Alignment

    • Slides
    • Additional reading: [R] Part 3, Chapter 17
      		•
      Oct 07 (Wed)
      Lecture 24      		 Dynamic Programming V: Bellman Ford Algorithm

    • Slides
    • Additional reading: [R] Part 3, Chapter 18
      		•
      Oct 08 (Thurs)
      Oct 09 (Fri)
      Lecture 25      		 Quiz 3 (LH 121)
      Oct 10 (Sat)
      Lecture 26
      Wednesday timetable      		 Dynamic Programming VI: Bellman Ford Algorithm (Contd.)

    • Slides
    • Additional reading: [R] Part 3, Chapter 18
      		•
      Week 13
      Oct 12 (Mon)
      Oct 13 (Tue)
      Lecture 27      		 Dynamic Programming VII: Bellman Ford Algorithm (Contd.)

    • Slides
    • Additional reading: [R] Part 3, Chapter 18
      		•
      Oct 14 (Wed)
      Lecture 28
      		 Dynamic Programming VIII: All Pairs Shortest Paths Problem

    • Slides
    • Additional reading: [R] Part 3, Chapter 18
      		•
      Oct 15 (Thurs)
      Oct 16 (Fri)
      Lecture 29      		 Network Flow I: Introduction and Ford-Fulkerson Algorithm

    • Slides
    • Additional reading: Notes by Roughgarden
    • Lectures [1, 2, 3, 4, 5] by David Karger
    • Visualizing flow algorithms
      		•
      Week 14
      Oct 19 (Mon)
      Oct 20 (Tues)
      Dussehra       		No Lecture
      Oct 21 (Wed)
      Lecture 30      		 Network Flow II: Maximum Flows and Minimum Cuts

    • Slides
    • Additional reading: Notes by Roughgarden
      		•
      Oct 22 (Thurs)
      Oct 23 (Fri)
      Lecture 31      		 Network Flow III: Maximum Flows and Minimum Cuts (Contd.)

    • Slides
    • Additional reading: Notes by Roughgarden
      		•
      Week 15
      Oct 26 (Mon)
      Oct 27 (Tue)
      Lecture 32      		 Network Flow IV: Edmonds-Karp Algorithm and Applications

    • Slides
    • Additional reading: Notes by Roughgarden
      		•
      Oct 28 (Wed)
      Lecture 33      		 No Lecture
      Oct 29 (Thurs)
      Oct 30 (Fri)
      Lecture 34      		 Quiz 4 (LH 325)
      Week 16
      Nov 02 (Mon)
        Group 1: Tutorial 13---Recap of Sheets 1-12
      Nov 03 (Tue)
      Lecture 35      		 Network Flow V: Edmonds-Karp Runtime Analysis (Contd.)

    • Slides (TBA)
    • Additional reading: Notes by Roughgarden
      		•
        Group 2: Tutorial 13---Recap of Sheets 1-12
      Nov 04 (Wed)
      Lecture 36      		 Network Flow VI: Maximum Flow Applications (Contd.)

    • Slides (TBA)
    • Additional reading: Notes by Roughgarden
      		•
      Nov 05 (Thurs)
        Group 3: Tutorial 13---Recap of Sheets 1-12
      Nov 06 (Fri)
      Lecture 37      		 NP-completeness I: Introduction

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapters 19 and 23
    • Fun with Hardness Proofs
      		•
        Group 4: Tutorial 13---Recap of Sheets 1-12
      Week 17
      Nov 09 (Mon)
      Govardhan Puja
        Group 1: Tutorial Sheet 14 (TBA; to be held on a different day)
      Nov 10 (Tue)
      Lecture 38      		 NP-completeness II: The Class NP

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapter 23
      		•
        Group 2: Tutorial Sheet 14 (TBA)
      Nov 11 (Wed)
      Lecture 39      		 NP-completeness III: Reductions

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapter 22
    • What Makes Mario NP-hard?
      		•
      Nov 12 (Thurs)
        Group 3: Tutorial Sheet 14 (TBA)
      Nov 13 (Fri)
      Lecture 40      		 NP-completeness IV: Reductions (Contd.)

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapters 19 and 22
      		•
        Group 4: Tutorial Sheet 14 (TBA)
      Week 18
      Nov 16 (Mon)
        No tutorial
      Nov 17 (Tue)
      Lecture 41      		 NP-completeness V: Reductions (Contd.) and P vs NP

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapters 22 and 23
      		•
        No tutorial
      Nov 18 (Wed) Assignment 2 (9 AM-1 PM, LH 121)