CSC 321 |
Spring 2002 |
|
|
Syllabus |
This class will introduce you to the basic concepts and techniques of algorithm design and analysis. We will cover sorting and searching, graph algorithms, greedy algorithms, dynamic programming, and the theory of NP-completeness.
Warning: Students who have taken this class in the past have experienced long hours, frustration, and poor eyesight brought on by prolonged staring at problem sets. The best way to avoid these symptoms is to see your instructor as soon as you feel them coming on. Do not put off homeworks until the night before a due date. It is best to begin them early and work on each for at least a little while every day.
You must have taken MAT 140 and either CSC 311 or CSC 313 before taking this class.
 |
The textbook "Introduction to Algorithms" by Cormen, et al., and is pictured to the left. Note that this is the 2nd edition. You will not be able to use the previous edition. |
This is a tentative schedule of the topics and chapters we will discuss. Please do
the reading before or early in each week. Note the dates of the midterm
and final exams.
| Week 1 | 4/1, 4/3 | Algorithm analysis, asymptotics, sorting (chapters 1, 2, and 3) |
| Week 2 | 4/8, 4/10 | Divide and conquer algorithms, solving recurrences, more sorting (chapters 2, 4, and 7) |
| Week 3 | 4/15, 4/17 | Specialized sorts, selection, dynamic programming (chapters 8, 9, and 15) |
| Week 4 | 4/22, 4/24 | Dynamic programming, graph theory (chapters 15, 22, and appendix B.4) |
| Week 5 | 4/29, 5/1 | Graphs and graph traversals (chapter 22) |
| Week 6 | 5/6, 5/8 | Review (5/6) and midterm exam (5/8) |
| Week 7 | 5/13, 5/15 | The greedy method, graph optimization algorithms (chapters 16, 23, and 24) |
| Week 8 | 5/20, 5/22 | Dynamic programming and greedy method examples (chapters 16 and 25) |
| Week 9 | 5/27, 5/29 | 5/27 is Memorial Day and a holiday. Introduction to complexity theory (chapter 34) |
| Week 10 | 6/3, 6/5 | NP-completeness, approximation algorithms (chapters 34, 35) |
| Finals week | Tuesday, 6/11 | Final exam, 11:45am to 2:00pm |
There will be two exams: a midterm, worth 25% of the grade, and a final, worth 35%. The remaining 40% will be made up by written assignments. Letter grades will be assigned according to the following table.
| Percentage | Grade |
|---|---|
| 92% to 100% | A |
| 89% to <92% | A- |
| 86% to <89% | B+ |
| 82% to <86% | B |
| 79% to <82% | B- |
| 76% to <79% | C+ |
| 73% to <76% | C |
| 70% to <73% | C- |
| 67% to <70% | D+ |
| 60% to <67% | D |
| <60% | F |
My office hours can be found on my personal web page.
I hold office hours specifically so that students have a time when they know I'll be in and available to answer questions. Please make use of my office hours! One of the resources you get when registering for a course is a chance to talk to the instructor one on one. Students often discover that even a brief chat about a program they're having trouble with will often clear up that (and other) problems, allowing them to proceed and complete the assignment.
In fact, you should stop by whenever you have a question. My teaching is not limited to the classroom. I have found that some the best teaching (and learning) happens when a student comes in to see me.
My office hours are posted above but I want to make it clear that I'm also available outside of those hours. The best way to see me then is to send me e-mail (jrogers@cs.depaul.edu) or call me (312-362-8334) and arrange for a meeting time. You can also try dropping by. If I'm in and not busily engaged in something else, I will be more than happy to see you.
Students may discuss assignments with one another in general terms. For example, you may discuss general strategies for attacking a problem. But you may not work together when writing the solution. I know it may sometimes not be clear what is considered permissible cooperation and what is considered cheating. If you are not certain, please discuss it with me ahead of time.
A corollary is that if you are having trouble getting started on an assignment, please come in and see me or send me e-mail (see my discussion about office hours above). Students often find that even a brief chat will clear up quite a few problems.
Students may not collaborate in any way on exams.
Activities that are clearly cheating include (but are not limited to): copying another person's work on a programming project, homework assignment, or exam; using any reference not authorized by the instructor on a programming project, homework assignment, or exam.
The penalty for cheating is an F in the course. Also, the appropriate dean will be informed in writing of cheating incidents and will be advised that students assigned an F for cheating should not be permitted to receive a W for the course.
