MCS 401/EECS 460: Computer Algorithms I

Fall 1999

Instructor David Marker

class meetings: MWF 10:00-10:50 310 AH
Office: 411 SEO, 341 SEO
e-mail: marker@math.uic.edu

Office Hours

Monday: 2:30-3:30 (411 SEO)
Wednesday: 8:30-9:30 (411 SEO) and by appointment

Description

Techniques for analyzing the efficiency of algorithms. We will study a number of classic algorithms and learn techniques for attacking new problems. Some of the specific topics covered will include:

Sorting
Graph Algorithms
Pattern Matching
Fast Fourier Transforms
Divide-and-Conquer Strategies
Dynamic Programming
NP-complte Problems

Texts

S. Baase, Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley, 2nd Edition.

Prerequisites

C or better in STAT 381 and MCS 360; or EECS 360

Grading

There will be one midterm and a final exam. Your course grade will be computed as follows:

Homework Assignments: 15%
Midterm Exam: 35%
Final Exam: 50%

Midterm Exam

The Midterm Exam will be given on Wednesday October 13. The Midterm will cover through section 4.3. Some sample midterms are in the links below.

Final Exam

The Final exam will be Wednesday December 8 at 8:00am.
The exam will be comprehensive covering all course material, but will emphasize material from the second half of the course.
You may bring two 8.5 by 11 pages (front and back) of notes.
My exam week office hours will be Monday 9-12.

Homework

Homework assignments will be assigned and graded weekly. Assignments will be collected at the begining of the class period they are due. Late homework will not be accepted. Two assignments will be droped when computing your homework grade.
Homework problems must be answered completely in clearly written English.
You are encouraged to also try unassigned problems in the text. I will be happy to discuss these problems with you.
You may discuss homework problems together, but each student must indpendently write up his or her solution.

Some Links

Interactive version of Dijkstra's Shortest Path Algorithm
Interactive version of Kruskal and Prim's Minimal Spanning Tree Algorithms
Sample midterm from 1990 (postscript file).
Sample midterm exams given by Professor Larson in 1993.
- 1st midterm (postscript file)
- 2nd midterm(postscript file)
Sorting Demonstration A visual demonstration of various sorting algorithms at work.
Homework assignments
translation table between "algorithmic language" in text and C
David Marker's Home Page

Cheating

Academic dishonestly of any form will not be tolerated and will be dealt with harshly. The minimum penalty for students involved in a cheating incident is failure in the course. Cheating may lead to expulsion from the University.