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
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.
7.3 Cheating and Collaboration
Certain forms of collaboration are beneficial for helping all involved
understand the material better and overcome small stumbling blocks.
Blatant copying of homeworks is not. What you hand in should be your
own work. The following are
guidelines on what collaboration on homeworks is authorized and what is
not.
Also it goes without saying that copying on quizzes or exams is cheating.
fs sa 211progs username all -clear