Homework answers / question archive / Homework 7: Suppose k1,k2 ∈R with k1 < k2 and both having at most one digit after the decimal point

Homework 7: Suppose k1,k2 ∈R with k1 < k2 and both having at most one digit after the decimal point

Computer Science

Share With

---

Homework 7:

1. Suppose k₁,k₂ ∈R with k₁ < k₂ and both having at most one digit after the decimal point. [10 pts] Suppose every x in your list A is a real number satisfying k₁ ≤ x ≤ k₂ with x having at most one digit after the decimal point. Modify the CountingSort pseudocode so that it can manage this list. What would the Θ time complexity be?

Solution:

2. Using the list [2

   

   1] where 2, 2⁰ and 2⁰⁰ are just different versions of the numbers 2, [10 pts] demonstrate why our implementation of CountingSort is unstable. Understanding the flow of the algorithm with this example should indicate to you how CountingSort can be very simply modified to make it stable. What would this modification be? You don’t need to rewrite the entire pseudocode, just explain the change.

Solution:

3. Suppose b = 2 is the fixed base. Suppose that we have a list of length n which contains integers [10 pts] between 0 and n inclusive. Show that the RadixSort+CountingSort time complexity will be Θ(nlgn).

Solution:

4. Explain how RadixSort+CountingSort can sort n integers between 0 and n² − 1 inclusive in [15 pts] Θ(n) time with two iterations of CountingSort.

Solution:

5. Suppose that M is a fixed positive integer and suppose we have a list of length n which contains [15 pts] integers between 0 and M inclusive. Show that the RadixSort+CountingSort time complexity will be Θ

   

   .

Solution:

6. Radix sort is the method used for alphabetizing whereby the underlying sort simply sorts [10 pts] by character in some way. Don’t worry about how this underlying sort works. Show how RadixSort works on the list of words:

ANTE,ANTI,AMEX,BITE,BARK,INTO,INIT, LARK,PARK,PACK,RITE,UNTO,UNIT,ZOOT

You only need to show the result of each RadixSort loop iteration.

Solution:

7. Assume A and B are binary strings of length n and rewrite the integer addition pseuducode so [10 pts] as to remove addition and comparison and instead use logical operators and (only once) and xor (only once).

Solution:

8. The integer addition pseudocde can be rewritten to eliminate carry and instead store the [5 pts] carry pre-emptively in C. Do so.

Solution:

9. Two’s Complement: For a given binary number B the Two’s Complement of the number is [15 pts] obtained by negating all the bits and adding 1. For example the two’s complement of B=01101 is not(B)+1=10010+1=10011. For a number B with N bits if we add B and its two’s complement we always get 2^N, for example B+not(B)+1=01101+10011=100000. Consequently for A>=B we have A+not(B)+1=A+(2^N)-B=2^N+(A-B) and so we can calculate A-B by instead calculating A+not(B)+1 and ignoring the resulting leftmost digit. For example:

1011101-0110111 = 1011101+not(0110111)+1

= 1011101+1001000+1

=610100110

Write the pseudocode for this. Just for extra fun and excitement:

• • Do not use a carry bit.
  • Do not use any conditionals.
  • Use only one loop.

You can just assume the additional resulting bit will be ignored.

Solution: