Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
EECS 376: Homework 2 Fall 2024
This homework has 10 questions, for a total of 100 points and 8 extra-credit points.
Unless otherwise stated, each question requires clear, logically correct, and sufficient justification to convince the reader.
For bonus/extra-credit questions, we will provide very limited guidance in office hours and on
Piazza, and we do not guarantee anything about the dificulty of these questions.
We strongly encourage you to typeset your solutions in IATEX.
If you collaborated with someone, you must state their name(s). You must write your oun solution for all problems and may not use any other student 's write-up.
(0pts) 0. Before you start; before you submit.
(a) Before starting this assignment, carefully read Handout 3 about“giving an algorithm," and follow it in your solutions.
(b) Correctness arguments and runtime analysis for divide-and-conquer/recursive algorithms should follow the recommended structure described in this week's discussion worksheet.
(c) If applicable, state the name(s) and uniqname() of your collaborator(s).(10 pts) 1. Self assessment.
Carefully read and understand the posted solutions to the previous homework. Identify one part for which your own solution has the most room for improvement (e.g., has unsound reasoning, doesn't show what was required, could be significantly clearer or better organized, etc.). Copy or screenshot this solution, then in a few sentences, explain what was deficient and how it could be fixed.
(Alternatively, if you think one of your solutions is significantly better than the posted one, copy it here and explain why you think it is better.)
If you didn't do last week's homework, choose a problem from it that looks challenging to you, . and in a few sentences, explain the key ideas behind its solution in your own words.
(6pts) 2. Confirming Karatsuba.
Apply Karatsuba's key insight to multiply the numbers (represented in decimal) 24 159032 and 39551414. Spifcally, fill in the followving table, following the definitions from lecture. You may use a calculator to compute M1, M2, M3 from XL, XR, YL, YR and perform additions and subtractions, but you may not directly multiply X . Y using a calculator. Apply Karatsuba's insight just once, i.e, do not calculate the products recursively.