CSS 549 Algorithm Design and Analysis
University of Washington, Bothell School of STEM Computing & Software Systems
Professor: Dr. Clark F. Olson Class: TTh 8:00-10:00pm, UW1-031
Office: UW1 271B Office Hours: TTh 5:45-7:45pm
Phone: (425) 352-5288 or by appointment
This course covers fundamental techniques for algorithm design and analysis, including computational complexity, greedy algorithms, divide-and-conquer algorithms, dynamic programming, graph algorithms, randomized algorithms, and computational intractability.
Topics and Learning Objectives
Students will be able to:
· Describe and implement certain greedy, divide-and-conquer, and dynamic programming algorithms.
· Select and apply an appropriate algorithmic technique (greedy, divide-and-conquer, dynamic programming, etc.) for solving computational problems.
· Apply graph algorithms to problem solving.
· Determine the computational complexity of an algorithm (recursive or iterative) and express it using Big-O notation.
· Recognize that certain problems are intractable and apply techniques, such as approximation algorithms, to address them.
Assignments / Grading
Students will complete programs, problems sets, and a short presentation (with write-up).
Assignments: 50% (All programs and problems sets will be equally weighted.)
Midterm Exam: 25%
Final Exam: 25%
All programs, problems sets and exams will be graded based on correctness and completeness. Documentation and use of good programming practices will also be considered. A student who achieves 80% of the possible points will receive a 2.7 grade in this course. Students with 95% and above will receive a 4.0 grade. Scores in between will be interpolated.
Assignments will be turned using a Catalyst dropbox. They are due prior to class on the due date and will be marked late promptly at 8pm. Assignments can be turned in up to 5 days late (including weekends) with a 10% grade reduction per day. No individual extensions will be given.
For all assignments (except for the presentation), students may work in pairs (but are not required to). When working as a pair, all substantial work must be performed with both students present. Except for students working in pairs, do not discuss solutions to the assignments, including program output. It is not acceptable to use (or even view) code or solutions found on the web (for example, GitHub) and it is also not acceptable for your code or solutions to be publicly accessible on the web (for example, a public GitHub repository). Plagiarism will result in an assignment score of zero and a misconduct letter in your student record. Please be very careful to adhere to the student code of conduct: http://www.washington.edu/cssc/for-students/student-code-of-conduct/
Please note that there is no extra credit in this course, so make sure that you turn in the best work that you can.
Make-up and rescheduled exams will not be given except under extraordinary circumstances. It is not acceptable to schedule a trip or another appointment on these days. Exceptional circumstances should be discussed with the instructor in advance, except in the case of a dire emergency, which should be well documented.
Please mute all cell phones prior to class. Talking and other noise during lecture should be kept to a minimum as a courtesy to other students who are trying to learn.
Tentative Schedule (subject to change)
See also: School of STEM Course Policies