Lecture: Th. 13.00-16.00
Room: 1301
Instructor: Vacharapat Mettanant
Prerequisites: 03603211 Discrete Mathematics, 03603212 Abstract Datatypes and Problem Solving
Objective: This course aims to improve your problem-solving and analysis skills. We will study basic algorithm design techniques such as greedy algorithms, dynamic programming, divide and conquer, and randomized algorithms. We also study the complexity of problems, including the complexity class P and NP, and how to deal with them.
Assignments: The assignment for each week will be posted by Friday evening, and it is due on the following Wednesday. All assignments must be written by yourself and submitted in the box in front of room 23604.
Scores: Homeworks 25%, Midterm 35%, Final 40%
Topics:
1
1 Dec 2022
Introduction
Review of Proof Techniques
Complexity Analysis, Big-O Notation
Linear Data Structures and Basic Operations
YouTube: Lecture 1
2
8 Dec 2022
Greedy Algorithms
Interval Scheduling
Scheduling to Minimize Lateness
3
15 Dec 2022
Graphs, Basic Graph Search
Testing Bipartite Graphs
4
22 Dec 2022
Minimum Spanning Tree
Prim's Algorithm, Kruskal's Algorithm
Union-Find Data Structure
5
29 Dec 2022
No Class!!!
6
5 Jan 2023
Directed Acyclic Graphs, Kahn's Algorithm
Shortest Paths, Dijkstra's Algorithm
Priority Queue, Binary Heap
Lecture: Directed Graphs, Kahn's Algorithm
Lecture: Shortest Paths, Dijkstra's Algorithm
YouTube: Lecture 15-18
7
12 Jan 2023
Dynamic Programming
Weighted Interval Scheduling
Longest Increasing Subsequence
Knapsack Problem
8
26 Jan 2023
Longest Common Subsequence
Bellman-Ford Algorithm
Floyd-Warshall Algorithm
9
2 Feb 2023
Divide and Conquer
Merge Sort, Counting Inversion
Integer Multiplication
Lecture: Merge Sort and Counting Inversion
YouTube: Lecture 31-32
10
9 Feb 2023
Closest Pair of Points
Quick Select
11
16 Feb 2023
Randomized Algorithms
Balls and Bins Analysis
Randomized Quick Sort
Global Minimum Cut, Karger's Algorithm
12
23 Feb 2023
Differential Privacy
Randomized Response
Laplace Mechanism
Exponential Mechanism
13
2 Mar 2023
P, NP, Polynomial-Time Reduction
NP-Complete
YouTube: Lecture 43-33
14
9 Mar 2023
Approximation Algorithms
Load Balancing
Metric TSP
Maximum Cut
15
16 Mar 2023
Fixed-Parameter Algorithms
Vertex Cover
Local Search
Simulated Annealing
Genetic Algorithms
Recommended Books:
Algorithm Design by Kleinberg and Tardos
Introduction to Algorithms by CLRS
The Algorithms Illuminated Book Series by Tim Roughgarden (with videos)
Resources:
YouTube Playlist from 2018 with complete Lecture Notes by me
YouTube Playlist 2020 by Jittat Fakcharoenphol
Lecture Slides for Algorithm Design by Kleinberg and Tardos by Kevin Wayne