# 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.

## 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

- Dynamic programming
- 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 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.

- 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.