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