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

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

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

Benton Hall, Room 205

650 E. High Street

Oxford, OH 45056

501 E. High Street

Oxford, OH 45056

- Campus Map
- Directions
- Online: Miami Online

- Main Operator 513-529-1809
- Office of Admission 513-529-2531
- Vine Hotline 513-529-6400
- Emergency Info https://miamioh.edu/emergency

1601 University Blvd.

Hamilton, OH 45011

- Campus Map
- Directions
- Online: E-Campus

- Main Operator 513-785-3000
- Office of Admission 513-785-3111
- Campus Status Line 513-785-3077
- Emergency Info https://miamioh.edu/regionals/emergency

4200 N. University Blvd.

Middletown, OH 45042

- Campus Map
- Directions
- Online: E-Campus

- Main Operator 513-727-3200
- Office of Admission 513-727-3216
- Campus Status 513-727-3477
- Emergency Info https://miamioh.edu/regionals/emergency

7847 VOA Park Dr.

(Corner of VOA Park Dr. and Cox Rd.)

West Chester, OH 45069

- Main Operator 513-895-8862
- From Middletown 513-217-8862
- Emergency Info https://miamioh.edu/regionals/emergency

Chateau de Differdange

1, Impasse du Chateau, L-4524 Differdange

Grand Duchy of Luxembourg

- Main Operator 011-352-582222-1
- Email luxembourg@MiamiOH.edu
- Website https://miamioh.edu/luxembourg

217-222 MacMillan Hall

501 E. Spring St.

Oxford, OH 45056, USA

- Main Operator 513-529-8600
- Emergency Info https://miamioh.edu/emergency

© 2023 Miami University All Rights Reserved