CSE 5311 - Design and Analysis of Algorithms

Fall 2011
Lectures: Mondays, Wednesdays and Fridays, 13:00-13:50, ERB129
Instructor: Dimitrios Kosmopoulos


Fall 2011 Syllabus PDF

Instructor:
Dimitrios Kosmopoulos
E-mail: kosmopo  uta  edu  
Office:  ERB644
Office hours: MoWe 15:00-17:00
Teaching assistant:
          Naeemul Hassan
E-mail: naeemulhassan gmail com
Office:  ERB509
Office hours:  TuTh 12:00-14.00


Recent Announcements:

12/2/11 Homework Set 5 is due 12/13/11, solutions to Set 4 are available

11/15/11 Solutions to midterm 2 are available

11/3/11 The next homework is due 11/18. Solutions to previous are available.

10/26/11 Projects topics are available. Assignment on first come - first served basis

10/19/11 Selected lecture notes are available


Class Schedule (tentative)

Lecture         Date         Topic Textbook Readings Lecture notes
1 Fri 08/26 Introduction    
2 Mon 08/29 Analysis concepts Chapter 2  
3 Wed 08/31 Analysis concepts Chapter 2  
4 Fri 09/02 Asymptotic analysis - Function Growth Chapter 3  
5 Wed 09/07 Asymptotic analysis - Function Growth Chapter 3  
6 Fri 09/09 Divide and Conquer Chapter 4  
7 Mon 09/12 Divide and Conquer Chapter 4  
8 Wed 09/14 Divide and Conquer Chapter 4  
9 Fri 09/16 Divide and Conquer Chapter 5  
10 Mon 09/19 Divide and Conquer Chapter 5  
11 Wed 09/21 Probabilistic analysis and randomized algorithms Chapter 10 Birthday paradox 3 persons
12 Fri 09/23 Probabilistic analysis and randomized algorithms Chapter 10  
13 Mon 09/26 Quicksort Chapter 12 Substitution/proof: quicksort cost
14 Wed 09/28 Quicksort Chapter 12  
15 Fri 09/30 Medians and Order Statistics Chapter 9 proof: Find median linear worst case
16 Mon 10/3 Medians and Order Statistics Chapter 9  
17 Wed 10/5 Heapsort Chapter 6 proof: Number of elements in heap
18 Fri 10/7  Binary Search Trees Chapter 12  
- Mon 10/10 EXAM 1 (Lectures 1-16)    
19 Wed 10/12  Binary Search Trees Chapter 12 proof: Binary Tree Height - random input
20 Fri 10/14 Binary Search Trees Chapter 12  
21 Mon 10/17 Red Black Trees Chapter 13  
22 Wed 10/19 Red Black Trees Chapter 13 Left Leaning Red Black - Trees
23 Fri 10/21 Introduction to Graphs / Minimum Spanning Trees Appendix B4/ Ch 23  
24 Mon 10/24 Minimum Spanning Trees Chapter 23  
25 Wed 10/26 Single Source Shortest Path Chapter 24  
26 Fri 10/28 Single Source Shortest Path Chapter 24  
27 Mon 10/31 Single Source Shortest Path Chapter 24  
28 Wed 11/02 All Pairs Shortest Paths Chapter 25  
29 Fri 11/04 All Pairs Shortest Paths Chapter 25  
- Mon 11/07 Network Flow Chapter 26  
30 Wed 11/09 EXAM 2 (Lectures 17-27) -  
31 Fri 11/11 All Pairs Shortest Paths Chapter 25  
32 Mon 11/14 Network Flow Chapter 26  
33 Wed 11/16 Network Flow Chapter 26  
34 Fri 11/18 Network Flow Chapter 26  
35 Mon 11/21 Network Flow Chapter 26  
36 Wed 11/23 Network Flow Chapter 26  
37 Mon 11/28 NP-Completeness Chapter 34  
38 Wed 11/30 NP-Completeness Chapter 34  
39 Fri 12/02 NP-Completeness Chapter 34  
40 Mon 12/05 NP-Completeness Chapter 34  
41 Wed 12/07 Project presentation    
42 Fri 12/09 Project presentation    
  12/12 FINAL EXAM (Comprehensive)

 


Homeworks

Set 1 Solutions
Set 2 Solutions

Set 3 Solutions

Set 4 Solutions

Set 5  Due: 12/13/11


Labs/Projects

Submission instructions   Deadline 12/5/11

 


Exams

Midterm 1 + solutions

Midterm 2 + solutions

Final + solutions