# 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

- Sorting and order statistics (examples follow)
- 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.

** **