CS 306 - Computer Algorithms II

Fall 2007


They are not heaps, of course, because it makes no sense to talk of a heap of numbers, and yet the numbers 1 through 5 form a perfectly acceptable set - {1, 2, 3, 4, 5}. Still less are heaps sets. A heap of sand does not yield a set of sand. The heaps belong off with the mounds, the piles, the stacks, the masses, and the batches; the sets are otherwise—remote, detached, abstract.

David Berlinski, The Advent of the Algorithm

Table of Contents

Course Description

This is the second of two courses on computer algorithms and data structures; see the CS 306 entry in the course catalog for the formal description of the course.

The prerequisite for this class is CS 305. In particular, from the textbook for this class, you are assumed to be familiar with the contents of chapters 1 through 8, 11, sections 12.1 through 12.6, and appendices C and D.

The course is divided into three three-week sections and one six-week section; see the syllabus for details.

The class meets in Howard Hall C1 (third floor) on Tuesdays and Thursdays, 6:00 p.m. to 7:50 p.m. There's no class on Thanksgiving, Thursday, 22 November.

Objectives

The course objective is to extend and exercise your algorithm design and implementation knowledge in three areas:

Instructor

R. Clayton, rclayton@monmouth.edu. Office hours are from 5 to 6 p.m. on Tuesdays and Thursdays in HH C1; see the schedule for details.

Grading

The usual grade ranges are in effect:
95 A
90 A-<95
86.6B+<90
83.3B <86.6
80 B-<83.3
76.6C+<80
73.3C <76.6
70 C-<73.3
60 D<70
F<60
All grades are kept with one digit of precision to the right of the decimal point and 0.05 rounded up. No grades are adjusted to a curve; that means, for example, that 89.9 is always a B+, never an A-.

Final Grade

The final grade is the weighted sum of the test-grade average and the assignment-grade average with the weights

    45%test grades
    45%assignment grades
    10%presentation grade

The test- and assignment-grade averages are straight, unweighted averages.

Mid-term grades are the straight, unweighted averages of whatever assignment and quiz grades have accumulated by the mid-term grade deadline (Tuesday, 23 October). A presentation grade, assuming it exists by the deadline, provides 10% of the mid-term grade with the other grades providing the rest; otherwise the other grades provide up the full amount.

Tests

There are four tests, one test for each of the sections; see the syllabus for the schedule. Tests are given in class, and are closed book with no notes; calculators and computers will not be necessary. The tests are cumulative, covering everything taught up to and including the class before the test. Tests should take no more than an hour to complete, and are given in the first hour of class. Test answers will be made available off the syllabus. There are no mid-terms or finals.

Programming Assignments

There are four programming assignments, one for each of the sections; see the syllabus for details.

Problem Presentation

Each person in class will give a talk about a problem they've solved; see the problem-talk page for more details.

Media

Textbook

The textbook for this class is ADTs, Data Structures, and Problem Solving with C++ by Larry Nyhoff Prentice-Hall, 2004. An errata is available off Nyhoff's web page for the book.

E-Mail

Feel free to send e-mail to rclayton@monmouth.edu . Unless I warn you beforehand, I'll usually respond within a couple of hours during the usual work days; if I don't respond within a day, resend the message.

Mail relevant to the class are stored in a hyper-mail archive. If your message is of general interest to the class, I'll store it, suitably stripped of identification and along with my answer, in the archive.

Home page

If you're reading this on paper, you can find the class home page at http://www.monmouth.edu/rclayton/web-pages/f07-306/index.html. I'll make the class notes, assignments, and tests available off the syllabus; you should get in the habit of checking the syllabus regularly.

Policies

Assistance

People who need assistance or accommodations above and beyond what is usually provided in class should contact the University's ADA/504 coordinator to get those needs met. See the Disability Services page for more details.

Attendance

I have no class attendance policy; you may attend class or not as you see fit. However, I hold you responsible for knowing everything that goes on in class; "I wasn't in class for that." is not an acceptable excuse for a wrong answer, or for giving no answer at all.

My attendance policy applies only to lecture attendance; it does not apply to other kinds of attendance which may be required for the course. Repeated failures to meet the attendance expectations set for tests, meetings, projects, labs or other forms of course work will have a bad influence on your grade.

Monmouth University does have a class attendance policy, which you can find in the Academic Information chapter of the Student Handbook. To the extent that I need to keep the record straight, I will take attendance. Attendance lists, however, are entirely for the University's benefit; I will make no use of them in grading.

Cheating

I deal with suspected cheating by failing first and asking questions later. Although cheating has many forms, I generally consider cheating to be any attempt to claim someone else's work as your own; also, I consider both the provider and the user of the work guilty of cheating. See the chapters on Academic Information and the Student Code of Conduct in the Student Handbook for more details.

Complaining about Grades

I recognize and encourage a student's sacred right to complain about their grade. There are, however, a few rules under which such complaining should take place, and those students who don't follow the rules will be less successful in their complaints than those students who do follow the rules.

First, the only complaint that matters is that something got marked wrong when it was actually right. When you come to complain, be prepared to present, in explicit detail, what it is you did and why you think it's right.

Second, complaints about a particular test or assignment are only valid until the next test or assignment is due; after that point the book is permanently closed on all previous test or assignment grades.

Late Assignments

Assignments must be turned in by their due date; assignments turned in after their due date are late. You should contact me as soon as possible if you need to negotiate a due-date extension. The longer you wait to negotiate, the less likely it is you'll be successful; in particular, you have almost no chance of getting an extension if you try for one the day before the due date, and you have no chance of getting an extention on the due date.

A late assignment is penalized five points a day for each day it's late. I use a 24-hour clock running from midnight to midnight to measure days; note this means that an assignment handed in the day after it's due is penalized ten points: five for the day it was due and five for the next day.

Missing Tests

There may occasionally be a conflict between taking a test and doing something else, particularly among those working full time. If you're going to be out of town, or on jury duty, or whatever, on a test day, let me know beforehand and we'll discuss a make-up test.

A make-up test must be scheduled to be taken by the date of the test following the missed test (or the final exam if you miss the last test). If a missed test is not made up by the time of the next test, you get a zero for the missed test.

There will be only one make up given per missed test. If more than one person misses the same test, those people will have to coordinate among themselves to pick a mutually agreeable date for the make up.

Links

The NIST dictionary of algorithms and data structures; the Stony Brook repository of algorithms and data structures, with the associated book.

FreeTechBooks' list of on-line data structures and algorithm books.

Softpanorama's old but wide ranging link page for data structures and algorithms.

Algosort's link page to algorithm pages.

Algorithm search engines (as opposed to search-engine algorithms) in general (seems borken, 30 Aug 07), for Haskell, and in detail.


This page last modified on 7 November 2007.