Introduction to the analysis and design of algorithms. Topics include: sorting , searching, advanced tree structures, graph algorithms, network flow problems, amortized analysis, divide-and-conquer, greedy algorithms, dynamic programming, combinatorial search algorithms, computational geometry and NP-completeness.

MATH 201, MATH 207 (grade of C- or higher) and CS 219 or permission of the instructor.

Horowitz, Sahni, and Sanguthevar, Computer Algorithms, 2008, 2nd ed., CS Press

- Asymptotic Complexity
- Data Structures
- Algorithmic Techniques: Divide-and-Conquer
- Algorithmic Techniques: The Greedy Method
- Algorithmic Techniques: Dynamic Programming
- Algorithmic Techniques: Graph Traversals
- Algorithmic Techniques: Backtracking
- Algorithmic Techniques: Branch & Bound
- Lower Bound Theory
- Theory of NP-Completeness
- Network Flows

On completing this course, the student will be able to:

- Analyze the asymptotic complexity of algorithms and describe their relative performance.
- Demonstrate a familiarity with major algorithms and data structures.
- Apply algorithmic design paradigms and methods of analysis to solve computational problems.
- Synthesize algorithms that employ data structures as key components.
- Explain and analyze major graph algorithms.
- Demonstrate a familiarity with applied algorithmic settings such as computational geometry, operations research, cryptography, distributed computing, operating systems, and computer architecture.

CS 319 | Student Outcomes (SOs) | ||||||||||

Course Learning Outcomes | a | b | c | d | e | f | g | h | i | j | k |

1. Analyze the asymptotic complexity of algorithms and describe their relative performance. | |||||||||||

2. Demonstrate a familiarity with major algorithms and data structures. | ✔ | ||||||||||

3. Apply algorithmic design paradigms and methods of analysis to solve computational problems. | |||||||||||

4. Synthesize algorithms that employ data structures as key components. | |||||||||||

5. Explain and analyze major graph algorithms. | ✔ | ||||||||||

6,. Demonstrate a familiarity with applied algorithmic settings such as computational geometry, operations research, cryptography, distributed computing, operating systems, and computer architecture. | ✔ |

See the pages "BSCS Course Matrix" and "BSCS Courses for Assessment"

SO | PI | Strategy |
---|---|---|

a | a.2 | Students will use mathematical techniques to evaluate the performance of algorithms. |

j | j.1 | Students will develop different data structures to solve a problem that underlines the tradeoff between memory management and processing performance. |