Midterm1 sample solution

Scan the array sequentially. Keep track of the max and min elements that have been seen so far. Each iteration:

There are n/2 iterations → total comparisons are 3n/2.

In the original selection sort, each pass identifies the max item. A pass covers the range [0, j]. Since j is decrementing, the range is shrinking from its end.

With algorithm from 1(a), each pass can identify both max and min items. We simply swap the max item to the end of the range and the min item to the start of the range.

Therefore, the range covered by each pass is shrinking from boths ends. Initially the range is [0, n-1], i.e. the whole arrary. After pass 1, it becomes [1, n-2]; after pass 2 it becomes [2, n-3]…​

When the range has 0 or 1 item, we’re done.

3/2 (n + (n-2) + (n-4) + .. + 2) = 3/8 n(n+2)

So we are (slightly) better than the original insertion sort.

Challenge: stack allows you to retrieve items you’ve just added from one end; on a queue, you can add items on one end, but can only get the items from the other end.

Let’s start by using one queue. Push is easy: simply add the item to the queue’s rear. When you want to "pop" from the queue’s rear, you will need to dequeue all existings items to the other queue — except the rear item, which you should remove and return.

Note that the relative order of all remaining items is still kept in the other queue (i.e. queue’s front does not change).

Then you switch to working the other queue.

See also: http://stackoverflow.com/questions/688276/implement-stack-using-two-queues

Just follow the index link.

Unused list and stack are fine with list heads only.

The tricky one is queue. You’ll want to remember its list’s end index, which will be used as the queue’s rear.

There’s a bit ambiguity in the question regarding Stack_Top(Stack_List), for which there are two alternative assumptions you may make:

One possible assumption [Recommended]: If we assume Stack_Top returns the value of the top of the stack (as we do on lecture slides):

An alternative assumption: If we assume Stack_Top returns the pointer to the top of the stack, then the given operations make the two lists intersect.

1.

2.

3.

("Recall that O() is not a "tight" upper bound …​")

Fibonacci(n) = 1 + Fibonacci(n-1) + Fibonacci(n-2)

Don’t overcount. The invocation to Fibonacci(N-1) will be counted within that call.

Since for fibonacci sequence we have f(n) = f(n-1) + f(n-2), Fibonacci(n) grows at least as fast as the fibonacci sequence, which is O(2^n) (again, this is not tight).

In fact, Fibonacci(n) ~= \Theta(1.6^n)

See also: https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence

Of course you only have to show intuition from numbers here.

Keep track of the previous 2 numbers in the sequence and keep adding.

Follow the ADT format on the slides

Call the node to be deleted as D.

In general, you will need to find the node that precedes D. To do so, you need to iterate the list from the head, and keeps checking whether the next link points to D. This is O(n).

Corner cases: