CS 5050: Advanced Algorithms

CS 5050: Advanced Algorithms

Spring 2008

Instructor: Changhui (Charles) Yan

Office: Old Main 401F

Phone: 797-2570

Place: Old Main 119

Time: MWF 12:30 pm- 1:20 pm

Office Hours: MWF 3pm-4pm

Textbook: Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons, Inc. ISBN: 0-471-38365-1.

Course Goal:

o Gain knowledge on a variety of computational problems and their algorithmic solutions.

Learning Outcomes:

o Be able to analyze the time and space complexities of an algorithm.

o Be able to choose appropriate data structures in the design of an algorithm based on their mathematical properties.

o Be able to design algorithms for new problems using standard algorithmic techniques.

Assignments:

Approximately, one assignment every two weeks.

Quizzes:

Quizzes will be given without notification in advance. They will be given at the beginning of a class and cover materials in the previous class.

Exams:

There will be two midterm exams and one comprehensive final exam.

Grading:

Assignments 40%
Quizzes 5%
Midterm exams 30%
Final exam 25%

Two scales to decide your final grade. You can use whichever gives you the better grade:

A [90,100] or top 15%

A- [85,90) or top [25%,15%)

B+ [80,85) or top [35%,25%)

B [75,80) or top [45%,35%)

B- [70,75) or top [55%,45%)

C+ [60,70) or top [65%,55%)

C [50,60) or top [75%,65%)

C- [0,50)

Late Work:

Assignments are due at midnight on the due date. Assignments handed within three days after the due time will be subjected to a 25% reduction in score. Assignments overdue by more than three days will get a grade of 0, except for a legitimate reason, e.g. illness, which must be documented.

Code of Conduct for Computer Science Classes:

As a computer scientist, or someone taking a computer science class, you are expected to perform your work at all times in an ethical manner. This means that in addition to doing your own work and giving appropriate credit when the work of others is used, you are required to protect your work.

A student that protects their work will not allow another student access to that work whether it be allowing it to be copied, or treating its security in such a way as to give unintentional access, such as "accidental" loss. It is the policy of the department that when duplicate (essentially the same) work is turned in by two or more students, without acknowledgement of allowed cooperation, all involved students will be considered in violation of this department policy. Under such circumstances, each student will receive minus the points possible for the work.

Thus, for a 15 point assignment, all would receive -15 points. If the infraction is deemed more egregious, then further action may be taken.

Disability Resource Center:

Students with physical, sensory, emotional or medical impairments may be eligible for reasonable accommodations in accordance with the Americans with Disabilities Act and Section 504 of the Rehabilitation Act of 1973. All accommodations are coordinated through the Disability Resource Center (DRC) in Room 101 of the University Inn, 797-2444 voice, 797-0740 TTY, or toll free at 1-800-259-2966. Please contact the DRC as early in the semester as possible. Alternate format materials (Braille, large print or digital) are available with advance notice.

Course website:

The website for this course is http://www.cs.usu.edu/~cyan/CS5050/.

Grader:

Yuxuan Wang (yuxuan.wang@aggiemail.usu.edu)

Last day to Drop: Jan 28

Last day to Add: Jan 28

1. Algorithm Analysis: Counting Primitive Operations, Amortization, and Master Method.

2. Greedy Method, Dynamics Programming

3. Graphs, DFS

4. BFS, Biconnectivity

5. Digraphs

6. Shortest paths