Computer Science C343 , A594: Data Structures, Fall 2007

General Information
Course Content
Textbooks

Communication
Participation
Quizzes and Exams
Grading
Programming Projects
Emacs
Course Evaluation

Useful Links
Miscellaneous

General Information

Professor

David S. Wise, Email
Office hours:

10:00am-11:00am Tuesday,
9:00am-10:00am Wednesday,
and by appointment.

Lindley Hall 330H; 855-4866.

Associate Instructor

Jay Powell, Email
Office hours:

12:45n-3:45pm Monday, LH330I;
9:00am-12:00n Tuesday;
and by appointment.

Lindley Hall 330I; 855-3804.

Undergraduate Instructor

Brad Snyder, Email
Office hours:

9:00am-11:00am Monday; LH330;
3:00pm-5:00pm Tuesday;
10-11am Friday;
and by appointment.

Lindley Hall 330 (outer).

Prerequisite C212, and corequisite C241 and (recommended) C335; or consent of instructor.

Computer Science C212: Introduction to Computer Science.

Computer Science C241: Discrete Structures for Computer Science.

Computer Science C335: Computer Structures.

Lecture:

Section 15492, 15438: MW, 4:00 - 5:15pm, LH 102.

Discussion sections

Section 15493, 15440: R, 9:05 - 9:55am, LH 019, Powell

Section 15494, 15439: R, 4:00 - 4:50pm, Library 033, Powell

Textbooks

Required Text

Lewis and Dennenberg, Data Structures and Their Algorithms, Reading, MA: Addison Wesley (1991, reprinted 1999).


Try to get a 1996 or later printing.
Some older Harper Collins editions have irritating errors.

The 1999 printing is published by Addison Wesley.

Required Reference (Choose one)

Brian Kernighan and Dennis Ritchie, The C Programming Language, Upper Saddle River, NJ: Prentice Hall PTR, 2nd edition (1988).

Samuel P. Harbison, III, and Guy L. Steele, Jr. C, A Reference Manual, Fifth Edition, Upper Saddle River, NJ: Prentice Hall (2002).
Either of these is a reference book that you will probably keep forever. If you are buying anew, consider well the second because it covers C99, important for system and parallel programming.

Other References

D. L. Knuth, Fundamental Algorithms, The Art of Computer Programming I, 3rd ed., Addison Wesley, 1997.

Career Day

is September 10, barely two weeks away. If you are an upperclassman (and all C343 students should be) and In Computer Science, run, do not walk, to the Informatics Placement Office (also to the College Placement office if in COaS) to get enrolled for the events of that week.

Communication

On individual or immediate matters, contact me or an associate instructor via email.

Noticing the wording above, you might conclude that I do not want to communicate. Wrong! I very much like to talk to students after class and in my office, but I find email awkward for technical discussions.
If you have a personal emergency, by all means send me email. If you want to propose an appointment outside office hours, email is fine. If more office hours are necessary, I'll move mine or post more.

Course Content

A detailed course outline, with week-by-week course schedule, is available.

This course is an introduction to application development in the Unix environment using the C programming language. C is more rudimentary than Java or C++ (under which it lives) knowledge of C++ or Java will make things awfully easy - except when it doesn't. One impact is that if you know C++, then you know C. Unfortunately, the C compiler is not way as restrictive as are other languages, and so it is easier to write code that will compile but won't run (or will run and do something predictable but entirely unexpected!)

We will cover the following topics, give or take one.

Abstract Data Types;
Linear allocation, linked allocation;
Handy AVAIL.c and AVAIL.h files;
Linear structures, stack, queues with a queue.c and queue.h files , dequeues;
Circular linking, Double linking, Header cells;
Classic algorithms illustrating good use of these structures;

Topological sort.

Trees, Binary trees, Naturally corresponding binary trees;
Tree traversal: preorder; inorder; postorder, triple order.
Threading of trees: inorder, level order;
Arrays: vectors, matrices, sparse matrices, strings;
Frequency-sensitive codes: Huffman and Lempel-Ziv encoding. A useful slide
Searching Knuth, Morris, Pratt and Boyer-Moore string search. List search.
Storage management: reference counting, garbage collection;
Searching trees: AVL trees, B-trees;
Warshall's algorithm .
Hash tables;
Greedy algorithms.
Application "in the rough." (How to tell the forest from the trees.)

COBOL data structure

Floyd's Hare 'n Tortise algorithm.

Grading

Grades are calculated as follows:

In-class tests 48%
Participation (including end-of-lecture pop quizzes) 4%
Programming Assignments 48%

Note: You must pass the final exam to pass the course!

Participation

Participation in the class can take many forms: attendance at lectures and discussions, asking and answering questions posed in class and on the newsgroup, and participating in group activities during lecture. In addition, there may be homework problems assigned in lecture that will be due the following lecture.

Quizzes and Exams

There will be two 30-minute quizzes, one 75-minute tests, and a two-hour final exam. They will be weighted roughly 50:100:200 for a total of 400 points, but (if, for instance, one turns out to be inordinately difficult) I reserve the right to tune these weights. The exams are subjective (written paragraphs, code) mostly, and it is difficult to assure that one point on the quiz is the same value as another point on the final exam.

Informatics Career Fair is September 10.
Quiz: September 24. Here is a sample Quiz 1 from 1998.
October 15, Midterm Test
November 14 or 19, Second Quiz
December 12, Final Examination (2:45pm - 4:45pm) Here is the final exam from 1996 in PDF

UNIX and Emacs

This course will use C as a programming languages. All programs must run with the C system installed as GNU's gcc under Linux.

Burrow(?) (LH004, 016) access has been requested for all enrolled students. You are welcome to use some other machine or environment (such as C++), but you will get no pity for "It worked fine on my machine at home" stories. If it doesn't work on burrow Linux, then as far as grading is concerned it never worked.

We recommend Emacs as an editor. (A good alternative - -if you already know it - is vi.) It is free, powerful, and easy to learn. If, for some reason, you have never used Emacs, never fear; it has a very nice built-in tutorial. To see it, type emacs at a nations prompt. (If you are working through telnet rather than at an X terminal, type emacs -nw instead.) Once inside Emacs, read what's on the screen before pressing any keys. The only two commands you absolutely need to remember are:

Ctrl-h t to launch the tutorial
Ctrl-x Ctrl-c to exit

If you have trouble with this, contact an AI immediately. Emacs is a basic tool for this course, and you will quickly fall behind if you are not comfortable with it. Don't worry about mastering every Emacs command; that would be impossible. Learn enough to get by, and watch the newsgroup (and this space) for more hints and tricks.

Hints and Tricks

If you develop your code on non-Unix machines, be sure to test it on the burrow. A file AddingMachine.c that works fine at home might get uploaded as addingmachine.c, which the loader/compiler won't like. Renaming the file again locally will be necessary to restore upper case.
- mv addingmachine.c AddingMachine.c

Programming Projects

This is a very important component to the course. There will be a programming assignment due almost every week on Tuesday 11:59pm. You will notice that these are structured into threads, and solving an early problem in the stream is necessary to easy solutions to the later ones. Do not fall behind!

You will submit your source code electronically using the. Vincent program. This program does not compile, run, debug, or test your code (that's your job); it merely saves your file in a convenient location so your AI can grade it later.

Programs will be judged on correctness, completeness, efficiency, generality, and aesthetics. Programs with no modules that compile will earn zero points.

Program descriptions will appear below as they are assigned. In general, solutions to the programming projects will not be supplied.

Programs are due by 11:59pm according to the system clock.

Assignments

Project 0 due Tuesday September 4 at 11:59pm.
Project 1: 4-banger calculator due Tuesday September 11 at 11:59pm.
Project 2: Linked Stacks and Queues due Tuesday September 18 at 11:59pm.
Project 3: Expression Calculator due Tuesday September 25 at 11:59pm. And a p3solution.tar with some test data .
Project 4: Cousins due Tuesday October 2 at 11:59pm.
Project 5: Earthworms' Children due Tuesday October 9 at 11:59pm.
Project 6: Trinomial Addition, Subtraction and Negation due Tuesday October 23 at 11:59pm.
Here are some commented test cases, which you will need to edit (in obvious ways) before using.
Project 7: Felines' Relatives due Tuesday October 30 at 11:59pm. Jay offers some test data. Brad offers his test cases (and its picture ) that he used to grade this assignment.
Project 8: Garbage Collection due Tuesday November 13 at 11:59pm. Jay offers some test data.
Optional Project 9: Derivatives due Wednesday November 22 at 11:59pm.
Project 10: Cats Have Names due Tuesday December 4 at 11:59pm.

Course Evaluations

Course evaluations will happen, but will be old-technology. (We have a nice on-line system, but not enough students bothered to use it. So we are back to paper.)

Other Random, Useful Links

How to use Vincent.
A reference card for the emacs editor.
A reference card for the vi editor.
A tutorial on UNIX.
A tutorial on make.
A useful makefile.
A tutorial on gdb. And a quick reference card
Indiana University Computer Science Department Home Page
The ACM Homepage
How to join ACM cheap!
Exposition on Boyer-Moore string search
Slides of Morton indexing and Ahnentafel indexing of matrices.

Miscellaneous

Incompletes are given only because of an unforeseen emergency that is preceded by diligent work, not for a pattern of weak performance. No student will be allowed to do ``extra work'' to raise his final grade or to make up missing work. The last day (until 4 p.m.) to withdraw with an automatic W is Wednesday, October 25.
Programs are due on the announced date, because solutions may be discussed immediately thereafter; late assignments would be accepted only under the conditions similar to what could justify an Incomplete. All grades become final one week after the material is returned to you. If there is a foreseeable medical, personal, or professional reason requiring you to miss a test, do let us know in advance and in writing.
Of course, we encourage discussion and debates over the course material, but you are expected to complete all work independently. Joint work (defined as pen hitting paper or fingers hitting keys) is not permitted. Similarly, we encourage you to use libraries both of books and of computer programs but, whenever you use archival or other borrowed material, you must cite the source completely. (Not only is this practice ethical, but a citation to the literature is often the most helpful and longest-lived documentation for a program.)
Read the Computer Science Department's Statement on Academic Integrity to be sure you understand the rules under which CS courses operate. "The work of others that is submitted and appropriately acknowledged is never, of itself, cheating; but it may not earn you any credit for the assignment" either.