CLRS 3e 2.1-4

2.1-4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1)-element array C. State the problem formally and write pseudocode for adding the two integers.

A = n bit binary array

B = n bit binary array

C= n+1 bit binary array

1:        sum=0  
2:        for i = 1 to n   
3:           sum = sum+A[i] + B[i]   
4:           C[i]=sum%2  
5:           sum=sum/2  
6:        C[n+1]=sum  

The way we do overflows with integers is using the base 10.  Modulo by 10 gives the last digit after adding.  Division by 10 gives the carry over.  For binary numbers, the same applies with base 2.

If we add 2 binary numbers A = 11 (number 3) and B = 11 (number 3) we get C = 110 (number 6)

CLRS 3e 2.1-3

2.1-3 Consider the searching problem:

Input: A sequence of n numbers A = <a1; a2; : : : ;an> and a value .

Output: An index i such that  v = Ai or the special value NIL if  does not appear in A.

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

LINEAR SEARCH: (A, v)

1:        r=NIL  
2:        for i = 1 to A.length   
3:           if(A[i]=v)   
4:             r=i
5:             return r 
6:           end if
7:        end for 
8:        return r   

We run through the length of the array, if we find the element we return it.  If we've reached the end of the for loop and haven't returned the value, then it wasn't found.  So we return NIL.

Loop Invariant - At the start of every loop, r contains the index of the search value, or r contains the special value NIL.

Initialization - At the start of the loop i=1, there are no elements in A yet considered for comparison. Value of r is NIL, indicating correctly that v has not yet been found.

Maintenance - At the start of each loop, we know r will hold the value NIL since it's not been found.  If it has been found, we would exit the loop and return the index at which it was found.

Termination - If we've reached the end of the loop then by our maintenance condition r will have the the value NIL.  If we've found the value, we exit the loop by returning the value.

CLRS 3e 2.1-2

2.1-2 Rewrite the INSERTION-SORT procedure to sort into non increasing instead of nondecreasing order.

INSERTION-SORT

1:            for j = 2 to A.length  
2:                 key=A[j]  
3:                 i = j -1 
4:                 while( i > 0 && A[i] < key )  
5:                      A[i+1]=A[i] 
6:                      i=i-1  
7:                 A[i+1]=key;  

CLRS 3e 2.2-1

2.1-1 Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the

array A = <31,41,59,26,41,58>

We start with A = <31,41,59,26,41,58>

A = <31,41,59,26,41,58>   //No Swaps (compare 31 < 41)

     

A = <31,41,59,26,41,58>   //No Swaps (compare 41 < 59)

              

A = <31,41,26,59,41,58>   //Swap 59 and 26 (59 > 26)

A = <31,26,41,59,41,58>   //Swap 26 and 41 (41 > 26)

A = <26,31,41,59,41,58>   //Swap 26 and 31 (31 > 26)

A = <26,31,41,41,59,58>   //Swap 59 and 41 (59 < 41)

A = <26,31,41,41,58,59>   //Swap 58 and 59 (59 > 58)

CLRS 3e 1.2-3

1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n²

runs faster than an algorithm whose running time is 2ⁿ on the same machine?

We need to find n such that

100n²  < 2ⁿ 

We can start trying to plot values to try and find where this starts to fail.

n              2ⁿ           100n²

1              2             100      

10            1024        10000

20            1048576  40000

We see a value of n between 10 and 20 will already tip over the equation where the exponential values will start running significantly slower than the quadratic equation.  We find this value to be at 15.    So the strength of polynomial algorithms is at display where just 15 values can make them start running significantly faster than exponential counterparts.

CLRS 3e 1.2-2

1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n² steps, while merge sort runs in 64 nlgn steps. For which values of n does insertion sort beat merge sort?

We need to find value of n such that insertion sort runs faster than merge sort so where:

8n² <  64 n lg n       (n > 0)
8n   <  64 lg n           (Obtained by canceling n on both sides)
n     <  8 lg n             (Obtained by diving both sides by 8)

Compute some values

n      8 lg n 

1      0

2      8

10    26.56

20    34.58

30    39.26

40    42.58

50    45.15

We see that 1 doesn't satisfy this condition but n between 10 and 40 definitely do.  At 50, the equation starts to fail again.  We now try values between 40 and 50 to find the exact point where it fails.  This point by brute force is obtained to be at 44.

So we conclude that between [2,43] the insertion sort algorithm runs faster than merge sort.

CLRS 3e 1.2-1

1.2-1 Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.

One example of application that requires algorithmic content at the application level is a map application.  One of the standard algorithms it uses is the shortest path algorithm to compute the least distance between any two points on the map.

CLRS 1.1-5

1.1-5 Come up with a real-world problem in which only the best solution will do.  Then come up with one in which a solution that is "approximately: the best is good enough.

When formulating a drug in the pharmacy for public use, accurate proportion of different elements need to be known before it can be tested on real patients.  While studying properties of proteins, its common to approximate certain parameters to focus on the study of required elements.

CLRS 3e 1.1-4

1.1-4 How are the shortest path and traveling salesman problems given above similar?  How are they different?

Both the shortest path algorithm and the traveling salesman problem want to minimize the overall distance travelled.  The shortest path algorithm is a one way path to find the shortest route from a source to destination.  An example would to be the shortest path from Pittsburgh to Chicago given all the intersection one would encounter.  The traveling salesman problem is to find the shortest overall path from a source, visit a set of destinations and then end up back at the source. 

An example would a mail delivery truck that delivery mails to different location everyday that wants to travel the least overall distance and end up back at the mail office.

CLRS 3e 1.1-3

1.1-3 Select a data structure that you have seen previously, and discuss its strengths and limitations.

Array Lists - Linear sequence of elements.

Advantages


• Search by index takes constant time.
• Search by value takes liner time or can be improved by using binary search for sorted arrays.
• Setting an element to new value with known index takes constant time, with unknown index takes linear time.
 
Disadvantages
• Insertion and deletion can take liner time in worst case.  It is not very friendly to change.  
• Mostly need continuous blocks of memory for storage which can be unwieldy for large lists.
• Size is fixed and although dynamic array can expand if more space is needed it takes linear time to double the size.

CLRS 3e - 1.1-2

1.1-2 Other than speed, what other measures of efficiency might one use in a real-world setting?

•       Memory usage
•       Security
•       Reliability
•       Maintainability
•       Usability

CLRS 3e 1.1-1

1.1-1 Give a real-world example that requires sorting or a real world examples that requires computing a convex hull. 

A real-world example that would require sorting: 

1. Books in a library sorted by genre and by author alphabetically
2. Ranking students in a class by sorting their grades