Unit 1 Flashcards
Define a computational problem
a problem that is expressed sufficiently precisely that it is possible to attempt to build an algorithm to solve it
What are the main properties of an algorithm?
an algorithm consists of a step-by-step list of instructions
an algorithm is a finite process (this means it is guaranteed to finish at some point)
the algorithm should solve any instance of the problem that might arise.
What are the properties of an abstract data type?
an abstract data type (ADT) is a logical description of the data used to solve a problem.
the ADT provides an encapsulation of the data by providing an interface with which the user interacts.
What is the relationship between an abstract data type and a data structure?
an ADT is implemented by a data structure; that is, the data structure provides the physical description of the data being used (a list, a table, etc.).
an ADT encapsulates the data structure and defines a set of operations which can be carried out on the data (via the interface).
the ADT therefore allows us to develop an algorithm without being concerned with the particular implementation of the underlying data structure
What property or properties does a dictionary have that would enable us to write a better algorithm?
entries are sorted alphabetically, that is, the data in the dictionary is structured to allow us to access and use the data more efficiently
Computational thinking
not merely knowing how to use an algorithm or a data structure, but, when faced with a problem, to be able to analyse it with the techniques and skills that computer science puts at our disposal.
Computational problem
described as a problem that is expressed sufficiently precisely that it is possible to attempt to build an algorithm to solve it
