Information
This course will cover basic algorithm analysis and design concepts, in addition to more advanced topics. It will be divided into two tracks:
- Classes: will cover more theoretical algorithmic concepts. Topics include: asymptotic analysis, recurrences, divide-and-conquer, dynamic programming, greedy algorithms, sorting, searching, graph algorithms, P, NP, and NP-completeness.
- Sections: will be more practical, focusing on programming challenges, especially the ACM ICPC challenge. Will include weekly homework assignments containing problems to be solved like the challenges.
Textbooks
- Introduction to Algorithms, Third Edition. Cormen, Leiserson, Rivest, and Stein (for classes).
- Programming Challenges. Skiena and Revilla (for sections).
Schedule
Date |
Type |
Topic |
Slides |
Reading |
Homework |
Wednesday 13 Feb. 2013 |
Section |
Introduction & Data Structures |
(pdf) |
SR Ch. 1, 2 |
PA #1 |
Thursday 14 Feb. 2013 |
Class |
Introduction |
(pdf) |
|
|
|
Class |
Algorithm Analysis |
(pdf) |
CLRS Ch. 1, 2 |
|
|
Class |
Asymptotic Analysis and Recurrences |
(pdf) |
CLRS Ch. 3, 4.3-4.5 |
|
Thursday 21 Feb. 2013 |
Class |
Heapsort and Quicksort |
(pdf) |
CLRS Ch. 6, 7 |
|
Wednesday 27 Mar. 2013 |
Section |
Strings and Sorting |
(pdf) |
SR Ch. 3, 4 |
|
Thursday 28 Feb. 2013 |
Class |
Quicksort (cont.) |
|
|
|
|
Class |
Linear Time Sorting and Order Statistics |
(pdf) |
CLRS Ch. 8, 9 |
HW #1 |
Thursday 7 Mar. 2013 |
Class |
Hashing I |
(pdf) |
CLRS Ch. 11 |
|
Thursday 14 Mar. 2013 |
Class |
Hashing II |
(pdf) |
CLRS Ch. 11 |
|
|
Class |
Binary Search Trees |
(pdf) |
CLRS Ch. 12 |
HW #2 |
Thursday 21 Mar. 2013 |
Class |
Dynamic Programming |
(pdf) |
CLRS Ch. 15 |
|
Thursday 28 Mar. 2013 |
Midterm |
Thursday 4 Apr. 2013 |
Class |
Greedy Algorithms |
(pdf) |
CLRS Ch. 16 |
|
|
Class |
Minimal Spanning Trees |
(pdf) |
CLRS Ch. 23 |
|
Thursday 11 Apr. 2013 |
Class |
Amortized Analysis and Disjoint Sets |
(pdf) |
CLRS Ch. 17, 21 |
|
Thursday 18 Apr. 2013 |
Class |
BFS and DFS |
(pdf)
|
CLRS Ch. 22
|
|
|
Class |
Dijkstra Algorithm
|
(pdf) |
CLRS Ch. 24
|
|
Thursday 25 Apr. 2013
|
Class
|
Bellman-Ford Algorithm
|
(pdf) |
CLRS Ch. 24
|
|
Thursday 2 May 2013
|
Class |
All-Pairs Shortest Paths
|
(pdf) |
CLRS Ch. 25
|
|
|
Class |
Network Flow
|
(pdf) |
CLRS Ch. 26
|
|
Thursday 9 May 2013
|
Break |
Thursday 16 May 2013
|
Class |
Max-Flow Min-Cut
|
(pdf) |
CLRS Ch. 26 |
|
Class Slides
- Lecture 0: Introduction (pdf)
- Lecture 1: Algorithm Analysis (pdf)
- Lecture 2: Asymptotic Analysis and Recurrences (pdf)
- Lecture 3: Heapsort and Quicksort (pdf)
- Lecture 4: Linear Time Sorting and Order Statistics (pdf)
- Lecture 5: Hashing I (pdf)
- Lecture 6: Hashing II (pdf)
- Lecture 7: Binary Search Trees (pdf)
- Lecture 8: Dynamic Programming (pdf)
- Lecture 9: Greedy Algorithms (pdf)
- Lecture 10: Minimal Spanning Trees (pdf)
- Lecture 11: Amortized Analysis and Disjoint Sets (pdf)
- Lecture 12: BFS and DFS (pdf)
- Lecture 13: Dijkstra Algorithm (pdf)
- Lecture 14: Bellman-Ford Algorithm (pdf)
- Lecture 15: All-Pairs Shortest Paths (pdf)
- Lecture 16: Network Flow (pdf)
- Lecture 17: Max-Flow Min-Cut (pdf)
Section Slides
- Section 1: Introduction and Data Structures (pdf)
- Section 2: Strings and Sorting (pdf)
Class Assignments
Programming Assignments
- Programming Assignment 1 (pdf)
- Programming Assignment 2 (pdf)
|
 Updating...
Ċ Mohamed Aly, Feb 28, 2013, 6:45 AM
Ċ Mohamed Aly, Mar 15, 2013, 8:31 AM
CMP448 HW03 Data.zip (3k) Mohamed Aly, Apr 11, 2013, 8:21 AM
Ċ Mohamed Aly, Apr 11, 2013, 8:21 AM
Ċ Mohamed Aly, Apr 27, 2013, 4:25 AM
CMP448 HW05 Data.zip (1412k) Mohamed Aly, May 18, 2013, 6:41 AM
Ċ Mohamed Aly, May 18, 2013, 6:41 AM
Ċ Mohamed Aly, Feb 11, 2013, 1:39 AM
Ċ Mohamed Aly, Feb 14, 2013, 3:53 AM
Ċ Mohamed Aly, Feb 14, 2013, 3:53 AM
Ċ Mohamed Aly, Feb 21, 2013, 6:17 AM
Ċ Mohamed Aly, Feb 28, 2013, 6:45 AM
Ċ Mohamed Aly, Mar 7, 2013, 5:46 AM
Ċ Mohamed Aly, Mar 14, 2013, 8:21 AM
Ċ Mohamed Aly, Mar 14, 2013, 8:21 AM
Ċ Mohamed Aly, Mar 21, 2013, 7:18 AM
Ċ Mohamed Aly, Apr 4, 2013, 8:29 AM
Ċ Mohamed Aly, Apr 4, 2013, 7:52 AM
Ċ Mohamed Aly, Apr 18, 2013, 9:06 AM
Ċ Mohamed Aly, Apr 27, 2013, 3:45 AM
Ċ Mohamed Aly, Apr 27, 2013, 3:45 AM
Ċ Mohamed Aly, Apr 27, 2013, 3:45 AM
Ċ Mohamed Aly, May 13, 2013, 6:31 AM
Ċ Mohamed Aly, May 18, 2013, 6:40 AM
Ċ Mohamed Aly, May 18, 2013, 6:40 AM
Ċ Mohamed Aly, Feb 17, 2013, 12:28 AM
Ċ Mohamed Aly, Mar 7, 2013, 5:50 AM
Ċ Mohamed Aly, Feb 14, 2013, 4:01 AM
Ċ Mohamed Aly, Mar 7, 2013, 5:50 AM
|