Algorithm Design and Analysis
Algorithm Design and Analysis
A study of the design and analysis of algorithms as solutions to problems, including dynamic programming, linear programming, greedy algorithms, divide-and-conquer algorithms, graph algorithms, and intelligent search algorithms.
| Hours | 3.0 Credit, 3.0 Lecture, 0.0 Lab |
| Prerequisites | C S 240 |
| Note | Students are allowed only 1 retake of C S 312. This includes students who have failed or withdrawn (received a "W" grade). If after 1 retake, a student needs to retake the course again, the student must wait 1 semester/term before being allowed to take any C S course and must follow the petition process at cs.byu.edu/retake-policy. This policy does not apply to classes dropped before the add/drop deadline. Petitions for exceptions to the policy can be completed at cs.byu.edu/retake-policy. |
| Taught | Fall, Winter |
| Programs | Containing C S 312 |
Course Outcomes:
Fundamental Computer Algorithms
The student understands fundamental computer algorithms that can be organized in the following algorithmic paradigms: dynamic programming, linear programming, greedy algorithms, divide-and-conquer algorithms, graph algorithms, intelligent search algorithms, and --to a lesser degree--randomized algorithms. As an algorithmic problem solver, the student can formulate novel or unfamiliar problems in mathematical terms so as to elucidate a given problem's relation to known problems, choose a paradigm for solving the problem, and design an algorithm to solve the problem.
Analysis
The student can analyze algorithms belonging to those algorithmic paradigms for their asymptotic worst-case behavior in terms of time and space. Furthermore, the student can analyze algorithms empirically (under simplifying assumptions) and understands the relationship of empirical analysis to average-case behavior. Also, the student can solve LTI difference equations (with geometric forcing functions and change of variable) and can use them to analyze the efficiency of recursive algorithms.
Efficiency
The student can make the distinction between problems and their algorithmic solutions. Moreover, the student can distinguish between efficient and inefficient solutions and can relate these distinctions to the complexity classes of problems, namely P, NP, and NP-Complete learned earlier in the curriculum (CS 252).
Correctness
The student can prove the correctness of a subset of the algorithms considered in the course.
Implementation
The student can independently implement selected algorithms in the context of motivating applications using C# with the Visual Studio IDE.