ÍÃ×ÓÏÈÉú

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 or MTH 331)

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

• 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.
• Explain the significance of NP-completeness
  • Define the classes P and NP.
  • Provide examples of classic NP-complete problems.
• Describe advanced data structures and algorithms 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.
• Implement advanced data structures and algorithms
  
  • Implement dynamic programming algorithms and analyze their running times.
  • Implement greedy algorithms and analyze their running times.
  • Implement divide-and-conquer algorithms and analyze their running times.
  • Implement several advanced algorithms. Representative algorithm categories include: randomized algorithms, linear programming, string matching, and computational geometry.