首页 >
> 详细

Homework Written

Due 11:59 pm Friday April 2, 2021

Show the steps of deriving your answers. Points will be deducted for answers without adequate

steps discussed or not compliant with the instruction. Submit your homework via Blackboard as

one PDF or Word document. Refer to the grading guidelines posted on Blackboard to

understand how the submitted exercises will be graded.

1. (25) [Divide and conquer: majority equivalence class] Do Textbook Exercise 3 in Chapter

5. Note that the problem of finding a set of more than half the bank cards that correspond to the

same account can be reduced to finding a majority equivalence class, that is, an equivalence class

that contains more than half the set elements (i.e., bank cards). Assume that the equivalence

tester requires two cards to give a test result. Give your answers as specified below.

a) Prove the property that if there exists a majority equivalence class in the set of size n then at

least one of the two halves (each of size n/2) has a majority equivalence class. Suggested

proof technique: proof by contradiction.

b) Based on the proven property, write an executable pseudocode of the recursive algorithm

designed using the divide-and-conquer approach. Name the algorithm “MajEC”. Hint:

divide the set of bank cards into two halves and call the algorithm recursively on each half.

c) Write a recurrence relation expressing the run-time T(n) of the recursive algorithm, and solve

it to derive the run-time in big-O; it suffices to derive the closed functional form of the runtime

and do not prove the big-O formally. The recurrence relation should have both recursive

cases and base cases. Either the recursion tree technique or the telescoping technique can be

used to derive the closed functional form. If the recurrence relation is one we have already

solved in class, it is sufficient to refer to it without solving it again.

2. (25) [Integer multiplication: reading & research] Read the discussion on Integer

Multiplication algorithm using divide-and-conquer in Section 5.5 of the textbook (pages 231 –

234), and provide answers as specified below. Assume the integers multipled are binary integers.

a) Write the key idea that enables the algorithm to divide the problem into three disjoint

subproblems -- that is, to achieve the multiplication of two n-bit integers from multiplying

two n/2-bit integers three times.

b) Write the resulting divide-and-conquer algorithm in an executable pseudocode. Name the

algorithm “MultInt”. Do not copy the pseudocode in the texbook but write your own

pseudocode. Make sure to add the base case; the textbook code may not have the base case.

Make use of the following functions as needed in your pseudocode.

• MultInt(x, y, n) returns the multiplication of two n-bit integers x and y.

• Add(x, y, n) returns the sum of two n-bit integers x and y, i.e., x + y.

• Sub(x, y, n) returns the difference of n-bit integer y from n-bit integer x, i.e., x – y.

• LSL(x, b) returns x shifted to the left logically by b bits. (Logical shift left(LSL)

shifts in bit 0’s on the least significant bits.)

• LSR(x, b) returns x shifted to the right logically by b bits. (Logical shift right(LSR)

shifts in bit 0’s on the most significant bits.)

• ceil(b) returns the ceiling of b.

• floor(b) returns the floor (i.e., truncation)of b.

Note:

• Dividing (i.e., separating) an n-bit integer into the upper n/2-bit integer and the lower

n/2-bit integer can be implemented in linear time by calling logical-shift by n/2 bits

(LSL and LSR below).

• Multiplying an integer by 2n can be implemented in linear time by calling logicalshift

left by n bits.

c) Write a recurrence relation that expresses the run-time, T(n), of the recursive algorithm, and

explain how each term in the recurrence relation is formed.

d) Write the steps of solving the recurrence relation to derive the run-time complexity T(n) =

O(nlg3) (=O(n1.585)). (Here, lg3 ≡ log23.) Use the recursion tree technique to derive the runtime

complexity; make a simplifying assumption that n is a power of 2 integer. Do not use

the master theorem in Section 5.2. There is no need to give a formal proof of big-O.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28