CS411 Analysis of Algorithms

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

1. Mon, Sep 01

   Labor Day (offices closed — no classes, registration or fee payment)

2. Thu, Sep 04

   First day of instruction; late registration begins

3. Fri, Sep 12

   Deadline for adding classes, late registration and fee payment; 5 p.m. in person, midnight at UAOnline

4. Fri, Sep 19

   Deadline for student- and faculty-initiated drops (course does not appear on academic record)

5. Fri, Sep 19

   Deadline for 100 percent refund of tuition and fees

6. Fri, Oct 10

   Freshman progress reports due

7. Wed, Oct 15

   Deadline to apply for admission for spring semester (graduate students)

8. Wed, Oct 15

   Deadline to apply for fall 2014 graduation

9. Mon, Oct 27

   Spring 2015 course list available at UAOnline

10. Fri, Oct 31

    Deadline for student- and faculty-initiated withdrawals (W grade appears on academic record)

11. Sat, Nov 01

    Deadline to apply for admission for spring semester (undergraduate students)

12. Mon, Nov 10

    Begin registration and fee payment for degree students for spring 2015 semester and WINTERmester 2015

13. Mon, Nov 17

    Begin registration and fee payment for non-degree students for spring 2015 semester

14. Thu, Nov 27

    Thanksgiving holiday (no classes, most offices closed)

15. Fri, Dec 12

    Last day of instruction

16. Mon, Dec 15

    Final examinations

17. Fri, Dec 19

    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.

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.