.121 15-20 Flashcards

Question

What is the time complexity of an insertion sort?

Answer 1

O(n^2) in all cases

Answer 2

recursively splits array into subarrays till there is just 1 item per array then merges subarrays together by comparing the heads of each

Answer 3

(start index + end index + 1) /2

Answer 4

pick a pivot (point/index) to split the subarray at sort so anything greater than the value of the pivot is behind it (swap any elements > pivot w/ one next to them and once you reach no swaps swap current index w/ pivot) recursively solve subarrays then merge

Answer 5

O(nlogn) in all cases

Answer 6

O(nlogn) in best + avg case but O(n^2) in worst case

Answer 7

non-linear ADT that stores elements hierarchially as nodes connected by edges w/ NO cycles or loops

Answer 8

file directory structures, XML + HTML, compilers and collision detection

Answer 9

root = top node (no parents) children = node w/ parents leaf = node w/ no children descendants/ancestors - relative of relative of

Answer 10

no. of nodes of longest path from given node to some leaf

Answer 11

number of nodes from given node to root

Answer 12

height of its root/depth of its deepest nodes

Answer 13

no. of nodes on longest path between any 2 leaves

Answer 14

n-1 edges as n nodes each have 1 edge going to them other than root

Answer 15

taking a node + its descendants from a full tree basically part of a tree

Answer 16

tree that imposes a max no. of children to each node e.g. binary = max 2

Answer 17

for any node, the height of its child subtrees differ by ≤ 1

Answer 18

void add (Object new, Object parent) Tree find(Object val) Tree remove(object n) void move(Object n, Object parent)

Answer 19

children become the children of that node's parents instead

Answer 20

used to search for nodes + used in move and remove functions

Answer 21

used to enumerate all elements in a tree or decide in which way we look through a tree to find elements

Answer 22

dot to left CLR

Answer 23

dot to right LRC

Answer 24

dot below LCR

Answer 25

all based on a depth-first search so can be implemented non-recursively using a stack or recursively

Answer 26

traverse tree from left to right at each level from the root using a queue (where a level is like root then all of that roots children then all of there children etc.)

Answer 27

DNS lookup compiler packet routing table dictionary

Answer 28

void insert (key k, value v) void delete (key k) value find (key k)

Answer 29

sorted arrays, search trees + hashing

Answer 30

sequential - insert = O(1), find + checking for duplicates = O(n) sorted - find = O(logn), insertion + deletion = O(n) given sorting

Answer 31

binary tree where each node has a k,v pair + nodes are sorted by their keys to be sorted, every nodes’ key must be ≥ all keys in its left subtree + strictly < than all keys in its right subtree

Answer 32

delete() - any children will become children of their ancestor insert() find() - if smaller (go left), if bigger (go right)

Answer 33

finding is very efficient on balanced trees but not degenerate/unbalanced w/ random insertion order expected height h = O(log n) + worst case TC = O(h) aka O(log n) - but can use SBBSTs to ensure this height

Answer 34

2-3 trees AVL trees (SBBST) red-black trees (builds upon 2-3 trees to represent 3-node as BT w/ red link) B-trees (generalisation of 2-3 trees for more keys per node)

Answer 35

splay trees + treaps - helpful for if you wanted tree to balance for common letter patterns rather than any letter sequence

Answer 36

inconvenient to implement -diff. node types - multiple compares per node - moving back up tree to split 4-nodes

Answer 37

2 node = 1 key, 2 children 3 node = 2 keys, 3 children same find() function but more complex insert()

Answer 38

to maintain perfect balance... - a 2-node is transformed into a 3-node OR - a 3-node is split into 3 2-nodes OR - non-root 3-node w/ a 3/2-node parent transforms into a TEMP 4-node (split later)

Answer 39

set of nodes + edges that capture relationships

Answer 40

graph w/ no self-loops

Answer 41

may be directed (arrows) or undirected (every edge = bidirectional) + weighted (associated values on edge)

Answer 42

nodes + hyperedges to capture k-wise relationships ( k > 2) rather than usual pairwise

Answer 43

subset of nodes + edges of a graph

Answer 44

spanning subgraph = formed from all nodes of the graph but only some edges spanning tree = spanning subgraph + tree minimal spanning tree = spanning tree w/ min. total sum of edge weights

Answer 45

same set of nodes + contains all the edges NOT in the other graph

Answer 46

measure from 0-1 that indicates how heavily connected its nodes are

Answer 47

undirected = strong - if path between any 2 vertices directed = weak - undirected ver. is connected but directed is not

Answer 48

addNode (Node n) removeNode (Node n) addEdge (Node n, Node m) removeEdge (Node n, Node m) isAdjacent (Node n, Node m) getNeighbours (Node n)

Answer 49

list of lists or adjacency matrix

Answer 50

N = nodes, E = edges mem. = O(N+E) TC = O(1) for addNode + O(N) for rest

Answer 51

2D array that can represent graphs 1 indicates edge between nodes, 0 doesn't symmetric for undir. so only need to modify 2 cells per edge only modify 1 cell for dir. graphs

Answer 52

N = nodes, E = edges mem. = O(N^2) TC = O(N^2) for add/removeNode + O(1) for rest

Answer 53

depth-first or breadth-first

Answer 54

using stack to push once visited + pop to backtrack start from source then visit current node's neighbours till hit an alr. visited backtrack + continue

Answer 55

using queue to enqueue then dequeue once fully visited start at source + visit all nodes at distance 1, then 2, etc. can form a BFS tree out of list of traversed edges to find shortest paths

Answer 56

sequence of non-repeating nodes from node x to y

Answer 57

given a graph G = (V, E) + source node s… shortest distances (to s) = distance from all nodes v ∈ V to s shortest paths (to s) = for each node v ∈ V the shortest path from v to s pathfinding (s to target) = shortest path from s to t

Answer 58

path that inc. least no. of edges - find using BFS

Answer 59

Dijkstra's - extended to A*, Bellman-Ford + Floyd-Warshall

Answer 60

initialise visited[] to not + distToSource[] to 0 for source + infinity for rest visit closest nodes to you then for all its neighbours if path is shorter than update it do till all nodes = visited

Answer 61

visited[] = not, distToSource[] = 0/infinity, prevNode[] = null do the same as shortest distance +record prevNode accordingly

Answer 62

set up arrays as per visit closest unvisited nodes + return path + distance once you find target path = prevNode[node], prevNode[prevNode[node], etc.

Answer 63

worst case = O(n^2) can improve to O(m + n log n) if using better data structs. like priority queues/SBBST

Answer 64

have extra info (heuristic) on distances for some nodes to source

Answer 65

have edges w/ negative weights (but not cycles)

Answer 66

uses heuristics to guide the search e.g. if weights represent actual travel distances then can approximate to straight line dist.

Answer 67

compute (over)estimations of the distances from source → all other nodes which you iteratively improve on improves all edges every iteration rather than picking 1 each time like Dijkstra's

Answer 68

O(n ⋅ m)

Answer 69

solve your problem in stages + in each stage choose the locally optimal choice fast (approximation) but can be incorrect/non-optimal

Answer 70

generic framework that underlies a class of algorithms e.g. divide + conquer, greedy + recursion

Answer 71

travelling salesman, shortest path + vertex 3-colouring

Answer 72

same as Dijkstra's start at source + visit closest unvisited till all are visited

Answer 73

repeatedly visit nearest node to current node + once all visited go back to origin !shortest route but correct

Answer 74

for i = 1 to V, choose for node v[i] the smallest colour that no neighbour has chosen yet (CANNOT solve vertex 2-colouring though)

Answer 75

Kruskal's + Prim's algorithms

Answer 76

start w/ tree T = ∅, sort edges from lowest - highest weight for i = 1 to [E], if edge e[i] doesn’t form a cycle when added to T then add it to T, or also T = T ∪ {e[i]}

Answer 77

takes O(|E|log|V|) worst case TC

Answer 78

start w/ V[t] = v[1] and E[r] = ∅ while V[t] ≠ V, find min. weight edge {u, w} going from node in T to node outside T, add {u, w} to E[t], w/o loss of generality, u ∈ T, then add w to V[t]

Answer 79

O(|E| + |V| log|V|) - best implementation O(|V|^2) or O(|E| log|V|) - easier implementation

.121 15-20 Flashcards

(103 cards)