Unit 1 Flashcards
What is a data structure?
A collection of data organised in a particular way.
What is a computational problem?
A problem that is expressed sufficiently precisely that it is possible to attempt to build an algorithm to solve it.
Is an algorithm a finite or an infinite process?
Finite - it is guaranteed to finish at some point.
What makes a problem computable?
If an algorithm can be found which solves the problem.
What is a key property of an algorithm?
It consists of a step-by-step list of instructions.
Does an algorithm need to solve every instance of a problem?
Yes. If an algorithm does not solve every instance of a problem, then it is not an applicable solution to the problem.
What is a computable problem?
A problem that is expressed sufficiently precisely that it is possible to build an algorithm to solve every instance of the problem in a finite number of steps.
What is an abstract data type?
A logical description of the data used to solve a problem (a data structure) - by the operations that may be performed on it and by the pre- and post-conditions of those operations.
How is an abstract data type implemented?
Using a data structure which provides a physical description of the data being used.
What is a decision problem?
A problem where the answer is either yes or no.
What word describes a decision problem that is computable?
Decidable.
What is an effective procedure?
An algorithm which solves a decision problem in a finite number of steps.
What word describes a decision problem that is not computable?
Undecidable.
What is computational thinking?
The ability to analyse a problem with the techniques and skills that computer science puts at our disposal.
What skill does being able to formulate a problem as a computational problem demonstrate?
Computational thinking.
