Instructor: Chris Lüer, PhD
Mo, We, Fr 11:00-11:50 am, RB 122
Description - Materials - Policies - Schedule
Required Textbook:
Brassard, Gilles and Bratley, Paul. Fundamentals of Algorithmics. Prentice-Hall 1995.
Web site: http://www.cs.bsu.edu/homepages/chl/324-06S/
Mailing List: http://www.bsu.edu/archives/cs324-l.html
Cheating. Consequences of cheating in this class: the course grade is lowered, possibly to F. No team work is allowed in this class. Material that is copied from books or Web pages needs to be quoted and the source must be given. Be aware of the Ball State University Student Academic Ethics Policy.
Assignments. Assignments are due Mondays at the beginning of class. Late assignments will be subject to a deduction of 20% and are accepted up to a week late. Write your name on the top of page 1; if an assignment has more than one page, please staple them. The oral presentation at the end of the semester counts as three assignments.
Grading.
Final Exam 40%
Tests 20%
Homework 40%
If you receive 93.3% of the total course credit, you will get an A. If you receive 90.0%, you will get an A- or better. If you receive 86.7%, you will get a B+ or better, and so on. The grading scale will be shifted so that the median grade is at least a B.
Tests. There will be three non-comprehensive midterm tests plus a comprehensive final exam. Each test will cover both the material presented in class and the related material from the textbook.
Students with special needs or disabilities. If you need course adaptations or accommodations because of a disability, if you have emergency medical information to share with me, or if you need special arrangements in case the building must be evacuated, please make an appointment with me as soon as possible.
| Week | Topic | Readings (chapters in the textbook) | Assignments due |
|---|---|---|---|
| 1 | Introduction | ||
| 2 | Holiday (Mo); Introduction | 1 | HW 1 |
| 3 | Efficiency of Algorithms | 2-3 | HW 2 |
| 4 | Analysis of Algorithms | 4 | HW 3 |
| 5 | Data Structures; Test 1 (We 2/8) | 5 | Prepare for Test 1 |
| 6 | Greedy Algorithms | 6 | HW 4 |
| 7 | Divide-and-Conquer Algorithms | 7 | HW 5 |
| 8 | Dynamic Programming | 8 | HW 6 |
| 9 | Graph Algorithms; Test 2 (We 3/15) | 9 | Prepare for Test 2 |
| 10 | String Matching | handouts | HW 7 |
| 11 | Probabilistic Algorithms | 10 | HW 8 |
| 12 | Computational Complexity | 12 | HW 9; presentation proposal |
| 13 | Student Presentations; Test 3 (We 4/12) 4/14: T. Daugherty - Shell Sort; J. Simon - Miller-Rabin; D. Gopalagari - Prim |
Prepare for Test 3 | |
| 14 | Student Presentations 4/19: P. Larimore - Ford-Fulkerson; D. Null; C. Wu - Counting sort 4/21: N. Chalasani - Radix Sort; S. Chilakapati - Floyd; D. Stanley - RSync |
||
| 15 | Student Presentations 4/24: Y. Li - Graph coloring; A. Nowels - Pointer doubling; B. Neal - Viterbi 4/26: L. Pullan - Boyer-Moore; S. McNeany - Huffman code; S. Jamison - Las Vegas 8 Queens |
Final Exam: Monday, 5/1/2006, 9:45 am - 11:45 am