CS250 - Analysis of Algorithms

CMPSC 250 - Algorithms

Spring 2008 Syllabus

Department of Computer Science
Allegheny College

Instructor Information

Name: Yuting Zhang
Office: Alden 104
Phone: 814-332-2565
Email: yzhang (at) allegheny (dot) edu

Office Hours
Mon, Wed, Fri: 10:00 - 11:00am
Tue, Thu: 11:00am - 12:00pm, 1:30pm - 2:30pm
I am often available for the additional meetings if needed.
However, students are highly encouraged to come for any questions during my office hours.

Course Information

Lectures
Monday, Wednesday, Friday: 9:00am - 10:00am (Alden 101)

Lab Sessions
Thursday: 2:30pm - 4:20pm (Alden 101)

Textbook
Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani. Algorithms. McGraw-Hill Higher Education, 2006.

Other Recommended Books
Anany V. Levitin. Introduction to the Design and Analysis of Algorithms. Second Edition. Pearson Addison-Wesley, 2006.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.Introduction to Algorithms. Second Edition. MIT Press/McGraw Hill, 2001.

Prerequisite
CMPSC 112 and Mathematics 205.

Course Website
http://cs.allegheny.edu/wiki/cs250S2008

Important Dates

01/29	Last day to add a class or choose credit/no credit
02/19	Last day to drop a class
03/15-03/23	Spring break
05/02	Final

Overview

A treatment of selected topics from the analysis of algorithms including models of computation, design of efficient algorithms, computational complexity, and NP-completeness. Students develop expertise in mathematical analysis and algorithmic programming methodology. One laboratory per week.

Objectives
By the end of the course, students should be familiar with problem analysis, the basic knowledge of algorithm complexity and general techniques in algorithm design and implementation. Students are expected to: 1) be familiar with the basic concepts of algorithm complexity; 2) be acquainted with simply mathematical analysis of algorithm complexity and correctness; 3) be proficient in general design techniques(such as divide and conquer, greedy, dynamic programming, etc) in various domains (such as sorting, searching, scheduling, graph, number theory, optimization, etc); 4) be able to apply the above techniques in problem solving; 5) be introduced to classic NP-complete problems; 6) be able to present algorithms using pseudo code; 7) be able to develop abstract thinking and original thinking.

Class Schedule

Lecture#	Date	Topic	Readings	Assignments
1	01/16	Introduction of Course, Background	Ch 0
2-4	01/18-01/23	Big-O notation, Fibonacci, Iterative and Recursive	Ch 0	Lab 1(01/24-02/7)
5-9	01/25-02/03	Algorithms with Number	Ch1	Lab 2(02/07-02/21)
9-14	02/05-02/15	Divide and Conquer Algorithms, Sorting, Searching	Ch 2	Lab 3(02/21-03/06)
15-21	02/18-02/29	Graphic Algorithms	Ch 3, 4
21-24	03/03-03/10	Greedy Algorithms	Ch 5	Lab 4(03/06-03/27)
25	03/12	Review	Ch1-5
26	03/14	Midterm	Ch1-5
Spring Break
27-35	03/24-04/11	Dynamic Programming	Ch 6, 7	Lab 5(03/27-04/10)
36-41	04/14-04/25	P and NP	Ch 8, 9	Lab 6(04/10-04/24)
42	04/28	Review
	05/02 9:00am	Final

The above schedule is subjected to change according to the progress of the class and the feedback of the student.
Students are responsible for ALL the materials covered in the lectures and lab sessions including any topics not in the textbooks.

Course Requirements

Class participation
Reading and study
Assignments including written homework, lab assignments
Quizzes and Exams.

Course Polices

Grading Policy
The grade that a student receives in this class will be based on class participation, grades on the midterm and the final exam, the grades for all assignments, including written homework, laboratories and projects. The grade is breakdown as shown below. All percentages are approximate and the instructor reserves the right to make necessary changes.

10% on Class Participation
5% on Quizzes
45% on Assignments
15% on Midterm
25% on Final Exam

Attendance Policy
Students are required to attend all lectures and laboratory sessions. The attendance and participation will account for 10% of the final grade. Small quizzes will be given in a randomly selected set of lectures or laboratories. Legitimately excusable absences (such as illness, death in the family or some college sponsored activities) will be considered with notice in advance. However, each unexcused absence has 2%(the first 3 absences) or 5% (all other absences) penalty on the final grade.

Assignment Late Policy
The following policy was adopted by the entire computer science department, effective beginning in fall of 2004:

All assignments will have a due date. The products of your work are to be turned in at the class or lab meeting on the due date. Late assignments will be accepted for up to one week past the assigned due date with a 10% penalty. All late assignments must be submitted at the beginning of the first class or laboratory that is scheduled one week after the given due date. No assignments will be accepted for credit after the one week late period. It is the student's responsibility to keep secure backups of all assignments and labs.

Usage Policy for Laboratory Facilities
The Instructor and the Department's Systems Administrator have invested a considerable amount of time to ensure that our laboratories will facilitate the completion of homework and laboratory assignments and projects. However, we will NOT be able to devote much time to the configuration of a student's personal computer. The student is responsible for the configuration time on his/her personal computer, and possible late penalty. Therefore, students are highly recommended to complete all assignments and the projects while using the Department's laboratory facilities.

Honor Code Policy
All students enrolled at Allegheny College are bound by the Honor Code. It is expected that your behavior will reflect that commitment. To this end, we expect that you will adhere to the following Department Policy:

It is recognized that an important part of the learning process in any course, and particularly in computer science, derives from thoughtful discussions with teachers, student assistants, and fellow students. Such dialogue is encouraged. However, it is necessary to distinguish carefully between the student who discusses the principles underlying a problem with others, and the student who produces assignments that are merely variations on someone else's work. It will therefore be understood that all assignments submitted to faculty of the Department of Computer Science are to be the original work of the student submitting the assignment, and should be signed in accordance with the provisions of the Honor Code. Appropriate action will be taken when assignments give evidence that they were derived from the work of others.

You are encouraged to periodically review the specifics of the Honor Code as stated in the College Catalogue and elsewhere.

Disability Policy
The American with Disabilities Act (ADA) is a federal anti-discrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact the Learning Commons at 332-2898.