Fall 2010 Syllabus

**Instructor:** Prof. J Genetti

**Office Hours:** 208B Chapman MWF 1-2, TR 10:30-11:30 or by appointment

**Phone/Email:** 474-5737 / `jdgenetti @ alaska . edu`

**Class Time/Location:** MWF 2:15-3:15 Chapman 106

**Class web page:**
`http://www.cs.uaf.edu/2010/fall/cs411`

**Prerequisites:** CS 311 and MATH 307

**Department policies:**
`http://www.cs.uaf.edu/cs/Policies.html`

**Required Textbook:** *The Design & Analysis of Algorithms* (2nd edition) by Levitin

**Expected Outcomes**

- Understand the pros and cons of the common sorting algorithms
- Be able to set up and solve recurrence relations for any algorithm
- Be able to determine the efficiency class of any algorithm
- Be able to choose and/or design the best algorithm for a given problem
- Understand NP-completeness and its impact on algorithm design
- Understand how approximation and random algorithms work and when they are appropriate
- Understand the classic algorithms from important problem domains (i.e. sets, graphs, polynomial arithmetic, GCD, parsing, sorting, etc)

**Exams:**

There will be a closed-book in-class mid-term exam **Friday October 22**
and an open-book in-class final exam on **Friday December 17 from 3:15-5:15pm**.
The mid-term is worth **30%** and the final exam is worth **40%** of
your final grade.

**Homework:**

Homework will be assigned on Fridays and due the following Friday by 5pm.
Late homework will only be accepted until the start of class on Monday
at a penalty of 25%.
The best 9 of 10 scores will make up **30%** of your final grade.

**Grading Policy:**

Final grades will be assigned based on the following percentage intervals:
A+ [95%,100%], A [90%,95%), A- [85%,90%),
B+ [80%,85%), B [75%,80%), B- [70%,75%),
C+ [65%,70%), C [60%,65%), C- [55%,60%),
D+ [50%,55%), D [45%,50%), D- [40%,45%), F [0%,40%).