Chapter 1 Exercise 1.1, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

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

Solution: The contact book in our phones needs to be sorted alphabetically so that we can find person phone number easily. Some other examples are flights, movie tickets they are all sorted by time. Even our daily schedules are sorted by time.

Convex hull can be defined as a step of points, a line connecting the points in a convex polygonic way, so that all the points are inside it.

 

In image processing application Convex hull is used.

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

Solution: 

1. Computer memory 
2. Network usage 

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

Solution:

Array Lists

Advantages:

1. Access element in constant time.
2. Element can be inserted in any place.

Disadvantages:

1. Random access takes n time.
2. Extra memory is utilized in making of index

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

Solution:

Similar: Both are graph algorithms and find path.
Difference: The shortest path algorithm needs 2 points, where as salesman algorithms needs a path between more points that returns to first point.


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.

Solution:

Sorting is a algorithm in real world in which only best solution will do.
Finding the shortest path between two places as couple of meters wont matter a lot.