Theory of Computation

What are the 4 main Computer Science Constructs?

• Sequence

• Selection

• Iteration

• Assignment

SSIA

What is meant by Abstraction?

Removal of unrequired information. Keeping only what is necessary.

What is meant by Decomposition?

Breaking down of a problem into smaller and edible chunks.

What is meant by Composition?

The combination. Like composite

What makes up a Turing Machine?

• Read & Write Head

• Infinite Tape

• Finite State Machine (FSM)

What symbol is used to highlight transition functions?

Greek Symbol Delta : δ

What is the difference between TM and UTM?

Turing Machine vs Universal Turing Machine is that the UTM can take in another input more than the general TM.

Why is the Turing Machine so important?

The Turing Machine explains the limits of computation as with this theoretical machine if to be impossible with such a machine then its stated to be an incomputable problem. Only provable through use of the Turing Machine

What does FSM stand for?

Finite State Machine

What does STD stand for?

State Transition Diagram

What does cardinality mean?

The Count meant to be used on a finite set stating the count within the set.

What does finite mean?

The ability to end.

What does infinite mean?

Unknowingly long.

How do you figure out the cartesian product?

Correct use of multiplication.

What is Regular Expression?

Simply put a way of describing a set.

What are the symbols used for Regular Expression?

• ‘*’ — Meaning zero or more

• ‘+’ — Meaning one or more

• ‘?’ — Meaning zero or one repeated (Optional)

• ‘|’ — Meaning “or“ a choice

• ‘()’ — Simply just groups them

Can sets contain other sets?

Yes. For those that fit. For example a set containing infinite numbers and one which include 1-10 they’ll defiantly be a set of a set.

What is set comprehension?

Expression of sets through selecting from larger general sets.

What is an empty set called?

{} or Ø

What is a subset?

Example:

A is a subset of B if it only contains items from Set B

Symbol : ⊆

What is a proper subset?

Example:

A is a proper subset of B if it only contains items from B but not all of them

Symbol : ⊂

What are the 3 different set operations?

• Union

• Intersection

• Difference

What does Union do considering sets?

Union would take two sets and combine them into a brand new one combining everything from the previous two. (No Duplicates)

Symbol : ∪

What does Intersection do considering sets?

An intersection considering sets when taking two sets the brand new set that would be created would only included those within the previous sets that are found|duplicate in both of them.

Symbol : ∩

What does Difference do considering sets?

When a difference is applied to two sets the resulting brand new set will only include one of the previous in the brand new one completely removing the other.

Example:
A/B
This will only include those from set A

Symbol : /

What does BNF stand for?

Backus-Naur Form

Considering BNF What is the difference between Terminal and Non-Terminals?

Backus-Naur Form considering the difference between Terminal and Non-Terminals:

Terminal — CANNOT be broken down into simpler parts
Non-Terminals — CAN be broken down into simpler parts

Why use BNF?

Backus-Naur form allows for notation of Context free languages.

What does the Halting Problem prove?

The halting problems shows that there are computational problems that are not possible to be solved.

From best to worst-case what are the BigO classifications?

• O(C)

• O(log2(n))

• O(n)

• O(nlog(n))

• O(n²)

• O(n³)

• O(2^n)

• O(n!)

What is meant by Heuristic?

The best guess or rather rule of thumb. Expectation

What is the BigO for a Binary Search?

O(log2 (n))

What is the BigO for a Linear Search?

O(n)

What is the BigO for a Merge Sort?

O(nlog(n))

What is the BigO for a Bubble Sort?

O(n²)

What is the difference between Tractable and Intractable?

The difference to whether a problem can be done within a polynomial amount of time or not.

• Tractable saying that it CAN.

• It’s an intractable saying that it CANNOT.

What is the Halting problem?

The unsolvable problem of determining whether any program will eventually stop if given a particular input.

What does Countably Infinite mean?

Its more of statement really which states that all infinite sets can be counted off with use of the natural numbers set (also being infinite) technically meaning every value up to infinity does have a ordinal value.

What counts as a countable set?

• finite sets

• countably infinite sets

What are the 4 different types of abstraction?

• Procedural

• Functional

• Data

• Problem