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 ()


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      		 Dynamic Programming IV: Sequence Alignment (Contd.) and Bellman-Ford Algorithm

    • Slides
    • Additional reading: [R] Part 3, Chapters 17 and 18
      		•
      Oct 02 (Wed)
      Gandhi Jayanti      		 No lecture
      Oct 03 (Thurs)
      Oct 04 (Fri)
      Lecture 26      		 Network Flow I: Ford-Fulkerson Algorithm

    • Additional reading: Notes by Roughgarden
    • Lectures [1, 2, 3, 4, 5] by David Karger
      		•
      Week 12 (Mid-Semester Break)
      Oct 07-11 No Lectures
        No tutorials
      Week 13
      Oct 14 (Mon)
      Oct 15 (Tue)
      Lecture 27      		 Network Flow II: Maximum Flow and Minimum Cut

    • Additional reading: Notes by Roughgarden
      		•
      Oct 16 (Wed)
      Lecture 28      		 Quiz 3
      Oct 17 (Thurs)
      Oct 18 (Fri)
      Lecture 29      		 Network Flow III: Edmonds-Karp Algorithm

    • Additional reading: Notes by Roughgarden
      		•
      Oct 19 (Sat)
      Lecture 30
      Wednesday timetable      		 Network Flow IV: Applications of Flows and Cuts

    • Additional reading: Notes by Roughgarden
      		•
      Week 14
      Oct 21 (Mon)
      Oct 22 (Tue)
      Lecture 31      		 Network Flow V: Minimum-Cost Bipartite Matching

    • Additional reading: Notes by Roughgarden
      		•
      Oct 23 (Wed)
      Lecture 32      		 Linear Programming I: Introduction and Applications

    • Additional reading: Notes by Roughgarden
    • Dantzig's article
      		•
      Oct 24 (Thurs)
      Oct 25 (Fri)
      Lecture 33      		 Linear Programming II: Duality (Part 1)

    • Additional reading: Notes by Roughgarden
    • The S-O-B method for remembering duals
    • A refresher on linear programming
    • Interactive website for writing dual LPs
      		•
      Oct 26 (Sat)
      Lecture 34
      Friday timetable      		 Linear Programming III: Duality (Part 2)

    • Additional reading: Notes by Roughgarden
      		•
        No tutorial
      Week 15
      Oct 28 (Mon)
      Oct 29 (Tue)
      Lecture 35      		 Linear Programming IV: Survey of LP Algorithms

    • Additional reading: Notes by Roughgarden
      		•
      Oct 30 (Wed)
      Lecture 36      		 Quiz 4
      Oct 31 (Thurs)
      Diwali
        No tutorial
      Nov 01 (Fri)
      Lecture 37      		 NP-completeness I: Introduction

    • Additional reading: [R] Part 4, Chapter 19
      		•
      Week 16
      Nov 04 (Mon)
      Nov 05 (Tue)
      Lecture 38      		 NP-completeness II: Reductions

    • Additional reading: [R] Part 4, Chapter 22
      		•
      Nov 06 (Wed)
      Lecture 39      		 NP-completeness III: More Reductions

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

    • Additional reading: [R] Part 4, Chapter 22
    • Fun with Hardness Proofs
      		•
      Week 17
      Nov 11 (Mon)
        No tutorial
      Nov 12 (Tue)
      Lecture 41      		 NP-completeness V: P vs NP, ETH, and SETH

    • Additional reading: [R] Part 4, Chapter 23
      		•
        No tutorial
      Nov 13 (Wed)
      Lecture 42      		 Wrap-Up

    • Additional reading: TBA
      		•
      Week 18
      TBA End-Semester Examination
      TBA Make-Up Exam