This course introduces basic concepts of design and analysis of computer algorithms: the basic principles and techniques of computational complexity (worst-case and average behavior, space usage, and lower bounds on the complexity of a problem), and algorithms for fundamental problems. It also introduces the areas of NP-completeness and parallel algorithms.
Jiwon Park, Taegyoung Lee, Yoonsung Choi.
Our TAs offer an office hour twice a week:
The class meets Monday and Wednesday from 13:00 to 14:15 in classroom #1 (room 1101) in building E3-1. Lectures are given in English.
The final grade will be composed as follows (small changes reserved):
Attendance will be taken in nearly every class. If you miss at most 3 lectures, you receive 10 attendance points. For 4 missed lectures, you receive 9 attendance points, and so on. For 13 or more missed lectures you receive no attendance points.
Going to a conference, workshop, doctor, interview, is no excuse for missing the class — you can use the three free missed classes for this.
There will be a midterm and a final exam.
The midterm exam is on April 16 from 13:00 to 15:40 in room 412 in the Creative Learning Building.
The final exam is on June 11 from 13:00 to 15:40 in room 412 in the Creative Learning Building.
Here is a rough list of what we will cover in each week of the semester.
| Week 1 | Introduction, graph basics and representation, DFS |
| Week 2 | Direct graphs, strongly connected components, BFS |
| Week 3 | Shortest paths |
| Week 4 | Reductions, recursion, divide-and-conquer |
| Week 5 | Sorting |
| Week 6 | Introduction to dynamic programming |
| Week 7 | More dynamic programming: edit distance, Huffman trees |
| Week 8 | Midterm exam |
| Week 9 | Greedy algorithms |
| Week 10 | Minimum spanning trees |
| Week 11 | Introduction to randomized algorithms |
| Week 12 | Hash tables |
| Week 13 | Lower bounds and adversary arguments |
| Week 14 | Polynomial time reductions, SAT |
| Week 15 | NP-Completeness |
| Week 16 | Final Exam |
This semester, we will try Classum, a new platform built by KAIST CS students.
In order not to miss important announcements about the course, you must register on Classum, and then add the course CS300A.
If you do not understand something, it is important that you ask questions. Classum allows you to ask questions and get answers from the instructor, the teaching assistants, and your classmates. You can ask questions anonymously, so don't be shy and ask!
Both Korean and English are acceptable on Classum :-). You make it easier for me if you write in English, but if the TAs can answer your question, then Korean is just fine.
The class will mostly use the book Algorithms by Dasgupta, Papadimitriou, and Vazirani. The international edition is quite inexpensive, and there is also a Korean translation. Students are not required to buy the book.
We will also make use of Jeff Erickson's lecture notes and lecture notes by Avrim Blum.
The material covered in the lectures so far:
| 02-26 | Introduction, Karatsuba's algorithm | slides, notes by Avrim Blum | Book 2.1 |
| 02-28 | Strassen's algorithm, Big-Oh, Omega, Theta | notes by Avrim Blum | Book 2.5, 0.3 |
| 03-05 | Solving recursions using recursion trees, master theorem | Appendix II in Jeff Ericksson's notes | Book 2.2 |
| 03-07 | Majority problem, Median & Selection problems | notes by Jeff Erickson | Book 2.4 |
| 03-12 | No class (business trip) | ||
| 03-14 | No class (business trip) | ||
| 03-19 | Closest point problem | ||
| 03-21 | Graphs, DFS | Book 3.1, 3.2 | |
| 03-26 | DFS in directed graphs, DAGs, topological sort, Strongly connected components, meta-graph | Book 3.3, 3.4 | |
| 03-28 | SCC computation, BFS, Dijkstra's algorithm | Book 3.4, 4.1–4.4.1 | |
| 04-02 | Dijkstra's algorithm, Bellman-Ford algorithm, negative cycles | Book 4.4.2, 4.6 | |
| 04-04 | Shortest path in DAGs; MST introduction and cut property | Book 4.7, 5.1, 5.1.2 | |
| 04-09 | Prim's algorithm, Kruskal's algorithm | Book 5.1.5, 5.1.3 | |
| 04-11 | Union-Find | slides, code | Book 5.1.4 |
| 04-16 | Midterm exam, April 16, 13:00–15:40, room 412 in CLB | ||
| 04-23 | Midterm review, 2-approximation for TSP | Book 9.2.3 | |
| 04-25 | Greedy algorithms for scheduling problems | notes by Jeff Erickson | |
| 04-30 | More examples of greedy algorithms: Stabbing intervals, Coloring intervals, Coin changing | ||
| 05-02 | Maximum independent set in interval graphs, Recursion without repetition, memoization, dynamic programming | notes by Jeff Erickson | |
| 05-07 | No class (Children's day) | ||
| 05-09 | DP and DAGs, longest increasing subsequence, edit distance | Book 6.1, 6.2, 6.3 | |
| 05-14 | Knapsack problem, optimal matrix multiplication, optimal binary search tree | Book 6.4, 6.5, Exercise 6.20 | |
| 05-21 | Shortest reliable path, All pairs shortest paths, independent sets in trees | Book 6.6, 6.7 | |
| 05-23 | Lower bounds, decision trees, adversary arguments | notes by Jeff Erickson, more notes by Jeff Erickson | |
| 05-28 | Reductions: Unique, MinIndSet, MaxClique, VertexCover, Hamiltonian Path and Cycle | notes by Jeff Erickson 29.8, 29.9 | Book 7.1.3 box on reductions, Book 8.2, 8.3 |
| 05-30 | Reductions: VC to Hamiltonian Path, Subset Sum, SAT, 3-SAT | Jeff's notes 29.11, 29.12, 29.6 | Book 8.3 |
| 06-04 | 3-SAT to IS, NPTH, ETH, SETH and their consequences | Jeff's notes 29.7 | |
| 06-06 | No class (Memorial day) | ||
| 06-11 | Final exam, June 11, 13:00–15:40, room 412 in CLB | ||
There will be one or two programming homeworks in this course. Programming can be done in most major imperative programming languages, such as Java, C, C++, Scala, Kotlin, or Python. Programming projects are submitted using an electronic submission server.
There will also be several small theoretical homework assignments, where you can test your understanding of the course material. You will have about one week to complete one assignment and they can be turned in in either Korean or English.
Homeworks must be submitted on paper in the homework box next to our classroom in E3-1.