Computer Science Department, U.C. Santa Cruz

CMPS-012B: Introduction to Data Structures
Course Syllabus - Spring 1997

Facts which at first seem improbable will, even on scant explanation, drop the cloak which has hidden them and stand forth in naked and simple beauty.
--- Galileo Galilei

General Information


Course Description and Prerequisites

He knew the things that were and the things that would be and the things that had been before.
--- Homer, The Iliad

Description (from the University Catalog):

Teaches students to implement common data structures and the associated algorithms with each data structure, through progressively difficult exercises. Topics include big "O" notation; pointers, recursion (induction), and dynamic allocation; linked lists and list processing; stacks, queues, binary trees and binary search trees; simple sorting techniques and simple search techniques. ANSI C programming is introduced.

Prerequisites

Course 12A. Prior experience with Athena/UNIX.

Outline

Approximately one week each will be spent on these topics (readings in parentheses). Details are subject to minor changes as we progress through the quarter.

  1. Introduction to Unix. The file system. Shell commands. Hodges, ch. 3-5. Introduction to Athena (on-line CATS tutorials at http://www2.ucsc.edu/cats/sc/handouts/unix/index.shtml). Introduction to C: statements and functions, arrays, structures, and files. Hodges, ch. 8-10. Kruse, appendix. C.
  2. Using gcc (the GNU C compiler). Programming principles. Style, identifier names, documentation and format. Refinement and modularity. Lists: specifications for a data structure. Coding. Kruse, ch. 1-2.
  3. Stacks. Array and list implementations. Recursion. Function call stack. The ``Towers of Hanoi'' example. Tail recursion. Kruse, ch. 3.
  4. Queues. Array and list implementations. Circular queues. Pointers and linked lists. Dynamic memory allocation, malloc(), and free(). Nodes, type declarations, and typedef. Abstract data types. Preconditions, postconditions, and invariants. Kruse, ch. 4.
  5. Generalized lists. Linked implementation. Searching and inserting into a list. Doubly linked lists. Strings in C and the null ('\0') plug. Array implementation of lists. Kruse, ch. 5.
  6. Searching. Keys and data. Sequential search. Binary search. Running time of an algorithm. Big-O notation. Analysis and bounds of algorithms. Kruse, ch. 6.
  7. Sorting. Insertion and selection sorts, array and list versions, Running time. Merge sort for linked lists. Quicksort, its running time, and choice of a pivot. Heaps and heap sort. Kruse, ch. 7.
  8. Tables and information retrieval. Multidimensional arrays. Row and column major ordering. Hash tables. Abstract data type Table. Hashing functions and hash tables. Kruse, ch. 8.6-8.8.
  9. Binary trees. Prefix, infix, and postfix traversals. Expression trees. Binary search trees. Insertion and deletion. Kruse, ch. 9.1-9.4.
  10. Bitstring implementation of sets. Miscellaneous other topics, depending on time.


On-Line Information

The class news group ucsc.class.cmps012b will be used for important announcements and information, and is required reading. You may post your own questions and comments to this news group. Postings to this group can be read using any news reader program, such as netscape or rn. If your web browser supports news groups and is configured properly, you can read the news group by clicking on the news group name above.

A World-Wide-Web page with class information (including this syllabus, class notes and assignments) can also be found at http://www.cse.ucsc.edu/classes/cmps012b.

Extensive CATS documentation (including information on Unix and Athena) is online at http://www2.ucsc.edu/cats/sc/handouts.


Attendance

Veni, vidi, vici. [I came, I saw, I conquered.]
--- Julius Caesar

Attendance at exams is, of course, required. Attendance at other class sessions is highly recommended; some classes may cover material beyond that in the book. Information in announcements made in class may not be available through other channels. If you miss a class, you should check the class web page for class notes and assignments.


Homework Assignments

For the things we have to learn before we can do them, we learn by doing them.
--- Aristotle

There will be approximately 5 or 6 homework assignments, which will usually involve writing a program. These assignments will provide an opportunity to use the material covered in class. All assignments must be submitted electronically on the CATS systems, so you must have a CATS/Athena account for this class. If you don't already have one, see the CATS web page "Registering for an account on Athena and ucscb" (http://www2.ucsc.edu/cats/sc/handouts/unix/register). The class homework locker is cmps012b.hwk. [Revised Apr. 14]

All assignments turned in must be your own work. You may discuss general methods to be used for an assignment with other students, and you may look at example code from books or on the web, but the specific program code or question answers handed in must be your work alone (otherwise, how are you ever going to learn to do this stuff?). You should be familiar with the section of the University undergraduate handbook, The Navigator (http://www.ucsc.edu/ucsc/navigator), regarding Academic Integrity.


Exams

It is this, it is this that oppresses my soul.
--- Lewis Carroll, The Hunting of the Snark

The exact times for exams will be announced in class and posted on the class web page. Exams will be "closed book," except that you will be allowed to bring one 8.5"x11" sheet of paper with any notes that you think will be useful; you may consult with classmates before class while preparing your notes sheet.


Due Dates, Rescheduling, and Late Policy

I wasted time, and now doth time waste me.
--- William Shakespeare, Richard II

Due Dates and Late Policy

All assignments must be submitted on-line to the class homework locker using the CATS submit program. Assignments turned in after approximately 8 a.m. of the day after they are due will not be accepted. A revised version of an assignment may be submitted at any time before this deadline, in which case it will replace your original submission.

Rescheduling

If you are unable to take an exam or complete an assignment at the scheduled time and wish to reschedule it, you must notify me as soon as possible. Rescheduling of exams and assignments will be possible only in exceptional circumstances. In case of illness, you should get a signed letter from a medical professional indicating that you were too ill to attend an exam and/or complete an assignment. Requests will be handled on a case-by-case basis.


Regrade Policy

Play it again, Sam.
--- never said by Humphrey Bogart in Casablanca

If you have questions about the grade you received on any assignment or exam, please contact me or one of the course staff as soon as possible. If you disagree with the assignment grade, you may ask to have it regraded. You should request a regrade as soon as possible after the item in question is returned to you. An item submitted for regrading may be regraded in its entirety, and may result in an increase, decrease, or no change in the grade. General information on University grading policies is available in the University undergraduate handbook, The Navigator (http://www.ucsc.edu/ucsc/navigator/), under the heading Evaluation of Performance.


Grading

Grades will be based on the following items, weighted as shown:

The class will be graded on a `curve'. In order to pass the course, you will need to do reasonably well on all three elements. The lowest grade homework assignment will be thrown out when computing the total assignment score.


CMPS012B Spring '97 pages maintained by Mike Goss <goss@cse.ucsc.edu>
This page last updated 04/14/97.