Spring 2010: Computer Science II, Data Structures, 22C:021

Coordinates

The course meets 10.30--11.20 am Monday, Wednesday, and Friday at 427 EPB. Each student is also registered for and will attend a weekly discussion section conducted by one of our TAs.

Content

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.

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 (50 percent), a midterm exam (20 percent), and the final (30 percent). Most of the homeworks will involve programming in Java.

Exam Dates

The midterm will be in class on wednesday Mar 10. The final will be during finals week as scheduled. So it is on Monday, May 10, at 2.15 pm in the classroom.

Teaching Assistants and Discussion Sections

Section         Time                    Location                TA
A01             10:30-11:20 Th          118 MLH                 Afroza 
A02             3:30-4:20 Th            214 MLH                 Raaj
A04             9:30-10:20 Th           113 MLH                 Varsha  

Office Hours

Kasturi         1.30-2.30 Mon, 1.30-2.30 Tue, 2.30-3.30 Wed     101E MLH
Afroza          10.30-11.30 Tue, 2.30-3.30 Fri                  B20J MLH
Raaj            11.30-12.30 Mon, 11.30-1.30 Wed                B20J MLH
Varsha          2.15-4.15 Tue                                   B20J MLH

Handouts and Notes

• First Day Handout
• Use these Lecture Notes on Java as a reference for stuff related to the programming language. We only need the material corresponding to the first four weeks of these lectures.
• The program for checking balance that we will develop over the second and third lecture.
• Slides on program for checking balance.
• The Tutorial on Eclipse that was covered in the first day of class.
• Our stack generalized to be a stack of Objects.
• A program we use to introduce linked lists. Subsequently, we see how to implement a stack as a singly linked list.
• Interfaces: Illustration through a general purpose method to find the maximum in an array.
• An example of a generic class , and a generic version of our stack.
• An example of a generic method
• An example use of a generic interface.
• Using the library class ArrayList together with iterators.
• Slides on using the ArrayList and LinkedList classes together with iterators.
• For discussing the author's implementation of a version of ArrayList in Section 3.4, we will use the following modified version of his program in Figures 3.15 and 3.16. Here are the slides we use.
• For discussing the author's implementation of a version of LinkedList in Section 3.5, we will use the following modified version of his program. Here are the slides we use.
• A simple recursive program to print a number out in base seven.
• A binary search tree of integers. The recursive delete and insert roughly correspond to Section 4.3 of the book.
• Slides based on our textbook's implementation of hash tables with separate chaining.
• Using an inbuilt hash table class.
• One way of representing directed graphs , corresponding to adjacency lists. Slides used to explain that program.
• The topics we covered in the course (this does not include things in the discussion sections).

Homeworks

• The first homework is a minor one worth 5 points, and is due Monday Feb 1 by 11:59 pm. The typical homework is worth 10 points. Please submit the source code (the .java file) into a dropbox named Homework1 in your section of the course within icon.
• The second homework is worth 10 points, and is due Wednesday Feb 10 at 11:59 pm. Please submit the source code into a dropbox named Homework2 in your section of the course within icon.
• The third homework is worth 10 points, and is due Friday Feb 19 at 11:59 pm. Please submit the source code into a dropbox named Homework3 in your section of the course within icon.
• The fourth homework is worth 10 points, and is due Monday Mar 1 at 11:59 pm. Please submit the source code into a dropbox named Homework4 in your section of the course within icon.
• The fifth homework is worth 10 points, and is due Wednesday Mar 24 at 11:59 pm. Please submit the source code into a dropbox named Homework5 in your section of the course within icon.
• The sixth homework is worth 10 points, and is due Wednesday April 7 at 11:59 pm. Please submit the source code into a dropbox named Homework6 in your section of the course within icon.
• The seventh homework is worth 10 points, and is due Wednesday April 21 at 11:59 pm. Please submit the source code into a dropbox named Homework7 in your section of the course within icon.
• The eighth homework is worth 15 points, and is due Tue May 4 at 11:59 pm. Please submit the source code into a dropbox named Homework8 in your section of the course within icon.