Unit 2 Flashcards
Give a brief definition of ‘abstraction’ as it is used in the context of computational thinking.
an abstraction is basically a simplification, a model of some problem or object from which all but the relevant details have been eliminated.
two kinds of abstraction:
- abstraction as modelling some part of reality, ignoring irrelevant details
- abstraction as encapsulation, where the inner mechanisms of a model are hidden from users.
Sequence
computers operate by executing instructions, such as assigning a value to a variable or evaluating an expression a sequence is a list of one or more instructions executed in order.
Iteration
repetition or looping, in other words repeating a sequence of instructions over and over. For instance, the Python while loop while a
Selection
computers are capable of is making a choice: they can perform a test of some kind and then branch into executing one sequence or another, depending on the evaluation of at least one Boolean expression.
How would you define an ADT in a few words?
an ADT is a description of a data structure purely in terms of the operations that can be carried out on it. the ADT offers no account of how these operations are programmed, how the data is stored, the programming language used, or any other specific details.
How does the concept of an ADT relate to the idea of abstraction as encapsulation?
with encapsulation the data handled by the data type is hidden inside it and can only be accessed through the operations it offers – its interface.
What is the relationship between an ADT and a data structure?
when an ADT is implemented, the result is a data structure.
Linear data structure
the stack is an example of a linear 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 does LIFO stand for and what does it mean?
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 are the operations of the Stack ADT, and what do they do?
Stack() Constructor; creates an empty stack
push(item) Adds item to the top of the stack
pop() Removes and returns the item at the top of the stack
peek() Returns the item at the top of the stack
isEmpty() Returns True if the stack is empty; False otherwise
size() Returns the number of items on the stack
What is a parenthesised expression, and what does it mean for it to be balanced or unbalanced?
to be interpreted properly (‘parsed’), such expressions must balance, so that opening parentheses match closing parentheses correctly.
Simple mathematical notation to denote a sequence
S = (s1, s2, s3, …, sn) S denotes the sequence s1, s2, s3, …, sn denote the items in the sequence, such that s1 is the first item in the sequence, s2 the second, etc. sn means the last item in the sequence.
What is the naive way of searching the dictionary for a word?
the strategy is to start with the first word in the dictionary and then plough through each word, one by one, either until the target word is located or until the end of the dictionary
Four logical connectives
∧ and
∨ or
¬ not
→ if … then
What benefits might the statement of pre- and postconditions have?
clarity - if the pre- and postconditions are clearly documented, then it is clear where the obligations between client and supplier lie.
non-redundancy - with clear statements of responsibility, programmers can avoid making unnecessary checks.
simplicity - with less redundancy, code becomes simpler, and therefore easier to read and debug.
Think of three ways in which algorithms might be compared.
their readability
the amount of memory space they use
the time they take to execute
Why is it useful to compare algorithms independently of particular programming languages and computers?
because computers differ in power, and there will also be a difference in speed between different programming languages, we need a more objective way of comparing algorithms than simple timings.
Function
a function is defined as a relationship between a set of possible inputs (the domain) and a set of possible outputs (the range), such that each input is related to exactly one output.
a function of x is generally written as f(x).
to take a commonly used example, x2 is a function of x.
every function has a characteristic graph, which we get by plotting x against f(x).
in the case of f(x) = x2, a series of values of x2 on the y-axis of the graph are plotted against each corresponding value of x (on the x-axis).
Big-O functions
when n is small, the functions are not very well defined with respect to one another. It is hard to tell which is dominant
however, as n grows, there is a definite relationship and it is easy to see how they compare with one another.
exponential > cubic > quadratic > log linear > linear > logarithmic > constant
Given the following code fragment, what is its Big-O running time?
test = 0
for i in range(n):
for j in range(n):
test = test + i * j
O(n2) since there is a singly nested loop
Given the following code fragment what is its Big-O running time?
test = 0
for i in range(n):
test = test + 1
for j in range(n):
test = test - 1
O(n)
even though there are two loops they are not nested
you might think of this as O(2n) but we can ignore the constant 2.
Given the following code fragment what is its Big-O running time?
i = n while i > 0:
k = 2 + 2
i = i // 2
O(log n)
the value of i is cut in half each time through the loop so it will only take log n iterations.
Big-O Efficiency of Python List Operators
Big-O Efficiency of Python Dictionary Operations
Which of the list operations shown below is not O(1)?
list.pop(0)
list.pop()
list.append()
list[10]
all of the above are O(1)
list.pop(0)
when you remove the first element of a list, all the other elements of the list must be shifted forward.
Which of the dictionary operations shown below is O(1)?
‘x’ in mydict
del mydict[‘x’]
mydict[‘x’] == 10
mydict[‘x’] = mydict[‘x’] + 1
all of the above are O(1)
all of the above are O(1)
the only dictionary operations that are not O(1) are those that require iteration
Within the inner loop there are two assignment statements. How many times are these executed, for an input of size n?
- recall that range(n) generates the numbers 0, 1, 2, …, n−1*
- whilst range(m, n) (where m is less than n) generates the numbers m, m+1, …, n−1.*
def someFunction(aList):
n = len(aList)
best = 0
for i in range(n):
for j in range(i + 1, n + 1):
s = sum(aList[i:j])
best = max(best, s)
return best
there are n outer loops, as i goes from 0 to n−1.
on the ith loop, there are n−i inner loops; that is:
when i is 0, there are n inner loops (as j goes from 1 to n)
when i is 1, there are n−1 inner loops (as j goes from 2 to n)
when i is 2, there are n−2 inner loops (as j goes from 3 to n)
…
when i is n−1 there is 1 inner loop (as j goes from n to n).
thus the pair of assignment statements is executed n + (n−1) + (n−2) + ⋯ + 2 + 1 times, this is the sum of all the integers up to n
