CSE 373 Winter 2007

Final Exam Topics

The final exam is cumulative, although a bit more weight will be given to topics covered since the midterm. You are responsible for everything covered in lecture and on the homework during the quarter. You are not responsible for any specific readings in the book, but you should be familiar with the material in the book relevant to these topics.

You may bring to the exam the 4x6" or smaller index card you had at the midterm, plus one new 4x6" or smaller card with whatever notes you find useful. Otherwise the exam is closed book, closed notes, etc.

• Be comfortable describing algorithms and data structures conceptually using pictures or diagrams, as well as implementing specific details using Java. Concentrate on the ideas - don't memorize code, but be able to work that out as needed.
• Know graph terminology and vocabulary, including concepts like path lengths, cycles, minimum spanning trees, etc.
• Understand alternative representations of graphs and be able to reason about the tradeoffs between them; in particular adjacency lists and adjacency matrices
• Be able to formulate problems as graph problems (or other data structures, for that matter) - picking appropriate representations and algorithms
• Know depth first search (DFS) and breadth first search (BFS), both on general graphs and more restricted data structures like trees
• Be able to use DFS and BFS to solve specific problems, for example finding cycles
• Know how a topological sort of a graph works and how to implement it
• Know Dijkstra's, Prim's, and Kruskal's algorithms - both how the algorithms work and how to analyze their runtimes
• Understand operations and implementations of priority queues
• Understand how binary heaps work, both as an implementation technique for priority queues and as a data structure in their own right.
• Basics of union/find algorithms, including weighted merge and path compression on find.
• Be able to explain the notions of greedy and divide-and-conquer algorithms
• Know the basics of sorting and searching, particularly being able to discuss the implementations and runtime costs of algorithms like Quicksort and/or Mergesort. Why are these O(n log n) normally? What are the worst cases? How do they compare to algorithms like insert and selection sort?
• Be able to discuss tradeoffs between different choices of data structures and algorithms to solve specific problems