Midterm Study Guide
CSE 373: Data Structures and Algorithms
Winter 2003

Midterm Exam, Wednesday February 12

• Exam policies
  • The midterm is closed book. No notes allowed either.
  • You will be provided with the text of the exam and enough paper (back pages) t o do you work. You can bring scratch paper if you wish so. Please no "cheating".
  • The exam begins promptly at 11:30 and ends at 12:20.
• Topics covered (in lecture order)
  • Proofs by induction.
    Lecture 1 and Weiss Chapter 1 Section 1.2.5
  • Mathematical background including Exponents, Logarithms, Series, Big Oh notation, Worst case analysis of algorithms.
    Lecture 5 and Weiss Chapter 1 Section 1.2 and Chapter 2 (but not in too great depth)
  • Linked lists. Simple linked lists and doubly linked lists. Array and Cursor implementations. Applications: sparse polynomials, unbounded integers, mergesort. Recursive algorithms.
    Lectures 2, 3 and 4. Weiss Chapter 1 Section 1.3 and Chapter 3 Sections 1 and 2.
  • Stacks and Queues, array and list implementations.
    Lecture 6 and Weiss Chapter 3 Sections 3.3 and 3.4.
  • Trees. Binary trees and Binary search trees. Traversal, insert, delete, find, findmin.
    Lecture 7 and Weiss Chapter 4 Sections 4.1, 4.2, 4.3 and 4.8.
  • AVL trees. Single and double rotations, insert, delete, find.
    Lectures 8 and 8a. Weiss Chapter 4 Section 4.4
  • Splay trees. Splaying, insert, delete, find. B-trees (definitions only).
    Lecture 9. Weiss Chapter 5 Section 4.5 and 4.7.
  • Hashing. Find, insert, delete (lazy deletion). Hash functions for integers and character strings. Chaining. Open addressing with linear probing, quadratic probing, and double hashing. Load factors. Rehashing.
    Lecture 10 and Weiss Chapter 5 Sections 5.1, 5.2, 5.3, 5.4 and 5.5.
  • Binary Heaps. Insert, findmin, deletemin. Increasing and decreasing keys.
    Lecture 11 and Weiss Chapter 6 Sections 6.1, 6.2, and 6.3 (not 6.3.4)
• Study suggestions
  • The only midterm I could find available on line is at:
    Autumn 01 Midterm
    Question 2.c is something I did not talk about. Also I will not ask a question like Question 5 since you did not have any prior HW question analyzing hashing.
  • Review the HW and their solutions. Do more concrete problems from the book. Suggestions from chapter 2: 2.2, 2.6, 2.7. Chapter 3: 3.6, 3.9, 3.10, 3.20 (this will give you a definition of lazy deletion). Chapter 4: 4.5, 4.6, 4.20, 4.27, 4.28, 4.41. Chapter 5: 5.2 (assume you rehash in a table of size 20). Chapter 6: 6.1, 6.2a, 6.3.
  • Be sure to know the Big Oh running times of common operations on lists, stacks, queues, trees of various kinds, hashing and binary heaps.
  • Practice all the operations in binary search trees, AVL trees, splay trees, hashing, binary heaps, and binomial heaps.