Fall 2009 Syllabus

**Instructor:** Prof. J Genetti

**Office Hours:** 208B Chapman MWF 1-2, T 2:00-3:30 or by appointment

**Phone/Email:** 474-5737 / `ffjdg @ uaf . edu`

**Class web page:**
`http://www.cs.uaf.edu/2009/fall/cs611`

**Prerequisites:** CS411

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

**Textbooks:**

Computers And Intractability: A Guide to the Theory of NP-Completeness
by Garey & Johnson

**Expected Outcomes**

- Complete understanding of sorting algorithms
- Understand NP completeness and its applicability to algorithm design
- Know how to prove an algorithm is NP-complete from scratch
- Know how to reduce an algorithm to NP-complete
- Understand how approximation algorithms work and when they are appropriate
- Become more familiar with important problems such as searching, selection, polynomial evaluation and decidability

**Exams:**

There will be a take-home mid-term exam due **Tuesday October 27 at 5pm** and
a closed-book in-class final exam on **Thursday December 17 from 3:15-5:15pm**.
Each exam is worth **25%** of your final grade.

**Homework:**

Homework will be assigned weekly during the semester.
Late homework is accepted at a 20% penalty per day (Mon-Fri).
This will make up **25%** of your final grade.

**Class Presentations:**

Each student will present several topics in class during the semester.
The exact number of presentations will depend on the number of students
in the class and lecture days available. You will have at least one
week to prepare your presentation.
You will be graded on the clarity of your presentation and the quality
of your answers to questions.
This will make up **25%** 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%).