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

## 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.

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

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