CS 3510: Design & Analysis of Algorithms

Fall 2021

Welcome to the course page for CS 3510 in Fall 2021, Georgia Tech’s undergraduate introductory course on algorithms and algorithmic thinking.

(You can find the Fall 2020 course page here)

Click to view the syllabus

Course Content

DPV refers to the textbook of Dasgupta, Papdimitriou, and Vazirani.

Recurrences and Cryptography

Day 1, Tuesday 8/24/2021: Introduction to Course
- Link to live session
- Introduction to course, overview of format
- Videos:
  - Course Intro Video
Day 2, Thursday 8/26/2021: Big-O, Logs, Fibonacci
- Link to live session
- Required Reading: DPV Chapter 0
- Videos:
- Homework 1A released, due Sunday 9/5 11pm
Day 3, Tuesday 8/31/2021: MergeSort and Multiplication
- Link to live session
- Required Reading: DPV Chapter 2.1 & 2.3
- Videos:
Day 4, Thursday 9/2/2021: Recurrences and Matrix Multiplication
- Link to live session
- Required Reading: DPV Chapter 2.2 & 2.5
- Videos:
Day 5, Tuesday 9/7/2021: Modular Arithmetic
- Required Reading: DPV Chapter 1.2 & 1.3
- Videos:
- Homework 1B released, due Sunday 9/19 11pm
Day 6, Thursday 9/9/2021: RSA Cryptosystem
- Required Reading: DPV Chapter 1.4
- Videos:
- Code: Want to see the RSA code in action? Here we do all of the operations in python.
Day 7, Tuesday 9/14/2021: Fast Fourier Transform
- Required Reading: DPV Chapter 2.6
- Videos:
  - Fast Fourier Transform overview
- Optional:
  - Interested in a more detailed treatment of the FFT? See Eric Vigoda’s lecture videos on the topic which are much more comprehensive than mine.
Day 8, Thursday 9/16/2021: Study Day
Day 9, Tuesday 9/21/2021: EXAM 1

Dynamic Programming

Day 10, Thursday 9/23/2021: Intro to DP & Shortest Paths in a DAG
- Required Reading: DPV Chapter 6.1
- Homework 2A released, due Sunday 10/3 11pm
- Videos:
  - Introduction to Dynamic Programming
  - Problem Solving Video
Day 11, Tuesday 9/28/2021: Longest Increasing Subsequences
- Required Reading: DPV Chapter 6.2
- Videos: (Note: This is a playlist with several videos!)
  - LIS + DP, Intro by Prof Abernethy, Details by Prof Vigoda
Day 12, Thursday 9/30/2021: Longest Common Subsequence
- OPTIONAL Reading: DPV Chapter 6.3
  - Note: Chapter 6.3 is about the edit distance between two strings, which is slighly different than the LCS. But the solutions are somewhat similar so you will likely find it helpful.
- Videos: (Note: This is a playlist with several videos!)
  - LCS + DP, Intro by Prof Abernethy, Details by Prof Vigoda
- Homework 2B released, due Tuesday 10/12 11pm
Day 13, Tuesday 10/5/2021: The Knapsack Problem
- Required Reading: DPV Chapter 6.4
- Videos:
  - The Knapsack Problem
Day 14, Thursday 10/7/2021: Chain Matrix Multiplication
- Required Reading: DPV Chapter 6.5
- Videos:
  - Chain Matrix Multiplication

Graph Algorithms

Day 15, Thursday 10/14/2021: Graphs traversal. Depth First Search. DP Practice.
- Required Reading: DPV Chapters 3.1, 3.2, and 3.3
- Videos:
  - Depth First Search
  - Suplemental: Prof. Vigoda’s lecture on DFS (you need to create a free account to access Udacity). Lecture-GR1
- Homework 3A released, due Sunday 10/24 11pm
Day 16, Tuesday 10/19/2021: EXAM 2
Day 17, Thursday 10/21/2021: Strongly connected components.
- Required Reading: DPV Chapter 3.4
- Videos:
  - Strongly Connected Components
  - Problem Solving Video
- Homework 3B released, due Monday 11/1 11pm
Day 18, Tuesday 10/26/2021: Breadth First Search. Dijkstra’s algorithm.
- Required Reading: DPV Chapters 4.1, 4.2, 4.3, 4.4, and 4.5
- Videos:
  - BFS + Dijkstra (playlist)
Day 19, Thursday 10/28/2021: Minimimum Spanning Trees + Kruskal
- Required Reading: DPV Chapter 5.1
- Videos:
  - Kruskal’s algorithm (playlist)
Day 20, Tuesday 11/2/2021: UnionFind + Prim’s Algorithm
- Required Reading: DPV Chapter 5.1
- Videos:
  - UnionFind + Prim (playlist)
  - Suplemental: Prof. Vigoda’s lecture on MST (Lecture GR3).

Complexity Theory and NP-completeness

Day 21, Thursday 11/4/2021: Introduction to Complexity, Reductions. Review for EXAM 3.
- Required Reading: DPV Chapter 8.1 and 8.2.
- Exam Prep Reading: For exam review, Chapters 3, 4 and 5.1 cover the exam content.
- Videos:
  - Introduction to Complexity Theory, Reductions
Day 22, Tuesday 11/9/2021: EXAM 3
- Homework 4A released, due Sunday 11/14 11pm
Day 23, Thursday 11/11/2021: Boolean satisfiability problems. SAT and 3-SAT.
- Required Reading: DPV Chapter 8.3 (specifically, the reduction SAT to 3SAT).
- Videos:
  - 2-SAT in P, 3-SAT is NP-complete
  - Problem Solving Video
Day 24, Tuesday 11/16/2021: Independent Set, Clique, and Vertex Cover.
- Required Reading: DPV Chapter 8.3 (specifically, the reductions from 3SAT to independent set(IS), and from IS to Clique and Vertex-Cover).
- Videos:
  - Independent Set, Clique, and Vertex Cover (playlist)
Day 25, Thursday 11/18/2021: SubsetSum is hard.
- Required Reading: DPV Chapter 8.3 (familiarize yourselve with the ILP and SubsetSum reductions).
- Videos:
  - SubsetSum is hard (playlist)
- Homework 4B released, due Monday 11/29 11pm (NO LATE SUBMISSIONS)
Day 26, Tuesday 11/30/2021: Cook-Levin Theorem. Review for Exam 4
- Videos:
  - Cook-Levin Theorem, aka “SAT is NP-complete”
  - (Optional!) More thoughts on what a “Turing machine” is: Turing Machines Explained - Computerphile`
Day 27, Thursday 12/2/2021: EXAM 4.
- Exam Prep Reading: Chapter 8 in the book covers NP.
Day 28, Thursday 12/7/2021: Optional, Review for Final Exam