CS 3510: Design & Analysis of Algorithms

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

Click to view the syllabus

Course Content

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

Recurrences and Cryptography

Day 1, Tuesday 8/18/2020: Introduction to Course
- Link to live session
- Introduction to course, overview of format
- Videos:
  - Course Intro Video
Day 2, Thursday 8/20/2020: Big-O, Logs, Fibonacci
- Link to live session
- Required Reading: DPV Chapter 0
- Videos:
  - Big-O Notation
  - Computing Fibonacci
- Homework 1A released, due Sunday 8/30 11pm
Day 3, Tuesday 8/25/2020: MergeSort and Multiplication
- Link to live session
- Required Reading: DPV Chapter 2.1 & 2.3
- Videos:
  - MergeSort Algorithm
  - Multiplication
Day 4, Thursday 8/27/2020: Recurrences and Matrix Multiplication
- Link to live session
- Required Reading: DPV Chapter 2.2 & 2.5
- Videos:
Day 5, Tuesday 9/1/2020: Modular Arithmetic
- Link to live session
- Required Reading: DPV Chapter 1.2 & 1.3
- Videos:
- Homework 1B released, due Sunday 9/13 11pm
Day 6, Thursday 9/3/2020: RSA Cryptosystem
- Link to live session
- 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.
NO CLASS Tuesday 9/8
Day 7, Thursday 9/10/2020: Fast Fourier Transform
- Link to live session
- 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, Tuesday 9/15/2020: EXAM 1
- Homework 2A released, due Sunday 9/27 11pm

Dynamic Programming

Day 9, Thursday 9/17/2020: Intro to DP & Shortest Paths in a DAG
- Link to live session
- Required Reading: DPV Chapter 6.1
- Videos:
  - Introduction to Dynamic Programming
Day 10, Tuesday 9/22/2020: Longest Increasing Subsequences
- Link to live session
- 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 11, Thursday 9/24/2020: Longest Common Subsequence
- Link to live session
- 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 Sunday 10/4 11pm
Day 12, Tuesday 9/29/2020: The Knapsack Problem
- Link to live session
- Required Reading: DPV Chapter 6.4
- Videos:
  - The Knapsack Problem
Day 13, Thursday 10/1/2020: Chain Matrix Multiplication + DP Practice
- Link to live session
- Required Reading: DPV Chapter 6.5
- Videos:
  - Chain Matrix Multiplication
Day 14, Tuesday 10/6/2020: EXAM 2
- Homework 3A released, due Sunday 10/18 11pm

Graph Algorithms

Day 15, Thursday 10/8/2020: Recap on graphs. Notation. Dijkstra’s algorithm.
- Link to live session
- Required Reading: DPV Chapters 4.3, 4.4 and 4.5
- Videos:
  - Standard notation on graphs
  - Dijkstra’s algorithm
Day 16, Tuesday 10/13/2020: Graphs traversal. Depth First Search.
- Link to live session
- Required Reading: DPV Chapters 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
Day 17, Thursday 10/15/2020: Strongly connected components.
- Link to live session
- Required Reading: DPV Chapter 3.4
- Videos:
  - Strongly Connected Components
  - Suplemental: Prof. Vigoda’s lecture on DFS.
- Homework 3B released, due Sunday 10/25 11pm
Day 18, Tuesday 10/20/2020: Minimimum Spanning Trees.
- Link to live session
- Required Reading: DPV Chapter 5.1
- Videos:
  - Kruskal’s algorithm
Day 19, Thursday 10/22/2020: The cut property and the cycle property.
- Link to live session
- Required Reading: DPV Chapter 5.1
- Videos:
  - The cut and cycle property
  - Suplemental: Prof. Vigoda’s lecture on MST (Lecture GR3).
Day 20, Tuesday 10/27/2020: Review for EXAM 3.
- Link to live session
- Required Reading: It is review day! Chapters 3, 4 and 5.1 cover the exam content.
Day 21, Thursday 10/29/2020: EXAM 3
- Homework 4A released, due Sunday 11/8 11pm

Complexity Theory and NP-completeness

Day 22, Tuesday 11/3/2020: Introduction to NP theory. Reductions.
- No live session
- Required Reading: DPV Chapter 8.1 and 8.2.
- Videos:
  - Introduction to NP-completeness. Reductions
  - Suplemental: Prof. Vigoda’s lecture (Lecture NP1).
Day 23, Thursday 11/5/2020: Boolean satisfiability problems. SAT and 3-SAT.
- Link to live session
- Required Reading: DPV Chapter 8.3 (specifically, the reduction SAT to 3SAT).
- Videos:
  - 3-SAT is NP-complete.
  - Suplemental: Prof. Vigoda’s lecture (Lecture NP2).
- Homework 4B released, due Sunday 11/15 11pm
Day 24, Tuesday 11/10/2020: Graphs problems.
- Link to live session
- Required Reading: DPV Chapter 8.3 (specifically, the reductions from 3SAT to independent set(IS), and from IS to Clique and Vertex-Cover).
- Videos:
  - Graphs problems This is profesor Vigoda’s lecture NP3. Watch it first!
  - Rudrata path
Day 25, Thursday 11/12/2020: Knapsack.
- Link to live session
- Videos:
  - Knapsack This is profesor Vigoda’s lecture NP4.
Day 26, Tuesday 11/17/2020: Review for EXAM 4.
- Link to live session
- Required Reading: Chapter 8 in the book covers NP.
Day 27, Thursday 11/19/2020: EXAM 4
Day 28, Tuesday 11/24/2020: NO CLASS