22C:21 Computer Science II: Data Structures

1:30-2:20 MWF Room 112 MH (MacBride Hall)

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 11-12:20 Monday and 11:00-12:20 Wednesday
Course website: http://www.cs.uiowa.edu/~sriram/21/fall08/

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 2 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 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: Kajari Ghosh Dastidar and Chris Dibbern. They will lead discussion sections according to the following schedule. 

Section         Time                    Location                TA
A01             8:30-9:20 Th            205 MLH                 Kajari Ghosh Dastidar
A02             3:30-4:20 Th            118 MLH                 Kajari Ghosh Dastidar
A04             1:30-2:20 Th            75 SH                   Chris Dibbern
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 will be posted shortly.

The discussion sections will complement the lectures in a variety of ways and will provide opportunity to deepen your understanding of the material covered in the lectures. In the beginning of the semester, the TAs will spend time on Java programming and using the Eclipse IDE. As the semester progresses, the discussion sections will provide specific guidance on programming projects, additional examples of data structures and running time analysis, additional examples of Java code snippets, etc. Due to their small size, the discussion sections will provide an environment in which students feel free to ask questions.

For this course, it will be helpful if you have an account on computer science machines. Most of you already have such accounts; the rest of you will get CS accounts by the end of the first week. You will also need a HawkID and a password to login to ICON to electronically submit your assigned work.

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/25-8/29 Classes, objects, and methods in Java; arrays in Java; brief introduction to running time analysis; linear search and binary search.

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

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

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

  • Week 5: 9/22-9/26 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: 9/29-10/3 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/6-10/10 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/13-10/17 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/20-10/24 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/27-10/31 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/3-11/7 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/10-11/14 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/17-11/21 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/1-12/5 Skip lists, a probabilistic alternative for balanced binary trees.

  • Week 15: 12/8-12/12 Make-up week.