Analysis of Algorithms

Course Description

This course builds on knowledge of elementary algorithm analysis gained in CS 3303: Data Structures, and introduces more advanced algorithms. Implementation strategies for algorithms including Brute Force, Branch and Bound, Divide and Conquer, Greedy, Linear Programming and Dynamic programming as well as techniques to analyze and evaluate the complexity of algorithms are taught. Finally the concepts of NP-complete, hard problems, impossible problems, and the halting problem will be explored. Learning Objectives and Outcomes: By the end of this course students will be able to: Articulate the characteristics and design of fundamental patterns of algorithms Implement algorithms using the Java programming language Understand the characteristics of the different algorithm designs including: Brute Force Backtracking Branch and Bound Greedy Divide and Conquer Linear Programming Dynamic Programming Asymptotically analyze algorithms Describe and discuss theoretical computer science concepts such as hard problems, NP completeness, and the halting problem. Course Schedule and Topics This course will cover the following topics in eight learning sessions, with one Unit per week. The Final Exam will take place during Week/Unit 9 (UoPeople time). Week 1: Unit 1 - Review of Data Structures and Algorithms Week 2: Unit 2 - Divide and Conquer AlgorithmsWeek 3: Unit 3 - Graphs (Part 1)Week 4: Unit 4 - Graphs (Part 2)Week 5: Unit 5 - Dynamic ProgrammingWeek 6: Unit 6 - Linear Programming and ReductionsWeek 7: Unit 7 - Limits to Computation (Part 1)Week 8: Unit 8 - Limits to Computation (Part 2)Week 9: Unit 9 - Review and Final Exam Learning Guide The following is an outline of how this course will be conducted, with suggested best practices for students. Unit 1: Review of Data Structures and Algorithms Read the Learning Guide and Reading Assignments Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum) Make entries to the Learning Journal Take the Self-Quiz Unit 2: Divide and Conquer Algorithms Read the Learning Guide and Reading Assignments Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum) Complete and submit the Programming Assignment Make entries to the Learning Journal Take the Self-Quiz Unit 3: Graphs (Part 1) Peer assess Unit 2 Programming Assignment Read the Learning Guide and Reading Assignments Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum) Complete and submit the Programming Assignment Make entries to the Learning Journal Take the Self-Quiz Unit 4: Graphs (Part 2) Peer assess Unit 3 Programming Assignment Read the Learning Guide and Reading Assignments Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum) Complete and submit the Programming Assignment Make entries to the Learning Journal Take the Self-Quiz Take the Graded Quiz Unit 5: Dynamic Programming Peer assess Unit 4 Programming Assignment Read the Learning Guide and Reading Assignments Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum) Complete and submit the Programming Assignment Make entries to the Learning Journal Take the Self-Quiz Unit 6: Linear Programming and Reductions Peer assess Unit 5 Programming Assignment Read the Learning Guide and Reading Assignments Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum) Make entries to the Learning Journal Take the Graded Quiz Take the Self-Quiz Unit 7: Limits to Computation (Part 1) Read the Learning Guide and Reading Assignments Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum) Make entries to the Learning Journal Take the Self-Quiz Unit 8: Limits to Computation (Part 2) Read the Learning Guide and Reading Assignments Participate in the Discussion Assignment (post, comment, and rate in the Discussion Forum) Make entries to the Learning Journal Take the Self-Quiz Read the Unit 9 Learning Guide carefully for instructions on the Final Exam Take the Review Quiz Complete and submit the anonymous Course Evaluation Unit 9: Course Review and Final Exam Read the Learning Guide and take the Review Quiz, if you haven't already done so Prepare for, take, and submit the Final Exam The Final Exam will take place during Week/Unit 9 (UoPeople time); exact dates, times, and other details will be provided accordingly by your instructor

Code

CS 3304

Credits

3

Subject

CS

Programs That Include This Course

• Bachelor's Bachelor of Science in Computer Science