Home | | Syllabus | | Assignments | | Lecture Notes
1) Write a function, Error_code interleave(List &list1, List &list2, List &list3) to interleave the
entries of two lists (list1 and list2) together and put the resulting list into list3. Thus list3 has
entries that alternate between the entries of list1 and list2. If one list has more entries than the
other, the extra entries are omitted.
You should make use of the public functions defined in the list class.
class List {
public:
// methods of the List ADT
List( );
int size( ) const;
bool full( ) const;
bool empty( ) const;
void clear( );
void traverse(void (*visit)(List_entry &));
Error_code retrieve(int position, List_entry &x) const;
Error_code replace(int position, const List_entry &x);
Error_code remove(int position, List_entry &x);
Error_code insert(int position, const List_entry &x);
protected:
// data members for a contiguous list implementation
int count;
List_entry entry[max_list];
};
Answer:
Error_code interleave(List &list1, List &list2, List &list3) {
int smaller;
List_entry x;
list3.clear();
if (list1.size() > list2.size()) {
smaller = list2.size();
} else {
smaller = list1.size();
}
for (int i = 0; i < smaller; i++ ) {
Error_code outcome;
outcome = list1.retrieve(i, x);
if (outcome != success) {
return outcome;
}
outcome = list3.insert(2*i, x);
if (outcome != success) {
return outcome;
}
outcome = list2.retrieve(i, x);
if (outcome != success) {
return outcome;
}
outcome = list3.insert(2*i+1, x);
if (outcome != success) {
return outcome;
}
}
return success;
}
2) For each of the following pairs of functions, use O notation to write how f(n) compares to g(n). I.e. write f(n) is o(g(n)), O(g(n)), Q(g(n)), W(g(n)), or w(g(n)). Explain each of your answers.
3) Draw the comparison tree for binary search 2 for a list of length 8. What is the height of the tree? What is the External path length of the tree? What is the Internal path length of the tree? What is the average number of comparisons made for successful searches? For unsuccessful searches?
4) Consider a function, f, defined as follows:
f(n) = f(n-1) + f(n/2) for n > 2 f((n) = n for n <= 2
a) Write the recursive function, int compute_f(int n), that computes f(n) for some integer n.
Answer:
int compute_f( int n) {
if (n <= 2) {
return n;
} else {
return compute_f(n-1) + compute_f(n/2);
}
}
b) Draw the recursion tree for compute_f(6).
5) Consider the following recursive function:
int foobar(int n, int ans) {
if (n <= 0) {
return ans;
} else {
return foobar(n-1, ans + n*n);
}
}
a) Fill in the following table for the values that n and ans take on in each recursive function call, starting with the function call, mystery(5, 0) (Note there may be more rows than you need).
| n | ans | return value |
| 5 | 0 | 55 |
| 4 | 25 | 55 |
| 3 | 41 | 55 |
| 2 | 50 | 55 |
| 1 | 54 | 55 |
| 0 | 55 | 55 |
b) Rewrite the foobar function using a while loop: int foobarWhile(int n)
Answer:
int foobarWhile(int n) {
int ans = 0;
while (n > 0) {
ans = ans + n*n;
n = n-1;
}
return ans;
}
6) Write the function, remove() for a doubly linked list.
template <class List_entry>
Error_code List<List_entry> :: remove(int position, List_entry &x)
/* Post: If 0 <= position < n, where n is the number of entries in the List, the function
succeeds:
The entry in position is removed from the List, and the entries in all later positions
have
their position numbers decreased by 1. The parameter x records a copy of the entry
formerly in position. Otherwise the function fails with a diagnostic error code. */
{
Node<List_entry> *old_node, *neighbor;
if (count == 0) return fail;
if (position < 0 || position >= count) return range_error;
//fill in the rest of the code here
set_position(position);
old_node = current; //current is a data member of the class
neighbor = current->back;
if (neighbor != NULL) {
neighbor->next = current->next;
}
neighbor = current->next;
if (neighbor != NULL) {
neighbor->back = current->back;
current = neighbor;
} else {
current = current->back;
current_position--;
}
x = old_node->entry;
delete old_node;
count--;
return success;
}
7) Consider the game tree for the (fictitious) game, fisbin, given below. Starting with the given values for each of the possible game endings use the minimax method to fill in the values of the other nodes in the tree. Assume that player 1 likes larger values and player 2 likes smaller values.
Home | | Syllabus | | Assignments | | Lecture Notes