CSE logo University of Washington Computer Science & Engineering
CSE326 Spring 2008
  CSE Home    326 Home   About Us    Search    Contact Info 

CSE 326
 Home
 Calendar
 Lectures
Assignments & Exams
 Projects
 Homeworks
 Midterm exam
 Final exam
Communication
 Discussion Board
 Mail to Course Staff
 Announcement Archive
Policies
 General Guidelines
 Grading Policies
 Programming Guidelines
 Written HW Guidelines
Misc
 LaTeX info
   

Final score distribution

 

Final Study Guide

   Final Exam
   10:30am - 12:20pm
   Thursday, June 12, 2008
   EEB 045
  • Exam policies
    • Closed book, closed notes.
  • Topics
    • All material from lecture up through Minimum Spanning trees is fair game.
    • This material corresponds to: Chapters: 1-9.
    • Here is a (fairly complete) summary of topics we’ve covered in lecture:
      • 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, 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.
      • Leftist Heaps and Skew 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, delete, build.
      • Splay trees - Splaying, insert, find, delete.
      • B+ trees - motivation, basic operations.
      • 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, Bubble sort, Selection sort, Shell sort, Binary tree 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. Depth-first, breadth-first search
      • Shortest paths. Dijkstra's algorithm for SSSP.
      • Minimum spanning tree: Prim’s and Kruskal’s algorithms
         
    • The focus will be on ideas/concepts about data structures and algorithms, *not* Java.
       
  • Study suggestions
    • Do concrete problems from the book and re-work problems from lecture, section, and HW.
    • 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.
       
  • Practice finals (which cover some topics that we did not):