Welcome to the course page for CS 3510 in Fall 2020, Georgia Tech's undergraduate introductory course on algorithms.
Below, DPV refers to the textbook of Dasgupta, Papdimitriou, and Vazirani.
- Day 1, Tuesday 8/18/2020: Introduction to Course
- Link to live session
- Introduction to course, overview of format
- Videos:
- Day 2, Thursday 8/20/2020: Big-O, Logs, Fibonacci
- Link to live session
- Required Reading: DPV Chapter 0
- Videos:
- 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:
- 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:
- 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
- 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:
- 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!)
- 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!)
- 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:
- Day 13, Thursday 10/1/2020: Chain Matrix Multiplication + DP Practice
- Link to live session
- Required Reading: DPV Chapter 6.5
- Videos:
- Day 14, Tuesday 10/6/2020: EXAM 2
- Homework 3A released, due Sunday 10/18 11pm
- 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:
- 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:
- 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
- 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