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

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