Steam-powered Turing Machine University of Washington Computer Science & Engineering
 CSE326 Summer 2006
  CSE Home     326 Home  About Us    Search    Contact Info 

Administrative
 Home
 Message Board
 Annoucement ArchiveCSE only
 Class List ArchiveCSE only
 Anonymous Feedback
 Mail Instructor & TAs
Lectures
 Calendar & Slides
 Midterm Study Guide
Projects
 Project 1
 Project 2 Phase A
 Project 2 Phase B
 Project 2 Phase C
 Project 3
Homework
 Homework 1
 Homework 2
 Homework 3
 Homework 4
 Homework 5
 Homework 6
 Homework 7
 Homework 8
Policies
 General Guidelines
 Grading Policies
 Programming Guidelines
 Writeup Guidelines
Computing
 Unix Basics
   

Midterm Study Guide

Midterm Exam, Monday, July 17, 2006

  • Exam policies
    • Closed book, closed notes. No cheating.
    • The exam begins promptly at 9:40 and ends at 10:40.
  • 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, amortized complexity.
    • Trees – definitions
    • Binary Heaps, D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
    • Binomial Queues - Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease.
    • Dictionary ADT
    • Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
    • AVL trees - Single and double rotations, insert, find.
    • Splay trees - Splaying, insert, find.
    • B trees - Motivation, choice of M and L.
    • Disjoint Union/Find - Up-trees. Weighted union (union by size) and path compression.
  • Study suggestions
    • Do concrete problems from the book and re-work problems from lecture, section, and homeworks. Suggestions of 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.8, 4.22, 4.27, 4.28. Chapter 6: 6.2, 6.3, 6.30.
    • Selected solutions to practice problems. Please note that some of the figures end up on the last page.
    • Practice all the operations in binary heaps, binomial queues, binary search trees, AVL trees, splay trees, and disjoint sets. Practice analysis of algorithms.
    • All material from lecture up through Disjoint Sets is fair game. This material corresponds to: Chapters: 1, 2, 3, 4, 6 (not including 6.6 and 6.7), and 8 (not including 8.6).


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to gyngve]