15-211 Course Information, Spring 1996


1. Organization

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:

(The latter method works from an andrew workstation as well, but the former is preferred because it puts less load on the server.)

Course staff in Wean 5th clusters:
Sundays and Mondays before due dates, 8-10pm+

2. Textbooks

  1. T. A. Standish, Data Structures, Algorithms, and Software Principles in C, Addison-Wesley, 1995.

  2. I. Pohl, C++ for C Programmers, Benjamin Cummings, 1994.

3. Course Requirements

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:

Note: Out of the 10 assignments + quizzes, we will drop the lowest score. That is, we will drop either the lowest assignment or the lowest quiz, whichever is lower (but not both!)

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.

4. Recitations

Recitations are Monday and Wednesday. Recitations will cover new material, go through examples of material discussed in lecture, and discuss issues related to the current homework assignment.

5. Class Schedule

All reading assignments are from Standish. All assignments are due at 11:59pm on Monday night.


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

6. Objectives

The purpose of 211 is to give students a solid foundation in data structures and algorithms, plus an appreciation for good program design, especially the use of abstraction and modularity.

After completing the course, students should have gained a firm grounding in the following:

  1. C and C++ programming: functions, pointers, structures, classes, the memory model, recursion, debugging techniques, I/O, etc.
  2. Foundations of algorithms and data structures.
    • Problem formulation. Extracting a mathematical problem out of an application task.

    • Data structure selection. Organizing the program data for efficient problem solution.

    • Algorithm design. Finding an efficient and systematic method for solving the problem.

    • Algorithm analysis.
      • Methods of proving algorithm correctness.
      • Asymptotic analysis of the space and time required by a program.

  3. Principles of good programming practice.
    • Modularity. Dividing a program into separate components, each having clean and well defined interfaces.
    • Abstraction. Separating the functionality of program component from its internal construction.
    • Code Design. Methods for writing code that can be easily understood and extended.

  4. The functionality and implementation methods for standard data abstractions including: queues and stacks, trees, priority queues, dictionaries, and graphs.

  5. Several standard data structures such as: arrays, lists, trees (search trees, balanced trees), hash tables, and graph representations (adjacency lists and adjacency matrices).

  6. Standard computational problems such as sorting, searching and various graph problems.

  7. Several algorithmic methods including: divide-and-conquer, tree and graph traversal methods, greedy algorithms, dynamic programming and memoizing.

  8. The basics of finite automata.

7. Useful Information

7.1 Office hours and help in clusters

Each member of the course staff has office hours given on the first page of this document. If these times are not convenient for you, please feel free to send email to one of us to set up an appointment.

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.

7.2 Assignments and Quizzes

Assignments form a critical part of the course work. Experience has shown that concepts are best learned by applying them to example problems or by implementing them in computer programs. The quizzes will be based on the material learned in the homeworks, as well as on recent material covered in class.

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:

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.

Not Cheating:

Cheating:

Also it goes without saying that copying on quizzes or exams is 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.

8. Facilities

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.

announce
For official announcements about the class. Only course staff may post to this bulletin board.
discuss
For general discussion, particularly among members of the class. Post here if you need a clarification or if you are confused about some part of an assignment.

We ask that students refrain from insulting anyone on the bulletin board.

9. Who to See?

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
Wed Jan 17 12:33:13 EST 1996