# CS 319 Algorithm Analysis

Catalog Description:

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.

Prerequisite:

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

Credits:
3
Offered:
Second semester
Required or Elective:
Required for the BS in Computer Science
Level:
Intermediate
Coordinator:
George Dimitoglou
Current Textbook:

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

Topics covered:
• 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
Student Learning Outcomes:

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

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.
Relation of Course Outcomes to Program Outcomes:

 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. ✔
Role in Assessment:

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.

Current syllabus: CS 319 01 Algorithm Analysis Spr 16 Dimitoglou.pdf 