5.1
5.7 Compute xy
Problem 5.7 Write a function that takes a double x and an integer y and returns xy. The time complexity should be O(n) where n is the number of bits in y. Assume addition, multiplication, and division take constant time. You cannot use any function except for those you write yourself. You can ignore overflow and underflow.
5.8 Convert base
In the decimal system, the position of a digit is used to signify the power of 10 that digit is to be multiplied with. For example, "314" denotes the numbers 3*100+1*10+4*1. (Note that zero, which is not needed in other systems, is essential in the decimal system, since a zero can be used to skip a power.) The base b number system generalizes the decimal number system: the string "ak-1ak-2 ... a1a0", where 0<=ai<b, denotes in base-b the integer a0*b0 + a1*b1 + a2*b2 + ... + ak-1*bk-1.
Problem 5.8 Write a function that performs base conversion. Specifically, the input is an integer base b1, a string s, representing an integer x in base b1, and another integer base b2; the output is the string representing the integer x in base b2. Assume 2 ≤ b1, b2 ≤ 16. Use "A" to represent 10, "B" for 11, ... and "F" for 15.
6.1 The Dutch national flag program
The quick sort algorithm for sorting arrays proceeds recursively --
it selects an element x (the "pivot"), reorders the array
to make all the elements less than or equal to x appear first,
followed by all the elements greater than x. This is known as the
Dutch national flag partitioning, because the Dutch national flag consists of
three horizontal bands, each in a different color.
Assuming that black precedes white and white precedes gray, Figure 6.1(b) on the next page is a valid partitioning for Figure 6.1(a) on the following page. If gray precedes black and black precedes white, Figure 6.1(c) on the next page is a valid partitioning for Figure 6.1(a) on the following page.
When an array consists of entries from a small set of keys, e.g., (0, 1, 2), one way to sort it is to count the number of occurrences of each key. Consequently, enumerate the keys in sorted order and write the corresponding number of keys to the array. If a BST is used for counting, the time complexity of this approach is O(n log k), where n is the array length and k is the number of keys. This is known as counting sort.
Counting sort, as just described, does not differentiate among different objects with the same key value. The current problem is concerned with a special case of counting sort when entries are objects rather than keys.
Problem 6.1 Write a function that takes an array A of length n and an index i into A, and rearranges the elements such that all elements less than A[i] appear first, followed y elements equal to A[i], followed by elements greater than A[i[]. Your algorithm should have (1) space complexity and O(n) time complexity.
A robot needs to travel along a path that includes several ascents and descents. When it goes up, it uses its battery to power the motor and when it descends, it recovers the energy which is stored in the battery. The battery recharging process is ideal: on descending, every Joule of gravitational potential enery converts to a Joule of electrical energy which is stored in the battery. The battery has a limited capacity and once it reaches this capacity, the energy generated in descending is lost.
Problem 6.8 Design an algorithm that takes a sequence of n three-dimensional coordinates to be traversed, and returns the minimum battery capacity needed to complete the journey. The robot begins with the battery fully charged.
Problem 6.16 Let A be an array whose entries re all distinct. Implements an algorithm that takes A and an integer k and returns a subset of k elements of A.All subsets should be equally likely. Use as few calls to the random number
An n X n 2D array A of integers can be written as a sequence of integers in several orders -- the most natural ones being row-by-row or column-by-column. In this problem we explore the problem of writing the 2D array in spiral order. For example, the answer of the 2D array in Figure 6.3 [...] should be "1 2 3 6 9 8 7 4 5".
Problem 6.22 Implement a function which takes a 2D array A and prints A in spiral order.
A string is a sequence of characters. A string may encode an integer, e.g., "123"
encodes 123. In this problem, you are to implement methods that take a string
representing an integer and return the corresponding integer, and vice versa. Your
code should handle negative integers. You cannot use library functions like
stoi in C++ and parseInt in Java.
Problem 7.1 Implement string/integer inter-conversion functions.
Consider the following two rules that are to be applied to strings over the alphabets {"a", "b", "c", "d"}.
Problem 7.2 Write a function which takes as input a string s, and removes each "b" and replaces each "a" by "dd". Use O(1) additional storage -- assume s is stored in an array that has enough space for the final result.
Each digit, apart from 0 and 1, in a phone keypad corresponds to one of three or found letters of the alphabet, as shown in Figure 7.1. Since words are easier to remember than numbers, it is natural to ask if a 7 or 10-digit phone number can be represented by a word. For example, "2276696" corresponds to "ACRONYM" as well as "ABPOMZN".
Problem 7.5 Write a function which takes as input a phone number, specified as a string of digits, return all possible chaacte sequences that correspond to the phone nmber. The cell phone keypad is specified by a mapping M tha ttakes a digit and returns the corresponding set of charactes. The character sequences do not have to be legal words or phrases.