Unit 3 Flashcards
Which of the following functions is recursive?
def fun(x): if x
return 1
else:
return x * fun(x - 1)
def fun(x):
if x
return 1
else:
return x * fun(x)
-------------------------------------------------- def fun2(n): for i in range(1, n): print(i) def fun1(n): for i in range(0, n): fun2(n) fun1(5) #called externally by the user
-------------------------------------------------- def fun(x): return x \* fun(x - 1)
def displayNumbers(aNumber):
for i in range(1, aNumber):
display(i)
def isOdd(aNumber):
if aNumber % 2 > 0:
return 1
else:
return 0
def fun(x): if x
return 1
else:
return x * fun(x - 1)
For a function to be recursive, such as this one:
- It must have a base case. Here the base case is: if x is smaller than one, the function returns 1.
- It must call itself. Here, the function calls itself in: x * fun(x - 1)
- The call to itself must move the the problem closer to the base case. That is indeed what is happening here, since subtracting 1 brings us closer to the base case where x is smaller than 1.
Complete the following extract, using the labels below:
A recursive algorithm must call _____, recursively. Each recursive call _____ the problem in some way. The current state of the algorithm (the values of its local variables and arguments) is _____ on the call _____ on each call. The _____ that allows the algorithm to stop recursing is called the _____.
- action
- an import
- another
- base case
- condition
- discarded
- expanded
- expands
- heap
- inductive
- infinite loop
- itself
- non-termination
- obliterates
- pile
- recorded
- recursive
- reduces
- reuses
- stack
- strengthens
A recursive algorithm must call itself, recursively. Each recursive call reduces the problem in some way. The current state of the algorithm (the values of its local variables and arguments) is recorded on the call stack on each call. The condition that allows the algorithm to stop recursing is called the base case.
Taking the unit of computation to be the comparison, what is the complexity and worst-case complexity of selection sort?
Complexity:
O(n)
Worst-case complexity:
O(n2)
How does the selection sort algorithm work?
The selection sort algorithm works by shifting the largest unsorted items, in turn, to the end of the list rather than swapping them with each other.
Which algorithm is more efficient in practice - insertion sort or selection sort?
Insertion sort is more efficient than selection sort.
What is the complexity of the following code?
def someFunction(aList):
n = len(aList)
for i in range(n):
print (aList[i])
for j in range(int(n/2)):
print(aList[j] + n)
print("all done")
listA = [1,2,3,4,5,6,7,8]
someFunction(listA)
- O(n)
- O(3n/2)
- O(n2)
- O(n3)
- O(1)
- O(3n/2 + 1)
O(n)
Which of the following statements are true about the attached diagrams in A-H?
- C and E are trees according to both definitions of trees in Miller and Ranum.
- A, F and H are trees according to the recursive definition of trees.
- B is a complete binary tree.
- G and H are binary heaps.
- A, D and H are binary trees.
- A, F and H are trees according to the recursive definition of trees.
- B is a complete binary tree.
Consider a function that does a preorder traversal of a binary tree, and as it visits each node of that tree it adds to a list the key for that node. The function returns the list of node keys.
Given the following graphical representation of a binary tree, what list would that function return?
[77, 11, 10, 7, 8, 4, 2, 0, 62, 48, 3, 32, 6, 5, 1]
This algorithm deals first with the root node, printing 77, and then recursively does a preorder traversal of the left subtree of 77 and then a preorder traversal of the right subtree of 77, so 77 is the first item in the traversal.
The preorder traversal of the left subtree (root node 11) again starts with the root node of this left subtree, printing 11, and then recursively doing a preorder traversal of the left subtree of this left subtree and then preorder traversal of the right subtree of this left subtree.
Complete the following extract, using the labels below:
According to Miller and Ranum, merge sort has complexity _____. It is a _____ algorithm that works by repeatedly splitting a list in half and invoking a merge sort on both halves. Only when the resulting sublist is empty or contains just one item can we say that that sublist is sorted. Pairs of sorted sublists are then combined together into a single sorted new list.
We will look at the list [10, 20, 11, 5, 100, 64, 2, 3].
As this list is not empty or containing just one item then _____ has not been reached, so we split it into two and recursively invoke a merge sort on both halves. The halves will be [10, 20, 11, 5] and [100, 64, 2, 3].
Looking at the first half – this list is not empty or containing just one item, so we split it into two and recursively invoke a merge sort on both halves. The halves will be _____.
Looking at the first of these halves – again this list is not empty or containing just one item, so we split it into two and recursively invoke a merge sort on both halves. The halves will be _____.
Once the base case has been reached, we can merge the two halves together to make a sorted list of length 2 [10, 20]. Similarly the other two-element list would make _____.
Merging these 2 two-element lists together to make one of length 4 gives us _____.
The second half of the original list, when merged together again gives _____.
The final sorted list is [2, 3, 5, 10, 11, 20, 64, 100].
- O(log n)
- O(n)
- O(n log n)
- O(n log n)
- adaptive
- brute force
- clever
- recursive
- recursive
- the base case
- the recursive step
- [2, 3, 5, 10]
- [2, 3, 64, 100]
- [5, 10]
- [5, 10, 11, 20]
- [5, 11]
- [5, 11, 10, 20]
- [5, 20]
- [11, 5]
- [11, 20]
- [11, 20, 64, 100]
- [5] and [11]
- [5, 10] and [11, 20]
- [10] and [11]
- [10] and [20]
- [10, 11] and [5, 20]
- [10, 20] and [11, 5]
- [11] and [20]
According to Miller and Ranum, merge sort has complexity O(n log n). It is a recursive algorithm that works by repeatedly splitting a list in half and invoking a merge sort on both halves. Only when the resulting sublist is empty or contains just one item can we say that that sublist is sorted. Pairs of sorted sublists are then combined together into a single sorted new list.
We will look at the list [10, 20, 11, 5, 100, 64, 2, 3].
As this list is not empty or containing just one item then the base case has not been reached, so we split it into two and recursively invoke a merge sort on both halves. The halves will be [10, 20, 11, 5] and [100, 64, 2, 3].
Looking at the first half – this list is not empty or containing just one item, so we split it into two and recursively invoke a merge sort on both halves. The halves will be [10, 20] and [11, 5].
Looking at the first of these halves – again this list is not empty or containing just one item, so we split it into two and recursively invoke a merge sort on both halves. The halves will be [10] and [20].
Once the base case has been reached, we can merge the two halves together to make a sorted list of length 2 [10, 20]. Similarly the other two-element list would make [5, 11].
Merging these 2 two-element lists together to make one of length 4 gives us [5, 10, 11, 20].
The second half of the original list, when merged together again gives [2, 3, 64, 100].
The final sorted list is [2, 3, 5, 10, 11, 20, 64, 100].
An incomplete proof by induction that the proposition
P(n) is true for all n,
where P(n) is the proposition that:
H(n) = 2n - 1 where H(n) is the number of moves required to move a tower of height n from one peg to another according to the rules of the Tower of Hanoi puzzle.
is given below.
Complete the following proof to give a complete and correct proof by induction, using the labels below:
Here is the proof:
To prove
- P(n) is true for all n, where P(n*) is the proposition that:
- H(n) = 2n* - 1 where H(n) is the number of moves required to move a tower of height n from one peg to another according to the rules of the Towers of Hanoi puzzle.
PROOF BY INDUCTION:
(1) _____. P(1) is obviously true since
* H*(1) = 21 - 1 = 1. (It takes one step to move a tower of height 1 from one peg to another.)
(2) _____.
Assume that P(k) is true for some k, i.e. that the number of moves required to move a tower of height k to another peg is
H(k) = 2k - 1. (_____)
We aim to show that _____, in other words that
H(k + 1) = 2<em>k</em> + 1 - 1.
We know that H(k + 1) = 2H(k) + 1 since, in order to move a tower of height k + 1, we need to move the tower of height k (H(k)) to another peg, then move the final disk (1) to the other peg, then move the tower of height k back on top of that single disk (another H(k))). (You might like to experiment a bit to convince yourself that this is indeed the case.)
Given this, together with the inductive hypothesis, it follows that:
H(k + 1) = 2(2<em>k</em> - 1) + 1 (we just substituted 2<em>k</em> - 1 for H(k))
So H(k + 1) = 2(2<em>k</em>) - 2(1) + 1 (multiplying out the brackets)
= 2<em>k</em> + 1 - 2 + 1 (multiplying out the brackets again)
= 2<em>k</em> + 1 - 1
which is exactly what we set out to prove.
Having proved both the basis and the inductive step, we may now conclude that _____ holds for all natural numbers n.
- H(n) is true
- recursive step
- the base case
- the inductive hypothesis
- inductive loop
- H(n + 1) = 2<em>n </em>+ 1 - 1
- stopping condition
- the inductive step
- P(k + 1) is true
- H(n) = 2<em>n</em> - 1
- P(k) is true
- P(k + 1) is true
- H(n + 1) is true
(1) the base case. P(1) is obviously true since
* H*(1) = 21 - 1 = 1. (It takes one step to move a tower of height 1 from one peg to another.)
(2) the inductive step.
Assume that P(k) is true for some k, i.e. that the number of moves required to move a tower of height k to another peg is
H(k) = 2k - 1. (the inductive hypothesis)
We aim to show that P(k+1) is true, in other words that
H(k + 1) = 2<em>k</em> + 1 - 1.
We know that H(k + 1) = 2H(k) + 1 since, in order to move a tower of height k + 1, we need to move the tower of height k (H(k)) to another peg, then move the final disk (1) to the other peg, then move the tower of height k back on top of that single disk (another H(k))). (You might like to experiment a bit to convince yourself that this is indeed the case.)
Given this, together with the inductive hypothesis, it follows that:
H(k + 1) = 2(2<em>k</em> - 1) + 1 (we just substituted 2<em>k</em> - 1 for H(k))
So H(k + 1) = 2(2k) - 2(1) + 1 (multiplying out the brackets)
= 2<em>k</em> + 1 - 2 + 1 (multiplying out the brackets again)
= 2<em>k</em> + 1 - 1
which is exactly what we set out to prove.
Having proved both the basis and the inductive step, we may now conclude that H(n) = 2<em>n</em> - 1 holds for all natural numbers n.
What are the properties of a tree?
- A tree is hierarchical
- Children of one tree node are independent of the children of another
- Leaf nodes are unique
- A tree can be empty
What is a binary tree?
A binary tree is a a tree in which each node has a maximum of two children, identified as the left or right child.
What is a complete binary tree?
A complete binary tree is a binary tree in which all parents have two children, except for the parents of the children at the bottom level of the tree. At the bottom level, all nodes must be as far to the left as possible.
What is a binary heap?
A binary heap has the same properties as a complete binary tree (every parent node has at most two children and every level of the tree must have its maximum number of nodes, aside from the lowest level, into which new nodes are added left to right), with an additional heap order property.
What is a binary min heap?
A binary min heap is a binary heap that follows the ordering rule which states that for every node n, with parent p, p will be less than or equal to n.
