Unit 2 - From Problems to Programs

Question 1

When turning a computational problem into a program, what do we transform the computation problem into?

Answer 1

Algorithms and abstract data types.

Question 2

When turning a computational problem into a program, what do we implement algorithms and abstract data types in?

Answer 2

A program.

Question 3

When turning a computational problem into a program, what does the machine express?

Answer 3

Algorithms and abstract data types.

Question 4

When turning a computational problem into a program, what do algorithms and abstract data types solve?

Answer 4

A computational problem.

Question 5

When moving from a computational problem through to an algorithm, what do we create?

Answer 5

A set of abstractions.

Question 6

In computer science, what is an abstraction?

Answer 6

A simplification, a model of some problem or object from which all but the relevant details have been eliminated.

Question 7

What three constructs form an algorithm?

Answer 7

Sequence, iteration and selection.

Question 8

What is a sequence?

Answer 8

A list of one or more instructions executed in order.

Question 9

What is iteration?

Answer 9

Repeating a sequence of instructions over and over.

Question 10

What is selection?

Answer 10

Evaluation of an expression to branch into executing one sequence or another.

Question 11

What is the result of implementing an abstract data type?

Answer 11

A data structure.

Question 12

How is an abstract data type implemented in a programming language?

Answer 12

As a data type or as a custom class.

Question 13

What is meant by a linear data structure?

Answer 13

Items persist in the same position, relative to the other elements. A linear data structure has two ends - a top and a base.

Question 14

Is a stack a FIFO or a LIFO data structure?

Answer 14

A stack is a LIFO data structure. Items added to a stack last come out first.

Question 15

What is the meaning of the formal logic connective ∧?

Answer 15

This is a conjunction, which means ‘and’.

Question 16

What is the meaning of the formal logic connective ∨?

Answer 16

This is a disjunction, which means ‘or’.

Question 17

What is the meaning of the formal logic connective ¬?

Answer 17

This is a negation, which means ‘not’.

Question 18

What is the meaning of the formal logic connective →?

Answer 18

This is an implication, which means ‘if … then’.

Question 19

What is meant by the term inertial convention?

Answer 19

Aspects of an abstract data type’s state not referred to in the postcondition are unaffected by the operation.

Question 20

What is meant by the term invariant?

Answer 20

An invariant of an abstract data type is a condition that must apply to every data structure that implements the abstract data type, throughout its lifetime.

Question 21

How is a function defined within mathematics?

Answer 21

As a relationship between a set of possible inputs (the domain) and a set of possible outputs (the range).