Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer Science Paper 1 > Theory of Computation > Flashcards

Theory of Computation Flashcards

1
Q

What is Abstraction?

A

Process of filtering out the details we don’t need in order to concentrate on those that we do – removing unnecessary details

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define Representational Abstraction.

A

Removing unnecessary details

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is abstraction by Generalisation?

A

Grouping by common characteristics to get a hierarchical relationship

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is information hiding?

A

The process of hiding all details of an object that do not contribute to its essential characteristics

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is procedural abstraction?

A

Breaking down a complex model into a series of reusable procedures; finds the generic method.

E.g.
(4*3) + 7 becomes
ab + c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is functional abstraction?

A

Procedural abstraction results in a procedure. Abstracting further disregards the method of a procedure and results in just a function which takes inputs and produces a specific output.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is Data Abstraction?

A

The reduction of a particular body of data to a simplified representation of the whole. For example, a stack could be implemented as an array and a pointer for the top of the stack.​

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is Automation?

A

Process of putting abstractions of models into action to solve problems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is Decomposition?

A

Process of breaking down a complex problem into parts that are easier to understand

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is Procedural Decomposition?

A

Breaking a problem down into smaller sub-problems

Each of which solves an identifiable task

Each of which might be further split up

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is Complexity of a linear search?

A

O(n)

As the size of the list increases, time taken increases at the same rate
‘n’ is worst case

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the complexity of a binary search?

A

O(log n)

As time taken increases the size increase, but by less and less each time
Halves tree/graph each time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is meant by the time complexity of an algorithm? ign

A

The number of clock cycles taken for the CPU to execute the algorithm

Expressed using ‘big O notation’

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Describe the Halting Problem?

A

The unsolvable problem determining whether a program will halt, given a certain input, without running the given program.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a Tractable Problem?

A

Problem that can be solved in an acceptable amount of time [polynomial time]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is an Intractable Problem?

A

Problem which cannot be resolved in polynomial time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is meant by the term Heuristic?

A

A method for producing a ‘rule of thumb’ to produce an acceptable solution to intractable problems

Better than n factorial

E.g,. Store your shortest path that you have so far and check another. Making approximation for the shortest path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How to identify Polynomial?

A

Nested loops are always polynomial

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

How to identify a Logarithmic Algorithm?

A

Halves the number of items each term

20
Q

What is meant by the term ‘Intractable Complexities’?

A

Ones more complex than polynomial

21
Q

State the Complexity Rules.

A

Remove all terms except one with largest factor/exponents

Remove any constants

3n^2 + 4n + 2 =
3n^2 =
n^2 =
O(n^2)

22
Q

Order of Algorithm Complexities:

A

Constant – O(c)

Logarithmic O( log(n) )

Linear O(n)

Linear Logarithmic O(n log(n) )

Polynomial O(n^2)

Exponential O(2^n)

Factorial O(n!)

Charlie Loves Licking Luscious Penis Every Friday !

23
Q

What does a Turing Machine consist of?

A

A finite state machine

A set of transition rules

A sensing read/write head

Start state

Set of accepting/ halting states

A tape that is infinitely long in one direction

State register/Current register

The finite alphabet of symbols that it can use

24
Q

Explain what a Universal Turing machine is

A

Turing machine that can simulate the behaviour of any other Turing machine

Faithfully executes operations on the data precisely as the simulated Turing Machine does

Acts as an interpreter

25
Q

Why is it not possible to create a Turing machine that solves the Halting Problem?

A

There is no algorithm that solves the Halting Problem

26
Q

Why is a universal Turing machine more powerful than any other computer?

A

It has infinite tape

27
Q

What type of object is enclosed in angle brackets in Backus-Naur Form?

A

Non-Terminal

28
Q

What name is given to an object in Backus-Naur form that can’t be broken down any further?

A

Terminal

29
Q

In Finite State Machine what is the double circle?

A

Valid halting state

When it is valid to stop

30
Q

How does a finite state machine differ from a Turing machine?

A

Don’t have to worry about tape

Or header

31
Q

What is meant by the term reject state?

A

No escape from that state -no way out

Rule won’t be valid if you stop there

32
Q

What are finite state machines used for?

A

Used to validate an input

Represent regular expressions in a computer

A less powerful Turing machine

33
Q

What is a heuristic algorithm?

A

An algorithm that makes a guess/estimate based on experience

Used to tackle intractable problems.

34
Q

What’s the relationship between a Turing machine and an Algorithm?

A

A Turing Machine can compute any algorithm.

35
Q

What’s the purpose of a Turing Machine?

A

To provide a theoretical model which helps us understand how computers solve problems step by step.

36
Q

What is the time complexity of a merge sort?

A

O(nlogn)

The log(n) comes from dividing each array into halves
Then the (n) comes from sorting them by merging

37
Q

What is meant by the ‘cartesian product of two sets’ ?

A

Two sets A and B, written AB, is the set of all ordered pairs (a,b) where a is a member of A and b is a member of B.
e.g.,
A= {1,3,5} B ={ 12,25,40 } Set C is defined as AB
C = {(1,12), (1,25), (1,40), (3,12), (3,25), (3,40), (5,12), (5,25), (5,40)}

38
Q

What is the time complexity of a bubble sort?

A

O(n^2)
Nested Forloop

39
Q

What is an example of an algorithm with a Factorial time complexity?

A

Travelling Salesman

40
Q

What is Problem abstraction​?

A

Removing details from a problem until it can be represented in a way that is possible to solve because the problem reduces to one that has already been solved.”

41
Q

What is a finite state machine?

A

A computing machine that has a fixed set of possible states, a set of inputs that change the state and a set of possible outputs.

42
Q

Transition function format

A

δ(Current State, Input) = (Next State, Output, Movement Dir)

43
Q

Symbol for Integers

A

Z

44
Q

What is meant by a Proper Subset?

A

⊂
A subset is made up entirely of elements of another set but there is at least one element in the original set not included in this set.

45
Q

What is meant by a subset?

A

⊆
The subset can contain ALL the elements of the other set

Computer Science Paper 1 (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions