Week 4 - From Problems to Programs Flashcards
Basing your answer on Unit 1, what is the definition of abstraction as used in the context of computational thinking.
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.
- modelling
- encapsulation.
ADTs
Abstract Data Types
What are the three basic things that computers can do ?
Sequence - computer operate by executing instructions.
Iteration - repeating a sequence of instructions over and over.
Selection - computers are able to make a choice.
How would you define an ADT in a few words?
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.
How does the concept of an ADT relate to the idea of abstraction as encapsulation?
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.
What is the relationship between an ADT and a data structure?
When an ADT is implemented, the result is a data structure.
Recall the description of an ADT, thinking of it as a ‘Black Box’
Essentially, an ADT can be thought of as a black box with a set of operations defined on it. All we know about the box is its interface: what we can ask it to do for us and what it will give us in return. What goes on inside the box is not specified.
What is meant by a linear data structure?
Stacks, queues, deques and lists are examples of data collections whose items are ordered depending on how they are added or removed. Once an item is added, it stays in that position relative to the other elements that came before and after it.
What does LIFO stand for and what does it mean?
LIFO stands for ‘Last-in First-out’. 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.
What are the operations of the stack ADT, and what do they do?
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
size() - Returns the number of items in the stack.
How do i iterate over a stack in python?
for x in range(aStack.size()):
What is a boundary value error?
is a name given to a bug that causes a program to branch into the wrong track or get stuck in an infinite loop. They are called this because the problems occur at the dividing lines between various conditions.
In a truth table when is P –> Q False?
the truth table for P –> Q is as follows
P Q P–>Q
F F T
F T T
T F F
T T T
What is P –> Q equivalent to?
(P ^ Q) v ¬P
What is the inertial convention?
Aspects of an ADT’s state not referred to in the postcondition are unaffected by the operation.
