HW2 Solution

pdf

School

University of Pennsylvania *

*We aren’t endorsed by this school

Course

5960

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by PresidentKangaroo6014

CIT 5960-Fall 2023 Module 3-4 Homework Assignment Jonathan Wan, Tuan Le, Helen Yue TOTAL POINTS 95 / 100 QUESTION 1 Q1 20 pts 1.1 4 / 4 ✓ - 0 pts Correct - 3 pts Lack of explanation - 4 pts Incorrect or no attempt - 2 pts Correct explanation but incorrect final answer 1.2 4 / 4 ✓ - 0 pts Correct - 2 pts Lack of explanation - 4 pts Incorrect or no attempt - 3 pts Correct explanation but incorrect final answer 1.3 4 / 4 ✓ - 0 pts Correct - 2 pts Lack of explanation - 4 pts Incorrect or no attempt - 2 pts Correct explanation but incorrect final answer 1.4 4 / 4 ✓ - 0 pts Correct - 2 pts Correct explanation but incorrect final answer - 3 pts Incorrect explanation but correct final answer - 3 pts Lack of explanation - 4 pts Incorrect or no attempt 1.5 4 / 4 ✓ - 0 pts Correct - 3 pts Lack of/Incorrect explanation - 1 pts Correct explanation but incorrect final answer - 4 pts Incorrect or no attempt QUESTION 2 2 Q2 23 / 25 - 0 pts Correct Algorithm (10 pts) - 10 pts Missing algorithm - 8 pts Incorrect algorithm - 6 pts Partially correct/Incomplete algorithm ✓ - 2 pts Minor errors in algorithm POC (9 pts) - 9 pts No correctness proof - 5 pts Incomplete proof (doesn't handle all cases, base case or inductive step is missing) - 2 pts Minor errors or missing justifications in proof Runtime (6 pts)

- 6 pts No runtime analysis - 4 pts Incorrect order of complexity - 2 pts Partially correct analysis (right order of complexity but missing / incorrect reasoning) Running Quickselect r times is not necessary. QUESTION 3 3 Q3 15 / 15 ✓ - 0 pts Correct Algorithm (6 points) - 6 pts Missing algorithm: - 4 pts Partially correct/Incomplete algorithm - 2 pts Minor errors in algorithm - 6 pts Wrong algorithm Correctness proof (6 points) - 6 pts No correctness proof - 3 pts Incomplete proof (doesn't handle all cases, base case or inductive step is missing) - 2 pts Minor errors or missing justifications in proof Runtime analysis (3 points) - 3 pts No runtime analysis - 2 pts Incorrect order of complexity - 1 pts Partially correct analysis (right order of complexity but missing or incorrect reasoning) QUESTION 4 Q4 20 pts 4.1 Q4.1 8 / 10 - 0 pts Correct - 10 pts Incorrect Algorithm (4 points) ✓ - 2 pts Partially correct/Incomplete algorithm - 4 pts Missing / Incorrect Correctness proof (4 points) - 4 pts Missing / Incorrect - 2 pts Incomplete proof / Minor Error Runtime analysis (2 points) - 2 pts Missing / Incorrect - 1 pts Didn't mention compute time of each indicator (max / min) - 1 pts Didn't mention a constant number of pass 2nd case is incorrect- we could have xi = xj for some teams tj ∈ S2 but yi ≥ yj for all other teams in S2 is the correct case. 4.2 Q4.2 9 / 10 - 0 pts Correct - 10 pts Incorrect / Missing Algorithm (4 pts) - 4 pts Incorrect / Missing - 2 pts Didn't recursively call on two halves (no QuickSelect) ✓ - 1 pts Didn't use (a) POC (4 pts) - 4 pts Incorrect / Missing - 1 pts Didn't reason base case - 1 pts Incorrect induction hypothesis - 2 pts Incorrect induction step Runtime (2 pts) - 2 pts Missing / Incorrect - 1 pts Cite QuickSelect runtime

- 1 pts Fail to give and solve recurrence relation QUESTION 5 5 Q5 20 / 20 ✓ - 0 pts Correct Algorithm (8 points) - 8 pts Missing algorithm: - 4 pts Partially correct/Incomplete algorithm - 2 pts Minor errors in algorithm Correctness proof (6 points) - 6 pts No correctness proof - 3 pts Incomplete proof (doesn't handle all cases, base case or inductive step is missing) - 2 pts Minor errors or missing justifications in proof - 1 pts Need a bit more details Runtime analysis (6 points) - 6 pts No runtime analysis - 4 pts Incorrect order of complexity - 2 pts Partially correct analysis (right order of complexity but missing or incorrect reasoning) - 1 pts Need a bit more details - 20 pts Incorrect or no attempt Page 3

Your preview ends here