The midterm is open notes/book. It is from 10:30-11:20 in Room 1505 SC (our classroom) on Friday, 3/3.

For the midterm you should read (i) your notes for lectures and discussionn sections, (ii) problem sets and their solutions, (iii) sample code, (iv) relevant material from the textbook, and (v) Lafore's code. My lecture notes from the first two weeks, when we were discussing running time analysis, are posted. From the text book read Chapter 1 (intro), Chapter 2 (arrays and a bit on logarithms and run-time analysis), Chapter 3 (pages 78-88, bubble sort), Chapter 4 (pages 132-143, queues), Chapter 5 (linked lists), Chapter 11 (on hashing; skip the stuff on open addressing), Chapter 13 (pages 615-623, graphs).

Specific topics, that the midterm covers, are:

1. Runnning time analysis: worst case running time analysis of simple code fragments involving loops and nested loops, analysis of linear search, binary search, and bubble sort, Big Oh notation and Big Theta notation.
2. Arrays and multi-dimensional arrays: defining and using arrays and multi-dimensional arrays in Java, efficiently resizing arrays, and implementation of the Set ADT, Queue ADT, and the Graph ADT using arrays.
3. Graphs: Adjacency matrix representation of graphs, the myGraph class that implements graphs using a triangular 2-dimensional array.
4. Linked lists: Singly and doubly linked lists, operations such as insert, delete, and search on linked lists, implementation of hashing with chaining using linked lists.
5. Hashing: hash tables, hash functions, collisions, hashing with chaining, etc.

The midterm contains 4 problems, each worth 50 points. Problem 1 involves doing running time analysis of a given code fragment, Problems 2-3 involve writing small amount of Java code to implement new methods for classes we have studied, and Problem 4 involves describing (in English; no code needed) how to implement an ADT with some prescribed properties.