|
General Information
|
|
Lecturer:
|
Wing-Kai Hon
|
|
wkhon @ cs
|
|
|
|
|
Tutors:
|
Simon, Cindy, Hsin-Pei, Terry
|
|
|
Henry, Rick, Andrew, Min-Hsin
|
|
|
Check iLMS for details
|
|
|
|
|
Meeting Time:
|
|
Wed 1010--1200, Fri 1010--1100
|
|
|
Announcements
|
|
Welcome to the Class!
|
|
References
1. Introduction to Algorithms, by Cormen et al.
2. Algorithms in C++, by Sedgewick
3. The Art of Computer Programming, by Knuth
|
|
Scoring Method
6 Assignments (0%)
3 Exams (2 * 40% + 1 * 20%)
--------------------------------------------------------
Total = 100%
|
|
|
Course Materials
|
|
Lecture
|
Topics
|
Related Files
|
|
1
|
Getting Started
|
[pdf]
|
|
2
|
Growth of Function
|
[pdf]
|
|
3
|
Recurrences
|
[pdf]
|
|
4
|
Heapsort
|
[pdf]
|
|
5
|
Quicksort
|
[pdf]
|
|
**
|
Probability and Expectation
|
[pdf]
|
|
6
|
Sorting in Linear Time
|
[pdf]
|
|
7
|
Lower Bound on Comparison Sorts
|
[pdf]
|
|
8
|
Order Statistics
|
[pdf]
|
|
9
|
Dynamic Programming I (Assembly Line, Memoization)
|
[pdf]
|
|
10
|
Dynamic Programming II (Matrix Chain Multiplication)
|
[pdf]
|
|
11
|
Dynamic Programming III (Optimal BST)
|
[pdf]
|
|
12
|
Dynamic Programming IV (Longest Common Subsequence)
|
[pdf]
|
|
13
|
Greedy Algorithm
|
[pdf]
|
|
14
|
Amortized Analysis I (Aggregate Method)
|
[pdf]
|
|
15
|
Amortized Analysis II (Accounting Method, Potential Method)
|
[pdf]
|
|
16
|
Amortized Analysis III (Dynamic Table)
|
[pdf]
|
|
17
|
Binomial Heap
|
[pdf]
|
|
18
|
Fibonacci Heap I (Insertion, Union, Extract-Min)
|
[pdf]
|
|
19
|
Fibonacci Heap II (Decrease-Key, Delete, Max-Deg)
|
[pdf]
|
|
20
|
Disjoint Sets I (Linked List)
|
[pdf]
|
|
21
|
Disjoint Sets II (Union by Size, Union by Rank, Path Compress)
|
[pdf]
|
|
22
|
Graph Algorithms I (BFS)
|
[pdf]
|
|
23
|
Graph Algorithms II (DFS)
|
[pdf]
|
|
24
|
Graph Algorithms III (Topological Sort)
|
[pdf]
|
|
25
|
Graph Algorithms IV (Strongly Connected Components)
|
[pdf]
|
|
26
|
Minimum Spanning Trees
|
[pdf]
|
|
27
|
Single-Source Shortest Paths
|
[pdf]
|
Teaching Plan
|
|
1
|
Basics
|
Lecture 01 to Lecture 03
|
|
2
|
Sorting & Order Statistics
|
Lecture 04 to Lecture 08
|
|
3
|
Advanced Design Techniques
|
Lecture 09 to Lecture 13
|
|
4
|
Advanced Analysis Technique
|
Lecture 14 to Lecture 16
|
|
5
|
Advanced Data Structures
|
Lecture 17 to Lecture 21
|
|
6
|
Graph Algorithms
|
Lecture 22 to Lecture 26
|
|
7
|
Selected Topics
|
KMP, NP-hardness
|
Last updated: February 12, 2017
|