Teaching‎ > ‎

CMP448 Spring 2013: Algorithms

Information

This course will cover basic algorithm analysis and design concepts, in addition to more advanced topics. It will be divided into two tracks:
  1. 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.
  2. 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)

Ċ
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
Comments