Department of
Computer Science

CS 350 Algorithms & Complexity

 

Class Piazza Site

signup

Course Description

Weekly Schedule

Course Overview

Required Textbooks

Grading Policy

Getting a Computer Account

Academic Integrity Policy

Advice on Testing

CS350, Section 1 Fall Quarter 2015
Tuesday and Thursday 14:0015:50
FAB 092 (at the bottom of the stairwell in the Engineering Building!)
CRN 11009

Instructors

Professor Andrew Black

spacer
503 725 2411

Office: FAB 11510

Office hours: Tuesday 16:0017:00 and Thursday 11:00noon. It's also fine to just wander by my office and see if I'm free.  To set up an appointment at an alternative time, please use the telephone.


Teaching Assistant
Katy Brimm

Office hours: Mon & Wed 13:3014:30

Location:  FAB 120 Fish Bowl

Course Overview

This course follows on from CS 311  which looks at what can and cannot be computed by looking closely at the complexity of computing the stuff that is computable. That means how much time, and sometimes how much space, an algorithm takes. Why does this matter, when computers are so fast? Because we often want to solve large instances of certain problems, and the time taken by some algorithms is exponential in the size of the problem instance. What that means is: if we choose an naive algorithm, solving the problem might take more time than the expected lifetime of the sun!

The approach of the course is mathematical: much of it is about deriving formulae for the expected running time of algorithms. However, there will also be some programming assignments, including a programming project.

Course Objectives

Upon the successful completion of this class, students will be able to:

1. Analyze the running time and space complexity of algorithms.
2. Use the big Oh notation. (e.g., O(n lg n).)
3. Describe how to prove the correctness of an algorithm.
4. Use the mathematical techniques required to prove the time complexity of a program/algorithm (e.g., limits and sums of series.)
5. Perform inductive proofs.
6. Prove and apply the Master Theorem.
7. Describe the notions of P, NP, NPC, and NP-hard.
8. Compare the rates of growth of functions.
9. Apply algorithmic complexity principles in the design of programs.
10. Design divide and conquer and dynamic programming algorithms.

Official Course Description

Required Textbook
gipoco.com is neither affiliated with the authors of this page nor responsible for its contents. This is a safe-cache copy of the original web site.