22C:21 Computer Science II: Data Structures

10:30-11:20 MWF Room 112 MH (MacBride Hall)

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 9-10 Tuesday, 11:30-12:30 Wednesday, and 2:30-3:30 Friday
Course website: http://www.cs.uiowa.edu/~sriram/21/fall07/

This is the second in the sequence of core undergraduate computer science courses and is required for all computer science majors and minors. It builds on the first course, Computer Science I: Fundamentals (22C:16) and and is concerned mainly with the design and implementation of data structures, algorithms for accessing and manipulating data structures, and the application and uses of data structures. Java is the programming language of choice for this course, but the last programming project may contain pieces that you will have to complete in C.

Required Legalese
This course is run by the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.

Prerequisite
C- or better in 22C:16

Textbook

There is no required textbook for this course. Links to a variety of reading material and Java code will be posted on the course page, as we go along. I have posted reading material for the first 4 weeks of the semester. Given the amount of freely available material of reasonable quality on the web and the rapidly rising costs of textbooks, I have decided to try (for the first time) a "no textbook" approach to this course. If you would rather have a book in your hand, you might purchase (or borrow) one of the following books, used in previous offerings of the course.

  1. Data Structures and Problem Solving Using Java (3rd Edition) (Hardcover) by Mark A. Weiss, published by Addison Wesley, 2005.

  2. Java Structures: Data Structures in Java for the Principled Programmer by Duane A. Bailey, published by McGraw-Hill, 2002.
But again, neither of these books is required! And if you are looking for a book on Java, the following has my recommendation:

Java in a Nutshell, Fifth Edition by David Flanagan, published by O'Reilly, 2005.

This book is not required either!

Discussion sections and Teaching Assistants

There are 3 discussion sections associated with the class. Each one of you is registered for a discussion section and should attend the discussion section you have registered for. The discussion sections will meet in the McLean Hall computer lab in 301 MLH and will be conducted by a Teaching Assistant (TA). There are two TAs for the course: Fang Yang and D. Ezra Sidran. They will lead discussion sections according to the following schedule. 

Section         Time                    Location                TA
A01             12:30-1:20 Th           301 MLH                 Ezra Sidran
A02             3:30-4:20 Th            301 MLH                 Fang Yang
A04             3:30-4:20 Th            301 MLH                 Fang Yang
Note that discussion sections A02 and A04 will meet simultaneously. You should think of the TAs as the front-line for getting help in this course. Together they will have 6 office hours per week, spread through the week and will also answer questions by e-mail and on the phone. Contact information and office hours for the TAs is as follows: 
        Fang Yang
        101N MLH, 335-2839
        fayang@cs.uiowa.edu
        Mondays 2:00-3:30, Fridays 11:30-1:00 

        D. Ezra Sidran
        101 N MacLean Hall, 335-2839
        dsidran@cs.uiowa.edu
        Tuesdays 2:30-4:30, Thursdays 2:30-3:30

In the past, discussion sections have been run in a classroom setting, more or less in a "lecture" format, with the Teaching Assistant (TA) doing most of the talking. In this offering of the course, I would like to run discussion sections more like a physics or a chemistry lab. Specifically, I will post a lab document at least one week prior to the discussion section meeting. The lab document will essentially describe a problem that you are expected to think about before coming to the lab. Lab documents for the first 4 weeks have already been posted. During the lab, you will spend 30 minutes solving the posted problem, with the help of the TAs. The TAs will come prepared with the solution and will walk around the lab helping individuals complete their solutions. At the end of 30 minutes the TAs will distribute an electronic version of their solution. The last 20 minutes of the lab will be spent solving a quiz based on the lab problem. Typically, you will find the quiz rather difficult if you don't spend the first 30 minutes of the lab thinking and working seriously on the given lab problem.

To get started in the lab on Thursday, 8/30, you will need an account on computer science machines. Most of you already have such accounts; the rest of you will get CS accounts by Wednesday, 8/29 in the lecture; please remember to pick these up. You will also need a HawkID and a password to login to ICON to electronically submit your quiz. In general, you will be submitting all your work electronically via the ICON dropbox.

To give you additional practice with material covered in the lectures and in the lab, you will be given a homework at the end of each lab. This homework will be due in the lab, the following week. Typically, for each homework you will submit a Java program, a 1-2 page writeup (in pdf format), and a README file to help us execute and understand your Java program.

Grading
Plus/Minus grading will be used for the course. There are the four components that will determine your grade.

Late submissions will not be accepted and in general you will be better off turning in what you have on time rather than seeking extra time to complete your work. Starting early is the key, especially to completing the programing projects on time. There will be no make-up exams in general and exceptions will be rare and only for students whose reasons are included in the University's policy on "Excused Absences from Examinations".

Solutions will be provided on the course page for all graded work, including programming assignments.

Students with disabilities
I would like to hear from anyone who has a disability which may require seating modifications or testing accommodations or accommodations of other class requirements, so that appropriate arrangements may be made. Please contact me during my office hours.

Academic Dishonesty
Academic dishonesty will not be tolerated. Under no circumstances should you pass off someone else's work as your own. This also applies to code or other material that you might find on the internet. Note that we will routinely use available software systems for detecting software plagiarism, to test any suspicions we might have. If you are unclear about what constitutes academic dishonesty contact your professor or consult the printed policy in the Schedule of Courses and the CLAS Bulletin (online version). We do want students to talk to each other about concepts and ideas that relate to the class. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.

Student Complaints
If you have any complaints or concerns about how the course is being conducted by me or by the TAs please feel free to talk to me. You are also welcome to get in touch the the Computer Science department chair, Prof. Jim Cremer (cremer@cs.uiowa.edu, 319-335-1713, 14D McLean Hall). Consult the college policy on Student Complaints Concerning Faculty Actions (online version) for more information.

Tentative List of Topics

  • Week 1: 8/27-8/31 Classes and objects in Java; arrays in Java; brief introduction to running time analysis; linear search and binary search.

  • Week 2: 9/3-9/7 Two-dimensional arrays; introduction to graphs; adjacency matrix representation of graphs; implementation of a Graph class.

  • Week 3: 9/10-9/14 Discussion of the Graph class methods; introduction to dynamic data structures; linked lists; implementation of singly linked lists.

  • Week 4: 9/17-9/21 Doubly linked lists; an application of linked lists: adjacency list representation of graphs; another application of linked lists: hashing with chaining.

  • Week 5: 9/24-9/28 Designing good hash functions and efficiently computing hash values; introduction to iterators in Java; the Iterator and the Iterable interface; inheritance from interfaces; implementing a linked list iterator.

  • Week 6: 10/1-10/5 Implementing multi-purpose data structures in Java; generics in Java; the Comparable and the Comparator interface; Abstract data types (ADTs); the queue and stack ADTs; algorithm for breadth-first search (BFS); implementing BFS using a queue; constructing BFS trees;

  • Week 7: 10/8-10/12 Implementing BFS using a queue; constructing BFS trees; applications of BFS; on recursion: base cases vs recursive cases; determining the correctness of recursive functions via inductive proofs; simple examples of recursion: fibonacci numbers, decimal to binary conversion, the power function, etc;

  • Week 8: 10/15-10/19 Implementing divide-and-conquer algorithms via recursion; introduction to merge sort. More on merge sort; another divide-and-conquer sort: quick sort; randomized quick sort;

  • Week 9: 10/22-10/26 Using recursion to implement search with backtracking; depth-first search of a graph via recursion; solving the 8-queens problem; solving the optimal change problem.

  • Week 10: 10/29-11/2 The priority queue ADT; a sorted array implementation of the priority queue ADT; binary heaps; implementing a priority queue ADT using binary heaps.

  • Week 11: 11/5-11/9 The shortest path problem; application of the priority queue ADT to Dijkstra's shortest path algorithm; an implementation using binary heaps; running time analysis of this implementation; comparison with an unordered array implementation.

  • Week 12: 11/12-11/16 Binary search trees; implementation of binary search tree operations: search, insert, and delete; Tree traversals: in-order, pre-order, and post-order. Implementation of a binary search tree iterator.

  • Week 13: 11/26-11/30 Introduction to balanced binary search trees; AVL Trees: definitions; insertion into an AVL tree and repairing imbalance using rotations; the two cases for responding to an AVL tree insert and the three cases for responding to an AVL tree delete.

  • Week 14: 12/3-12/7 Skip lists, a probabilistic alternative for balanced binary trees.

  • Week 15: 12/10-12/14 Make-up week.