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:

1. Articulate the characteristics and design of fundamental patterns of algorithms
2. Implement algorithms using the Java programming language
3. Understand the characteristics of the different algorithm designs including:
4. Brute Force
5. Backtracking
6. Branch and Bound
7. Greedy
8. Divide and Conquer
9. Linear Programming
10. Dynamic Programming
11. Asymptotically analyze algorithms
12. 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 Algorithms

Week 3: Unit 3 – Graphs (Part 1)

Week 4: Unit 4 – Graphs (Part 2)

Week 5: Unit 5 – Dynamic Programming

Week 6: Unit 6 – Linear Programming and Reductions

Week 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