CSE 521 Assignment #0
Winter 2010

Due: Thursday, January 7, 2010.

Reading Assignment: Kleinberg and Tardos Chapters 1 to 3.

Survey Questions:

1. For each of the following topics, indicate your level of comfort on a scale of 1-5, where 1 means "I've never been exposed to this" and 5 means "I'm completely comfortable and knowledgeable about this material".

   • basic graph traversal and algorithms, such as depth-first search and breadth-first search, connected components, Finding an articulation point in an undirected graph, etc.

   • Dijsktra's shortest path algorithm.

   • Minimum spanning tree algorithms (Prim's and Kruskal's).

   • Technique of divide and conquer.

   • Dynamic programming.

   • Basics of maximum flow, such as max-flow=min-cut and augmenting path algorithms.

   • Algebraic algorithms (FFT, primality testing, etc.).

   • NP-completeness reductions (e.g. SAT to clique, coloring, Hamiltonian path).

   • Randomized algorithms (what have you been exposed to here?).

   • Linear programming (definition, simplex algorithm, duality theory).

   • Approximation algorithms (of NP-hard problems).

2. What book did you use in your undergraduate algorithms course?