Catalog description:

Design, analysis and implementation of algorithms and data structures. Dynamic programming, brute force algorithms, divide and conquer algorithms, greedy algorithms, graph algorithms, and red-black trees. Other topics include: string matching and computational geometry.

Prerequisites:

CSE 274 and MTH 231

Required topics (approximate weeks allocated):

• Mathematical foundations (2)
  • Asymptotic complexity
  • Analysis of loops
  • Analysis of recursion
  • Recurrence relations
• NP-completeness (0.5)
  • P vs NP
  • Example NP complete problems
  • Brute force algorithms
• Advanced data structures (3)
  • A technique of self-balancing trees (e.g., red-black trees, 2-3 trees, B-trees)
  • At least two additional topics in advanced data structure. Some representative topics:
  • Augmenting for determining order statistics
  • Skip lists
  • Fibonacci heaps
  • Quadtree
  • Additional techniques for maintaining balanced trees
• Advanced algorithms (7.5)
  • Dynamic programming
    • Characteristics of dynamic programming solutions.
    • Applications (e.g., matrix-chain multiplication, longest common subsequences).
  • Greedy algorithms
    • Characteristics of greedy algorithm solutions.
    • Applications (e.g., Huffman coding, fractional knapsack).
  • Graph algorithms
    • Review of: breadth-first and depth-first traversals, Dijkstra's shortest path algorithm, topological sort, adjacency matrix, adjacency list.
    • All-pairs shortest path.
    • Minimum spanning trees: Kruskal and Prim algorithms
    • Maximum flow: Ford-Fulkerson algorithm
  • Divide and conquer
    • Characteristics of divide and conquer solutions.
    • Review of: binary search, quicksort, merge sort
    • Applications (e.g., Strassen’s algorithm) 
  • At least two additional topics in advanced algorithms. Some representative topics:
    • Probabilistic analysis and randomized algorithms
    • Polynomials and FFT
    • Linear programming
    • Number-theoretic algorithms
    • Parallel algorithms
    • String matching: Rabin-Karp and Knuth-Morris-Pratt algorithms
    • Computational Geometry: convex hull, closest pair of points, line intersection
• Exams (1)

Course Outcomes

1. Characterize the runtime and storage requirements of a proposed algorithm or data structure.
   • Determine the time and space complexity of simple algorithms.
   • Explain what is meant by “best”, “expected”, and “worst” case behavior of an algorithm.
   • State the formal definition of Ο, Θ, and Ω and how these describe the amount of work done by an algorithm.
   • List, compare, and contrast standard complexity classes. 
   • Use big O notation formally to give asymptotic upper bounds on time and space complexity of algorithms. 
   • Use recurrence relations to determine the time complexity of recursive algorithms.
2. Explain the significance of NP-completeness.
   • Define the classes P and NP.
   • Provide examples of classic NP-complete problems.
3. Describe and implement advanced data structures and identify the computational problem that they solve.
   • Describe and implement advanced data structures and identify the computational problem that they solve.
   • Describe the operation of, and performance characteristics of, several advanced data structures such as: 2-3 trees, B-trees, skip lists, Fibonacci heaps, and quadtrees.
4. Describe and implement advanced algorithms and identify the type of problems that they can be applied to.
   • Describe and implement dynamic programming algorithms and analyze their running times.
   • Describe and implement greedy algorithms and analyze their running times.
   • Describe and implement divide-and-conquer algorithms and analyze their running times.
   • Describe and implement several advanced algorithms. Representative algorithm categories include: randomized algorithms, linear programming, string matching, and computational geometry.