misc Flashcards
time complexity of merge sort
nlog(n)
time complexity of bubble sort and why
O(n2), n items will be examined, n number of times
base case def
problem that can be solved without any more recursive calls, stops infinite recursion
heuristic solution
discounting consideration of options which may not be the best
static vs dynamic data structures
dynamic can shrink/grow during run time
static size must be declared at compile
protected vs private
protected can only be accessed in class and derived subclasses
why would an adjacency matrix be used
many edges between vertices
edges rarely change
what is the halting problem
non computable problem that determines if the program will stop without running. the program
4 components of a Turing machine
read/write head
transition rules
halting states
state register
what is a universal Turing machine
a Turing machine that can simulate any other Turing machine
and compute any computable sequence
why is a UTM more powerful than any other device
infinite amount of memory/tape
representational abstraction def
removing extraneous details
abstraction by generalisation
grouping by similar traits
pros and cons of dynamic data structure
No excess memory used
no limit to number of items that can be added
BUT additional memory used for pointers
BUT memory leak possible
how does a queue work
how does a priority queue work
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
explain how a value is stored in a hash table
hashing algo is applied to key
result is the index to store at
collision when same key generated
collision handling method is used
steps involved in rehashing
larger hash table created
values from old table transferred over
to a position determined by new hashing algo
procedural decomposiiton
breaking it down to smaller problems
to give identifiable tasks and smaller sub problems
benefits of RPN
easier for computer to understand
simpler to code
no brackets needed
