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 1 repeat of each C S undergraduate course (all 100-, 200-, 300- or 400-level courses). This includes all students who received any grade including those who withdraw (receive a "W" grade) from a C S course. Students must wait 1 semester/term before being allowed to take a course they have failed twice. Petitions for exceptions to the policy can be completed at cs.byu.edu/undergraduate-handbook/retake-policy-cs-courses/. |
| 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.