Unit 1 Flashcards
What are the five deep questions in computing identified by Jeannette Wing?
- What is computable?
- P = NP?
- What is intelligence?
- What is information?
- How can we build complex systems simply?
What are measures of goodness in computational thinking?
- Usability
- Modifiability
- Maintainability
- Cost
- Beauty
- Elegance
- Correctness
- Efficiency
What defines a computational problem?
A problem is computational if it can be expressed sufficiently precisely that it is possible to attempt to build an algorithm to solve it.
What defines a computational thinker?
A computational thinker has the skills to:
- Formulate a problem as a computational problem
- Construct a good computational solution for the problem, or explain why there is no such solution
What are the drivers of computing?
- Technology
- Society
- Science
What would be the result of typing the following into a Python interactive shell?
>>> a = [1, 2, 3, 4, 5]
>>> b = [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’]
>>> x = a[:3]
>>> y = b[4:]
>>> z = b[::2]
x references [1, 2, 3]
y references [‘e’, ‘f’]
z references [‘a’, ‘c’, ‘e’]
True or False:
A trade-off between resources such as memory and execution time is often necessary when deciding which algorithm is best for a given task.
True
What are important factors when designing algorithms?
- Simplicity
- Correctness
- Speed
- Accuracy
Complete this computational thinking diagram:
Complete this computational thinking diagram:
What is an algorithm?
An algorithm consists of a precisely stated, step-by-step list of instructions.
A problem is computable if it is possible to build an algorithm which solves any instance of the problem in a finite number of steps.
What is an effective procedure?
An effective procedure must terminate and must also solve every instance of that problem.
What is encapsulation?
Encapsulation is about hiding details of an implementation from users to manage complexity.
In computing, will a hierarchy of layers always eventually bottom out at a layer consisting of electronic components?
No.
Electronic components are not the only physical substrate from which computers can be built.
What are the two kinds of abstraction, and how are they different?
Abstraction as modelling is the relationship between a part of reality and a model which represents the interest of this reality.
Abstraction as encapsulation is the relationship between a layer that implements the model (the implementation) and a layer through which users interact with the model (the interface).
Rules of Blackjack:
- Blackjack is played with a dealer and one player
- Aim of the game is to get a higher hand than the dealer without going over 21 (going bust)
- The player can ask repeatedly for another card to be dealt until they either go bust or decide to stop.
- If the player goes bust, the dealer wins.
- If the player does not go bust, the dealer must deal themselves cards until the value of their hand is more than 17, at which point the dealer stops dealing.
- If the dealer goes bust, the player wins.
- If the dealer does not go bust, whomever has the highest value wins.
- If both the dealer and the player have the same value, the dealer wins.
- You can assume the pack contains 52 cards, which will not run out, and that both dealer and player have been dealt 2 cards each at the start of the algorithm.
- The algorithm should continue dealing cards until the dealer or the player wins the game.
Complete the following algorithm template for dealing out and playing a hand of Blackjack:
- if __________
- then
- deal the player a card
- if __________
- then
- finish: the dealer wins
- __________
- if the dealer’s hand value is
- then
- deal the dealer a card
- if the dealer’s hand value is > 21
- then
- __________
- __________
- if __________
- then
- finish: the dealer wins
- else
- finish: the player wins
Use the following phrases to fill in the blanks:
- finish: the dealer wins
- finish: the player wins
- go back to step 1
- go back to step 8
- the player asks for a card
- the dealer’s hand value is > 21
- the player’s hand value is > 21
- the dealer’s hand value is >= the player’s hand value
- if the player asks for a card
- then
- deal the player a card
- if the player’s hand value is > 21
- then
- finish: the dealer wins
- go back to step 1
- if the dealer’s hand value is
- then
- deal the dealer a card
- if the dealer’s hand value is > 21
- then
- finish: the player wins
- go back to step 8
- if the dealer’s hand value is >= player’s hand value
- then
- finish: the dealer wins
- else
- finish: the player wins
When is a problem computable?
What is a computational problem?
A problem is computable if it is possible to build an algorithm that solves every instance of the problem that might arise in a finite number of steps.
A computational problem is one that is expressed sufficiently precisely that it is possible to attempt to build an algorithm to solve it.
What is a computational problem?
When is a problem computable?
A computational problem is one that is expressed sufficiently precisely that it is possible to attempt to build an algorithm to solve it.
A problem is computable if it is possible to build an algorithm that solves every instance of the problem that might arise in a finite number of steps.
What is an abstract data type (ADT)?
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.
The ADT allows us to develop an algorithm without being concerned with the particular implementation of the underlying data structure.
What is a data structure?
A data structure provides the physical description of the data being used (a list, a table, etc.).
The data structure is encapsulated by an ADT, which defines a set of operations which can be carried out on the data.
What is a decision problem?
A decision problem is a problem stated in a formal language (usually logic or mathematics) for which the answer is yes or no.
What is a decidable problem?
A decidable problem is a decision problem that is computable.
What is an algorithm?
An algorithm is a finite process consisting of a step-by-step list of instructions that should solve any instance of the problem that might arise.
What is computational thinking?
Computational thinking is the skill of understanding and reasoning about algorithms and data structures.
What are the measures of goodness in computational thinking?
- Cost
- Efficiency
- Maintainability
- Correctness
- Elegance
- Modifiability
- Usability
- Beauty
What does iteration mean?
Iteration (also called looping or repitition) means the algorithm repeats a group of steps (the body of the loop) some number of times depending on a condition which is tested before each repitition.
What does selection mean?
Selection (also known as branching) is when part of an algorithm follows different paths depending on some condition.
Complete this diagrammatic representation of abstraction as modelling:
Complete this diagrammatic representation of abstraction as modelling:
Complete this diagrammatic representation of abstraction as encapsulation:
Complete this diagrammatic representation of abstraction as encapsulation:
