Instructor: Chris Lüer, PhD
Tu, Th 5:00-6:15 pm, RB 104
Description - Materials - Policies - Schedule
Required Textbook: Kleinberg, Jon, and Tardos, Éva. Algorithm Design. Pearson 2005.
Web site: http://www.cs.bsu.edu/homepages/chl/324-07F/
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 Tuesdays 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 | Introduction | 1 | HW 1 |
| 3 | Algorithm Analysis | 2 | HW 2 |
| 4 | Graphs | 3 | HW 3 |
| 5 | Test 1 (Th 9/20) | Prepare for Test 1 | |
| 6 | Greedy Algorithms | 4 | HW 4 |
| 7 | Divide-and-Conquer Algorithms | 5 | HW 5 |
| 8 | Dynamic Programming | 6 | HW 6 |
| 9 | Test 2 (Th 10/18) | Prepare for Test 2 | |
| 10 | Graceful labeling and planarity | handouts | HW 7 |
| 11 | Dynamic Programming | 13 | HW 8 |
| 12 | Randomized Algorithms | 8 | HW 9; presentation proposal |
| 13 | Computational Complexity; Test 3 (Th 11/15) | Prepare for Test 3 | |
| 14 | Break | ||
| 15 | Tu 11/27: M. Fleming, Random Number Generation; Chen, Shell Sort; Decker, Grover
Th 11/29: Wagner, A-Star; Corn, Bellman-Ford; Gevirtz, MD5; Lakes, Luhn/CRC; McWhirt, Blowfish |
HW 10 | |
| 16 | Tu 12/4: Mellinger, Bezier; Arnold, Convex Hull; Cheng: Secant
Th 12/6: T. Fleming, Prim; Binford, Scanline Rendering; Tinsley, TBA; Wang, Radix Sort; Termion, Sudoku Solver |
Final Exam: Wednesday, 12/12, 4:30 pm - 6:30 pm