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. Thu, Aug 25

   Residence halls open, 8 a.m.

2. Thu, Aug 25

   Orientation for new students

3. Mon, Aug 29

   First day of instruction; late registration begins

4. Thu, Sep 01

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

5. Mon, Sep 05

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

6. Fri, Sep 09

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

7. Fri, Sep 09

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

8. Mon, Sep 12

   Deadline for tuition and fee payment and refunds; 5 p.m. in person, midnight at UAOnline

9. Sun, Oct 02

   Early progress reports due

10. Sat, Oct 15

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

11. Mon, Oct 17

    Deadline to apply for fall 2016 graduation

12. Mon, Oct 31

    Spring 2017 course list available at UAOnline

13. Tue, Nov 01

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

14. Fri, Nov 04

    Last day for student- and faculty-initiated withdrawals (W grade appears on academic transcript)

15. Mon, Nov 14

    Begin registration and fee payment for spring 2017 semester and WINTERmester 2017

16. Mon, Nov 21

    Begin registration and fee payment for nondegree students for spring 2017 semester and WINTERmester 2017

17. Thu, Nov 24

    Thanksgiving holiday (no classes, most offices closed)

18. Sat, Dec 10

    Last day of instruction

19. Mon, Dec 12

    Final examinations

20. Sun, Dec 18

    Residence halls close, noon

21. Wed, Dec 21

    Deadline for faculty to post grades, noon

Grading Policies

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.

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.