CS411 Analysis of Algorithms

Course
76046
Section
F01
Credits
3 + 0
Prerequisites:
  • CS311
  • MATH307
Instructor
Glenn Chappell
Phone
907-474-5736
Office
Chapman 201B
Email
ggchappell@alaska.edu
Office Hours
MWF
T
Meeting Time
Room
104 Chapman
Course Website
/courses/cs411/2014-fall/
Required Texts
A. Levitin, Introduction to the Design and Analysis of Algorithms, 3rd ed.

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

    • Labor Day (offices closed — no classes, registration or fee payment)
    • First day of instruction; late registration begins
    • Deadline for adding classes, late registration and fee payment; 5 p.m. in person, midnight at UAOnline
    • Deadline for student- and faculty-initiated drops (course does not appear on academic record)
    • Deadline for 100 percent refund of tuition and fees
    • Freshman progress reports due
    • Deadline to apply for admission for spring semester (graduate students)
    • Deadline to apply for fall 2014 graduation
    • Spring 2015 course list available at UAOnline
    • Deadline for student- and faculty-initiated withdrawals (W grade appears on academic record)
    • Deadline to apply for admission for spring semester (undergraduate students)
    • Begin registration and fee payment for degree students for spring 2015 semester and WINTERmester 2015
    • Begin registration and fee payment for non-degree students for spring 2015 semester
    • Thanksgiving holiday (no classes, most offices closed)
    • Last day of instruction
    • Final examinations
    • Residence halls close, noon

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: