Comp 215 Programming Project: Implementations and Reflections of
Divide and Conquer Algorithms
Introduction
Your goal for this project is to study and implement several divide and
conquer algorithms that often come up in job interviews. For each
problem you select, you will first
be asked to come up with your own solution, then compare that with a
known solution, and implement the known solution in either Java or
Python. After completing the implementations, you will write a
reflection discussing what you learned.
Program Details
You are welcome to use
either Java or Python for this project. If you insist on using a
language other than one of these two, you must have instructor approval
before starting the project.
You may discuss the algorithms to solve the problems in these exercises with classmates, but
the implementations and reflections should be your own work. You
must include an acknowledgement of any discussion collaborators in
your documentation.
Regardless of the programming language you use, you are expected to turn
in well structured, well documented code. For guidance, you can refer
to the CS Program Style Guide and
CS Program Documentation Standards.
The specifics will obviously vary from one language to the next, but
these standards should give you a starting point.
Part 1: Algorithms and Programming
Read through the introduction and sections 4 and 5 of the article "50
divide and conquer interview questions [easy, medium, hard]".
For each of sections 1, 2, and 3 (easy, medium, and hard divide and
conquer questions), select one problem that interests you. For each
problem you select, complete the following:
- Read through
the problem and come up with a solution of your own that uses the divide
and conquer strategy. Write your solution in words/pseudocode.
- Look at the solution provided and compare with what you did. Explain
any differences between your solution and the solution you looked
at.
- Implement the given solution. Make sure to run the code with a good
set of test cases. Think about what the average cases are and what your
boundary cases would be.
Part 2: Reflections
After completing Part 1, think about and reflect on the following:
- How does the divide and conquer approach work? What types of
problems does it apply to?
- What did you learn about the divide and conquer approach when
applying it to the questions you selected? What was obvious, or
straightforward? What difficulties did you encounter with the
algorithm?
- What did you learn about programming? Did you attempt to write
code from your solution(s) or did you code the solution that was
provided? What went well? What issues did you encounter?
Your reflection should be at least a couple of paragraphs. A page or
more would not be unrealistic. You should think about what you learned
and how things went before you jump into writing. Use complete
sentences and correct grammar.
Handing In
There are two separate due dates for Part 1 and Part 2.
For Part 1, you should submit a zip file on Kit that contains the
following:
- A document describing the questions you chose and your
pseudocode.
- Any code files you created. Code should be well-documented.
For Part 2 you should submit a pdf file on Kit with your reflection.
Grading Criteria
Grades on this project will be broken down as follows:
| Part 1: Question descriptions and pseudocode: | 4 |
| Part 1: Implementations: | 4 |
| Part 2: Reflection: | 4 |
| Total: | 12 |
This page is maintained by Pamela Cutter pcutter{at}kzoo{dot}edu.
Official Disclaimer