Recurrence relations, combinatorics, recursive algorithms, proofs of correctness.
Prerequisites or Corequisites
CS 261 with C or better and (CS 225 [C] or MTH 231 [C])
Please post all course-related questions in the Q&A Discussion Forum so that the whole class may benefit from our conversation. Please contact the instructor or TA privately for
matters of a personal nature, who will reply to course-related questions within 24 hours during business hours on weekdays, as well as return your assignments and grades for course activities to you within five days of the due date.
If you experience any errors or problems while in your online course, contact 24-7 Canvas Support through the Help link within Canvas. If you experience computer difficulties, need help downloading a browser or plug-in, or need assistance logging into a course, contact the IS Service Desk for assistance.
Most of the material is on the canvas site. For a few sections you would refer to the following resources. Additionally, you would use these resources for the optional readings.
Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein, 3rd Edition.
The ebook is available at
The programming assignments needs to be submitted in Python language. Python language can be learnt or revised at: https://openbookproject.net/thinkcs/python/english3e/ Or https://www.pythoncheatsheet.org/
Note: Check with the OSU Beaver Store for up-to-date information for the term you enroll (OSU Beaver Store website). If you purchase course materials from other sources, be very careful to obtain the correct ISBN.
Measurable Student Learning Outcomes
1. Prove the correctness of algorithms using induction.
2. Define O, Ω, and θ in a rigorous way.
3. Solve simple recurrence relations.
4. Implement a recursive algorithm to solve a simple problem.
5. Implement a divide-and-conquer algorithm to solve a problem of intermediate difficulty.
6. Implement a polynomial-time heuristic algorithm to solve an NP-hard problem.
7. Explain how a problem is shown to be NP-complete.
8. Compute the time complexity of polynomial-time and exponential-time iterative and recursive algorithms.
9. Design dynamic programming algorithms and analyze their running time.
Evaluation of Student Performance
• Assignments: 120 points
• Quizzes: 70 points
• Discussions: 35 points
• Midterm Exam: 50 points
• Final Exam: 60 points
• Bonus:3 points
o Homework: Graph Algorithms : 3 point
Grade Percent Range
A+网课™ 支持PayPal, WechatPay, AliPay等各种付款方式!
E-mail: email@example.com 微信:apluswk