CS_Algos

Question 1

divide-and-conquer

Answer 1

• take a problem break it down into smaller sub-problems
• solve them recursively
• combine the results of the sub-problems to get the solution to the original problem

Question 2

Merge sort

Answer 2

• recursive algorithm
• canonical divide-and-conquer:
  
  • • split the data in 2 parts,
  • • solve recursively left half,
  • • solve recursively right half
  • • merge the 2 parts

Question 3

Merge sort runtime

Answer 3

O(n log n)
- at level j in the *recursive tree*:
  -- 2^j sub-problems
  -- n /(2^j) items per sub-problem
  -- upper bound per sub-problem:
     --- 6 * #items
- total lines executed at level j:
2^j * [6 * n / (2^j)] = 6n
- total levels from root to leaf in *recursive tree*:
  log_2(n) + 1
- total lines executed in recursive tree:
  [log_2(n) + 1] * 6n

Question 4

Asymptotic time complexity

Answer 4

• big-O notation: (default) upper bound of the asymptotic computational complexity (worst-case scenario)
• big-Omega notation: lower bound of the asymptotic computational complexity
• big-Theta notation: (tight estimates) upper and lower bounds coincide: the function on the left can be sandwhiched between constant multiples of the function on the right: max[f, g] = Theta(f + g)

Question 5

Counting inversions

Answer 5

• inversion in a permutation p is pair i, j w/ i < j for which p(i) > p(j)
• a comparison sorting algos (i.e. merge-sort) can be adapted to count inversions in a sequence
• can be used as a measure of similarity between ratings sequences of 2 users
• merging and counting the split inversions are done in O(n) and the overall sorting and counting in O(n log n)

Question 6

Quick Sort

Answer 6

• choose a good pivot
• split the array in 2 parts: (1) < pivot, (2) > pivot
  
  • • in linear time and in place (by swapping elements)
  • • pivot ends up in the right position
  • • keep the seen elements in the 2 partitions
  • • use 2 counters: (a) the separator for 2 parts in seen elements, (b) the next element unseen yet
• sort the partition (1)
• sort the partition (2)

Question 7

Random contraction algo

Answer 7

• while there are more than 2 vertices in the graph:
  
  • • pick a remaining edge (u,v) uniformly at random
  • • merge u and v into a single node
  • • remove self-loops and allow for parallel edges
• return the cut represented by the final 2 vertices

Question 8

BFS

Answer 8

• explore the entire graph (all nodes) in layers
• used for shortest path discovery (using dist(v) property), connected components (using unexplored property)
• uses a queue, FIFO,
  
  • • initialize it with start of the graph
  • • append new unseen (unxeplored property) item to the end
  • • extract the next item to process from the front
  • • stop when the queue is empty
• O(m+n)

Question 9

DFS

Answer 9

• explore the entire graph (all nodes) aggresivelly withbacktrack
• used for topological sort, strongly connected components in DAG
• uses a stack, LIFO,
  
  • • initialize it with start of the graph
  • • append new unseen (unxeplored property) item to the front
  • • extract the next item to process from the front
  • • stop when the queue is empty
• O(m+n)

Question 10

Topological sort

Answer 10

in a DG is a node labelling such that:

• for f(v) in the set {1..m}
• for any edge (u, v), f(u) < f(v)

Question 11

Strongly connected components

Answer 11

• for a DG graph
  1. reverse the graph
  2. on reversed graph do DFS and mark ‘finnishing time’ as new labelling (start with the main sink node, end of graph)
  3. on the normal graph with new labelliing do DFS repeatdly and mark all nodes discovered by a DFS with its leader (start node) : a SCC; start with max label/finnishing time from previous step

Question 12

Heap

Answer 12

• container of keyed objects with parent’s key smaller than the children keys and the following operations:
  
  • • EXTRACT-MIN O(log n)
  • • INSERT O(log n)
  • • HEAPIFY with n items batches O(n)
  • • DELETE O(log n)
• speeds up Djikstra algo to O(m log n)
• the array representation is by levels in a binary tree such that children of node i are 2i and 2i + 1

Question 13

Sorted arrays

Answer 13

• static data structure with following operations
  
  • • SEARCH O(log n)
  • • RANK O(log n)
  • • SELECT O(1)
  • • MIN / MAX O(1)
  • • PRED / SUCC O(1)
  • • OUTPUT values O(n)

Question 14

Balanced binary search trees

Answer 14

• similar to sorted arrays but are trees with key of left child smaller than parent’s, and the key of the right child is greater than parent’s
• dynamic data structure with following operations
  
  • • SEARCH O(log n)
  • • RANK O(log n)
  • • SELECT O(log n)
  • • MIN / MAX O(log n)
  • • PRED / SUCC O(log n)
  • • INSERT O(log n)
  • • DELETE O(log n
  • • OUTPUT values O(n)

Question 15

Search tree property

Answer 15

• all keys in the left seach subtree are smaller than the current node key
• all keys in the right search subtree are greater than the current node key

Question 16

Hash tables

Answer 16

• the hash function, with diff ways of solving collisions:
  
  • • chaining: using linked lists for buckets
  • • open addressing: probes a sequence of hashed buckets, i.e. linear (first bucket empty in sequence), double hashing (2 hash functions with 2nd as an offset)
• no order guarantee
• operations:
  
  • • INSERT O(1)
  • • DELETE O(1)
  • • LOOKUP O(1)

Question 17

Bloom filters

Answer 17

• similar to hash tables with more efficient space a allocation used to remember values seen
• aka HASH SETS with NO FALSE NEGATIVES guarantee
• cons:
  
  • • cannot store pointers to the objects just the values
  • • can have FALSE POSITIVES with SMALL probability (may say a point is in when actually is not) i.e. validate new item in a list of weak pwd
  • • cannot do deletes
• operations:
  
  • • INSERT
  • • LOOKUP

Question 18

Python list - time complexity

Answer 18

(https://wiki.python.org/moin/TimeComplexity)
avg case, amortized worst case (CPython impl.):
Copy O(n), O(n)
Append O(1), O(1)
Pop last O(1), O(1)
Pop intermediate O(k), O(k)
Insert O(n), O(n)
Get Item O(1), O(1)
Set Item O(1), O(1)
Delete Item O(n), O(n)
Iteration O(n), O(n)
Get Slice O(k), O(k)
Del Slice O(n), O(n)
Set Slice O(k+n), O(k+n)
Extend O(k), O(k)
Sort O(n log n), O(n log n)
Multiply O(nk), O(nk)
x in s O(n),
min(s), max(s) O(n),
Get Length O(1), O(1)

Question 19

Python dict/set - time complexity

Answer 19

(https://wiki.python.org/moin/TimeComplexity)
avg case, amortized worst case (CPython impl.):
Copy O(n), O(n)
Get Item O(1), O(n)
Set Item O(1), O(n)
Delete Item O(1), O(n)
Iteration O(n), O(n) 
(set) x in s O(1), O(n)

Question 20

Python deque - time complexity

Answer 20

(https://wiki.python.org/moin/TimeComplexity)
avg case, amortized worst case (CPython impl.):
Copy O(n), O(n)
append O(1), O(1)
appendleft  O(1), O(1)
pop O(1), O(1)
popleft O(1), O(1)
extend O(k), O(k)
extendleft O(k), O(k)
rotate O(k), O(k)
remove O(n), O(n)

Question 21

Python open() - buffering

Answer 21

the default buffering policy for open():
- binary files will use the default buffer size of the host system
- text files will use a TextIOWrapper only if marked with attribute isatty (interactive tty or terminal)
otherwise specify explicitly the buffer size (> 1, in bytes) for binary files or 1 for text files