hirhs

Question 1

Application of Breadth First Search

Answer 1

Shortest path for an unweighted graph

Question 2

Application of Depth First Search

Answer 2

Generating a Maze

Question 3

Application of Pre-Order

Answer 3

Copying a tree

Question 4

Application of In-Order

Answer 4

Binary Search tree outputting contents in ascending order

Question 5

Application of Post-Order

Answer 5

Infix to RPN conversion

Question 6

Time Complexity of Linear Search

Answer 6

O(n)

Question 7

Time complexity of Binary Search

Answer 7

O(logn)

Question 8

Time complexity of Binary Tree Search

Answer 8

O(logn)

Question 9

Time complexity of bubble sort

Answer 9

O(n^2)

Question 10

Time complexity of Merge Sort

Answer 10

O(nlogn)

Question 11

What is an algorithm

Answer 11

A sequence of steps that can be followed to complete a task and that always terminates

Question 12

What is representational abstraction

Answer 12

• A representation arrived at by removing unnecessary details

Question 13

What is generalisation or catorgerism abstraction

Answer 13

• A grouping by common characterisctics to arrive at a hierarchical relationship of the “is a kind of” type

Question 14

What is automation

Answer 14

• Putting models into action to solve problems

Question 15

How is automation achieved (4)*

Answer 15

• Creating Algorithms
• Implementing the algorithms in code
• Implementing the models in data structures
• Executing the code

Question 16

RegEx *

Answer 16

0 or more repititions

Question 17

RegEx +

Answer 17

1 or more repititions

Question 18

RegEx ?

Answer 18

0 or 1 repititions

Question 19

What is a regular language

Answer 19

A language that can be represented by RegEx

Question 20

Why can BNF represent some languages RegEx cant

Answer 20

• BNF can use recursion to represent languages which RegEx cannot

Question 21

How many permutations for n distinct objects

Answer 21

n!

Question 22

What is a tractable problem

Answer 22

• Problems that have polynomial (or less) time solution

Question 23

What is a intractable problem

Answer 23

• Problems that have no polynomial (or less) time solution

Question 24

When are Heuristic Methods used

Answer 24

• When tackling intractable problems
• Heuristic methods will trade off correctness for speed

Question 25

What is the significance of the halting problem

Answer 25

- Demonstrates that there are some problems that cannot be solved by computers

Question 26

What is the halting problem

Answer 26

Given a description of a program , and some input, is it possible to tell, without running the program, whether it will halt with the given input or loop forever, for any program

Question 27

What does a turing machine consist of (4)

Answer 27

- A finite set of states - A finite alphabet of symbols - An infinite tape with marked off squares - A sensing read/write head that can travel along the tape

Question 28

What is the importance of turing machines (2)

Answer 28

- Provide a model of computation - Provide a definition of what is computable

Question 29

What would 1 | & , -> mean in a state transition diagram

Answer 29

1 is read, write & and move ->

Question 30

When is a program computable

Answer 30

- If and only if it can be computed by a turing machine

Question 31

What is a Universal Turing Machine

Answer 31

- Simulates the behaviour of other Turing Machines when given their transition rules and their input data encoded on its own tape

Question 32

Why can a Universal Turing Machine be considered more powerful than any computer

Answer 32

It has a infinite amount of memory tape

Question 33

What is information hiding

Answer 33

- Hiding all details of an object that do not contribute to its essential characterisitcs

Question 34

Convex combination of vectors?

Answer 34

- a**u**+ b**v** - a, b >= 0 - a + b = 1

Question 35

What is procedural decomposition (3)

Answer 35

- Breaking down a problem into sub problems - Each sub problem acomplishes an identifiable task - Which might be further subdivided

Question 36

What is Problem abstraction

Answer 36

- Details are removed untill the problem is represented in a way that is possible to solve

Question 37

What is functional abstraction

Answer 37

- Where the particular computation method is hidden