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
bamarken@alaska.edu
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

    • Residence halls open, 8 a.m.
    • Orientation for new students
    • First day of instruction; late registration begins
    • Deadline to apply for admission for spring semester (international students)
    • Labor Day (offices closed — no classes, registration or fee payment)
    • Deadline for adding classes and late registration; 5 p.m. in person, midnight at UAOnline
    • Last day for student- and faculty-initiated drops (course does not appear on academic record)
    • Deadline for tuition and fee payment and refunds; 5 p.m. in person, midnight at UAOnline
    • Early progress reports due
    • Deadline to apply for admission for spring semester (graduate students)
    • Deadline to apply for fall 2016 graduation
    • Spring 2017 course list available at UAOnline
    • Deadline to apply for admission for spring semester (undergraduate students)
    • Last day for student- and faculty-initiated withdrawals (W grade appears on academic transcript)
    • Begin registration and fee payment for spring 2017 semester and WINTERmester 2017
    • Begin registration and fee payment for nondegree students for spring 2017 semester and WINTERmester 2017
    • Thanksgiving holiday (no classes, most offices closed)
    • Last day of instruction
    • Final examinations
    • Residence halls close, noon
    • Deadline for faculty to post grades, noon

Grading Policies

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.

UAF academic policies http://www.uaf.edu/catalog/current/academics

CS Department policies http://www.cs.uaf.edu/departmental-policies/

Disabilities Services:

The UAF Office of Disability Services implements the Americans with Disabilities Act (ADA), and ensures that UAF students have equal access to the campus and course materials. I will work with the UAF Office of Disability Services (208 WHITAKER BLDG, 474-5655) to provide reasonable accommodation to students with disabilities.

Updated: