22C : 021 (CS : 2230) Computer Science II: Data Structures Fall 2012

Class Schedule

2.30–3.20 pm Monday, Wednesday, and Friday at LR1 Van Allen (VAN).

Instructor and Office Hours

Kasturi Varadarajan: 101D MacLean Hall, 335-0732, kasturi-varadarajan@uiowa.edu Office hours: 3.30–4.30 Mon and 2.00–4.00 Tue. You can also set up an appointment to meet me at other times.

Discussion Section

Each of you is also enrolled in a discussion section that meets once a week and will be led by one of our TA’s:

• 22C:021:A01: Meets 11:00-11:50 Th, in 202 LC (Lindquist Center).

• 22C:021:A02: Meets 12:30-1:20 Th, in 219 NH (North Hall).

• 22C:021:A03: Meets 2:00-2:50 Th, in E244 CB (Chemistry Building).

• 22C:021:A04: Meets 3:30-4:20 Th, in 346 JH (Jessup Hall).

Teaching Assistants

The teaching assistants for each discussion section and office hours will be announced shortly on the course website.

Course Web Page

www.cs.uiowa.edu/∼kvaradar/fall2012/ds.html. I will make this accessible from your

ICON page once I activate it.

Departmental Information

Department of Computer Science, 14 Maclean Hall. The office of the DEO, Prof. Alberto Segre, is located here.

Content

Programs, in the course of performing computation, often need to store, query, and update large, or somewhat large, amounts of information. There are usually different ways in which the program can be designed to do this information processing. Some of these ways are good, and others not so good. In several contexts, this distinction is crucial – it can determine whether an application is useful or completely useless. In brief, then, the goal of this course is to learn that there are usually these different ways of doing the information processing, which are called data structures, and to learn to be increasingly sensitive to the distinction between the good and the bad ways.

That is a lofty goal, but we will begin in a modest way, by first acquiring familiarity with the constructs in Java, the programming language we will use. We will then learn some rather neat things to do, like solving problems using recursion and building linked lists.

We will then dive into several data structures, such as stacks, queues, lists, trees, priority queues, hash tables, and binary search trees. Each of these is a good way of processing information in some contexts, as we will see. Finally, assuming time permits, we will finish off by discussing graphs and basic algorithms on graphs, which illustrate quite well the idea of a good data structure.

For our textbook, we will use “Data Structures and Algorithms in Java”, by Goodrich and Tamassia, ISBN 978-0-470-38326-1.

Prerequisites

Computer Science I (22C:016). Discrete Structures (22C:019) is a corequisite if not taken as a prerequisite.

Grading

The grading will be based on several homeworks (25 percent), two in-class midterms (25 percent each), and the final (25 percent).

Roughly speaking, there will be a homework every week, and I will try to make these due on Monday. This way, you may make greater use of the TA discussion sections on Thursday. Most of the homeworks will involve programming in Java.

The policy on late homeworks is that you have a quota of three days for the entire semester that you may use for late submissions. So for example, there will be no penalty if you submit the fifth homework a day late, the seventh two days late, and the rest of the homeworks on time. Once you use up your quota of three days, any homework submitted late will not be accepted and you will get 0 points for that homework.

When you submit a homework X days late, your quota gets decreased by X irrevocably. You can only be late by an integer number of days – if you submit 10 hours after the deadline, for example, your quota is depleted by one day.

Exam Dates

The midterms will be in our usual classroom and during our class on Wednesday, Sep 26 and on Wednesday, Oct 31. The final will be during finals week, and the coordinates will be announced later. (The final is scheduled by the Office of the Registrar.)

Collaboration

No collaboration is allowed on the exams. For homework problems, collaboration is allowed and encouraged, assuming each of you has first spent some time (about 30 minutes) working on the problem yourself. However, no written transcript (electronic or otherwise) of the collaborative discussion should be taken from the discussion by any participant. It will be assumed that each of you is capable of orally explaining the solution that you turn in, so do not turn in something you don’t understand.

Course Accounts

You will be assigned an account on the computer science department machines shortly, if you do not already have one. In addition, you will need your HawkId and password to access information about this course on ICON and to submit the programming assignments.

Administrative Home

The College of Liberal Arts and Sciences is the administrative home of this course and governs matters such as the add/drop deadlines, the second-grade-only option, and other related issues. Different colleges may have different policies. Questions may be addressed to 120 Schaeffer Hall, or see the CLAS Academic Policies Handbook at

http://clas.uiowa.edu/students/handbook.

Electronic Communication

University policy specifies that students are responsible for all official correspondences sent to their University of Iowa e-mail address (@uiowa.edu). Faculty and students should use this account for correspondences .

Accomodations for Disabilities

A student seeking academic accommodations should first register with Student Disability Services and then meet privately with the course instructor to make particular arrangements. See www.uiowa.edu/∼sds/ for more information.

Academic Honesty

All CLAS students have, in essence, agreed to the College’s Code of Academic Honesty: ”I pledge to do my own academic work and to excel to the best of my abilities, upholding the IOWA Challenge. I promise not to lie about my academic work, to cheat, or to steal the words or ideas of others; nor will I help fellow students to violate the Code of Academic Honesty.” Any student committing academic misconduct is reported to the College and placed on disciplinary probation or may be suspended or expelled (see CLAS Academic Policies Handbook).

Making a Suggestion or a Complaint

Students with a suggestion or complaint should first visit with the instructor (and the course supervisor), and then with the departmental DEO. Complaints must be made within six months of the incident. (See CLAS Academic Policies Handbook).

Understanding Sexual Harassment

Sexual harassment subverts the mission of the University and threatens the well-being of students, faculty, and staff. All members of the UI community have a responsibility to uphold this mission and to contribute to a safe environment that enhances learning. Incidents of sexual harassment should be reported immediately. See the UI Comprehensive Guide on Sexual Harassment for assistance, definitions, and the full University policy.

Reacting Safely to Severe Weather

In severe weather, class members should seek appropriate shelter immediately, leaving the classroom if necessary. The class will continue if possible when the event is over. For more information on Hawk Alert and the siren warning system, visit the Department of Public Safety website.