Oct 26, 2021
 HELP 2020-2021 Undergraduate Academic Catalog [ARCHIVED CATALOG] Print-Friendly Page (opens a new window)

# CS 3851 - Algorithms

3 lecture hours 2 lab hours 4 credits
Course Description
This course extends the study of algorithms introduced in CS 2852. Common algorithms, algorithmic paradigms, data structures, and modeling techniques used in the design and analysis of algorithms are covered. The course emphasizes the relationship between algorithms and programming and includes multiple formal techniques for analyzing computational complexity. Students will identify or state a non-trivial computational problem, design and/or select an algorithm that solves the problem, choose among competing algorithms, and justify their decision based on computational complexity.  Laboratory activities include the implementation and comparison of problem specific algorithms. (prereq: CS 2852 , MA 262 , MA 3320 )
Course Learning Outcomes
Upon successful completion of this course, the student will be able to:
• Compare and contrast formal (e.g., proofs) and empirical (e.g., tests, benchmarks) methods for analyzing algorithms
• Interpret the formal statement of a computational problem
• Identify use of and apply algorithm design techniques such as divide and conquer and dynamic programming
• Construct correctness proofs for algorithms
• Model asymptotic time and space complexity using techniques such as recurrence relations
• Apply asymptotic complexity analysis to choose among competing algorithms
• Implement, test, and benchmark algorithms in software
• Apply algorithms involving graph and tree structures
• Describe the implications of demonstrating that a particular algorithm is NP complete
• List at least three engineering applications of algorithmic design and analysis

Prerequisites by Topic
• Big-O notation
• Java programming
• Set theory
• Recursion
• Methods of proof
• Graphs
• Trees

Course Topics
• Algorithmic analysis
• Mathematic tools
• Divide and conquer algorithms
• Greedy algorithms
• Dynamic programming algorithms
• Graph algorithms such as breadth-first and depth-first search
• NP completeness

Laboratory Topics
• Algorithmic analysis
• Divide and conquer algorithms (e.g., sorting algorithms), including writing and solving recurrence relations
• Greedy algorithms
• Dynamic programming algorithms
• Graph algorithms
• Independent research presentation

Coordinator
Dr. Ronald J. Nowling