Data Structures & Algorithms
CS 305

Fall 2010


When we multiplied the surface area of our homes by the value of a square foot, we experienced a euphoria unequaled by almost any other: the pleasure principle of an algorithm.

Claudia Piñeiro, Thursday Night Widows, 2005

Table of Contents

Course Description

Introduction to the design, implementation, and use of elementary data types (list, stack, queue, binary tree); algorithms for sorting and searching informal complexity analysis. Prerequisites: Computer Science 176 and one of Mathematics 120, 130, or Computer Science 202.

The course is divided into five sections. See the syllabus for details.

The class meets on Wednesdays and Fridays in Howard Hall 216 (the SE conference room, formally known as B-1) from 1 p.m. to 2:50 p.m. Class starts on Wednesday, 8 September and ends on Wednesday, 15 December. There is no class on Friday, 26 November (there is class on Wednesday, 24 November). Tuesday, 9 November is the last day to withdraw from class with a W on your transcript.

Objectives

At the end of this course you should
  1. know some basic data structures and algorithms,
  2. be able to choose wisely among data structures and algorithms, and
  3. design and write code supporting data structures and algorithms well.

Instructor

R. Clayton, rclayton@monmouth.edu. Office hours are from noon to 1 p.m. on Wednesdays and Fridays in HH 318 (schedule).

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 quiz-grade average and the assignment-grade average with the weights

60%assignment grades
40%quiz grades

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

The mid-term grades.
The final grades.

Quizzes

There are four quizzes, one quiz for each section after the first section; see the syllabus for the schedule. Quizzes are given in class, and are closed book with no notes; calculators and computers will not be necessary. The quizzes are cumulative, covering everything taught up to and including the class before the quiz. Quizzes should take no more than an hour to complete, and are given in the first hour of class. Quiz answers will be made available off the syllabus.

There are no midterms or final exams. Mid-term grades are computed from the straight, unweighted average of what ever grades have accrued by the day mid-term grades are due (Tuesday, 26 October).

Programming Assignments

There are four programming assignments, one for each section after the first. Each assignment is as long as the section in which it is given; see the syllabus for details.

Media

Textbook

There are many data structures and algorithms textbooks, all more or less the same. Theres no assigned textbook for this course; instead, pick a textbook or two youre comfortable with. As a first cut, compare the books table of contents with the syllabus to make sure the topics mentioned in the syllabus appear in the table of contents. You can glean further advice from a small annotated bibliography of data structures and algorithms books.

Please do not interpret Theres no assigned textbook for this course to mean Great! I dont need a textbook. Absorbing everything you need to know from lectures wont be possible, not the least because there wont be time to cover everything in lectures. Working it out over a textbook or two will give you the time and space to learn what you need to know. In addition, the tests are written assuming knowledge found in basic data structures and algorithms textbooks.

This is a programming course, and youll be programming in Java. In addition, the course will cover (possibly) new Java features in just enough detail to get by in data structures and algorithms. You should have at hand at least one Java programming language book to help you recover the old details and pursue further the new details. The book from CS 175 and 176 should be fine. Also recommended are Core Java 2, Vol. 1 Fundamentals by Cay Horstmann and Gary Cornell, Sun Microsystems Press, 2008. and Java in a Nutshell by David Flanagan, OReilly Media, 2005.

E-Mail

Feel free to send e-mail to rclayton@monmouth.edu . Unless I warn you beforehand, Ill usually respond within a couple of hours during the usual work days; if I dont 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, Ill store it, suitably stripped of identification and along with my answer, in the archive.

Home page

If youre reading this on paper, you can find the class home page at http://www.monmouth.edu/rclayton/web-pages/f10-305/index.html ( http://tinyurl.com/mucs305f10h ). Ill make the class notes, assignments, and quizzes available off the syllabus ( http://tinyurl.com/mucs305f10s ); you should get in the habit of checking the syllabus regularly.

Podcasts

The lectures for this class will be recorded and podcast. Audio will be available on the syllabus and via an RSS feed.

Microblogging

Follow the course on identi.ca ( http://identi.ca/mucs305 ) or twitter ( http://twitter.com/mucs305 ). The same messages appear on both services.

Policies

Assistance

People who need assistance or accommodations above and beyond what is usually provided in class should contact the Universitys 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 wasnt 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 Universitys 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 elses 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 students sacred right to complain about their grade. There are, however, a few rules under which such complaining should take place, and those students who dont 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 its 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 youll 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 ten points a day for each day its 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 its 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 youre going to be out of town, or on jury duty, or whatever, on a test day, let me know beforehand and well 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

Learn data structures 'n' algorithms in the comfort of your home, courtesy of MIT. Theres also a more recent, non-video, advanced but still introductory version of the course.

The NIST dictionary of algorithms and data structures.

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

Softpanoramas old but wide ranging link page for data structures and algorithms.

Algosorts link page to algorithm pages.

The last time I taught this course.


This page last modified on 18 July 2010.

Creative
    Commons License