Learning Outcomes:

CSA464.1:  The student should be able to characterize the performance of a proposed algorithm or data structure.
CSA464.1.1  The student can analyze both recursive and non-recursive algorithms, deriving a function that expresses their running times.
CSA464.1.2  The student can solve recurrence relations using mathematical induction.
CSA464.1.3  The student can formally define the asymptotic notations: Ο, Θ, and Ω
CSA464.1.4  The student can compare running time function using asymptotic notation.
CSA464.1.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.

CSA464.2:  The student should be able to select an appropriate algorithm or data structure to solve a real problem.
CSA464.2.1  The student should be able to describe use of, and performance characteristics of, some self-balancing tree structure (i.e. red-black trees, AVL trees, B-trees, etc…)

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

CSA464.2.3  The student should be able to design greedy algorithms, analyze their running times, and prove their correctness. Algorithms to be discussed include:

• Huffman coding
• Fractional knapsack

CSA464.2.4  The student should be able to design divide-and-conquer algorithms and analyze their running times. Algorithms to be discussed include:

• Binary search
• Quicksort and Mergesort
• Linear-time median

CSA464.2.5  The student should be able to design dynamic programming algorithms and analyze their running times. Algorithms to be discussed include:

• Longest common sub-sequence or sequence alignment
• 0-1 Knapsack

CSA464.3: The student should be able to characterize those problems that are unlikely to have an efficient solution.
CSA464.3.1  The student should be able to define the complexity classes P, NP, NP-Hard, and NP-Complete.
CSA464.3.2  The student should be able to define the concept of a “polynomial-time verifier,” and explain its usefulness in proving problems to be in NP.
CSA464.3.3  The student should be able to define the concept of a “polynomial-time reduction,” and explain its usefulness in proving problems to be NP-Hard.
CSA464.3.4  The student can 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

CSA464.3.5  The student should be able to prove problems to be NP-Hard by selecting an appropriate known NP-Hard problem, and producing a poly-time reduction.
CSA464.3.6  The student should be able to describe the history and importance of the P vs. NP problem, and explain why NP-Hard problems are thought not have efficient solutions.
CSA464.3.7  The student should be able to explain why the dynamic programming algorithm for 0-1 Knapsack does not count as “polynomial time.”

CSA464.4: The student should be able to use the algorithms research literature to find research related to a real problem.
CSA464.4.1  The student should be able to perform a literature search about an algorithmic problem.
CSA464.4.2  The student should be able to read and critique scholarly articles.
CSA464.4.3  The student should be able to synthesize the results of a literature search to create a survey of an algorithms research area.
CSA464.4.4  The student should be able to implement an algorithm from a scholarly article.
CSA464.4.5  The student should be able to define “plagiarism,” and analyze case studies to identify cases of intellectual fraud.