Algorithms, covering basic analysis techniques, basic design techniques (divide-and-conquer, dynamic programming, greedy), basic and advanced graph algorithms, and NP-completeness theory.
Additional Requirements for Graduate Students: Graduate students will have additional problems in their homework assignments and exams.
Athena Title
Algorithms
Prerequisite
(CSCI 2720 or CSCI 2725) and (CSCI 2670 or CSCI 2670E)
Semester Course Offered
Offered every year.
Grading System
A - F (Traditional)
Student Learning Outcomes
By the end of this course, students will be able to analyze time complexity for algorithms using asymptotic notation.
By the end of this course, students will be able to apply various sorting and selection algorithms and determine which algorithm to apply for different types of data.
By the end of this course, students will be able to apply advanced design and analysis techniques, including greedy and dynamic programming techniques.
By the end of this course, students will be able to analyze and prove properties for various graph algorithms.
By the end of this course, students will be able to choose (and/or apply) the appropriate algorithm to solve real-world problems and defend the selection (integrated into the above outcomes).
By the end of this course, students will be able to describe decision problems and prove problems are in P.
By the end of this course, students will be able to prove a problem is in NP, co-NP, or NP-complete.
Topical Outline
Analyze complexity of algorithms.
a. Analysis of recursive algorithms using recursion trees.
b. Analysis of recursive algorithms using substitution method.
c. Analysis of recursive algorithms using Master theorem.
Apply various sorting and selection algorithms and determine which algorithm to apply for different types of data.
a. Provide runtime analysis of various sorting algorithm including heapsort, quicksort, counting sort, and radix sort.
b. For a given type of input data, determine the best choice of sorting algorithm.
c. Prove the O (n lg n) lower bound for comparison-based sorting algorithms.
Advanced design and analysis techniques, including greedy algorithms and dynamic programming.
a. Design and prove the optimality of greedy algorithms.
b. Design dynamic programming algorithms, including solution recurrence formulation, iterative, bottom-up design, and development of trace-back subroutines.
Analyze and prove properties for various graph algorithms.
a. Depth-first search and breadth-first search.
b. Minimum spanning tree.
c. Single-source shortest path and all-pairs shortest path.
d. Network flow – max flow / min cut.
Choose (and/or apply) the appropriate algorithm to solve real-world problems and defend the selection.
a. Select between various sorting algorithm for different data scenarios and justify selection.
b. Select between using a greedy strategy or dynamic programming for optimization problems.
c. Select appropriate graph algorithm for a given graph-related question.
d. Derive a graphical representation for a real-world problem and solve the problem using graph properties.
Describe decision problems and prove problems are in P.
a. Describe decision problems.
b. Prove a problem is in P by providing a deterministic decider.
Prove a problem is in NP, co-NP, or NP-complete.
a. Prove a problem is in NP by providing a verifier or a nondeterministic decider.
b. Prove a problem is NP-Complete by providing a polynomial time reduction from a known NP-Complete problem.
c. Describe the Cook-Levin Theorem proving SAT is NP-Complete.
