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