Programming using stack

Problem:

A stack is a useful structure for storing data because it has many useful applications. For example, it can be applied in implementing recursive computing method. A stack is a “last-in-first-out” structure — data items are stored linearly as one item is placed on top of the other. The only two operations are: pop and push. The pop operation retrieves the top data item on the stack, while the push operation puts a new data item on the top of the stack. The figure below shows how a stack works:

(a) Can you write up a computing procedure for DFS using a stack instead of using recursion?

(b) Can you suggest a practical situation where we must use a stack instead of using recursion?

Follow-Up:

(a) The first possible version is as follows.

Stack_DFS1(x):

1. Mark x; Push(x);
2. if stack is empty, then end of algorithm; otherwise, do the following:
3.    y = top of stack (without popping it);
4.    if there is a neighbor z of y that is not marked, then do:
5.       Mark z; Push(z);
6.    else
7.       Pop;
8. go to Step 2.

Another possible version is as follows.

Stack_DFS2(x):

1. Push(x);
2. if stack is empty, then end of algorithm; otherwise, do the following:
3.    y <- Pop;
4.    if y is not marked, then Mark y;
5. for every neighbor z of y that is not marked, do the following:
6.    Push(z);
7.    go to Step 2.

(b) In the Web crawling application, we need to use a stack. In fact, crawling is done by many computers running the “search” (or explore) simultaneously. Each computer takes the next node to be explored from the top of the stack, downloads the HTML file, and then scans it for further hyperlinks. But when a new HTML document is found (i.e., a “neighbor”), no recursive call is made; instead, the new node is pushed onto the stack.

Yet one interesting question remains: when we see a HTML document, how do we know it is indeed “new” (i.e., not marked) so that we want to push it on stack?

Making change using dynamic programming

Problem:

Consider the problem of making change. Assume coins of values 25 cents (i.e., a quarter), 10 cents (dime), 5 cents (nickel), and 1 cent (penny). Suppose now we want to return 63 cents in change. What would you do?

Now suppose that our coins’s values are instead: 1 cent, 5 cents, and 11 cents. We want to make change of 15 cents. Can you apply the same method as what you did above?

Follow-Up:

We can use a greedy method to find the smallest number of coins required for the first case:

63 (divide) 25 = 2         remainder =13
13 (divide) 10 = 1         remainder = 3

Thus, we need two quarters, one dime, and three pennies.

However, it is easy to see that the greedy method does not work for the second case. Indeed, we end up using one 11 cents and four 1 cent, while in fact three 5 cents would do good.

The lesson, again, is that greedy method does not always work.

Some of you discovered solving the second case using a “recursive” idea:

f(15) = min { f(14), f(10), f(4) } + 1

where f(n) denotes the minimum number of coins needed to make change for n cents.

The rationale of the above “recursive” idea is that the first term inside the “min” represents the case where one 1 cent coin is used so that we still need to make change for 14 cents. Similarly, the second term represents the case where one 5 cents coin is used so that we still need to make change for 10 cents. Finally, the third term represents the case where one 11 cents coin is used so that we still need to make change for 4 cents.

To really compute the answers, we need to further “reduce” the problems on the right side of the above equation (called a recurrence equation), until we get to the trivial cases, e.g., f(1), f(5), f(11) .

In fact, to construct the final answer, we need to build it from “bottom-up”, i.e., at the beginning we use the trivial cases, and then construct the bigger cases, and so on, until we get to the original question.

There is an official name for this “bottom-up” construction of recursively defined solutions—dynamic programming. This is a very powerful algorithm design paradigm that can be applied in solving many problems.

Further Inquiry:

(a) What is the estimated running time of the above dynamic programming method?
(b) Can you find a general relationship for the coin denominations so that the greedy method is optimal?

HW: Sorting in the daily life

Problem (10 points):

This problem is about a common daily life application of sorting. Specifically, sorting (e.g., QuickSort) is usually done before we want to search for something. For example, bank accounts are always sorted according to the account numbers in order to facilitate searching a particular account on request.

Consider, as shown above, a sorted (in ascending order) list of n numbers (assume n is a power of 2, i.e., n = (2^k) for some positive integer k ). To search for a number x in the list, we can use the following algorithm. Compare x with the number in the middle of the list (i.e., m shown above). If they are equal, then our job is done. If x is smaller than that middle number, then we repeat this search process using just the left half of the list; otherwise, we repeat this search process using just the right half of the list.

(a) Why we can use just the left half of the list if the first comparison tells us that x is smaller than

the middle number?

(b) Please express the above algorithm as a recursive method.

(c) Please give the number of comparisons needed in the worst case. Explain your answer.

HW: "Greedy" computing

Problem (10 points):

We just learnt about “greedy” computing method—trying to choose the best move in every step,

without regard to future options.

(a) What do you think is the necessary condition for the greedy computing method to find optimal solutions?

(b) How do you compare greedy computing method with recursive method (or divide-and-conquer)?

(c) Can you find other daily life computing problems where greedy method is good?

Computing using depth-first-search (DFS)

Problem:

In class today, we learn about a computing method for traversing a graph (see Presentation #2, slide #9), called depth-first-search (DFS).

(a) Can you write up a recursive computing procedure for doing so?

(b) Can you analyze its estimated running time?

(c) Can you name some “everyday computing” applications of this method?

Follow-Up:

(a) A possible recursive algorithm is as follows:

DFS(x):

1. Mark x;
2. For every neighbor y of x that is not marked:
3. DFS(y);

(b) As discussed in class, the DFS procedure visits each and every node once, also each and every link once. Thus, the estimated running time should be on the order of N + E , where N and E are the number of nodes and number of links, respectively.

(c) We need to use DFS for many useful daily life applications:

• playing chess: searching for the best move in the game tree;
• playing puzzle: searching for the exit in a maze;
• crawling the Web: the crawler program (e.g., in Google) needs to search the Web graph (i.e., visualizing the Web as a graph of connected documents, where the connections are the hyper-links) in a depth-first way.

Compution using recursive method

Problem:

The number n! is defined as n × ( n – 1 ) × ( n – 2 ) × … × 2 × 1 .

(a) Can you write up a recursive method to calculate the value of n! ?

(b) You are given a function called print( n ) which shows the value of n on the screen. Using your idea in (a) above, can you write up a recursive method to print numbers from n to 0 on the screen?

Follow-up:

(a) The number n! is defined as n × ( n – 1 ) × ( n – 2 ) × … × 2 × 1 .
We can express its computation as a recursive method below. Assume n > 1 .

Calculate_Factorial(n)

1. Is n = 1?
2. If yes, then answer is: 1
3. If no, then answer is: n x Calculate_Factorial(n-1)

(b) Using an idea similar to the above, we can solve the “printing” problem as follows. Assume n>0 .

Show_n_downto_0(n)

1. print(n)
2. Is n = 0?
3. If yes, then we are done
4. If no, then do: Show_n_downto_0(n-1)

Problem:

We observe that . Assume n is a power of 2.

Can you write up a recursive method to calculate the value?

Follow-up:

We can express this computation as a recursive method below.

Calculate_Power(a, n)

1. Is n = 1?
2. If yes, then answer is: a
3. If no, then:
4.        b = Calculate_Power(a, n/2)
5.        answer is then: b x b