22C:21 Computer Science II: Data Structures

10:30-11:20 MWF Room 106 GILH

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.

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 courses, 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 will 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
Mark Allen Weiss, Data Structures and Algorithm Analysis in Java, Second Edition, Published by Addison Wesley, ISBN 0-321-37013-9. Go here to look for bargains on this book.

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

Quizzes: 15% There will be a quiz in every discussion section meeting. Each quiz will be 20 minutes long and will be based on material covered during the previous week.
Homeworks: 15% One homework problem will be assigned every week. These will be posted on the class homepage and you will have one week for each problem.
3 Programming Projects: 30% These will be posted on the class homepage and you will have 3 weeks to work on each programming project.
2 Exams: 40% There will be one mid-term exam (worth 20% of your grade) and one final (worth 20% of your grade). The schedule for the exams is:
```
Midterm	                March 9th, Friday			10:30-11:20 (in 106 GILH)
Final			May 8th, Tuesday 			12:00-2:00 (in 106 GILH)
```
All exams will be open book/notes exams. The final will be cumulative,

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.

Teaching Assistants and Discussion Sections
There are two TAs for the course: Uday Verma and Saurav Pandit. They will lead discussion sections according to the following schedule.

Section         Time                    Location                TA
A01             12:30-1:20 Th		N200 LC			Uday Verma	
A02             8:30-9:20 Th		132 MH			Saurav Pandit	
A04             2:30-3:20 Th		130 SH			Saurav Pandit

Discussion sections provide opportunity to deepen your understanding of concepts covered in lectures. The TAs will divide their time between going over examples they have prepared and answering your questions. Because of their smaller size, discussion sections provide an environment in which students feel comfortable asking questions. Contact information for the TAs and office hours will be announced shortly. 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.

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.

Topics
Here is a tentative list of topics planned for this offering of the course.

Introduction to programming in Java. 1-dimensional and multi-dimensional arrays. Examples of programming with arrays including binary search, bubble sort, adjacency matric representation of graphs.
Classes and objects in Java. Constructors, static methods, garbage collection, subclasses and inheritance, and abstract classes and interfaces. Examples using the Java collections framework.
The List ADT. References (pointers) in Java and how to use these to construct lists. Singly linked lists, circular lists, doubly linked lists. Various list methods. List Iterators. Adjacency list representation of graphs.
Recursion and its many uses. Simple examples: power, binary search, etc; Divide-and-conquer examples: merge sort, quick sort; Recursion for backtracking and depth-first search in graphs.
Analysis of algorithms. Worst case vs average case analysis. Simple examples with loops, nested loops, etc. Big Oh notation. Logarithms and examples of code that runs in O(log n) time or O(n log n) time.
Stack ADT. Implementation and applications to infix to postfix conversion, and activation records. How to rewrite recursive functions as iterative stack-based functions.
Queue ADT. Implementation and application to breadth-first search. Run-time analysis of breadth-first traversal.
Binary Trees. Tree traversals. The Search Tree ADT and the search, insert, and delete operations. Worst case examples and average case analysis.
Balanced Binary Trees. AVL Trees. Single rotation and double rotation. Analysis of AVL tree operations.
Priority Queue ADT. Implementation using binary heaps. Application to implementing Dijkstra's shortest path algorithm on graphs.
Additional topics. Time permitting we will discuss (i) hash tables or (ii) skip lists or (iii) B-trees.