Course Syllabus COMP 550 001 old 122 Algorithms and Analysis Spring 2009 Meeting Place FB007 Meeting Time 11 00 12 15 TuTh Instructor Prof David Plaisted Telephone 962 1751 Office SN352 E mail plaisted at cs unc edu Office Hours MW 1 2 TA Hao Xu Telephone 843 7409 TA Office SN353 E mail xuh cs unc edu TA Office Hours MW 2 3 Text Introduction to Algorithms Cormen Leiserson Rivest and Stein McGraw Hill 2001 Prerequisites COMP 411 001 old 120 and COMP 410 001 old 121 Grading Homework Midterm Exams Pop Quizzes Final Exam 30 38 2 30 The first mid semester exam will be on Thursday February 12 during class The second mid semester exam will be on Thursday March 26 during class The final exam will cover the entire course All exams are closed book and closed notes There will be about 8 homework assignments Some of the homework assignments may be timeconsuming Homework assignments are due at the beginning of class on the due date given Homeworks turned in during class but after the beginning of class will be penalized 10 percent Homework turned in after class but on the same day will be penalized 20 percent Homeworks turned in the next day will be penalized 30 percent Homeworks turned in on subsequent days will be penalized 40 percent or more There will also be 5 or more pop quizzes These do not count much but help me to see how well the class is learning the material and help you to remember the material better We will use power point slides prepared by Mark Foskey Dinesh Manocha Ming Lin and Jack Snoeyink together with my notes from a previous class offering The course web page is at www cs unc edu plaisted comp550 and includes power point slides homework and practice exams Please observe basic courtesy in class If you yawn try to do so quietly If you need to leave the room it is not necessary to do so while my back is turned Class participation may influence your grade especially if it is on the borderline I make a check mark next to the students who I remember have participated and this could affect the boundary between grades Students who do not come to class often tend to get lower grades unless they have exceptional ability in abstract thinking You should be aware that the honor code which prohibits the giving or receiving of unauthorized aid on exams and homework is in effect Topics The list of topics I plan to cover is given below 1 Topics Covered Chapter 2 Introduction Program Correctness Chapter 3 Appendix A Asymptotic notation sums functions Chapter 2 3 4 Recurrences Divide and Conquer Appendix C Chapter 5 Counting and Probability Chapter 6 Heapsort Chapter 7 Quicksort Chapter 8 1 Decision Trees Exam 1 Chapter 8 Sorting in Linear Time Chapter 9 Selection Chapter 11 Hash Tables Chapter 12 Binary Search Trees Chapter 13 Red Black Trees Classes 1 1 2 2 1 1 1 1 2 2 2 1 1 Advanced Design and Analysis Techniques Chapter 15 Dynamic Programming Exam 2 Chapter 15 Dynamic Programming Chapter 16 Greedy Algorithms will skip 16 4 and 16 5 1 1 1 2 Graph Algorithms Chapter 22 23 Graph Algorithms Chapter 24 25 Shortest Paths 3 2 TOTAL 28 2