CSE logo University of Washington Computer Science & Engineering
 CSE 326 Winter 2010
  CSE Home    326 Home   About Us    Search    Contact Info 

Assignments & Exams
 Projects
 Written Homeworks
 Midterm Exam
 Final Exam
Administrative
 Home
 Annoucement ArchiveCSE only
 Message Board
 Anonymous Feedback
Lectures
 Calendar & Slides
Handouts
 First Day Handout
Policies
 General Guidelines
 Grading Policies
 Programming Guidelines
 Written HW Guidelines
Computing
 Unix Basics
 LaTex Info
   

Final Exam Study Guide

Final Exam: 2:30-4:20pm, Tuesday, March 16, 2010

  • Exam policies
    • The exam will be held in our regular lecture room (EEB 125)
    • Closed book, closed notes.
    • The exam begins promptly at 2:30 and ends at 4:20.
  • Topics
    • All material from lecture is fair game, although you can assume that material you have not been tested on yet (post-midterm material) will be emphasized a bit more.
    • This material corresponds to: Chapters: 1-9, and 10.3.4
    • Here is a (fairly complete, but not exhaustive) summary of topics we've covered in lecture that are fair game for the exam:

      Pre-Midterm:

      • Linked lists. Simple linked lists, doubly linked lists, circularly linked lists.
      • Stacks and Queues, array and list implementations.
      • Recursion. Designing algorithms recursively.  Inductive proof.
      • Asymptotic analysis, Big-O. Worst, amortized (just the idea), average, best cases.  Upper and lower asymptotic bounds.  Analyzing loops, recurrences.
      • Trees - definitions
      • Binary Heaps, D-heaps - Findmin, Deletemin, Insert. Additional operations of increaseKey, decreaseKey, buildHeap.
      • Skew Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey
      • Leftist Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey
      • Binomial Queues - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey.
      • Dictionary ADT
      • Binary search trees - Inorder, preorder, postorder traversals, insert, delete, find, build.
      • AVL trees - Single and double rotations, insert, find, (no delete), build.

      Post Midterm:

      • Splay trees - Splaying: zig, zig-zig, and zig-zag rotations, insert, find, (no delete).
      • The memory hierarchy. Temporal and spatial locality. Data structure choice and the memory hierarchy.
      • B trees - motivation, choice of M and L, basic operations of find, insert, delete.
      • Hashing. Properties of good hash functions. Selecting hash table size. Separate chaining and open addressing. Linear Probing, Quadratic Probing, & Double Hashing to resolve collisions. Rehashing.
      • Sorting. Insertion sort, Selection sort, Heap sort, Merge sort, quicksort. In-place sorting. Stable sorting.
      • Bucket sort, Radix sort.
      • Lower bound on comparison sorting.
      • Disjoint Union/Find - Up-trees. Weighted union (union by size) and path compression.
      • Graphs. Directed and undirected. Adjacency list and adjacency matrix representations. Edge and vertex complexities.
      • Topological sorting.
      • Graph searching (just the ideas on these - don't have to be able to execute). Depth-first, breadth-first, best-first.
      • Shortest paths: Dijkstra's algorithm for SSSP, Floyd-Warshall for APSP
      • Minimum spanning tree: Prim's and Kruskal's algorithms
      • Huffman Coding will only appear as an extra credit question.
    • The focus will be on ideas/concepts about data structures and algorithms, not Java. Although you could be asked to write short bits of Java or pseudo code.
       
  • Study suggestions
    • Do concrete problems from the book and re-work problems from lecture and homework.
    • Practice all the operations on the data structures.
    • Practice analysis of algorithms.  Learn and be able to reason about the complexities of operations on the data structures we've discussed in class.
    • Try practice finals.
    • Review the practice midterms.
       
  • Practice finals (which cover some topics that we did not):


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