Instructors:
Prof. Avrim Blum Prof. Bruce Maggs Prof. Daniel Sleator 4107 Wean Hall, x8-6452 4123 Wean Hall, x8-7654 4128 Wean Hall, x8-7563 avrim+@cs.cmu.edu bmm+@cs.cmu.edu sleator+@cs.cmu.edu Hours: Wed. 11:00-12:00 Hours: Wed. 4:30-5:30 Hours: Mon. 4:00-5:00
Teaching Assistants:
Doug Baker Carl Burch Robert Driskill
8102 Wean Hall, x8-3042 7203 Wean Hall, x8-3621 3502 Wean Hall, x8-3619
ldbapp+@cs.cmu.edu cburch+@cs.cmu.edu robd+@cs.cmu.edu
Hours: Mon. 3:00-4:00 Hours: Fri. 9:00-10:00 Hours: Mon. 1:00-2:00
Course Secretary: Head Grader:
Dorothy Zaborowski Martin Dixon
4116 Wean Hall, x8-3779 3505 Wean Hall
mdixon+@andrew.cmu.edu
Hours: TBA
Lecture: TuTh 12:00-1:00, DH 2315. Avrim Blum and Daniel Sleator
Recitations:
A M,W 8:30 SC 200 Carl Burch
B M,W 9:30 SC 200 Carl Burch
C M,W 10:30 SC 200 Robert Driskill
D M,W 11:30 SC 200 Robert Driskill
E M,W 12:30 SC 200 Doug Baker
F M,W 1:30 SC 200 Doug Baker
G M,W 2:30 SC 200 Bruce Maggs
H M,W 3:30 SC 200 Bruce Maggs
Course Web page:
Course staff in Wean 5th clusters:
Sundays and Mondays before due dates, 8-10pm+
Your participation in the course will involve the following forms of activity: attending and participating in lectures and recitations, reading the texts, doing the homework assignments, and taking the quizzes, midterm, and final. You should also periodically read the course bulletin boards (discussed in Section 8).
The grade will break down as follows:
Although your grade does not depend directly on attendance, you will be responsible for the material covered both in the main lecture and in your recitation.
Grades for the course will be determined by a curve. First, we will compute a weighted total of each student's scores on assignments and exams. These will be plotted as a histogram, and then approximate cutoff points for the different letter grades will be determined. Individual cases, especially those near the cutoff points may then be adjusted upward or downward based on factors such as earned extra credit and participation in recitation discussions. Very roughly, we expect to give about 25-30% A's, 30-40% B's, 20-25% C's, and about 10% ``other.'' This is not a requirement; we could give all A's if performance warrants it.
Make-up on the quizzes or exams will be given only by presenting a letter from your Dean or the Director of Athletics. Be prepared to present your student I.D. at the Midterm and Final.
The textbooks cover most of the material taught in the course. In the schedule shown in Section 5,, you will see the readings associated with each section of the course. It would be a good idea to read over each of these sections twice--a brief reading before the lecture to become familiar with the basic concepts, and a more thorough reading later to understand the details.
Class Date Day Lecture Reading Other
0 16-Jan T Course Overview Ch. 1 1 18-Jan Th C/C++ Programming Ch. 2, 3 2 23-Jan T 3 25-Jan Th 4 30-Jan T Stacks, Queues, and Ch. 4.1, 4.2, 4.6, 7 Assignment 1 Due Mon. 5 1-Feb Th C++ Classes 6 6-Feb T Program Design/Analysis Ch. 5 7 8-Feb Th Quiz 1 8 13-Feb T Performance Analysis Ch. 6, A.1, A.2, A.4 Assignment 2 Due Mon. 9 15-Feb Th Dynamic Programming 10 20-Feb T Trees Ch. 9.1--9.3, 9.6--9.7 11 22-Feb Th Sorting Ch. 13.1, 13.2, A.7 12 27-Feb T Ch. 13.4, 13.5 Assignment 3 Due Mon. 13 29-Feb Th Midterm Exam 14 5-Mar T Heaps, Heapsort, and Ch. 9.4, 9.5, 13.3 15 7-Mar Th Priority Queues Ch. 4.3, A.6 16 12-Mar T Radix Sort Ch. 13.6 Assignment 4 Due Mon. 17 14-Mar Th Hashing Ch. 11 18 19-Mar T 19 21-Mar Th Quiz 2 26-Mar T Spring Break 28-Mar Th Spring Break 20 2-Apr T Balanced Trees Ch. 9.9--9.10 Assignment 5 Due Mon. 21 4-Apr Th 22 9-Apr T Graphs Ch. 10 23 11-Apr Th 24 16-Apr T Assignment 6 Due Mon. 25 18-Apr Th 26 23-Apr T Finite Automata Quiz 3 27 25-Apr Th 28 30-Apr T Advanced Topics Assignment 7 Due Mon. 29 2-May Th Review
After completing the course, students should have gained a firm grounding in the following:
There will also be TAs or other course staff available in the Wean 5th floor clusters on Sunday and Monday evenings before assignments are due to help with frustrating C problems, questions about the course, the meaning of life, or whatever.
Assignments will typically consist of a programming part and often a written part as well. Both are to be handed in electronically. The deadline will typically be Monday night at 11:59PM. Late assignments will be accepted with a 20 point penalty up until 8:30AM Wednesday. You may not hand in part of an assigment on-time and part of it late. More information on electronic handin procedures is in Section 8 and explicit instructions will be given on each homework as well.
The grade on the programming part of an assignment will be broken down into two parts:
Not Cheating:
Cheating:
Because we are grading on a curve, to be fair to all students we must enforce a strict policy with respect to cheating. Programs that are identical or exhibit suspicious similarities will be automatically flagged, and students will be asked to explain how such similarities came about and how their programs work. The penalty for cheating will depend on the severity of the offense and the student's past record in this regard. At the very least the student will be given a score of 0 for the assignment; failing the course outright (or worse!) is a distinct possibility as well.
To help prevent cheating, you should read-protect
the directory in which you develop your assignments (if you
work on an Andrew machine). To protect a directory named,
for example, 211progs, you would type the command
fs sa 211progs username all -clear
where username is your Andrew userID. Please read-protect any directories in which you develop code for 15-211.
Programming: We will be using the Objectcenter environment for writing C++ programs (see the Objectcenter tutorial). With very few exceptions, Ansi C programs are legal C++ programs. We will teach several C++ constructs that are not part of C, that serve the purposes of the course. You are allowed to use C++ features not taught in class in your programs, as long as they make your program simpler or more understandable (C++ has many constructs that can easily make a program less understandable; please don't throw them in just to seem more impressive).
You may develop your code using whatever compiler you want, and on whatever machine you want. However, your final program must be a legal C++ program that runs in Objectcenter on the Andrew workstation (or, equivalently, compiles using the ``CC'' compiler that Objectcenter uses), or compiles using g++, the GNU C++ compiler. You are free to use g++ if you prefer it to Objectcenter, but you will have to figure out how to compile using g++ on your own.
Electronic Hand-in: Assignments will typically consist of a programming part and a written part. Both parts are to be handed in electronically. To hand in an assignment, simply copy the appropriate files into your ``handin'' directory: /afs/andrew/scs/cs/15-211/handin/userid
where userid is your Andrew user ID, (e.g., st00).
If there are written exercises, you should put your solutions in a plain text file.
If the programming part of your handin does not work correctly, you should create a file called bugreport, which should be copied into the handin directory along with your code. The purpose of bugreport is for you to describe what problems your program has, and what might be the causes for them. This will help the graders give you partial credit, and it is to your advantage to hand this file in. In particular, if your program only works partially, or you have some idea what needs to be fixed, or where the bug(s) are, say so!! It will help establish to the grader that you understand what's going on, what the problems are, and why you should get at least partial credit for your program.
At each of the deadline times for an assignment, a program will scan through your handin directories, scooping up your files. You will receive email confirmation of the files found sometime after the handin deadline.
If you wish to hand in late, you must make certain your handin directory has no files in it at the regular handin time (and for a few more hours while collection is taking place). If there is even a single file present at this time, the system will treat that as your handin, and will ignore any late-handins. To repeat: you are only allowed to submit your file(s) for collection once (i.e. whatever is in the handin directory at the collection time is what you've handed in). Up until the handin time, you can copy new versions of your file(s) into your handin directory as many times as you want.
Only you plus the teaching and grading staff have access to your handin directory. You must be logged in under your Andrew user ID to get access to your directory.
Getting handouts: If you miss a handout in class, you can get it electronically from /afs/andrew/scs/cs/15-211/handouts. Make sure you know how to print out PostScript documents before printing them. You can also get handouts and other information from our web page at /afs/andrew/scs/cs/15-211/www/home.html.
Communicating:
For urgent communication with the teaching staff, it is best to send electronic mail to the addresses on the first page of this document. We have also set up two bulletin boards for this class, cmu.cs.class.cs211.announce and cmu.cs.class.cs211.discuss.
We ask that students refrain from insulting anyone on the bulletin board.
Since the teaching staff for this class is large, you might wonder who you should see about what. Here is some help.
We hope you will enjoy the course, and the staff is always glad to hear your comments or suggestions.
Last modified by
Avrim Blum