22C:153 DESIGN AND ANALYSIS OF ALGORITHMS

Classes: 118 MLH,  Tu-TH 9:30 am - 10:45 am

Professor: Dr. Suely Oliveira   email: oliveira@cs.uiowa.edu
Office: MLH 101H - phone: 335-0731 - office hours:  Tu-TH 1:00 pm-2:00 pm

TA: Jeevan Kodali -- email: jkodali@cs.uiowa.edu
Office: MLH 101 L- phone: 335-2543 - office hours:  MWF 12:30 pm-1:30 pm

Syllabus (postscript)    Syllabus (pdf)

Main Topics & Handouts  (mores links will be added  during the semester)
 

  •  Undergraduate Review: Mathematical Foundations (1 week)

    • (Ch. 3, Ch. 4)
    Handout: Growth of Functions
    Handout: Asymtotic Analysis  (ps)(pdf)
    Handout: Recurrences (ps)    (pdf)
     
  •  Sorting Algorithms, Probabilistic Analysis and

    • Introduction to Randomized Algorithms  (2 weeks)
    ( Ch. 2, 5.1, 5.2, Ch.  7.1,7.3,7.4,  8.1, 8.2)
    Insertion,mergesort, quicksort, lower bounds for sorting.
    The hiring problem and quicksort analysis.
    Handout: Insertion
    Handout:  Comparison based sorting (ps)   (pdf)
    Handout: Quicksort simulation
     
  • Advanced Design and Analysis Techniques (Chapters 16, 17, and 18) (4 weeks)

    • Divide and Conquer Algorithms, Dynamic Programming
    Greedy Algorithms,  and Amortized Analysis.
     
  • Graph Algorithms  (Chapters 23, 24, 25, and 26). (4 weeks)

    • DFS and applications (strongly connected components), Shortest paths algorithms
    (Dijkstra's and Bellman-Ford algorithms). All-Pairs Shortest Paths algorihtms.
    Flow Networks, Ford-Fulkerson Method, Maximum Bipartite Matching.
    Handout: Shortest Paths (ps)       (pdf)
    Handout: All-Pairs Shortest Paths (ps)  (pdf)
     
  • NP-Completeness and Approximation Algorithm (Chapters 36 and 37) (5 weeks)

    • NP-Completeness reducibility, NP-completeness proofs, Satisfiability problem,
    3-CNF-SAT, CLIQUE, HAM-CYCLE, TSP and vertex-cover problem.
    Handout: NP-Completeness part I  (given in class)
    Handout:  NP-Completeness part II  (given in class)
    Handout: NP-Completeness part III  (given in class)
     
  • Other  Topics

    • Seleted topics from part VII in the book.
  • HOMEWORK AND PROGRAMMING ASSIGNMENTS  (group work)

    • Homework1-->    (postscript)(pdf)    (on undergraduate review)
    Homework2--> 15.2-1, 15.2-3, 15.3-1, 15.3-3, 15.5-1,  15.5-2, 15-2
    Homework3-->  22.4-1 (pg 551), 22.5-1, 22.5-2, 22.5-3 (pg. 557), more over email.
    Homework4--> 25.1-6, 25.2-1, more will be given in class
    Homework5--> 34.2-3 (pg 983) and 34.5-2 (pg 1017)
    Homework6 -->  projects on NP-completeness and approximation algorithms.

    (Any other homeworks are not to be turned in or graded)

  • QUIZZES DATES (individual work,  quiz 1 and 2 are open book)

    • Quiz 1   --> (on undergraduate review, dynamic programming and greedy algorithms)
    Quiz  2  --> (on graph algorithms)
  •  FINAL EXAM DATE (individual work, closed book)

    • Final Exam Date:

    grades  (please contact me if you find any mistakes)


    How to Submit your programs electronically
    A Software you can use for graphs, etc MATLAB

    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