联系方式

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

您当前位置:首页 >> CS作业CS作业

日期:2021-03-30 10:52

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.


版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp