Definitions

Question 1

What is an algorithm?

Answer 1

A sequence of unambiguous instructions for solving a problem (obtaining a required output
for any legitimate input in a finite amount of time)

Question 2

What is a Set?

Answer 2

A collection of elements.
Usually containing no repetitions, and in no particular order

Question 3

What is the result of a union (∪) of these two sets?
T1 = {1,3,4,6}
T2 = {1,2,6,7}

Answer 3

T1 ∪ T2 = {1,2,3,4,6,7}
“The set of elements present in either set”

Question 4

What is the result of an Intersection (∩) of these two sets?
T1 = {1,3,4,6}
T2 = {1,2,6,7}

Answer 4

T1 ∩ T2 = {1,6}
“The set of elements appearing in both sets”

Question 5

How do you represent an empty set?

Answer 5

∅ = A set with no elements

Question 6

What is a subset(⊂)?

Answer 6

A set where every element in the subset is present in the superset.
R1 = {1,3} is a subset of R2 = {1,2,3,4,5}

Question 7

What are Undecidable Problems?

Answer 7

A problem for which there exists no algorithm capable of solving all instances of the problem in a finite amount of time

Question 8

What is an NP problem?

Answer 8

A problem that can be solved in polynomial type using a non-deterministic algorithm

Question 9

What is a P problem?

Answer 9

A problem that can be solved in polynomial time (e.g n or n2)

Question 10

What is a Non-deterministic Algorithm?

Answer 10

An algorithm that will make guesses as it proceeds.

It will then check it’s answer later to see if the guess was right?

Question 11

What is pseudocode?

Answer 11

A mixture of natural and programming languages
Used to describe an algorithm

Question 12

What do these mean in pseudocode?
1. x ← 0
2. if n > 0 then
3. for k ← 1 to n do
4. // Input or Output

Answer 12

1. Value assignment
2. If statement
3. Iteration
4. Comment