Course Syllabus: CMPS 12B

Introduction to Data Structures
Professor Tara Madhyastha (tara@soe.ucsc.edu)
Spring 2002

1. Course Information

This class meets T/TH 4-5:45 PM in Stevenson Academic 150.

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. Prerequisite: cmps012a. Prior experience with Unix is assumed.

Newsgroup

ucsc.class.cmps012b. This is required reading and should be a primary point (along with lab attendance) for asking questions and discussing course material.

Web Page

www.soe.ucsc.edu/classes/cmps012b/Spring02-02. I will post assignments to the web page, and the syllabus is available there.

Directory

/afs/cats.ucsc.edu/courses/cmps012b-tm/. The Examples subdirectory contains many examples.

Grades

The final grade in this course and your narrative evaluation will be based on:

 Final exam during exam week: 30%
Midterm exams in class: 2 @ 15% = 30%
Programming projects: 5 @ 8% = 40%

Thus, I will compute a weighted average of your grades as above. However, your final grade may be adjusted up or down based on your performance. In particular, you cannot pass the class if you don't make a solid attempt at all the programming projects or take all the exams. You cannot pass the class if you do not master the skills in the syllabus.

Instructor Contact Information

My office is 127 Baskin Center, and my phone number is 459-3285. Office hours are Tuesday 2-4pm.

TA Information
There are two TAs for this class: Enes Hastor (enes@cse.ucsc.edu) and Garima Tripathi (garima@cse.ucsc.edu). The TAs are graduate students responsible for grading exams and holding lab sessions.

Tutor Information
There are two tutors for this class: Leslie Clark (lesliec@cats) and Andrew Hale (andyhale@cats).. The tutors are undergraduate students responsible for helping with assignments and grading assignments.

2. Textbooks and References

The following textbooks will be useful during the course. The first is the formal text and the rest are for background reading.

1. Frank Carrano, Janet Prichard: Data Abstraction and Problem Solving with Java. Addison-Wesley, 2001, ISBN 0-201-70220-7. This is the required textbook.

 2. Mark Sobell: A Practical Guide to the Unix System, 3rd ed  Addison-Wesley, 1995, ISBN 0-8053-7565-1. This is background reading to ensure knowledge of Unix. Students who already have a good Unix textbook need not buy this one. However, at least one good Unix book is required reading for any Computer Science major.

 3. Tomasz Muldner: C for Java Programmers. Addison Wesley, 2000, ISBN 0-201-70279-7. To be used later in the course when C is introduced.

 4. The Java Tutorial. http://java.sun.com/docs/books/tutorial.

 5. Java 2 Platform, Standard Ed, v1.2.2 API . Important packages: java.lang, java.io, and java.util.

The following books are reference materials and are listed here as useful sources of information for the advanced programmer, but should not be considered as directly important to the course. A student whose budget is tight need not buy any of them.

 1. Ken Arnold, James Gosling, David Holmes: The Java Programming Language, 3rd ed. Addison-Wesley, 2000, ISBN 0-201-70433-1. Optional reading. A general description of Java. It will not be referred to directly.

 2. Al Kelley, Ira Pohl: A Book on C, 4th ed . Addison-Wesley, 1998, ISBN 0-201-18399-4. An introduction to C. Not directly related to course material, but reading it will bring a Java programmer up to speed with C.

 3. Gilad Bracha, James Gosling, Bill Joy, Guy Steele: The Java Language Specification, 2nd ed. Addison-Wesley, 2000, ISBN 0-201-31008-2. Not ordered for the bookstore. This is for language lawyers.

 4. Samuel Harbison, Guy Steele: C, a Reference Manual, 4th ed. Prentice-Hall, 1995, ISBN 0-13-326224-3. A general reference to the C language. Not readable as a text book, but contains answers to C language lawyering. Not required in order to pass the course. Also see: /afs/cats.ucsc.edu/courses/cmps112-tm/-Lang-Specs/C.standard/.

 5. Charlie McDowell: C for Java Programmers: a Primer. Bundled with Java by Dissection. Also available on the web as a secured PDF file at http://mightywords.com/, quick search keyword McDowell. A short inexpensive introduction to C.

 6. Ira Pohl, Charlie McDowell: Java by Dissection: The Essentials of Java Programming. Addison-Wesley, 2000, ISBN 0-201-61248-8. This is a textbook appropriate for cmps012a, not cmps012b. It is, hence, not a textbook for this course. It is recommended for those who want a book to learn basic Java. It will not be referred to in the course, and is recommended only for those students whose previous course was not in Java.

 7. Jerry Peek, Tim O'Reilly, Mike Loukides: Unix Power Tools, 2nded. O'Reilly & Associates, 1998, ISBN 1-56592-260-3. A very good book full of tips and tricks for Unix. Consists of a thousand or so one-page blurbs and can be read a little at a time here and there. Will help you become a Unix Power User,but not necessary in order to pass the course.

 3. Syllabus

The following topics will be covered during the quarter, each of them taking approximately one week.

 1. Overview of Data Structures. Introduction to Unix. The file system. Shell commands. AFS. Review of Java. Java statements, classes, methods, and fields. Arrays. The main class. Primitive vs reference objects.

 2. Using javac and java. Class and jar files. Style, identifier names, documentation and format. Refinement and modularity. System arguments (main's args) and file access. Standard input, output, and error streams. Gnu make (gmake) and GNUmakefiles.

 3. Linked lists and references. Specifications for a data structure. Abstract data types. Information hiding. Preconditions, postconditions, and invariants. Interface classes and implementation classes. Throwing and catching exceptions.

 4. The linear data structures: Stacks, array and list implementations. Queues, array and list implementations. Circular queues

 5. Recursion: factorial, Fibonacci, towers. The function call stack. Running time of an algorithm. Big-O notation. Informal introduction to analysis and bounds of algorithms.

 6. Tables and information retrieval. Hash tables and hashing functions. Binary trees. Prefix, infix, and postfix traversals. Expression trees. Binary search trees. Insertion and deletion. Keys and data. Sequential search. Binary search.

 7. Introduction to C. argc and argv. Standard I/O library, <stdio> and FILE*. Cstrings: pointers to character arrays with the null plug. typedef.

 8. Abstract data types in C. Header files as interfaces. Pointers as references. Structures as classes. Implementation files. malloc() as new. Using free() in a non-garbage collected language.

 9. Sorting. Details of easy to understand {O( )} sorts: insertion and selection sorts, array and list versions, Running time.

 10. Overview of better {O(n log n)} sorts: Merge sort for linked lists. Quicksort, its running time, and choice of a pivot. Heaps and heap sort.

 4. Academic Integrity and Cheating

Cheating will not be tolerated. Cheating is defined as giving or receiving unpermitted aid in any programming assignments, examinations, or other course work that is used by the instructor as a basis of assigning grades. Incidents of cheating will be reported to the Provost of the student's college and to the School of Engineering for disciplinary action. Cheating in any part of the course may lead to failing the course and suspension or dismissal from the University. At the very least, you will fail the class if you cheat.

Be warned that the School of Engineering has a policy of being highly intolerant toward cheating and/or academic dishonesty. All students shall read the UC Santa Cruz Academic Integrity web pages: http://oasas.ucsc.edu/avcue/integrity/.

Students are expected to maintain high standards of academic honesty. That means that any work submitted by a student which is not completely his/her own is not acceptable. The only exceptions are code provided by the instructor or TA, whether given in class or provided in the instructor's course directory, and code taken from the assigned textbook. Specifically, what is not acceptable is swapping code. Helping each other with general questions is OK and that is one of the uses of the newsgroup.

Any code not written by the student must be acknowledged in the README submitted with the assignment. Submitting code not written personally by the student and which is not acknowledged in the README is always cheating, whether or not the code would be otherwise authorized. Submitting code not written personally by the student, even if acknowledged in the README, is cheating if it pertains to parts of assignments that the student is expected to write individually. This refers to programs received from anyone, even tutors, or found on the web or other open-source code sources. And if an argument toward honesty does not convince you, note that if you can surf the web to find some code, so can others too, and they may then submit the same code you do.

Getting help from tutors in developing programs is of course expected. Tutors, in the course of their duties, may provide small code fragments, or explain to students how to rewrite their code, or how to debug existing code and modify it in order to get it working.

5. Due Dates

Assignments are due on midnight of the day they are due. A Cats Unix account is required in order to pass the course. All assignments will be submitted electronically via the Cats Solaris servers and must work on these machines in order to receive a grade. Graders are required to be logged into the Cats Solaris Operating Environment machines when doing any part of the grading. Whether or not an assignment works with another environment will not influence an assignment score in any way.

When I say midnight, I mean midnight, not 00:01 or 00:05 or 9am the next morning. And if you haven't submitted anything, you will get a zero for the assignment. Note that it will be hard to pass the class if you don't do a good job on all the assignments. Do things early and get them in on time.

6. Submitting Assignments

Firstly, it is important for you to understand how to submit an assignment. Waiting until the due date to find that out will likely mean that you will not be able to submit, and hence will score zero. Submitting assignments is like voting in Chicago: do it early and do it often! If you submit a file that has already been submitted, the new submit will replace the old.

Submit homework with the command:

 submit volume assignment files...

The volume name is in general the registrar's catalog code (with a hyphen and the initials of the instructor if two people are teaching the course), a period, the quarter, and the two-digit year. The quarter is a single letter (f, w, or s). You can always find out what volumes are available with the command:

 ls /afs/cats.ucsc.edu/class/

Example1:

 submit cmps012b-tm.s02 asg1 README Makefile factorial.c format.c

Example2:

 submit cmps012b-tm.s02 asg1 *

Note: You should do each assignment in a separate directory and make sure that there are only source files in the directory you are in before using the star (*) version of submit. Otherwise a lot of random junk will also be submitted.

Once you have turned in something, you may look at it with either of the commands:

 peek cmps012b-tm.s02 asg1

 ls -lag /afs/cats.ucsc.edu/class/cmps012b-tm.s02/asg1/$USER/

If you want to play around with submitting before actually doing it, submit to junk. Anything submitted to junk will be deleted without any further action, but you can use it if you like to learn about submit and peek.

Note that there are two offerings of CMPS 012B this quarter: one taught by Professor Mackey and one taught by myself (Professor Madhyastha). Our last names both start with the same letter, thus, the volume names for submission differ by exactly one character. This is not an excuse for submitting assignments to the wrong directory. If you are in my class and you submit to his directory, I give you a zero. End of story.

7. Appeals to scores and inaccuracies in grading

If you disagree with a score assigned to you in a programming project, you should send email to one of the TAs asking for more information and detailing your objections or disagreements. If the number of TAs is not equal to 1, please see further information in the README, newsgroup, or score report sent to you. There is always a deadline for appealing the scores, which will be given in the email sent to you after grading. For score reports that you receive prior to the last week of classes, this will normally be seven days after you receive a report. Because of the extremely tight schedule during exam week, reports sent after the last due date will have a deadline of 24 hours.

For tests, the time to make note of any grading errors is immediately after the class during which the tests are returned. Test score appeals must be done in person with the test in your possession at that time, not via email.

You will have access to grades when they are entered through the class web page.

8. General grading guidelines for programming projects

These are the general scoring guidelines to be used in scoring programming projects. The maximum score is 60 points. Of that: 30 points are for program source code, programming quality, style, and anything other than does it work. 30 points are for program output, correctness, completeness, and how well it works.

The graders will assign total scores out of 60 based on the following assumptions as to the values of these scores:

 60/60 Extremely impressive. Brilliant solution. The grader looked at it critically to try to take a couple of points off, but couldn't find anything. Probably could TA the course.

 55/60 Outstanding. Almost perfect except for a few unimportant details. Normal grade for a very good student who does everything right, makes no mistakes, but has a small amount of room for improvement.

 50/60 Excellent. A few minor things here and there don't work. Mostly everything is OK. Given another few weeks, it probably would get fixed. Next year's tutor.

 45/60 Really quite good. Undoubtedly will pass well above the no-pass cutoff.

 40/60 Above average. No question that it is a passing grade, but not all that impressive. Definitely a pass.

 35/60 Acceptable. Reasonable code. Probably will pass the course and while not very impressive there is no reason to consider a failing grade provided the student passes the exams.

 30/60 Almost acceptable. Maybe. After graduation, should not be hired for systems work, and should stick to Cobol, Windoze, or Web stuff. Code is all there, looks reasonable, but craps out before it actually does anything.

 25/60 Unacceptable. Serious doubts about whether the student knows the work. Will not likely pass.

 15/60 A start on the program, but not much of anything.

 5/60 Charity points.

 1/60 Minimum score for anything submitted.

 0/60 Reserved number meaning nothing submitted.

Assignments will be graded out of 60 regardless of their weight toward the final grade. Also, these should be though of as recommendations from the grader to me. Final assignment of grades is up to me and I am not dumping that on the grader. But the grader should know how I will be interpreting the numbers. Also, it's on a curve, so each of the above numbers will be interpreted as plus or minus some number larger than epsilon.

9. Disability Accommodations

A student with a disability is required to meet with a Disability Resource Center (DRC) service coordinator at the beginning of the quarter to determine required accommodations. The student is then required to bring to the instructor an Accommodation Request Form, provided by the DRC, and to discuss what accommodations are needed. The DRC, not the instructor, makes the determination that a disability exists and is valid. For disability-related testing accommodations, arrangements must be made at least three weeks before each test or exam. For more information contact the Disability Resource Center, 146 Hahn Student Services, (831)459-2089, http://www2.ucsc.edu/drc/, drc@cats.ucsc.edu.

DRC requires two weeks notice if a proctor is needed. Students requesting disability accommodation must ensure that the instructor is notified well in advance that accommodation is needed. Accommodation can not be provided if the DRC can not provide a proctor.