CompSci 351: Data Structures & Algorithms--Fall 2008

John Boyland

Homepage http://www.cs.uwm.edu/classes/cs351
Please check here for answered questions for assignments or for schedule changes.


Instructor and TAs


Name Section Office Phone Hours
John Tang Boyland 401 EMS 925 6986 T 2-3pm, R 11am-noon, F 8:30-9:30am
Mohamed Elbendary 801 803 EMS E212   W 3-5pm
Wen Hu 804 EMS E212   M 10-11am

If you have email questions, please send to compsci-351@uwm.edu.

Introduction

CompSci 351 is a difficult course, but a rewarding one. It is a course on programming in which you learn by doing. Thus the course involves a lot of hands-on work in the computer lab. However, this course also emphasizes concepts and so written and oral explanations will be required.

Desired Outcomes

Students will be competent in object-oriented programming in C++, more specifically, they will be

Requirements

Students must have received a `C' or better in CompSci 251. This course assumes that you are familiar with and have mastered the material from CompSci 251. In particular, this class assumes students are

  1. able to write, compile and execute C++ programs in a UNIX environment;
  2. able to use and write simple makefiles;
  3. able to use control structures, including member functions and exceptions;
  4. able to use and implement overloaded operators;
  5. able to use standard datatypes including arrays, strings and vector;
  6. able to use and implement stream insertion extraction operators;
  7. able to define classes with information hiding (abstract data types ADTs);
  8. familiar with different kinds of testing;
  9. able to write black-box unit tests of simple ADTs;
  10. familiar with pointers.

Texts

The required textbook for the course is

Michael Main and Walter Savitch. Data Structures and Other Objects Using C++. Addison-Wesley. Either the second or third edition is acceptable.

Grading

The grade for the course will be computed from the following parts:

0%
Collaboration Quiz
You must pass a collaboration quiz in lecture.
0%
Pre-Test
You must pass a pre-test given during the first lab section.
40%
Exams
There will be two midterms each worth 10% and one final exam of 20% of the grade.
Exams are cumulative, a better score on a later exam replaces an lower score on an earlier exam.

39%
Homework
There will be a homework due every week (14 in all), partly programming and partly text. Each homework is due at 11:00 pm on Wednesdays. Late homework will not be accepted. Each homework is worth 3% of the grade. After all homeworks are graded, the lowest grade will be dropped. This policy is in place to give students flexibility in times of personal emergencies. Do not misuse it.

11%
Labs
There will be twelve or more lab assignments that should be done during lab. Each completed lab counts 1% of the total grade and the lowest lab scores will be dropped to get 11 scores. They are graded pass/fail, with partial credit given for an incomplete lab. With permission of your TA, you may complete a partially finished lab at later point if you run out of time; it is your responsibility to show the TA that the lab has been completed. Note that you must either be present during lab hours, or prearrange your absence with your TA to get any credit for the lab. Missed lab assignments cannot be made up.

10%
Quizzes
Over the course of the semester, there will be 12 (or more) graded quizzes during lecture. Quizzes are related to material covered during lectures. Each quiz counts 1% of the total grade and the ten best quiz scores will be counted. There is no way to make up a missed quiz.
Exceptions to these rules can be made only in extraordinary circumstances. Advance notice of a need for an exception should be given whenever possible.

Criteria

Programs and written assignments will be graded for correctness, suitability, style, clarity and practicality. Although we may provide solutions to some assignments, there are usually a wide variety of correct answers to any particular assignment.

Academic Honesty

All graded assignments must be your own work (your own words), but you may work with other people as long as you list their names prominently on the first page of the assignment, and/or in a comment at the top of the assignment, for example:

// Wendy Lee, Homework #6, CS 351
// I discussed this assignment with Sam White,
// and Pat Long.  We looked at each other's code notes, 
// but did not exchange the copies.
For this course, verbal communication and collaboration using non-code text or hand-written code is permitted, as long as it is properly documented. Documentation must also be made for help from anyone not in the course, such as a tutor, friend, or relative, and for information off the Web.

You may not make copies of assignments through email, disks, scanning or any other automatic copying technique, except where specifically indicated in an assignment. Similarly, you may not make xerographic copies of portions of homework, or give people print-outs of your programs. At the very least, you must write every word in your assignments. If you are unsure whether something is permitted, please check with an instructor or TA. If you turn in a program which is an electronic copy (or a minor variation of a copy) of other people's, then the source and people who give credit to the source will receive zero for the assignment, while those who do not give credit may be given an 'F' grade for the course. Do not send your programs by email to other people!

Whether or not you have permission of the other, submitting someone else's work as your own is plagiarism, a serious instance of academic misconduct. Everyone is responsible for learning the material themselves. Some of the assignments may be graded in person, especially in cases where the individual contribution to the assignment is not clear. If you are graded in person, you will be expected to demonstrate that you have mastered techniques used in the material you submitted.

Grade equivalents

All assignments will be assigned a numeric grade. Often, however, letter grades will be used. This table shows how these letter grades are converted into numeric values.

Letter Grade A+ A AB B BC C CD D DF F _
Equivalent Score 100 95 90 85 80 75 70 65 60 40 NA
A grade written _ is not yet available; it does not mean zero. A grade of I means there is some work the student has not yet done. If this work is not turned in, the grade may revert to a grade of zero.

Course Grades

At the end of the course, the numeric grade will be converted into a letter grade according to the following scale:

Letter Grade A A- B+ B B- C+ C C- D+ D D- F
Minimum Score 92 90 87 82 80 77 72 70 67 62 60 0
There is no curve, but the instructors reserve the right to increase a grade if they believe it would not reflect the student's mastery of the material. A grade can only be decreased for academic dishonesty.

Special Features of the Filesystem

All your work should be done in the AFS volume assigned to you:

/afs/cs.uwm.edu/users/classes/cs351/Section/PantherID.
You may wish to make a symbolic link from a UNIX acount to this directory. Before you can access this directory, you will need to authenticate yourself to AFS using Kerberos. This can be done using
/usr/afsws/bin/klog PantherID
and type your Kerberos password. You can omit naming the PantherID if your account has the same loginname. The kpasswd.uwmcs command in the same directory can be used to change your kerberos password.

The root directory of your volume has some special subdirectories:

OldFiles
The directory includes a copy of your volume taken at 1am. If you accidentally delete a file that you need, please look for a backup here before contacting lab staff.
homework
This directory has subdirectories for each homework assignment. This is where you place your assignment files. After the deadline, the directory for that homework will become read-only.
lab
This directory is to be used for lab assignments.
misc
This directory can be used for anything else associated with the course.
Grades
This is a symbolic link to a directory includes a file giving the grade for each assignment. The first line gives the numeric grade and the remainder of the file gives comments. The file summary lists all the scores and computes the weighted percentage.

Schedule


Date Topic Relevant reading
   
9/2 Container ADTs Ch. 2, 3
9/9 Pointers, Dynamic Arrays Ch. 4
9/16 Vectors, Using Iterators Lecture notes
9/23 Linked Lists Ch. 5
9/30 Doubly-Linked Lists, Midterm 1 Lecture notes
10/7 Templates, Writing Iterators, Nested Classes Ch. 6.1-6.2,6.5, 6.6
10/14 Stacks and Queues Ch. 7, 8
10/21 Binary Search Trees Ch. 10
10/28 Graphs Ch. 15
11/4 Hashing, Midterm 2 Ch. 12.2-12.4
11/11 Derived Classes and Inheritance Ch. 14.1-14.2
11/18 Virtual Member Functions, Hierarchies Ch. 14.3
11/25 Reading Code Lecture Notes
12/2 STL: containers and algorithms Ch. 6.3,6.4
12/9 Review  
12/18 Final Examination (10:00-12:00 noon)  

Examinations

Midterm 1
Thursday, October 2
Midterm 2
Thursday, November 6
Final
Thursday, December 18 (10:00am)

Notes

About this document


John Tang Boyland 2008-08-29