A sequence of steps that can be followed to complete a task
1 of 22
What is abstraction?
Breaking a problem down into its key components
2 of 22
What is a Finite State Machine (FSMs)?
A machine that can be only in a finite set of states and does not give an output
3 of 22
What is a Mealy Machine?
A machine with a finite number of states that does give an output
4 of 22
What is a "dead" (halting) state? (FSMs)
A state with no outgoing transitions
5 of 22
What is the symbol for an empty set (a set with no elements)?
{}
6 of 22
What is a finite set?
A set whose elements can be counted up to a particular number
7 of 22
What are some examples of an infinite set?
Natural numbers - N
Real numbers - R
8 of 22
What is a subset?
A set within a set
9 of 22
What is a proper subset?
A subset that only contains elements from the set its contained in
10 of 22
What is the meaning of ∈ (membership)?
is an element of
11 of 22
What is the meaning of ∪ (union)?
the elements that are contained by both sets uniquely (shared elements)
12 of 22
What is the meaning of ∩ (intersection)?
the elements that are contained in both of the sets (all elements)
13 of 22
In what two ways can a program be more efficient than another program?
+Space-wise (Storage)
+Time-wise (Faster)
14 of 22
What is meant by constant time (big O notation)?
An algorithm that has an O notation of O(1)
This means that input size does not impact processing time
15 of 22
What is meant by linear time (big O notation)?
An algorithm that has an O notation of O(n)
This means that input size directly impacts processing time
16 of 22
What is meant by polynomial time (big O notation)?
An algorithm that has an O notation of O(n^x)
This means that input size impacts processing time
17 of 22
What is meant by exponential time (big O notation)?
An algorithm that has an O notation of O(2^n)
This means that input size exponentially impacts processing time
18 of 22
What is meant by logarithmic time (big O notation)?
An algorithim that has an O notation of O(log n)
This means that input size can only impact processing time to a certain extent
This is the best case for an algorithm
19 of 22
What is a tractable problem (big O notation)?
A problem with a solution that is Polynomial or Exponential
20 of 22
What is an intractable problem (big O notation)?
A problem that has no polynomial (or less) time solution
21 of 22
What is the halting problem?
A problem proposed by Alan Turing that states if a program (H) knows if a program halts
Comments
No comments have yet been made