CSI 3105A/B FALL 2014 CSI 3105 DESIGN AND ANALYSIS OF ALGORITHMS (3 h.p.w.t., - 3 cr.) Analysis of algorithms: worst-case analysis, complexity analysis, asymptotic notations and basic complexity classes. Algorithm design techniques: brute force, divide and conquer, dynamic programming, greedy, backtracking. Computational complexity of problems: lower bound arguments, the classes P, NP, NP-complete, dealing with NPcomplete problems. Prerequisites: CSI2110 and CSI2101 or (for honors mathematics students only: CSI2110, MAT2141 or MAT2143). COURSE WEB PAGE: http://www.site.uottawa.ca/~sylvia/csi3105web/index.htm TIME & LOCATION: PROFESSOR: Mon. Wed. Name: Office: Office Hours: Email: 13:00 – 14:30 11:30 – 13:00 LPR 155 LPR 155 Dr. Sylvia Boyd STE 5106 Monday 10:30-12:00 [email protected] TEXTBOOK:(Required) Foundations of Algorithms (Fifth Edition), by R. Neapolitan, Jones and Bartlett Publishers Available at: Agora Bookstore: www.agorabookstore.ca **NOTE: This is the same textbook that was used for the last few years although it is a newer edition. Note that the previous editions can also be used, there is very little difference. COURSE NOTES: Will be provided via email. COURSE EVALUATION: Assignments: There will be 4 assignments. The assignments are to be handed in directly to the professor by the due date and time. Assignments which are late by at most one day will lose 10%. Assignments received 24 hours or more after the due date and time will receive a grade of 0. Cheating on assignments will not be tolerated--students must do their own work. For a full description of the current academic fraud regulations, please follow: http://www.engineering.uottawa.ca/downloads/pdf/FacultyRegu lationsEnglish2008.pdf Class Test: There will be a closed book class test: Monday, October 27, 2014 (location to be determined) Exam: There will be a closed book 3 hour final exam scheduled in December. Marking Scheme: Let A M X T = = = = average assignment mark mark on class test mark on final exam ( 2X + M )/ 3 (a combined test mark) If (T >= A) or (T >= 70) Final Mark = .75*T + .25*A Else Final Mark = (1-R)*T + R*A where R = .25*(max(0,T-50))/20. COURSE OBJECTIVES: 1) 2) 3) To learn various algorithm design techniques, and recognize when to apply them. To understand the importance of efficiency in algorithms. To learn how to analyze and compare algorithms according to predicted time and space requirements. COURSE OUTLINE: 1) 2) 3) 4) 5) 6) Introduction Algorithms: Efficiency, Analysis and Order The Divide and Conquer Approach The Dynamic Programming Approach The Greedy Approach Computational Complexity of a Problem: An introduction to the Theory of NP and NP Completeness Backtracking 7) SOME SPECIAL NOTES REGARDING IN-CLASS BEHAVIOUR: • Taking photographs or videos during class is strictly prohibited. SOME SPECIAL NOTES FROM THE FACULTY OF ENGINEERING: • Class attendance is mandatory. As per academic regulations, students who do not attend 80% of the class will not be allowed to write the final examinations. • All components of the course (i.e laboratory reports, assignments, etc.) must be fulfilled otherwise students may receive an INC as a final mark (equivalent to an F). This is also valid for a student who is taking the course for the second time.