CSE 373: Data Structures & Algorithms

Autumn 2010

**Exam policies:**

- Closed book, closed notes. Calculators NOT allowed.
- The exam begins promptly at 2:30 and ends at 3:20.

**Topics covered: **

- Stacks and Queues, array and list implementations.
- Recursion. Designing algorithms recursively.
- Asymptotic analysis, Big-O. Worst case, upper bound, lower bound, analyzing loops, recurrences.
- Trees – definitions
- Dictionary ADT
- Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
- AVL trees - Single and double rotations, insert, find.
- Binary Heaps -
Findmin, Deletemin, Insert.
~~Additional operations of increase, decrease, buildheap~~

**Sample midterms: **

**NOTES**

·
**Topics covered on these exams may not be the
exact same topics covered on our exam; please see the list of topics listed
above for topics covered on our exam.**

·
**These are provided to help you study and are
not meant to be interpreted as a guarantee of the format of our actual midterm
in terms of length or type of questions.**

**Midterm I samples:**

- Sample
Midterm I (Solution to Sample
Midterm I) (Extra steps written
out for Sample Midterm I) (Note, we will
__not__have any questions on Splay Trees on our midterm) - Midterm I from 08sp (Solution to Midterm I from 08sp)
(Note, we will
__not__have any questions on Splay trees or amortized analysis on our midterm) - Midterm I from 09wi (Solution to Midterm I from 09wi)
- Midterm I from 09sp (Solution to Midterm I from 09sp)
(Note, we will
__not__have any questions on hashing on our midterm) - Midterm I from 10sp (Solution to Midterm I from 10sp)
- Midterm I from 10au (Solution to Midterm I from 10au)

**Midterm II samples: (These are mostly **__not__** relevant except where noted.)**

- Sample Midterm II (Key to Sample Midterm II)
- Midterm II from 08sp (Key to Midterm II from 08sp) (contains a binary min heap question)
- Midterm II from 09wi (Key to Midterm II from 09wi)
- Midterm II from 09sp (Key to Midterm II from 09sp) (contains AVL and binary min heap questions)

**Study suggestions: **

- Do concrete problems from the book and re-work problems from lecture and HW. Suggestions of a few more problems from the book: Chapter 2: 2.6, 2.10. Chapter 3: 3.21, 3.22, 3.23 (a). Chapter 4: 4.1, 4.2, 4.8, 4.9, 4.19, 4.25, Chapter 6: 6.2, 6.3.
- Practice all the operations on stacks and queues, binary search trees, AVL trees, and binary heaps.
- Practice analysis of algorithms.
- All material from
lecture up through binary min heaps is fair game. This material corresponds to: Chapters:
1, 2, 3, 4 (
section 4.5 on Splay trees, 4.7 on B-trees, or 4.8), and 6 (__Not Including:__: sections 6.5-6.9).__Not including__