Computational Thinking Flashcards
What is representational abstraction?
The process of removing unnecessary details until its possible to represent the problem in a way that it can be solved
What is abstraction by generalisation?
The process of placing aspects of the problem into broader categories to arrive at a hierarchical representation
What is procedural abstraction?
The concept that solutions can be broken down into a series of subroutines or procedures
All of which can be solved individually and can be further broken down
What is functional abstraction?
Abstracting a procedure into a group of common functions
What is problem abstraction?
The process of reducing a problem down into its simplex components until the underlying processing requirements that solve the problems are identified.
What is information hiding?
The process of providing a definition or interface of a system whilst hiding the inner workings (e.g. GUI hides the complexity of a program)
What is decomposition?
The process of breaking large complex tasks into smaller, more manageable tasks
What is composition?
Creating a working system from the smaller processes
What is automation?
Creating computer models of real life situations and putting them into action
(e.g. Computer Model that models the profits of a coffee shop)
What is a set?
A data type which contains unordered, unique values
What is the cardinality of a set?
The number of elements within a set (only in finite sets)
What is a subset?
A set which contains items from another set, but not every item from the other set
Symbol: ⊆
Membership of a set symbols:
In a set: ∈
Not in a set: ∉
What is a union? (combining sets)
Elements in A OR B
Set A ∪ Set B
What is an intersection? (Combining Sets)
Elements in A and B
Set A ∩ Set B
What is a difference? (Combining Sets)
A set which contains items exclusive to one set
A NOT B
B NOT A
A\B = {x : x ∈ A and x ∉ B}.
What does the * represent? (Regular Expressions)
- Means 0 or more repetitions
ab* = {a, ab, abb, abbb, …}
What does the + represent? (Regular Expressions)
+ Means 1 or more repetitions
a+b = {ab, aab, aaab, …}
What does the ? represent? (Regular Expressions)
? means that the previous character is optional
a?b = {b, ab}
What does | represent? (Regular Expressions)
means or
a|b = {a, b}
What does () represent? (Regular Expressions)
() is used to group regular expressions
(ab) | (cd) e = {abe, cde}
What is Big O Notation?
Big O Notation describes the complexity of an algorithm, by assuming the worst case scenario.
What is the order of complexity? (Least Complex to Most Complex)
Constant O(1)
Logarithmic O(logN) Binary Search
Linear - O(N) Linear Search
Linear Logarithmic - O(NLogN) Merge Sort
Polynomial - O(^2) Bubble Sort
Exponential - O(2^N) Recursively Counting Fibonacci Numbers
Factorial - O(N!) Travelers Problem
What is an intractable problem?
A problem that is theoretically possible, but not within polynomial time
(e.g. Factorial or Exponential)
