misc

Question 1

time complexity of merge sort

Answer 1

nlog(n)

Question 2

time complexity of bubble sort and why

Answer 2

O(n2), n items will be examined, n number of times

Question 3

base case def

Answer 3

problem that can be solved without any more recursive calls, stops infinite recursion

Question 4

heuristic solution

Answer 4

discounting consideration of options which may not be the best

Question 5

static vs dynamic data structures

Answer 5

dynamic can shrink/grow during run time
static size must be declared at compile

Question 6

protected vs private

Answer 6

protected can only be accessed in class and derived subclasses

Question 7

why would an adjacency matrix be used

Answer 7

many edges between vertices
edges rarely change

Question 8

what is the halting problem

Answer 8

non computable problem that determines if the program will stop without running. the program

Question 9

4 components of a Turing machine

Answer 9

read/write head
transition rules
halting states
state register

Question 10

what is a universal Turing machine

Answer 10

a Turing machine that can simulate any other Turing machine
and compute any computable sequence

Question 11

why is a UTM more powerful than any other device

Answer 11

infinite amount of memory/tape

Question 12

representational abstraction def

Answer 12

removing extraneous details

Question 13

abstraction by generalisation

Answer 13

grouping by similar traits

Question 14

pros and cons of dynamic data structure

Answer 14

No excess memory used
no limit to number of items that can be added
BUT additional memory used for pointers
BUT memory leak possible

Question 15

how does a queue work

Question 16

how does a priority queue work

Answer 16

move each item back one place, starting at the rear, until you find an item with same or higher priority to add
Add the item behind that

Question 17

explain how a value is stored in a hash table

Answer 17

hashing algo is applied to key
result is the index to store at
collision when same key generated
collision handling method is used

Question 18

steps involved in rehashing

Answer 18

larger hash table created
values from old table transferred over
to a position determined by new hashing algo

Question 19

procedural decomposiiton

Answer 19

breaking it down to smaller problems
to give identifiable tasks and smaller sub problems

Question 20

benefits of RPN

Answer 20

easier for computer to understand
simpler to code
no brackets needed