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