Algorithms
Title  Algorithms (55001) 

Quarter  Spring 2016 
Instructor  Geraldine Brady (gb52@uchicago.edu) 
Website  http://people.cs.uchicago.edu/~brady/MPCS55001/ 
Syllabus  Course DescriptionThe course is an introduction to the design and analysis of efficient algorithms, with emphasis on developing techniques for the design and rigorous analysis of algorithms rather than on implementation. Algorithmic problems include sorting and searching, discrete optimization, and algorithmic graph theory. Design techniques include divideandconquer methods, dynamic programming, greedy methods, graph search, as well as the design of efficient data structures. Methods of algorithm analysis include asymptotic notation, evaluation of recurrences, and the concepts of polynomialtime algorithms. NPcompleteness is introduced at the end the course. Students who complete the course will have demonstrated the ability to use divideandconquer methods, dynamic programming methods, and greedy methods, when an algorithmic design problem calls for such a method. They will have learned the design strategies employed by the major sorting algorithms and the major graph algorithms, and will have demonstrated the ability to use these design strategies or modify such algorithms to solve algorithm problems when appropriate. They will have derived and solved recurrences describing the performance of divideandconquer algorithms, have analyzed the time and space complexity of dynamic programming algorithms, and have analyzed the efficiency of the major graph algorithms, using asymptotic analysis. Course ContentsTopics covered include: sorting and searching; divideandconquer; dynamic programming; graph search; shortest paths; optimal spanning trees; NPcomplete problems; hashing and cryptography, time permitting. CourseworkLectures: Students are responsible for all material presented in lectures. Class participation is encouraged. Discussion sessions: Weekly discussion sessions are held on Saturdays. Students are responsible for all material covered at the discussion sessions. Homework: Weekly homework assignments are assigned after class and due the following week at the beginning of class. Exams: There are four quizzes (weeks 4, 5, 9, and 10), a midterm exam (week 6), and a final exam (week 11). There will be no makeup exams. Course gradeThe course grade will be based on homework and exams: Homework: 5%. Quizzes: 20% (5% for each of 4 quizzes). Midterm: 25%. Final: 50%. Course TextbookIntroduction to Algorithms (Third Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (ISBN 9780262033848). PrerequisitesCompletion of MPCS 50101 (or programming waiver) and MPCS 50103 (or math waiver) or consent of the instructor. 
Prerequisites (Courses)  MPCS 50103 Mathematics for Computer Science: Discrete Math or math placement waiver

Prerequisites (Other)  
Satisfies  Core Theory 
Time  Thursdays 5:30  8:30 
Location  Ryerson 276 