COSC 320 Assignment 2 Problems
Covering divide and conquer and recurrence relations.
January 27, 2024
This assignment is due on Friday, Feb 9 at 10pm Kelowna time on Canvas. Assignments submitted after this deadline, will receive a penalty or won’t be accepted. Please see course outline for details. Please follow these guidelines:
• We strongly recommend that you prepare your solution using LATEX, and submit a pdf file. We will accept solutions that are prepared using other good formatting systems, as long as they are clearly legible. Solutions that are handwritten or difficult to read will receive a grade of zero.
• Whenever possible, keep the solution to a subproblem on a single page, rather than having it span two pages.
• Include in question 1 below the names of each member of your team. You need to form teams, which will be recorded on Canvas. If you want an extra double-check on your identity, include your student number. Reminder: groups should include a maximum of three students; we encourage groups of two.
• Start each problem on a new page, using the same numbering and ordering as this handout.
• Submit the assignment via Canvas. Your group must make a single submission.
• If you include the problem definitions, we would also appreciate it if you could typeset your solutions in blue, as it makes it easier for TAs to find the solutions.
Before we begin, a few notes on pseudocode. Your pseudocode should communicate your algorithm clearly, concisely, correctly, and without irrelevant detail. Reasonable use of plain English is fine. You should envision your audience as a capable COSC 320 student unfamiliar with the problem you are solving. Don’t include what we consider to be irrelevant detail.
Remember also to justify/explain your answers, unless explicitly indicated otherwise. We understand that gauging how much justification to provide can be tricky. Inevitably, judgment is applied by both student and grader as to how much is enough, or too much, and it’s frustrating for all concerned when judgments don’t align. Justifications/explanations need not be long or formal, but should be clear and specific (referring back to lines of pseudocode, for example).
In this class the words “prove”, “explain”, “show” and “justify” are used interchangeably; we’re not looking for the formality that might be expected in a Math class. You don’t need to be more formal when a proof is requested, but sometimes formal notation or assertions can really help make concepts clear and unambiguous.
On the plus side, if you choose an incorrect answer when selecting an option but your reasoning shows partial understanding, you might get more marks than if no justification is provided. And the effort you expend in writing down the justification will hopefully help you gain deeper understanding and may well help you converge to the right selection :)
Ok, time to get started...
1 List of names of group members (as listed on Canvas)
Provide the list here. This is worth 1 mark. Include student numbers as a secondary failsafe if you wish.
2 Statement on collaboration and use of resources
To develop good practices in doing homeworks, citing resources and acknowledging input from others, please complete the following. Answer Yes or No to each question below. This question is worth 2 marks.
1. We used the following resources (list books, online sources, etc. that you consulted):2. One or more of us consulted with course staff during office hours.
3. One or more of us collaborated with other COSC 320 students; none of us took written notes during our consultations.
If yes, please list their name(s) here:
4. One or more of us collaborated with or consulted others outside of COSC 320; none of us took written notes during our consultations.
If yes, please list their name(s) here:
3 Solving Recurrences