IS-2610 Data Structures

Thur 6:00-8:50 PM Room 404 LIS - 135 N. Bellefield

Sept 1 to Dec 15, 2005

Instructor: Art Wetzel

Office: 216A Mellon Institute (PSC/CMU)
Phone: 412-268-3912
Email: awetzel@psc.edu
Office Hours: by appointment
Class Web page: http://www.psc.edu/~awetzel/is2610.html

GSA: Jinghua Bao
Email: jib2+@pitt.edu

Required Text

Robert Sedgewick, Algorithms in C: Parts 1-4 Fundamentals Data Structures Sorting Searching Addison-Wesley 1998

Additional papers and handouts from class should all be considered as required reading.

Grading:

Examinations 50%
Assignments 50%

Prerequisites:

For this course I assume college level math skills and some previous programming experience. Ideally everyone would know C and have a working knowledge of the UNIX environment. Unfortunately, since this is not always the case, I will take a little time in the beginning of the term to provide some extra tutorial introduction to C and UNIX/Linux.

Goals:

The primary goal of this course is to provide an overview of the theory and practice surrounding the application of data structures to effective programming and computational problem solving in real world applications. This includes not only data representation but also algorithm design and performance analysis with proper consideration of computing hardware characteristics. Particular attention will be paid to those concepts which have broad applicability, have maintained their importance over a significant period of time, and are expected to maintain their importance into the future. We will use C as the primarly programming language because it is the most widely used and available programming language and because it lets us clearly expose the operation of the data structures we will be using rather than hiding them as encouraged by some other languages.

Course Content:

The course consists primarily of two components
(1) Underlying principles
(2) Implemetation methods

We will roughly follow the order of presentation of the text book at least initially. By the end of the term we should have covered about 2/3rds of the book, having skipped some of the specialized areas. This means we will try to keep up an average pace of one chapter per week.

There will be a strong interplay between theory and practice and a variety of presentation levels so that no one should become either lost or bored provided they do the readings and other work outside of class time. Special C programming and math skills will be reviewed as required. If you feel you need a supplemental C book I suggest you select one that fits your own level and style by going to a book store and spending a few minutes looking over the possibilities. From my point of view the best is still The C Programming Language by Kernighan and Ritchie. Both the 1st and 2nd editions are in print - the first being classical C and the second based on ANSI C.

General Class Issues:

All students must have a suitable UNIX/Linux/Cygwin account for C programming before the 2nd week of class. You should also check your email and the class web page regularly to let me to field your questions and to provide clarification and corrections to class and assignment issues.

There will generally be an assignment every week except for the week of an exam. This will result in 8 or 9 assignments. At the end of the term I will drop your lowest assignment score and average the others. This is indended to cover the usual sick days, travel and other circumstances. If you miss a week please DO NOT ask for a makup assignment as that is to be covered by the dropped score. The only exceptions would be due to extended illness or similar special emergency.

I keep a web page "http://www.psc.edu/~awetzel/is2610.html" where assignments, template programs, test files etc will be available. This is also where you should pick up the assignments if you miss a class. The majority of your programming should be done in the C/UNIX environment. For those who work on PCs away from PITT and who do not have a dial in or network capability you may consider using Linux on your own machine.

Unless I tell you otherwise, all assignment programs should emailed to "awetzel@psc.edu" with the Subject line "IS2610 Final assignment #N" where the N changes weekly from 1, 2, 3 etc. Also, make sure that the first line of your program includes your name. All assignments must be received in ON TIME in order to obtain a nonzero score since I will hand out my solution for class discussion on the due date! Be sure to turn in what ever you have even if its not working to get a reasonable partial credit. Make sure that all programs are in a form that I can recompile and run them. If an assignment asks for some particular computed results or written conclusions then please put that into your program source as a block comment. Sent your program as an attachment or as plain text and NOT html and do NOT send your compiled binaries.

Students are encouraged to cooperate in discussing solution strategies and in helping each other with mechanical aspects of editing and programming. However, each student's work should be uniquely their own. NO SOURCE CODES should be duplicated between students! Other that the templates that I provide everything that you program or write must pass through your own fingertips!

Readings from the texts will be supplemented by additional handouts which cover specific topics not included in the book. For the purpose of exams, all handouts are considered as required reading. The general philosophy of the lectures is based on the fact that you all have the books and can read them. Therefore, the lectures will not always repeat the same material. Usually the lectures/class discussions will provide clarifications/extensions to material in the texts, present alternative views to the texts or cover material which is not in the texts at all.

Policies:
Attendance is your responsibility. If you must miss class, get all handouts and assignments from other students or the class web page or email as soon as you can. Due dates will not be modified except in cases of medical or employment urgency. Get notes from another student.
Tests:
Each test will cover lectures, readings, and assignments from the weeks not covered on the previous exam. Unless stated explicitly otherwise, all material is eligible for testing. Makeup exams may be given only under emergency circumstances. If you know ahead of time that you must be away on the night of an exam, then you should arrange to take the exam early.

Academic Honesty:
It is okay to discuss problems and solutions with others. It is not okay to show someone your program, to copy someone elses work, or to copy solutions directly from other textbooks or materials. All work must pass through your own fingertips!!!
Program Grading:
Grading on programs will be on a 10 point scale based upon the following factors: