For week 2
You must submit the questions marked with (*) at the beginning of your tutorial.
1. (*) Consider the following specification for a searching problem. int srch(int A[], int n, int K);
// PRE: n is the length of A, and A is sorted (increasing order).
// POST: Return the index i such that
// i <= n, AND
// for all j, st i < j < n, K < A[j], AND
// for all j, st 0 <= j <= i, K >= A[j]
(Note that the second clause means "for all indices j strictly between i and n we must have that K < A[j]", and the third clause means "for all indices no more than i, we must have that K >= A[j]".) Now consider the array A= {1,2,2,3,5,6}, with n= 6.
If K= 3, what index must srch return?
If K= 2, what index must srch return?
If K= 4, what index must srch return?
If K= 1, what index must srch return?
2. (*) Recall the Binary Search strategy for searching for items in a sorted array: in an array A with indices l and r delimiting the part of the array still to be searched, the item which approximately divides A[l..r] (at index mid) is examined, and the search continues for some other portion of the array.
If A[mid] < K, what portion of the array must be searched?
If A[mid] > K, what portion of the array must be searched?
If A[mid] == K, what portion of the array must be searched?
How might your answers change if you are asked to write a Binary Search implementation for srch at Question 1?
(Note that A[i..j] stands for the portion of the array containing indices between (and including) i and j. This means that i <= j.)
3. struct Node {
int item;
Node* link;
};
Write a function to insert a node at the front of a linked list.
Write a function to remove the node at the front of the linked list.
What test cases would you use to test your function? (Hint: What are the boundary cases?)
4. (Carrano, page 333.) Suppose you have a stack astack, and a temporary stack temp, show how you can use the stack operations to:
Count the number of items in aStack, leaving aStack unchanged.
Delete every occurrence of a specified item from aStack, leaving the order of the remaining items unchanged.
5. How many iterations are required in each of the following algorithms?
for (int i=0; i<n; i++)
for (int j=n; j>i; j--)
cout << a[i][j];
int i=1;
while (i<n)
{
cout << i;
i = i * 2;
}
for (int i=n; i>0; i=i/2)
for (int j=n; j>i; j--)
cout << a[i][j];
int i=0;
while (i<n*n)
{
cout << i;
i = i + 1 ;
}
All enquiries to Annabelle McIver