Fall 2009: Computer Science II, Data Structures, 22C:021
The course meets 2.30--3.20 pm Monday, Wednesday, and Friday
at 112 MH. Each student is also registered for and will attend a weekly
discussion section conducted by our TA.
In brief, the course will be about problem solving using data structures, with Java as the language
for expressing our ideas. See
this previous offering to get a rough idea of the course.
Here is an "official" course description: The second course required for computer science majors and minors emphasizes the design, implementation, and analysis of common data structures and algorithms. The goal is to teach how data structures provide the necessary data abstraction for the development of large software systems and their central role in software engineering. Data structures covered include sets, linked lists, stacks, queues, hash tables, trees, heaps, and graphs. Students are introduced to algorithms for searching, sorting, and data structure manipulation and learn the techniques to analyze program efficiency. Programming using recursion and dynamic data structures are covered. The programming language is Java.
For our textbook, we will use
"Data Structures and Algorithm Analysis in Java 2/E" by Weiss, ISBN 0321370139. After the first couple
of weeks of lectures and discussion sections, this book will become quite readable.
Computer Science I (22C:016). Discrete Structures (22C:019) is
a corequisite if not taken as a prerequisite.
The grading will be based on several homeworks (50 percent), of which
there be nine or ten, one midterm (20 points) and
one final (30 points). Most of the homeworks will involve Java
The midterm will be in class on Wednesday, October 14.
The final exam is on Tuesday, Dec 15, at 7:30 am in our regular classroom.
Teaching Assistant and Discussion Sections
Each of the students in the class is registered for a discussion section
that he/she is expected to attend. The TA for the class is
Marcus Ernster. He will lead
discussions according to the following schedule.
Section Time Location
A01 8:30-9:20 Th 205 MLH
A02 3:30-4:20 Th 116 MLH
Kasturi 4.00-5.00 Mon, 1.30-2.30 Tue, 4.00-5.00 Wed 101E MLH
Marcus 11.00-12.30, Mon and Fri
Handouts and Notes
- First Day Handout
- Java Lecture Notes. We need only the notes
for the first four weeks for the most part. Use these notes as a reference if you need to
understand something related to the programming language.
- A first java program that checks for balance, Aug 26.
- Slides used on Aug 26
- Our stack, generalized.
- Slides used on Aug 28. Please note that slides
often do not summarize the lectures, because much of the lectures is done on the blackboard.
- An Eclipse Tutorial
you may find useful.
- A variant of the code we wrote in class on Aug 31 to study
a linked list implementation.
- Implementing a stack using linked lists rather than arrays,
- Interfaces: Illustration using a general purpose method
to find the maximum in an array, Sep 2 and 4.
- A A generic stack class , Sep 4.
- Slides on Generic methods, classes, and interfaces , Sept 9.
- A generic class ,
a generic method , and
a use of a generic interface
- An example with lists and iterators , Monday Sep 14. (Corresponds
to Section 3.3 of text.)
- On Wednesday, Sept 16, we studied the interfaces implemented by the ArrayList and LinkedList
classes (Section 3.3 of the book). We very briefly talked about recursion.
- On Friday, Sept 18, we will study the author's implementation of ArrayList in Section 3.4
of the book. Our discussion will be based on the following
modified version of the code in Figures 3.15 and 3.16. In our modification,
ArrayListIterator is a top-level class (as in Figure 3.18) and not an inner class as
in Figures 3.15 and 3.16. Here are the slides used in the
- The Java programs in the textbook are available at the
author's site .
- On Monday, Sept 21, we will study the author's implementation of LinkedList in Section 3.5
of the book. Our discussion will be based on the following
modified version of the code in that section. The code is modified so that
(a) LinkedListIterator and Node are top level classes and (b) the iterator implementation does
not check for concurrent modification. Here are the slides
used in the lecture.
- A simple recursive program to print a number out in base 7, and
a corresponding non-recursive program that uses a stack to
"effect" the recursion.
- A binary search tree of integers with search and insertion
capabilities. Two versions of insert are given -- a recursive and a non-recursive one.(Sep 30
and Oct 2).
- A binary search tree with a delete method added. The
recursive delete and insert roughly correspond to the code in Section 4.3 of the book.
- Slides on Hash Tables based on textbook, Oct 16.
- Using a library hash table implementation , Oct 19.
- Slides on Priority Queue Implementation based on textbook.
- Slides on Mergesort and Quicksort code from textbook.
- A basic class for representing directed
graphs, and corresponding slides
- A simple program to illustrate threads.
This example partitions the task of searching an
array among two threads.
- On Wednesday, Sep 2, we will discuss the Queue data structure and a possible implementation
using arrays. The first homework, based on this, is to provide the corresponding code for
the outlined MyQueue class . After writing the code, you can
test it using the main method I have written. The homework is due Sep 9, at 11.59 pm. You
should submit the source code (the .java files) into a folder in icon that I will create for this homework.
- On Friday, Sep 11, we will discuss an implementation of the Queue data structure using doubly
linked lists. The second homework is to provide the code corresponding to this implementation
for the outlined MyQueue class . The homework is due
Sep 18, at 11:59 pm. Again, look for a dropbox named Homework2 in icon to submit the source
code. You may find it useful to study our stack implementation
using singly linked lists, and to look at the overview of linked lists in Section 3.2
of the book.
- Homework 3, due Sep 30 at 11:59 pm. Look for a dropbox named Homework3
in icon to submit the source code. Please note that in describing the homework, I have assumed
that you have been following the discussion in class to some degree. If you have not been doing
that, please read Sections 3.3, 3.4, and 3.5 of the text.
- Homework 4, due Oct 9 at 11:59 pm. Look for a dropbox named Homework4
in icon to submit the source code.
- Homework 5, due Oct 23 at 11:59 pm. Look for a dropbox named Homework5 in icon to submit the source code.
- Homework 6, due Nov 4 at 11:59 pm. Look for
a dropbox named Homework6 in icon.
- Homework 7, due Nov 18 at 11:59 pm. Note that
this home work is worth 1.5 times a regular homework.
- Homework 8, due Dec 7 at 11:59 pm.