CSE 464/564 Algorithms (3 credits)

Catalog Description:

Review of basic data structures and algorithms. Analysis of algorithms. Problem assessment and algorithm design techniques. Algorithm implementation considerations. Concept of NP-completeness. Analysis of algorithms selected from topics relevant to computer science and software engineering (sorting, searching, string processing, graph theory, parallel algorithms, NP-complete problems, etc.)

Prerequisites:

CSE 274 /CSE 606 or equivalent and Discrete Math (MTH 231).

Required topics (approximate weeks allocated):

  • Mathematical foundations (2-3)
    • asymptotic complexity
    • recurrence relations
    • analysis of loops
    • analysis of recursion
  • Program correctness (1)
  • Probabilistic analysis and randomized algorithms (1)
  • Advanced data structures (2-3)
    • Hash tables
    • Red-black trees
  • Some selection of algorithms from at least 6 of the following categories. (6 weeks)
    • Sorting and order statistics (examples follow)
      • HeapSort
      • Quicksort
      • Sorting in linear time
      • Median and order statistics
    • Dynamic programming (examples follow)
      • Matrix-chain multiplication
      • Longest common subsequences
    • Greedy algorithms (examples follow)
      • Activity selection
      • Huffman coding
      • Fractional Knapsack
    • Amortized analysis
    • Graph algorithms (examples follow)
      • Breadth-first and depth-first search
      • Topological search
      • Minimum spanning trees: Kruskal and Prim algorithms
      • Dijkstra's shortest path algorithm
      • Maximum flow: Ford-Fulkerson algorithm
    • Polynomials and FFT
    • Number-theoretic algorithms
    • String matching (examples follow)
      • Rabin-Karp
      • Knuth-Morris-Pratt
    • Computational Geometry
  • NP-completeness (2)
    • Polynomial time
    • Polynomial-time verification
    • NP-completeness and reducibility
    • NP-completeness proofs
    • NP-completeness problems

Graduate students: Students enrolled in CSE 564 will be given additional readings and/or assignments.

Learning Outcomes:

1: Design an appropriate algorithm or data structure to solve a real problem.

1.1: The student can describe use of, and performance characteristics of, some self- balancing tree structure (i.e. red-black trees, AVL trees, B-trees, etc…)

1.2: The student can design greedy algorithms, analyze their running times, and prove their correctness. Algorithms to be discussed include Huffman coding and Fractional knapsack

1.3: The student can describe and analyze the following advanced algorithms: Linear time sorts like radix- and counting-sort; Exponentiation by repeated squaring; Some graph algorithm (.e.g. topological sort, network flow, or all-pair shortest path)

1.4: The student can design divide-and- conquer algorithms and analyze their running times. Algorithms to be discussed include: Binary Search; Quicksort and Mergesort; Linear- time median.

1.5: The student can design dynamic programming algorithms and analyze their running times. Algorithms to be discussed include: Longest common subsequence or sequence alignment; 0-1 Knapsack.

2: Characterize those problems that are unlikely to have an efficient solution.

2.1: The student can define the complexity classes P, NP, NP-Hard, and NP-Complete.

2.2: The student can define the concept of a polynomial-time verifier, and explain its usefulness in proving problems to be in NP.

2.3: The student can define the concept of a polynomial-time reduction, and explain its usefulness in proving problems to be NP-Hard.

2.4: The student can identify and define the most well-known NP-Complete problems, including: 0-1 Knapsack and subset-sum; 3-SAT and circuit-sat; Traveling salesperson and Hamiltonian path; Graph coloring; Vertex cover and independent set; Subgraph- isomorphism.

2.5: The student can prove problems to be NP-Hard by selecting an appropriate known NP- Hard problem and producing a poly-time reduction.

2.6: The student can describe the history and importance of the P vs. NP problem, and explain why NP-Hard problems are thought not to have efficient solutions.

2.7: The student can explain why the dynamic programming algorithm for 0-1 Knapsack does not count as polynomial time.

3: Use algorithms research literature to find research related to a real problem.

3.1: The student can perform a literature search about an algorithmic problem.

3.2: The student can read and critique scholarly articles.

3.3: The student can synthesize the results of a literature search to create a survey of an algorithms research area.

3.4: The student can implement an algorithm from a scholarly article.

3.5: The student can define plagiarism, and analyze case studies to identify cases of intellectual fraud.

4: Characterize the performance of a proposed algorithm or data structure.

4.1: The student can analyze both recursive and nonrecursive algorithms, deriving a function that expresses their running times.

4.2: The student can solve recurrence relations using mathematical induction.

4.3: The student can formally define the asymptotic notations: Ο, Θ, and Ω

4.4: The student can compare running time functions using asymptotic notation.

4.5: The student can explain the differences between worst-case analysis, average-case analysis, and amortized analysis. The student can explain why best-case analysis is not useful.