CScD-501 (...Algorithms) Syllabus

CScD-501
Design and Analysis of Algorithms
Course Syllabus
Winter 2009

Instructor: Timothy Rolfe
Office: 304 CEB
Office Hours: MoTuThFr, 10:00-10:50 am; We, 4:00-4:50 pm.
Email: TRolfe@ewu.edu — This is the preferred means for sending messages
Phone: 359-6162 (24-hour voice-mail — note that e-mail is the preferred message means.)
Class: MoWe, 5:00-6:50 pm in CEB-228.
Textbook: Computer Algorithms, by Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekeran, Silicon Press, 2008 (Second Edition). ISBN: 978-0-929306-41-4

Catalog Description:

CSCD 501 Design and Analysis of Algorithms 4 cr

Prerequisites: CScD-320 (formerly 327); Math 301, Math 225, or CScD-310.

The study of algorithms: Asymptotic analysis of computing time and space requirements. Strategies for designing algorithms: Divide-and-conquer, Greedy method, Backtracking, etc. Analysis of graph algorithms. Introduction to parallel algorithms and their analysis. Further topics as time permits such as techniques for algebraic manipulations, lower bound theory, and NP-Complete problems.

Course Objectives:

The student will become familiar with families of algorithms and their characteristics.

The student will learn to select algorithms and/or heuristics appropriate to the problem being solved.

The student will become familiar with a number of graph algorithms and their applications in a number of fields.

The student will become familiar with strategies for dividing computational tasks to allow the use of multiple processing elements to find their solution.

Schedule of Material

This schedule will be subject to refinement as the quarter progresses.

Week	References	Topics
1-2	Ch. 1 Section 2.6	Review of fundamental analysis topics Graph algorithms








Final		Comprehensive Final Examintion

Grading:

POINT TOTALS:

In-class exam: one midterm — 1/4 of the final grade
Assignments and projects: equal to an in-class exam — 1/4 of the final grade
Final Exam: equal to twice an in-class exam (comprehensive) — 1/2 of the final grade

COURSE GRADING:

Numerical percentage is calculated by dividing total points earned by total points possible.

Conversion to grade point system is as follows (briefly, 95/4.0, 85/3.0, 75/2.0, 65/1.0)
     95-100% : 4.0
     62-94%   : subtract 0.1 grade point for each percentage point less than 95
     60-62%   : 0.7
       0-59%   : 0.0

GENERAL POLICIES:

ADA: Americans with Disabilities Act: If there is any student in this class who has special needs for accommodation, please feel free to discuss the matter with the instructor. Students requiring accommodations need to contact Kevin Hills, Director of Disability Support Services (DSS). He can be reached at (509) 359-6871. The DSS Office is located in 124 TAW.
No makeup exams will be given without prior arrangements being having been made, or in the case of a DOCUMENTED emergency after the fact.
Assignments are due by the last emptying of the assignments' box (around 4:45 pm) on the due date. Assignments will not be accepted after the solution set has been distributed. Prior to this, late assignments will lose 10% of their value per class day.
All students are expected to act in accordance with the ACM Standards for Professional Behavior available through this link. This means cheating will not be tolerated. Students who copy another's program/work may be subject to severe disciplinary action, which may include a course grade of 0.0 and a written statement in his/her permanent record.