[Q&A] For the following questions, please put your answers in a text file midterm.txt or an MS Word file midterm.doc. For questions that could have multiple correct answers, giving one of the correct answers is enough.

1. (10pt) Given logN < N for any N > 1, prove 2000N*logN + 2N² = O(N²).

2.

a. (5pt) Suppose we want to insert values 1,2,3,4,5,6,7 into an empty binary search tree. How can we order the insertions so that after the insertions, the resulting tree will be identical to the one shown in Figure 1?

b. (10pt) After removing 4 and 5 from the tree shown in Figure 1 using the Remove algorithm discussed in the lecture notes, we traverse the tree in

• pre-order
• in-order
• post-order

For each case, list the nodes in the order in which they are visited.

[Programming] Consider an OrderedLinkedList class, which is similar to the DoubleLinkedList class we implemented in Homework 1, except that the nodes in the list are always sorted based on the value field in the ListNode class. Note that there is a class variable order in the OrderedLinkedList class, which indicates whether the nodes are sorted in ascending order or descending order. For this problem, you must complete the OrderedLinkedList class by implementing the following two methods:

• (35pt) void reverse() - reverses the list, or in other words, if the nodes are sorted in ascending order before reverse() is called, then after reverse() is called, they will be sorted in descending order, and vice versa. Note that the worse-case complexity of your reverse() method must be linear or better; otherwise you will not receive any credit.
• (40pt) OrderedLinkedList merge(OrderedLinkedList other) - merges two ordered lists into a new ordered list. Note that
• merge() returns a new list and should not change the two original lists.
• The two original lists may be sorted in different order, e.g. one may be in ascending order and the other may be in descending order.
• The new list should be sorted in ascending order.
• The worst-case complexity of the merge() method must be linear (or better), i.e. O(N+M) where N and M are the numbers of nodes in the two original lists; otherwise you will not receive any credit.