UWB and UW Seal
   
Home

Syllabus
Homework assignments
Slides

Message board
Assignment dropbox

UWB Information Technologies
UWB Quantitative Skills Center
UWB Writing and Communication Cntr.
Syllabus

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

                                    E-mail: cfolson@uw.edu                   

 

Description:

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.

 

Textbooks

  • Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley, 2006.

 

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.

 

Course policies

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)

Date

Topic

Reading

Assignments

Jan.  4

Introduction

Chapter 1

 

Jan.  9

Jan. 11

Algorithm analysis

Graphs

Chapter 2

Chapter 3

 

Jan. 16

Jan. 18

Greedy algorithms

    …

Chapter 4

Program 1 due

Jan. 23

Jan. 25

Divide and conquer

    …

Chapter 5

 

Problem set 1 due

Jan. 30

Feb.  1

Dynamic programming

    …

 

Chapter 6

 

 

Feb.  6

Feb.  8

Network flow

Midterm

Chapter 7

Program 2 due

Feb. 13

Feb. 15

More network flow

    …

Chapter 7

 

Problem set 2 due

Feb. 20

Feb. 22

Intractability

     …

Chapter 8

 

Feb. 27

Mar.  1

     …

PSPACE

 

Chapter 9

 

Program 3 due

Mar.  6

Mar.  8

Student presentations

Student presentations

Chapter 10-13

 

 

Write-up due

Mar. 15

Final – Thursday

 

 

 

See also: School of STEM Course Policies