Unit 2 Flashcards
Name: GetOdd
Inputs: A set of natural numbers I = {i<em>1</em>, i<em>2</em>, i<em>3</em>, …, i<em>k</em>}
Outputs: A set of natural numbers O = {o<em>1</em>, o<em>2</em>, o<em>3</em>, …, o<em>j</em>}
Precondition: k > 0
Postcondition:
Which of the following statements could form part of the postcondition of the problem?
- I is not equal to O
- o<em>j</em> is not in I
- For all i<em>i</em> in I, i<em>i</em> is in O
- For all o<em>i</em> in O, o<em>i</em> is in I
- j k
- j k
- For all o<em>i</em> in O, o<em>i</em> is in I
- j k
The following structured English specifies an algorithm that is intended to determine whether or not a candidate passes their driving test. The criteria for passing is that the candidate will pass if they make 15 or fewer driving faults and no serious or dangerous faults.
- set drivingFault to 16
- set seriousFault to 0
- set dangerousFault to 0
- set result to True
- IF seriousFault is greater than 0
- set result to False
- IF dangerousFault is greater than 0
- set result to False
- IF drivingFault is greater than 15
- set result to False
Assume that the structured English has been transformed into Python code.
Note that the first three lines of code are there to state the performance of a specific candidate, but in a more elaborate version of the program, these might be read in from a database or user input.
Which one of the following statements are correct?
- result will be False
- result will be True
- It is not possible to determine the value of result
- The Python code implementing this algorithm will crash as the algorithm is faulty
result will be True:
The example illustrates a very common type of error in handling selection.
Lines 1 to 3 set values for each of the test fault results, with drivingFault set to 16 and both seriousFault and dangerousFault set to 0.
Line 4 initialises result to True
Lines 5, 7 and 9 show nested if statements. If the value of seriousFault is greater than 0, then the body of that first if statement is entered. In this case, since the value of seriousFault was set to 0, the body of the if statement is not entered, and since all the remaining code is nested inside that if statement, none of it will be executed and result will remain True.
The three selection criteria are actually of equal importance and should not be nested. A correct version of the algorithm is:
- set drivingFault to 16
- set seriousFault to 0
- set dangerousFault to 0
- set result to True
- IF seriousFault is greater than 0
- set result to False
- IF dangerousFault is greater than 0
- set result to False
- IF drivingFault is greater than 15
- set result to False
Complete the following truth table:
3 advantages
What are the possible advantages of the statement of pre- and postconditions?
- Clarity
- Non-redundancy
- Simplicity
What is defensive programming?
Defensive programming is a style of programming where programmers put in checks before calling a function and also within the function.
What are the disadvantages to defensive programming?
Defensive programming can lead programmers to put in checks everywhere, which leads to slower and less reliable code.
Are checks needed when pre- and postconditions have been used?
Yes, checks are still required, because otherwise the calling code can’t be sure that it’s meeting the pre-conditions.
However, the use of pre- and postconditions means that programmers can avoid making unnecessary checks.
An ADT called ShoppingList offers the following services to clients:
addItem(x) – Inserts x as the last item
removeItem(x) – Removes the item x from the shopping list
makeFavourite(x) – Notes that the item x is a favourite
removeFromFavourite(x) – Notes that the favourite item x is no longer a favourite
isFavourite(x) – Returns True if x is a favourite, False otherwise
isIn(x) – Returns True if x is on the shopping list, False otherwise
isEmpty() – Returns True if there are no items on the shopping list, False otherwise
size() – Returns the number of items on the shopping list
ShoppingList should not allow duplicate entries in the list.
Based on the service descriptions above, complete the following table, using the labels below:
[Precondition] [Postcondition]
[addItem(x)] [] []
[removeFromFavourite(x)] [] []
[Invariant] []
- isEmpty()
- ¬isEmpty()
- isIn(x)
- ¬isIn(x)
- isFavourite(x)
- ¬isFavourite(x)
- size() = 0
- size() >= 0
- size()
- size = old size + 1
[Precondition] [Postcondition]
[addItem(x)] [¬isIn(x)] [isIn(x)]
[removeFromFavourite(x)] [isFavourite(x)] [¬isFavourite(x)]
[Invariant] [size() >= 0]
Consider the following Python function, foo(), which receives as input a list of numbers aList.
def foo(aList): a = 7 b = 5 n = len(aList) for i in range(n): for j in range(n): a = i \* a b = j \* j w = i \* j v = i + w x = v \* v for k in range(n): w = a \* k + 23 v = b \* b a = w + v
Assuming that the length of the list (n, in this function) is the size of the problem, and taking a step (i.e. the basic unit of computation) to be an assignment statement, choose the appropriate T(n) function and the complexity for foo’s algorithm from the options below.
- T(n) = 3 + n + 5n2 + 2n3, complexity O(n3)
- T(n) = 3 + 6n2 + 2n3, complexity O(n3)
- T(n) = 3 + 2n + 5n2 + 2n3, complexity O(n2)
- T(n) = 3n + 5n2 + 2n3, complexity O(n)
- T(n) = 3 + n + 5n2 + 2n3, complexity O(n!)
- T(n) = 3n + 5n2 + 2n3, complexity O(n3)
- T(n) = 7n2 + n + 3, complexity O(n2)
T(n) = 3 + n + 5n2 + 2n3, complexity O(n3)
Which of the following functions grows the fastest as n increases?
- 3n2 + 20n
- (9n2)/2 + 10n + 100
- 5n2 + 5n
- 3n2 + 5
- 4n2 + 3n + 100
- n2 + 1000
5n2 + 5n
This question is about carrying out a binary search for the item 22 in this list: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59].
Select one correct statement about the first partition of the list to be searched, and select one correct statement about the last non-empty partition of the list to be searched.
- Starting with the list [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59], the last non-empty partition of this list that will be searched is [19]
- Starting with the list [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59], the first partition of this list that will be searched is [19, 23, 29, 41, 43, 47, 53, 59]
- Starting with the list [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59], the last non-empty partition of this list that will be searched is [23]
- Starting with the list [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59], the first partition of this list that will be searched is [2, 3, 5, 7, 11, 13, 17]
- Starting with the list [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59], the first partition of this list that will be searched is [2, 3, 5, 7, 11, 13, 17, 19]
- Starting with the list [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59], the first partition of this list that will be searched is [23, 29, 41, 43, 47, 53, 59]
- Starting with the list [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59], the last non-empty partition of this list that will be searched is [23]
- Starting with the list [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 41, 43, 47, 53, 59], the first partition of this list that will be searched is [23, 29, 41, 43, 47, 53, 59]
What is a linear data structure?
A linear data structure is a data structure in which items persist in the same position, relative to other elements.
All linear structures can be thought of as having two ends:
- In the case of a list, the ‘beginning’ and the ‘end’
- In the case of a stack, the ‘top’ and the ‘base’
What is a Stack?
The Stack ADT is an example of a linear structure, in which items persist in the same position, relative to other elements.
A stack has two ends - the ‘top’ and the ‘base’.
Stacks are LIFO (last-in first-out) structures. Items added to a stack last come out first, so an item’s position in the stack is related to the order in which it was added.
What is an invariant?
An invariant of an ADT is a condition that must apply to every data structure that implements that ADT throughout its lifetime.
The invariant must hold true as soon as the instance has been constructed, and remain true at all subsequent times - an operation should never have the effect of leaving an invariant false.
How does the binary search algorithm work?
- Define the search partition to the whole list
- Locate the midpoint of the list and check to see if that is the item we are looking for
- If not, check whether the midpoint is higher or lower than the item we are looking for
- Adjust the start and end of the partition to either the first half or the second half of the original partition - if the midpoint is lower than the item we are looking for, discard the first half, if the midpoint is higher than the item we are looking for, discard the second half
- Repeat until search term has been found
Complete the following truth table:
