Analysis of Algorithms
1. What is the smallest number of divisions made by Euclid's algorithm among all inputs 1 ≤ m, n ≤ 30?
2. What is the largest number of divisions made by Euclid's algorithm among all inputs 1 ≤ m, n ≤ 30?
3. #5, Exercises 1.1
Design an algorithm to find all the common elements in two sorted lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output should be 2, 5, 5.What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are m and n, respectively?
4. #12, Exercises 1.1
Locker doors - There are n lockers in a hallway, numbered sequentially from 1 to n. Initially, all the locker doors are closed. You make n passes by the lockers, each time starting with locker #1. On the ith pass, i = 1, 2, . . . , n, you toggle the door of every ith locker: if the door is closed, you open it; if it is open, you close it. After the last pass, which locker doors are open and which are closed? How many of them are open?
5. #1, Exercises 1.2
OldWorld puzzle Apeasant finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the peasant himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Solve this problem for the peasant or prove it has no solution. (Note: The peasant is a vegetarian but does not like cabbage and hence can eat neither the goat nor the cabbage to help him solve the problem. And it goes without saying that the wolf is a protected species.)
6. #2, Exercises 1.2
NewWorld puzzle There are four people who want to cross a rickety bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person's pace. (Note: According to a rumor on the Internet, interviewers at a well-known software company located near Seattle have given this problem to interviewees.)
7. #4, Exercises 1.3
K¨onigsberg bridges The K? onigsberg bridge puzzle is universally accepted as the problem that gave birth to graph theory. It was solved by the great Swiss-born mathematician Leonhard Euler (1707-1783). The problem asked whether one could, in a single stroll, cross all seven bridges of the city of K? onigsberg exactly once and return to a starting point. Following is a sketch of the river with its two islands and seven bridges:
a. State the problem as a graph problem.
b. Does this problem have a solution? If you believe it does, draw such a stroll; if you believe it does not, explain why and indicate the smallest number of new bridges that would be required to make such a stroll possible.
8. #4, Exercises 1.4
a. Let A be the adjacency matrix of an undirected graph. Explain what property
of the matrix indicates that
i. the graph is complete.
ii. the graph has a loop, i.e., an edge connecting a vertex to itself.
iii. the graph has an isolated vertex, i.e., a vertex with no edges incident to it.
9. #8, Exercises 1.4
How would you implement a dictionary of a reasonably small size n if you knew that all its elements are distinct (e.g., names of the 50 states of the United States)? Specify an implementation of each dictionary operation.
10. #8, Exercises 2.1
For each of the following functions, indicate how much the function's value
a. log2 n b. square root of n c. n d. n^2 e. n^3 f. 2^n