Date: Thu, 07 Nov 1996 19:23:52 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Thu, 31 Oct 1996 18:30:59 GMT Content-length: 20386 CS 367 - Lecture 2

CS 367-2
Introduction to Data Structures
Fall 1996

Course email address: cs367-2@cs.wisc.edu
Course home page: http://www.cs.wisc.edu/~cs367-2/cs367.html

INSTRUCTOR: Yannis Ioannidis
Office: 7357 Computer Sciences
Office hours: Tuesday 8:45-9:30 am / Thursday 8:45-9:30 am
Office phone: 263-7764
Email address: yannis@cs.wisc.edu
Home page: http://www.cs.wisc.edu/~yannis/yannis.html



Contents


News

Assignment 3

Assignment 3 is now ready.

Midterm Statistics

Some interesting exam statistics for Section 2: max: 98, min: 22, median: 78, mean: 77.92

Old Midterm

A sample old midterm is now available to help you in your preparation for our own midterm.

Assignment 2

Assignment 2 is now ready.

Notes on O-notation and Binary Search

The notes on O-notation and Binary Search are now available. If you want to print either one of them, open the File menu from the (Ghostview) window that shows you the document, and choose the ``Print...'' menu item.

Women In Computer Science

Some female faculty, graduate students, and undergraduates have formed a group called WICS (Women In Computer Science). One of the group's goals is to encourage more women to become computer science majors. So if there are any women in this class who would like to talk to someone about majoring in computer science, or doing graduate studies in computer science, or if there are any women who would like some extra help with their classwork, they should see Suzan (a computer science grad student) during her office hours or email her to make an appointment. Suzan's e-mail address is: stodder@cs.wisc.edu and her office hours are Tuesday & Thursday 1:30-2:30 in room 1345.

Assignment 1

Assignment 1 is now ready.

Out of Town

The first week of classes I will be out of town at the VLDB Conference. Jim Larus will give the lectures for me. I will be in class September 10th.

Teaching Assistants

Both people listed below are teaching assistants (TAs) for the course. They will be grading your homework assigments and will be happy to answer questions about the assignments, or any other aspect of the course that is giving you trouble. Note that TAs are not assigned to specific sections.

Chin Tang Chin
Office: 3310 Computer Sciences
Office hours: Monday 9:30-10:30am / Tuesday 2:30-3:30pm / Friday 9:30-10:30am
Office phone: 262-1721
Email address: cchin@cs.wisc.edu
Home page: http://www.cs.wisc.edu/~cchin/cchin.html

Wei Zhang
Office: 1343 Computer Sciences
Office hours: Wednesday 10:00-11:00am / Thursday 9:00-10:00am / Sunday 3:00-4:00pm
Office phone: 262-5596
Email address: weiz@cs.wisc.edu
Home page: http://www.cs.wisc.edu/~weiz/weiz.html

Lecture Information

Lecture: 9:30 - 10:45 Tuesday and Thursday
1325 Computer Sciences and Statistics

The C++ Language

CS 367 will be taught using the C++ programming language, and you will be required to do your programming assignments in C++. We didn't choose C++ just to make your life more difficult. Most people who become fluent in C++ think it is far superior to C or Pascal; the use of C++ is growing tremendously in the field and the odds are that if you ever have to write another program after this course ends, you will be able to write it in C++. (The same statement is not true about Pascal. C is also widely available, but after an initial startup period you will be more productive in C++ than in C.) If you go on to take more computer science courses, with few exceptions you will be required to use C++ in those courses.

Text

The text book for this course is Data Abstraction and Problem Solving with C++: Walls and Mirrors by Frank M. Carrano (ISBN # 0-8053-1226-9). This is a well-written text that covers most (but not all) of the material in this course. It also includes a lot about C++, so a separate text for the language is not necessary. For my lectures I will often (but not always) be following CS 367 Lecture Notes - Fall 1993 by David J. DeWitt. These notes are actually considerably more complete that simple lecture notes, but they are still short of a true text book (there is very little narrative text, no exercises, etc.) As a recommended additional source, you may want to purchase these notes, which are available from the DoIT documentation desk near the Dayton Street entrance of the Computer Sciences building (1210 W. Dayton St).

If this is the first experience with Unix for you, you will need some information about activating your account, logging in, creating, editing, and manipulating files, and compiling, running, and debugging programs. The handout CS 1000, available from the DoIT information desk (where the DeWitt notes are available), contains all the key information. You will find it invaluable. See also the help section below.

As I mentioned above, the lectures will often follow the DeWitt notes, although I may supplement them with a few handouts during the course of the semester. Nonetheless, You are responsible for all material covered in lecture! The exams will be based on the lecture material, reading assignments in the notes, and the course assignments.

Grading

There will be one or two evening exams during the course of the semester, a final exam and five programming assignments. The exams will determine 50% of the final grade (with approximately equal weight for each one), and the programming assignments will count for 10% each.

Exams

Exam 1
Tuesday, October 22nd, 7:15pm-9:15pm, 1351 Chemistry.
Exam 2
TBA
Final Exam
Wednesday, December 18th, 5:05pm-7:05pm, place TBA

Course Schedule

The following is the list of topics that will be covered in this course. A more detailed scheduled will be provided later. semester.
TOPIC                           DEWITT'S        
                                NOTES           WALLS AND MIRRORS
===========================================================================

Introduction, Administration                    1-42 (general familiarity)
Basic stuff of C++              lecture #2      101-135, App A, App C
---------------------------------------------------------------------------
Functions                       lecture #3      App A
Pointers                        lecture #4      141-150, App A
---------------------------------------------------------------------------
Records & dynamic storage       lecture #5      141-150, App A
Lists                           lecture #6      150-177
---------------------------------------------------------------------------
Lists                           lecture #6      150-177
Binary Search and O notation                     83- 86, 393-405
---------------------------------------------------------------------------
Advanced Lists                  lecture #7      177-189
Advanced Lists                  lecture #7      177-189
---------------------------------------------------------------------------
Stacks                          lecture #8      249-295
Queues                          lecture #9      307-344
---------------------------------------------------------------------------
Hashing                         lecture #10     591-608
Hashing                         lecture #10     591-608
---------------------------------------------------------------------------
Recursion  (Evening Exam)       lecture #11      50- 93, 203-238
Trees                           lecture #12     439-468, 501-502
---------------------------------------------------------------------------
Trees                           lecture #12     439-468, 501-502
Binary Trees - Sort & Search    lecture #13     468-500
---------------------------------------------------------------------------
AVL Trees					587-590
AVL Trees					587-590
---------------------------------------------------------------------------
Graphs                          lecture #16	620-646
Graphs                          lecture #16	620-646
---------------------------------------------------------------------------
Graphs                          lecture #16	620-646
Graphs                          lecture #16	620-646
---------------------------------------------------------------------------
Sorting                         lecture #17     405-432
THANKSGIVING
---------------------------------------------------------------------------
Sorting                         lecture #17     405-432
Sorting                         lecture #17     405-432
---------------------------------------------------------------------------
To be announced

Assignment 0

This is an absolute necessity to get a grade other than F! Bring in a photograph of you. It should not be your picture from your 1st birthday, nor should it be the one from that boy/girl scout trip in the summer of 1984. Other than that, it can be color or black-and-white, any size, etc. No grade will be given without a photo!

Programming Assignments

Proficiency in a programming language (Pascal, C, C++, or FORTRAN) at the introductory level is assumed; the equivalent UW-Madison prerequisite course is CS 302.

Assignments must be done in C++ on the designated machines. These are in the machine rooms on the first floor of the CS building. I encourage you to use these machines.

If you prefer to use a home computer, you may do so, with certain restrictions: You must have a C++ compiler on your home machine; you must log on to your university account often to read email and get copies of data files; finally, we will require that you turn in your C++ program electronically (via email) so if you work at home you must make provisions to download your programs to your university account and to make sure that they compile and run with the g++ compiler on the SPARCstations.

I often use electronic mail to notify students of changes in assignments, hints for programs, etc. I assume that you will read all electronic mail that I send.

Late Policy

No late assignment will be accepted. Assignments must be turned in exactly when they are due. In order to avoid lateness caused by machine loads, coincident due dates for several classes, etc., simply be sure to get started right away on each assignment. Things are certain to go wrong now and then, so don't wait until the last minute to start. Any exceptions must be approved by me, and you will need a very good excuse. If you get into trouble, see me as soon as possible.

Cheating

The Computer Science department takes a very hard line stance on cheating. You are welcome to communicate with each other on design of algorithms and data structures, but there is to be no sharing of code.

You are also expected to learn, understand, and obey the Computer Systems Lab Policies governing your computer accounts.

Help

If you are having problems with the course work or programs, please let me know as early in the semester as possible.

Office Hours Policies

If you need help debugging a program, the best way to get help is to visit any one of the CS 367 TA's during his office hours, taking along a current hard copy of your program. My office hours are intended as a time for me to re-explain concepts that I have presented in class but about which you are still confused, or to answer your specific questions about course material. I encourage you to use email as a reliable way to contact me about any problems; I read and respond to email several times daily, almost every day of the week.

Program Grading

Programs are graded on all of the following criteria.
  1. Correctness: The program should behave correctly/normally on typical input. The program should behave as stated in the project specifications.
  2. Clarity: The program should be easy to read and understand. (See the notes on style below for more information about clarity).
  3. Robustness: Correct behavior in extreme or unusual situations. The program should handle such situations in a reasonable and logical manner (that is, it should not simply blow up).
  4. Quality of test data: The test data for the program should demonstrate all facets of the program's capabilities, including unusual cases.
  5. Efficiency: Avoid unnecessarily inefficient algorithms or constructs. However, efficiency should never be pursued at the expense of clarity.
  6. Modularity: The program should be modular and should make effective use of parameters.
  7. Completeness: You should incorporate all information into your program; there should be no need for any sort of extra (paper) documentation.
  8. Generality: The program should be as general as possible, subject to consideration of efficiency and clarity. You should avoid arbitrary limitations (such as a bound on the size or complexity of the input) whenever possible. When limitations are necessary, they should be expressed as defined constants near the top of the program so that they can be easily changed. The only numeric literals that should appear in your program are those values not very likely to change (such as 0, 1, or 3.1415926535).

Style

  1. Use meaningful identifier names.
  2. Use a consistent naming scheme for identifier names. A suggested convention is as follows
  3. Do not put multiple statements on a single line.
  4. Skip lines between functional groups of code.
  5. Use a clear and consistent indentation style (see the DeWitt notes for a suggested style).

External Documentation

This should be included as a long comment at the beginning of your program. It is addressed to both the typical user and to someone who wants to know superficially how the program works: Information included in the assignment about the problem description need not be repeated, but may be briefly summarized for the first point above. A statement referring the user to the assignment document is then sufficient. Note that this only applies to the problem description!

Internal Documentation

There are four main types of internal documentation:

Using Unix and Vi

Many people working with UNIX for the first time will find that it takes some time to become comfortable with it (this is particularly true if your only previous programming experience is with Pascal using MacPascal on a MacIntosh.) I strongly urge you to put in the time early in the semester to become comfortable with Unix. While this time may be painful, it is time well spent. Also, you may wish to attend a UNIX tutorial. They will be held in rooms 1240 Comp Sci in two sessions on each of the following days: TBA You will want to pick up a copy of CS 1000 before you go.

The Program Development Cycle

The program development cycle in a UNIX environment is:

for (;;) {
    edit your program             // %vi program.c
    compile your program          // %g++ -Wall -g  program.c
    if (there are compilation errors)
        continue;
    run your program              // %a.out < inputfile > outputfile
    look at your output           // %vi outputfile
                                  // or %more outputfile
    if (there are no errors)
        break;
    if (you are too tired to continue) {
	print a listing to take home
                 // pr program.c inputfile outputfile | lpr
	goto home
    }
    debug the program
                                  // gdb a.out
                                  // run
                                  // ...
                                  // quit
}
you're done!  turn in the result
		 // submission instruction to be given out later

yannis@cs.wisc.edu
Mon Aug 19 17:28:14 CDT 1996