CS230 Data Structures - Spring 2008

CS230 Home | Syllabus | Assignments | Documentation | CS Dept

Instructors

Instructor: P. Takis Metaxas
Office: SCI E116
Office Hours: Mondays 11:30-12:30, Wednesdays 4:30-6:00, Fridays 2:30-4:00

Lab Instructor: Stella Kakavouli
Office: SCI E127
Office Hours: Mon 10-12, Tue 1:30-2:30, Thu 9-11, and by appointment

Teaching Assistant: Cassie McLeod and Sha Lu
TA Hours: Wed 7-9pm with Sha, and Mon 8-10pm with Cassie.
Drop-in hours are held in S160A or in the Linux Lab (micro focus area). Starting the week of 2/4.

Course Overview

CS230 focuses on four "big ideas":

1. Data Abstraction: In order to cope with the complexity of writing large programs, it is desirable to express them as combinations of components whose behavior can be understood independently from their implementation. In CS111, you learned how methods provide an abstraction barrier between the caller and implementer of a method. We will review this notion and introduce abstract data types as a way to represent computational values and the operators that manipulate them.
   
2. Modularity: The ability to create large and complex computer programs is enhanced if they can be composed out of reusable components with standard interfaces that can be combined in mix-and-match ways. We will study how to compose programs out of such components.
   
3. Performance Analysis: Programs are often judged by how effectively they make use of resources such as space and time. We will explore ways to describe the efficiency of algorithms and use these tools to evaluate various approaches to implementing data structures and algorithms.
   
4. Standard Abstract Data Types: We will learn about the implementation and use of classical data structures such as lists, stacks, queues, trees, tables and graphs, which should be in every programmer's bag of tools.

We will use Java as the language for describing implementations of these structures and their application.

Prerequisites

The prerequisite for CS230 is CS111, Computer Programming and Problem Solving. Students with significant programming experience (including knowledge of Java) who have not taken CS111 may take the course with the permission of the instructor.

Lectures and Labs

There are two 70-minute lectures each week that will introduce the main content of the course. Every student is also required to attend one 110-minute lab each week. Lab work will include exercises to review and reinforce the lecture material and to develop general programming, testing and debugging skills. The labs will also provide further opportunity to ask questions about course material and discuss homework assignments.

Lectures are held on Mondays and Thursdays at 9:50-11:00AM in SCI-264. Labs are held on Tuesdays at 10:30-12:20AM and 6:00-7:50PM in SCI-160A.

Textbooks/Notes

Text: Regular reading will be assigned from the required text, Java Foundations, by Lewis, DePasquale and Chase. You can find it in the campus bookstore and on reserve in the Science Library.

The first 5 chapters of this text provide a review of Java 1.5, which we will move through quickly during the first three weeks of the semester. The new material for CS230 is covered in Chapters 6-18, which will be the focus of the rest of the course. This material will be supplemented with lecture handouts.

E101 and SCI 173 Libraries: The CS department has purchased many books relevant to CS230 that are kept in the bookshelves near the front door of E101 and in the bookshelves in the CS student lounge, SCI 173. You may use these books around the E101 and 173 areas. Please do not remove any of these books, so that they remain available to all students.

Assignments

There will be weekly assignments in which you will write Java programs that emphasize concepts discussed in class. Many of the assignments will be challenging. Keep in mind that programming often consumes more time than you expect. Start your assignments early! This will give you time to think about the problems and ask questions if you hit an impasse.

All assignments are due in class on the advertised due date. You should turn in both a "hard" (paper) copy of your assignment and a "soft" (electronic) copy of any programs from the assignment. The assignment handouts will provide instructions on how to drop off your eletronic copy.

Lab Exercises

Lab exercises will be distributed in the Tuesday labs. Some of the lab work will be completed during the scheduled lab time. For the rest, work on your own and consult the posted solutions.

Final Project

During the last few weeks of the semester, you will work on an extended programming project that you will design and build from scratch. After choosing an interesting application or problem, you will first build a skeleton of the object classes, methods, abstract data types and user interface needed for your application, and then fill in the details to create a fully working implementation. Each student will give a short presentation of her final project during the last lab class of the semester. Guidelines for the final project will be posted mid-semester.

Late Assignment Policy

Turning in assignments on time makes it easier to keep on track with the course and to turn in the next assignment on time. We will use the following policy:

An assignment due on a particular day will be accepted at the beginning of the class on that day. No late work will be accepted unless there are extenuating circumstances (e.g., sickness, personal crisis, family problems). In this case you may request an extension before the due date.

Collaboration Policy

We believe that collaboration fosters a healthy and enjoyable educational environment. For this reason, we encourage you to talk with other students about the course material and to form study groups.

Because the programming assignments in this course are challenging, you will be allowed on any assignment to form a two-person "team" with a partner. The two team members must work closely together on the assignment and turn in a single hard- and soft-copy of the assignment for the team. The grade received on such a submission will be given to both team members.

Team efforts on assignments are subject to the following ground rules:

• The work must be a true collaboration in which each member of the team will carry her own weight. It is not acceptable for two team members to split the problems of the assignment between them and work on them independently. Instead, the two team members must actively work together on all parts of the assignment. In particular, almost all programming on the assignment should be done with the two team members working at the same computer. It is strongly recommended that both team members share the responsibility of "driving" (i.e., typing at the keyboard), swapping every so oftern.

  The fact that team members have to program together means that you need to carefully consider a potential partner's schedule before forming a team. You cannot be a team if you cannot find large chunks of time to spend at a computer together!

• You can only work with a given partner on a single problem set during the semester. So if you want to continue to collaborate, you must choose a different partner for every assignment. Rotating through partners is a good way to build community in the class and is helpful for avoiding situations where one individual feels pressured to continue working with another.
• You are not required to have a partner on any assignment, but you are encouraged to do so. Based on past experience, working with a partner can significantly decrease the amount of time you spend on an assignment, because you are more likely to avoid silly errors and blind alleys. On the other hand, it can be difficult for teammates to find time to work together, and certain individuals make yake more time on an assignment than they would alone. In this case, there are still benefits to working with a partner, but they may be outweighed by the time cost.

Unless otherwise instructed, teams are allowed to discuss problem sets with other teams and exchange ideas about how to solve them. However, there is a thin line between collaboration and plagiarizing the work of others. Therefore, we require that each (one-person or two-person) team must compose its own solutions to each assignment. In particular,

You must compose your own solution to each assignment and lab problem. You may discuss strategies for approaching the programming problems with your classmates and may receive general debugging advice from them, but you are required to write and debug all of your code. Furthermore, you should never look at another student's code.

In keeping with the standards of the scientific community, you must give credit where credit is due. If you make use of an idea that was developed by (or jointly with) others, please reference them appropriately in your work. It is unacceptable for students to work together but not to acknowledge each other in their write-ups.

Exams

There will be one in-class closed-book exam and two in-term take-home exams that are both open book and open notes. There will be no final exam. The take-home exams will require the use of a computer. You are not allowed to collaborate with anyone else on the take-home exams. The dates of the exams are:

Exam 1 will take place in class on Thursday, February 21.
Exam 2 will be distributed on Monday, March 31, and due on Thursday, March 4.
Exam 3 will be distributed on Thursday, April 24, and due on Monday, April 28.

Please mark these dates in your calendars as they are not flexible.

Grading Policy

Your final grade for the course will be computed as a weighted average of several components. The relative weight of each component is shown below:

Computers

All programming in CS230 will be done on the CS department's Linux workstations, described in the Linux document. These workstations can be accessed remotely through MACs and PCs. Each CS230 student will have a password-protected account on the CS fileserver, puma. You will have a limited amount of space on puma to store your course-related files. The Documentation page has pointers to documentation for all the software packages used in CS230.

Course Directory

The CS230 course directory is located at /home/cs230 on puma. This directory contains material relevant to the class, including course software, and online versions of assignments and programs. From a web browser, the course web pages are available via links from the document you are currently reading. All of the course Java software will be placed in the download folder inside the /home/cs230 directory.

Course Conference on FirstClass

There is a CS230 conference on FirstClass named CS230-S08. This conference has several purposes. We will use it to make class announcements, such as corrections to assignments and clarifications of material discussed in class. We encourage you to post questions or comments that are of interest to students in the course. Please do not post significant amounts of Java code (i.e. more than one or two lines of code) in your messages on the FirstClass conference! The instructors will read messages posted in the conference folder on a regular basis and post answers to questions found there. If you know the answer to a classmate's question, feel free to post a reply yourself. The course conference is also a good place to find people to join a study group. You should plan on reading conference messages on a regular basis.

Finding Help

If you have any questions at all about the class (whether big or small, whether on assignments, lectures, reading, or whatever) please contact one of the instructors. Simple questions can often be answered via the FirstClass conference or e-mail. Questions of general interest (e.g. clarifying ambiguities in an assignment, wondering why posted programs do not work as expected) should be posted to the CS230 conference. Other questions can be emailed to your instructors.

If you have a complex question or need help in understanding the material, you are encouraged to see one of the instructors or the CS230 tutor. The best time to see an instructor is during our office hours. If these times are not convenient, we can schedule an appointment for another time. You can schedule an appointment in person or by e-mail.

Cassie McLeod will be the CS230 tutor this semester and she will hold regular drop-in hours to help with your questions. The schedule of her drop-in hours will be made available early in the term. If you are having trouble with the course, you can request a one-on-one tutor from the Pforzheimer Learning and Teaching Center (PLTC). This service is confidential and free of charge; please take advantage of it if you need some extra help! Contact an instructor or PLTC for more information about this service.

Finally, when looking for help, do not overlook other students. Get to know your classmates early in the term so that you can help each other out!

Students with Special Needs

If you have any disabilities, including learning disabilities, you are encouraged to meet with an instructor to discuss accommodations that may be helpful to you.

Mathematical Modeling Distribution

CS230 counts for one Mathematical Modeling (MM) distribution credit.