# CS411 Analysis of Algorithms

Course
73803
Section
F01
Credits
3 + 0
Prerequisites:
• CS311 or CS480
• MATH307
Instructor
Brandon Marken
Phone
907-474-6104
Office
Chapman 210B
Email
Office Hours
M
W
Meeting Time
Room
Chap 104
Course Website
/courses/cs411/2016-fall/
Required Texts
Introduction to the Design and Analysis of Algorithms. Anany Levitin 3rd edition.

## Course Description

Analysis of classic algorithms, their implementation and efficiency. Topics from combinatorics (sets, graphs), algebra (integer arithmetic, primes, polynomial arithmetic, GCD, Diophantine equations, encryption), systems (parsing searching, sorting) and theory (recursion, Turing machines). The complexity classes P, NP and NP complete.

## Course Outcomes

• Ability to select the proper data structure to solve a problem
• Ability to determine the efficiency class of an iterative algorithm
• Ability to determine the efficiency class of a recursive algorithm
• Ability to recognize the complexity class of a problem
• Ability to use abstraction to solve a given problem with an existing algorithm
• Ability to design an efficient algorithm to solve a problem
• Ability to select the proper data structure to solve a problem
• Ability to recognize the complexity class of a problem
• Ability to design an efficient algorithm to solve a problem

## Tentative Schedule

21. ### Wed, Dec 21

Weight Description
10% Quizzes
25% Midterm Exam
25% Final Exam
40% Homework

Grades will be assigned based on the following percentage intervals:

A+
[97%, 100%)

A
[93%, 97%)
A-
[90%, 93%)
B+
[87%, 90%)

B
[83%, 87%)
B-
[80%, 83%)
C+
[77%, 80%)

C
[73%, 77%)
C-
[70%, 73%)
D+
[67%, 70%)

D
[63%, 67%)
D-
[60%, 63%)
F
[0%, 60%)

## Policies

Students are expected to be at every class meeting on time, and are responsible for all class content, whether present or not. If absence from class is necessary, in-class work (other than quizzes) and homework may be made up only if the instructor is notified as soon as possible; in particular, absences due to scheduled events must be arranged ahead of time. Academic dishonesty will not be tolerated, and will be dealt with according to UAF procedures. Students in this class must pay the CS lab fee. Payment allows access to the Chapman 103 lab.