Unit 2

Question 1

Give a brief definition of ‘abstraction’ as it is used in the context of computational thinking.

Answer 1

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:

1. abstraction as modelling some part of reality, ignoring irrelevant details
2. abstraction as encapsulation, where the inner mechanisms of a model are hidden from users.

Question 2

Sequence

Answer 2

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.

Question 3

Iteration

Answer 3

repetition or looping, in other words repeating a sequence of instructions over and over. For instance, the Python while loop while a

Question 4

Selection

Answer 4

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.

Question 5

How would you define an ADT in a few words?

Answer 5

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.

Question 6

How does the concept of an ADT relate to the idea of abstraction as encapsulation?

Answer 6

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.

Question 7

What is the relationship between an ADT and a data structure?

Answer 7

when an ADT is implemented, the result is a data structure.

Question 8

Linear data structure

Answer 8

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’.

Question 9

What does LIFO stand for and what does it mean?

Answer 9

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.

Question 10

What are the operations of the Stack ADT, and what do they do?

Answer 10

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

Question 11

What is a parenthesised expression, and what does it mean for it to be balanced or unbalanced?

Answer 11

to be interpreted properly (‘parsed’), such expressions must balance, so that opening parentheses match closing parentheses correctly.

Question 12

Simple mathematical notation to denote a sequence

Answer 12

S = (s₁, s₂, s₃, …, s_n) S denotes the sequence s₁, s₂, s₃, …, s_n denote the items in the sequence, such that s₁ is the first item in the sequence, s₂ the second, etc. s_n means the last item in the sequence.

Question 13

What is the naive way of searching the dictionary for a word?

Answer 13

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

Question 14

Four logical connectives

Answer 14

∧ and

∨ or

¬ not

→ if … then

Question 15

What benefits might the statement of pre- and postconditions have?

Answer 15

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.

Question 16

Think of three ways in which algorithms might be compared.

Answer 16

their readability

the amount of memory space they use

the time they take to execute

Question 17

Why is it useful to compare algorithms independently of particular programming languages and computers?

Answer 17

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.

Question 18

Function

Answer 18

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, x₂ 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) = x₂, a series of values of x₂ on the y-axis of the graph are plotted against each corresponding value of x (on the x-axis).

Question 19

Big-O functions

Answer 19

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

Question 20

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

Answer 20

O(n²) since there is a singly nested loop

Question 21

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

Answer 21

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.

Question 22

Given the following code fragment what is its Big-O running time?

i = n while i > 0:

k = 2 + 2

i = i // 2

Answer 22

O(log n)

the value of i is cut in half each time through the loop so it will only take log n iterations.

Question 23

Big-O Efficiency of Python List Operators

Answer 23

Question 24

Big-O Efficiency of Python Dictionary Operations

Answer 24

Question 25

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)

Answer 25

list.pop(0)

when you remove the first element of a list, all the other elements of the list must be shifted forward.

Question 26

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)

Answer 26

all of the above are O(1)

the only dictionary operations that are not O(1) are those that require iteration

Question 27

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

Answer 27

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