COL351, Fall Semester 2026

Analysis and Design of Algorithms

Instructor: Rohit Vaish ()

Teaching Assistants:
TBA


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.

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.

  • For the institute's attendance requirements, only the submissions from tutorials will be taken into account.

  • Audits are not allowed.

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

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

  • Slides (TBA)
  • Additional reading: [R] Part 1, Chapter 1
  • Communicating algorithms
    		•
      Group 2: Tutorial Sheet 1 (TBA)
    July 29 (Wed)
    Lecture 3    		 Divide and Conquer II: Merge Sort (Contd.) and Asymptotic Analysis

  • Slides (TBA)
  • Additional reading: [R] Part 1, Chapters 1 and 2
  • Understanding (log) scale: Powers of Ten
    		•
    Jul 30 (Thurs)
      Group 3: Tutorial Sheet 1 (TBA)
    July 31 (Fri)
    Lecture 4    		 Divide and Conquer III: Counting Inversions

  • Slides (TBA)
  • Additional reading: [R] Part 1, Chapter 3
    		•
      Group 4: Tutorial Sheet 1 (TBA)
    Week 3
    Aug 03 (Mon)
      Group 1: Tutorial Sheet 2 (TBA)
    Aug 04 (Tue)
    Lecture 5    		 Divide and Conquer IV: Matrix Multiplication and Master Theorem

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

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

    Last date for course drop

  • Slides (TBA)
    		•
      Group 4: Tutorial Sheet 2 (TBA)
    Week 4
    Aug 10 (Mon)
      Group 1: Tutorial Sheet 3 (TBA)
    Aug 11 (Tue)
    Lecture 8    		 Graph Algorithms I: Basic Definitions, Representation, and Search

  • Slides (TBA)
  • Additional reading: [R] Part 2, Chapters 7 and 8

    • Last date for adding courses in lieu of dropped courses
    Finalization of roll lists
      Group 2: Tutorial Sheet 3 (TBA)
    Aug 12 (Wed)
    Lecture 9    		 Graph Algorithms II: BFS, DFS, and Applications

  • Slides (TBA)
  • Additional reading: [R] Part 2, Chapter 8
    		•
    Aug 13 (Thurs)
      Group 3: Tutorial Sheet 3 (TBA)
    Aug 14 (Fri)
    Lecture 10    		 Graph Algorithms III: Topological Ordering and Strongly Connected Components

  • Slides (TBA)
  • Additional reading: [R] Part 2, Chapter 8
    		•
      Group 4: Tutorial Sheet 3 (TBA)
    Week 5
    Aug 17 (Mon)
      Group 1: Tutorial Sheet 4 (TBA)
    Aug 18 (Tue)
    Lecture 11    		 Graph Algorithms IV: Kosaraju's Algorithm

  • Slides (TBA)
  • Additional reading: [R] Part 2, Chapter 8
    		•
      Group 2: Tutorial Sheet 4 (TBA)
    Aug 19 (Wed)
    Lecture 12    		 Graph Algorithms V: Dijkstra's Algorithm

  • Slides (TBA)
  • 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
  • How Google Maps finds shortest paths by Veritasium
    		•
    Aug 20 (Thurs)
      Group 3: Tutorial Sheet 4 (TBA)
    Aug 21 (Fri)
    Lecture 13    		 Greedy Algorithms I: Job Scheduling

  • Slides (TBA)
  • Additional reading: [R] Part 3, Chapter 13
    		•
      Group 4: Tutorial Sheet 4 (TBA)
    Week 6
    Aug 24 (Mon)
      Group 1: Tutorial Sheet 5 (TBA)
    Aug 25 (Tue)
    Lecture 14    		 Greedy Algorithms II: Job Scheduling (Contd.)

  • Slides (TBA)
  • Additional reading on Huffman Coding: [R] Part 3, Chapter 14, [KT] Chapter 4.8
  • How Computers Compress Text
    		•
      Group 2: Tutorial Sheet 5 (TBA)
    Aug 26 (Wed)
    Milad-un-Nabi    		 No Lecture
    Aug 27 (Thurs)
      Group 3: Tutorial Sheet 5 (TBA)
    Aug 28 (Fri)
    Lecture 15    		 Greedy Algorithms III: Minimum Spanning Trees

  • Slides (TBA)
  • On the History of MST Problem
  • Additional reading: [R] Part 3, Chapter 15
    		•
      Group 4: Tutorial Sheet 5 (TBA)
    Week 7
    Aug 31 (Mon)
      Group 1: Tutorial Sheet 6 (TBA)
    Sep 01 (Tue)
    Lecture 16    		 Quiz 2

  • Slides (TBA)
    		•
      Group 2: Tutorial Sheet 6 (TBA)
    Sep 02 (Wed)
    Lecture 17    		 Linear Programming I: Introduction

  • Slides (TBA)
  • Additional reading: Notes by Roughgarden
    		•
    Sep 03 (Thurs)
    Lecture 18
    Friday timetable    		 Linear Programming II: Applications

  • Slides (TBA)
  • Additional reading: Notes by Roughgarden
    		•
      Group 4: Tutorial Sheet 6 (TBA)
    Sep 04 (Fri)
    Janmashtami
    		 No Lecture
      Group 3: Tutorial Sheet 6 (to be organized on a different day)
    Week 8
    Sep 07 (Mon)
      Group 1: Tutorial Sheet 7 (TBA)
    Sep 08 (Tue)
    Lecture 19    		 Linear Programming III: Duality

  • Slides (TBA)
  • Additional reading: Notes by Roughgarden
    		•
      Group 2: Tutorial Sheet 7 (TBA)
    Sep 09 (Wed)
    Lecture 20    		 Linear Programming IV: Duality (contd.)

  • Slides (TBA)
  • Additional reading: Notes by Roughgarden
    		•
    Sep 10 (Thurs)
      Group 3: Tutorial Sheet 7 (TBA)
    Sep 11 (Fri)
    Lecture 21
    		 Mid-Term Review and Introduction to Dynamic Programming

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

    		•
      Group 4: Tutorial Sheet 7 (TBA)
    Week 9 (Sept 12-18)
    Date (TBA) Assignment 1
  • Slides (TBA)
    		•
      Week 10
      Sept 21 (Mon)
        Group 1: Tutorial Sheet 8 (TBA)
      Sept 22 (Tue)
      Lecture 22      		 Dynamic Programming I: Weighted Independent Set

    • Slides (TBA)
    • Additional reading: [R] Part 3, Chapter 16
      		•
        Group 2: Tutorial Sheet 8 (TBA)
      Sep 23 (Wed)
      Lecture 23      		 Dynamic Programming II: Weighted Independent Set (Contd.) and Knapsack

    • Slides (TBA)
    • Additional reading: [R] Part 3, Chapter 16
      		•
      Sep 24 (Thurs)
        Group 3: Tutorial Sheet 8 (TBA)
      Sep 25 (Fri) No lecture
      Mid-term evaluation of projects
        Group 4: Tutorial Sheet 8 (TBA; to be held on a different day)
      Week 11 (Mid-Semester Break)
      Sep 28-Oct 04 No Lectures
        No tutorials
      Week 12
      Oct 05 (Mon)
        Group 1: Tutorial Sheet 9 (TBA)
      Oct 06 (Tue)
      Lecture 24      		 Dynamic Programming III: Knapsack (Contd.) and Sequence Alignment

    • Slides (TBA)
    • Additional reading: [R] Part 3, Chapters 16 and 17
      		•
        Group 2: Tutorial Sheet 9 (TBA)
      Oct 07 (Wed)
      Lecture 25      		 Dynamic Programming IV: Sequence Alignment (Contd.) and Bellman-Ford Algorithm

    • Slides (TBA)
    • Additional reading: [R] Part 3, Chapters 17 and 18
      		•
      Oct 08 (Thurs)
        Group 3: Tutorial Sheet 9 (TBA)
      Oct 09 (Fri)
      Lecture 26      		 Dynamic Programming V: Bellman-Ford Algorithm (Contd.)

    • Slides (TBA)
    • Additional reading: [R] Part 3, Chapter 18
      		•
        Group 2: Tutorial Sheet 9 (TBA)
      Oct 10 (Sat)
      Lecture 27
      Wednesday timetable      		 Quiz 3

    • Slides (TBA)
      		•
      Week 13
      Oct 12 (Mon)
        Group 1: Tutorial Sheet 10 (TBA)
      Oct 13 (Tue)
      Lecture 28      		 Dynamic Programming VI: All Pairs Shortest Paths Problem

    • Slides (TBA)
    • Additional reading: [R] Part 3, Chapter 18
      		•
        Group 2: Tutorial Sheet 10 (TBA)
      Oct 14 (Wed)
      Lecture 29
      		 All Pairs Shortest Paths Problem (Contd.) and Introduction to Network Flows

    • Slides (TBA)
    • Additional reading: Notes by Roughgarden
    • Lectures [1, 2, 3, 4, 5] by David Karger
      		•
      Oct 15 (Thurs)
        Group 3: Tutorial Sheet 10 (TBA)
      Oct 16 (Fri)
      Lecture 30      		 Network Flow II: Ford-Fulkerson Algorithm

    • Slides (TBA)
    • Additional reading: Notes by Roughgarden
    • Visualizing flow algorithms
      		•
        Group 4: Tutorial Sheet 10 (TBA)
      Week 14
      Oct 19 (Mon)
        Group 1: Tutorial Sheet 11 (TBA)
      Oct 20 (Tues)
      Dussehra       		No Lecture
        Group 2: Tutorial Sheet 11 (TBA; to be held on a different day)
      Oct 21 (Wed)
      Lecture 31      		 Network Flow III: Maximum Flows and Minimum Cuts

    • Slides (TBA)
    • Additional reading: Notes by Roughgarden
      		•
      Oct 22 (Thurs)
        Group 3: Tutorial Sheet 11 (TBA)
      Oct 23 (Fri)
      Lecture 32      		 Network Flow IV: Edmonds-Karp Algorithm

    • Slides (TBA)
    • Additional reading: Notes by Roughgarden
      		•
        Group 4: Tutorial Sheet 11 (TBA)
      Week 15
      Oct 26 (Mon)
        Group 1: Tutorial Sheet 12 (TBA)
      Oct 27 (Tue)
      Lecture 33      		 Network Flow V: Edmonds-Karp Algorithm (Contd.) and Applications

    • Slides (TBA)
    • Additional reading: Notes by Roughgarden
      		•
        Group 2: Tutorial Sheet 12 (TBA)
      Oct 28 (Wed)
      Lecture 34      		 Quiz 4

    • Slides (TBA)
      		•
      Oct 29 (Thurs)
        Group 3: Tutorial Sheet 12 (TBA)
      Oct 30 (Fri)
      Lecture 35      		 Network Flow VI: Edmonds-Karp Runtime Analysis (Contd.)

    • Slides (TBA)
    • Additional reading: Notes by Roughgarden
      		•
        Group 4: Tutorial Sheet 12 (TBA)
      Week 16
      Nov 02 (Mon)
        Group 1: Tutorial Sheet 13 (TBA)
      Nov 03 (Tue)
      Lecture 36      		 Maximum Flow Applications (Contd.)

    • Slides (TBA)
    • Additional reading: Notes by Roughgarden
      		•
        Group 2: Tutorial Sheet 13 (TBA)
      Nov 04 (Wed)
      Lecture 37      		 NP-completeness I: Introduction

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapters 19 and 23
    • Fun with Hardness Proofs
      		•
      Nov 05 (Thurs)
        Group 3: Tutorial Sheet 13 (TBA)
      Nov 06 (Fri)
      Lecture 38      		 NP-completeness II: The Class NP

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapter 23
      		•
        Group 4: Tutorial Sheet 13 (TBA)
      Week 17
      Nov 09 (Mon)
      Govardhan Puja
        Group 1: Tutorial Sheet 14 (TBA; to be held on a different day)
      Nov 10 (Tue)
      Lecture 39      		 NP-completeness III: Reductions

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

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapters 19 and 22
      		•
      Nov 12 (Thurs)
        Group 3: Tutorial Sheet 14 (TBA)
      Nov 13 (Fri)
      Lecture 41      		 NP-completeness V: Reductions (Contd.) and P vs NP

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapters 22 and 23
      		•
        Group 4: Tutorial Sheet 14 (TBA)
      Week 18
      Nov 16 (Mon)
        No tutorial
      Nov 17 (Tue)
      Lecture 42      		 Wrap-Up

    • Slides (TBA)
    • Additional reading: [R] Part 4, Chapters 22 and 23
      		•
        No tutorial
      Date (TBA) Assignment 2
    • Slides (TBA)
      		•