CSE 374 Algorithms I

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.


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.