CSE 373 Winter 2006

Final Exam Topics

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. The exam will be biased towards topics covered since the second midterm, but is likely to include earlier material - particularly the relationships between earlier topics and more recent ones. You are still responsible for topics from the midterm exams, even if they aren't covered extensively on this one.

• 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 Dijkstra's and Prim's algorithms - both how the algorithms work and how to analyze their runtimes
• Understand operations and implementations of priority queues
• 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