An interpreter reads a program and executes it (does what it says to do).
A compiler reads a program and translates it into another language.
- depth
The maximum of the distances from the root to each leaf.
- balanced
If d is the depth of the binary tree, all leaves are at depth d or depth d-1.
- left-justified
If d is the depth of the binary tree, all leaves at depth d are as far left as possible.
Do the base case(s) first.
Recur only with a simpler case.
Do not both use and modify global variables.
Don't look down.
IntList has public instance variables
int value and IntList next, with the
obvious meanings. Write a recursive method int size
to count the number of values in the IntList list. int size(IntList list) {
if (list == null) return 0;
else return 1 + size(list.next);
}
int size()
method described in the previous question.int size(IntList list) {
int count = 0;
while (list != null) {
count++;
list = list.next;
}
return count;
}
int myArray[][] = new int[3][8],
what value is in myArray[1]?
An int array containing 8 zeros.
for (int i = 0; i < a.length; i++) a[i] = i * i;
O(a.length), since we do one constant time operation for each element of a.for (int i = 0; i < 10000; i++) a[i] = i * i;
O(1), since the number of iterations is fixed, and each pass through the loop does only constant-time operations.
- Insertion sort
All the elements to the left of some index are sorted with respect to one another.
Precisely: For increasing k, i < j & j < k implies a[i] <= a[j]. - Selection sort
All the elements to the left of some index are in their final position.
Precisely: For increasing k, i < k & i < j implies a[i] <= a[j].
A heap is an area of memory from which the programmer can allocate storage.
A heap is a binary tree in which every node has the heap property.
(A node has the heap property if the value in the node is at least as large as the value in any child of that node.
Stack class extends the
Vector class. Why does your instructor think this is a
bad design?Because a Vector has many operations which should not be available to a Stack.
|
 |
int max1(int[] nums, int last) {
if (last == 0) return nums[0];
else {
if (nums[last] > max1(nums, last - 1)) {
return nums[last];
} else {
return max1(nums, last - 1);
}
}
} |
int max2(int[] nums, int last) {
if (last == 0) return nums[0];
else {
int temp = max2(nums, last - 1);
if (nums[last] > temp) {
return nums[last];
} else {
return temp;
}
}
} |
The second one is much faster.
The first takes exponential time, O(2nums.length), because every call may result in two recursive calls.
The second makes one call for each element of the array, so is only linear time, O(nums.length).
A, 5%; B, 12%; C, 31%; D, 34%; E, 17%; F, 1%
- Draw the corresponding Huffman tree.
A + F = 6 (v)
B + v = 18 (w)
w + E = 35 (x)
C + D = 65 (y)
x + y = 100 (z)
- Tell the binary encoding for each letter.
A = 0010 B = 000 C = 10 D = 11 E = 01 F = 0011
f(N) = g(N) + h(N), what
do each of the following stand for?N
A particular node in the search tree.
g
The (known) cost of getting from the start node to node N.
h
The estimated cost of getting from node N to a goal node.
f
The estimated cost of getting from the start node to a goal node via a path passing through node N.
Mark each node as you get to it, so you know not to explore from there again.
Keep a set of visited nodes, so you know not to explore from them again.
An algorithm which "remembers" previous results and uses them when computing new results.
absX = x > 0 ? x : -x; 
Preferences method get(key, xxx),
what is the second parameter used for?A default value, to return in case the key is not found.
The farther ahead you look, the better you can choose a move.
Your opponent has the same heuristic (means of evaluating each node) as you have.
(One point of credit: The earlier you can find a cutoff, the more searching you will save.)
Whenever you see a way to improve it.
-or-
When it is necessary in order to add new functionality.