Apr 18, 2024  
2020-2021 Undergraduate Academic Catalog 
    
Catalog Navigation
  Catalog Home
  Academic Calendar
  University Overview
  Admissions Department
  Academic Regulations and Policies
  Student Financial Services
  Academic Departments, Undergraduate Degree Programs, Minors and Certificates
  Degree Programs, Minors and Certificates
  University Scholars Honors Program
  Reserve Officers’ Training Corps. (ROTC)
  English as a Second Language
  Course Descriptions
  Administration, Board of Regents, Faculty and Advisory Committees
  Campus Map
  Student Resources
  My Portfolio
HELP
2020-2021 Undergraduate Academic Catalog [ARCHIVED CATALOG]

Facebook this Page (opens a new window)
Tweet this Page (opens a new window)
Add to Portfolio (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


Facebook this Page (opens a new window)
Tweet this Page (opens a new window)
Add to Portfolio (opens a new window)