Data Structures and Algorithms

CSCI 5870

Fall Semester 2008

Course Syllabus and Objectives

Instructor:	Dr. Robert Kramer
Office:	326 Meshel Hall
Phone:	(330) 941-1495
E-mail:	kramer@cis.ysu.edu
WWW:	http://www.cis.ysu.edu/~kramer
Office Hours:	Monday 11am – 12pm Wednesday 11am – 12pm Thursday 12pm – 2pm Friday 11am – 12pm Also by appointment

Prerequisites

CSCI 2617 – Data Structures

CSCI 3710 or MATH 3715 – Discrete Mathematics

Textbook

• Computer Algorithms – Introduction to Design and Analysis, 3^rd edition, by Baase and Van Gelder

Objectives

• To examine common algorithm analysis techniques
• To explore common algorithm paradigms
• To explore various classic algorithms within these paradigms

Grading

Your grade is determined from the following sources:

Work	Percentage of grade
Written homework	40% total
Midterms	60% total
Programming projects	up to 10% extra credit

Grades are normally assigned using traditional 90% - 80% - 70% - 60% cutoffs. I reserve the right to lower these thresholds, but not to raise them.

Policies

Attendance

Attendance is required; with few exceptions, those who do best in courses are those who attend regularly. You will be allowed three unexcused absences; additional missed classes will result in a 5% deduction from your overall grade. Late arrivals and early departures (10 minutes or more) count as an absence.

Late Homework

Assignments are due by the end of the day (11:59pm) on the due date. For each calendar day late, 10% of the assignment’s possible score will be deducted.

Academic Honesty

You are expected to do your own work in this course! You are free to give general help to others in the course, but you may not collaborate on assignments, unless specifically permitted in the assignment. Turning in (substantially) identical work will result in a zero grade for that assignment. Subsequent collaboration will result in failure of the course.

Students With Disabilities

In accordance with University procedures, if you have a documented disability and require accommodations to obtain equal access in this course, please contact me privately to discuss your specific needs. You must be registered with CSP Disability Services, which is located at Wick House, and provide a letter of accommodation to verify your eligibility. You can reach CSP Disability Services at 330-941-1732.

General Stuff

• If you have a question in class, please ask!
• Check my web pages for class-related information. I will be posting assignments on the web, as well as other pertinent information.
• Don’t wait until the last minute to do assignments!

Topic List

Lecture Topics	From the Book
Introduction Algorithm Analysis	1.1, 1.4 – 1.6 (you should review 1.3)
Algorithm Correctness Recursion and Recurrence Equations	3.5 – 3.7
Sorting	4.1 – 4.9, 4.11
Selection Algorithms Adversary Arguments	5.1 – 5.4, 5.6
Graph Algorithms	7.1 – 7.7
Greedy Algorithms	8.1 – 8.4
Dynamic Programming	10.1 – 10.6 9.4, 11.5
String Matching	11.1 – 11.4
Polynomials	12.1 – 12.4
Parallel Algorithms	14.1 – 14.5
NP-Complete Problems	13.1 – 13.8
Dynamic Sets (time permitting)	6.1 – 6.6

Important Dates

• Last day of Add/Drop period: Tuesday, September 2, 2008
• Last day to withdraw with a W: Thursday, October 30, 2008
• Final exam: Friday, December 12, 2007

8am – 10am