M269 - Unit 2.1 And 2.2

Front 1

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

Back 1

In computer science, an abstraction is basically a simplification, a model of some problem or object from which all but the relevant details have been eliminated.

In Unit 1, two kinds of abstraction are distinguished:

• abstraction as modelling some part of reality, ignoring irrelevant details

• abstraction as encapsulation, where the inner mechanisms of a model are hidden from users.

Front 2

Write informal definitions of ‘algorithm’ and ‘computable problem’, as you understand the terms from your study of Unit 1.

Back 2

• An algorithm consists of a step-by-step list of instructions.

• A problem is computable if it is possible to build an algorithm that solves in a finite number of steps every instance of the problem that might arise.

Front 3

How would you define an ADT in a few words?

Back 3

At the heart of data abstraction is the abstract data type (or ADT). 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. Programmers need to work these out themselves.

Front 4

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

Back 4

Also central to the idea of the ADT is the concept of encapsulation: the data handled by the data type is hidden inside it and can only be accessed through the operations it offers – its interface.

Front 5

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

Back 5

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

Front 6

1. What is meant by a ‘linear data structure’?

Back 6

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

Front 7

What does LIFO stand for and what does it mean?

Back 7

Last-in first-out.

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.

Front 8

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

Back 8

Front 9

Why might it be a bad idea simply to use a list object on its own as a stack?

Back 9

There are at least two reasons why simply using a list directly as a stack is a poor approach:

• We wish to define methods with names appropriate to a stack (e.g. push(), pop(), etc.), rather than simply using the existing methods provided by list. Using list indirectly enables us to do this.

Front 10

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

Back 10

Parenthesised expressions are expressions in brackets. They are found in arithmetic and in most programming languages. To be interpreted properly (‘parsed’), such expressions must balance. A balanced parenthesis has an open bracket " ( " followed by a closed bracket " ) ".

Front 11

Give some examples of a few of the problems that computers are currently capable of solving?

Back 11

Here are a few interesting ones:

• Translate a passage in one human language into another human language
• Render virtual scenes with realistic lighting and texture
• Recognise the song being played in a bar
• Plan a route from A to B.

Front 12

Every algorithm is built from some combination of just three basic components, what are these three components?

Back 12

• Sequence - A sequence is a list of one or more instructions executed in order.

• Iteration - Iteration is another word for what we would normally call repetition or looping.

• Selection - Meaning choice.

Front 13

What are stacks, queues, deques, and lists all examples of?

Back 13

Stacks, queues, deques, and lists are examples of data collections whose items are ordered depending on how they are added or removed.