22C:031 ALGORITHMS  (Fall 2004)

Classes: 70 Van,  Tu-TH 9:30-10:45.

Professor: Dr. Suely Oliveira
email: oliveira@cs.uiowa.edu
Office: MLH 101H - phone: 335-0731
office hours: Tuesdays &Fridays,  2:30 - 4:00, others by appointment. 

TA :  Wenli He
email: whe@cs.uiowa.edu
Office: MLH 101L - phone: 353-2543
office hours:  Mondays 1:00-3:00

TA:   Mike Decoster
email: mdecoste@cs.uiowa.edu
Office: MLH 101K - phone: 353-2542
office hours:  Wednesdays 2:30-4:30

Syllabus (postscript)    Syllabus (pdf)
How to Submit your programs electronically
A Software you can use for graphs, etc MATLAB

Textbook: Introduction to Algorithms,
Cormen, Leiserson and Rivest.
Some Handouts
  •  Basic Review  (Chapters 1, 2 and 4).
    • Handout1: Insertion
    Handout 2: Growth of Functions
    Handout 3: Asymtotic Analysis  (ps)      
    Handout 4: Divide and Conquer (ps)    
    Handout: Probablistic Analysis(ps)     
     
  • Heapsort and Quicksort (Chapters 7 and 8)
    • Handout 5: Comparison based sorting (ps)  
     
  • Sorting in Linear time (Chapter 9), Some Statistics (Chapter 10)
    • Handout 6: Quicksort simulation
    Handout 7: Non-Comparison based sorting (ps)    
     
  • Advanced Design and Analysis Techniques (Chapters 16 and 17)
    Dynamic Programming(ps)  
    Greedy Algorithms(ps) 
    •  
  • Graph Algorithms (Chapters 24, 25, and 26).
    • Handout 14: Prim's and Kruskal Algorithms (ps)   
    Handout 15: Shortest Paths (ps)  
    Handout 16: All-Pairs Shortest Paths (ps) 

  •  Introduction to NP-Completeness  and Approximation Algorithms (Chapters 36 and 37)
    • Handout 17: NP-Completeness (ps)    

    Homeworks and Exams Dates

     homework 1: Due September 9th  (Wenli He)
    homework 2: Due September 16th  (Decoster)
    homework 3: Due  September 23rd (Wenli He)
    exam 1: September 30th - closed book (Max =  107,  Avg = 79.2, Min =37)
    homework 4:  Due October 21st (Decoster).
    homework 5:  Due October 28th (Decoster).
    exam 2: November 4th -  open book (Max =  99,  Avg = 53.5, Min = 3.5)
    homework 6:   Due November 16th, (Wenli)
    homework 7:   Due November 30th (Wenli)
    exam 3: December 2nd - open book & notes (Max = 80, Avg = 60.1, Min =35)
    Final: Wednesday, December 15th, 12:00 pm. (open book)
    Grades: There will be approximately 7-8 homeworks, 3 in-class  exams (no team work, not comprehensive), and one comprehensive final exam.

    University Rules:

    Note 1:I need to hear from anyone who has a disability which may require some modification of seating, testing or other class requirements so that appropriate arrangements may be made. Please see me after class or during my office hours .
    Note 2:This course is given by the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found at:   http://www.uiowa.edu/~provost/deos/crossenroll.doc
    Note3: Complaints should be initiated at the faculty or department level. The Department of Computer Science Departments has offices in 14 McLean Hall.