general

Question 1

Does the Random Contraction Algorithm always gives you the minium cut?

Answer 1

No this is a random algorithm. It will return the minimum cut solutions only on average!

Question 2

What is the complexity of addition of 2 array of n-digits N+N?

Answer 2

It is O(n) or O(logN) where N is the actual value of the number. Indeed the number of digits n is n= is log₁₀(N)

Question 3

What is the fastest you can be in sorting an array (theoretical bound)?

Answer 3

Nlogn you can never ever get linear time in sorting! So you should love merge sort quick sort etc!

Question 4

What is the complexity of a simple sorting algorithm? name a few of them

Answer 4

They are all n^2 like insertion bubble sort etc. Merge sort a recursive algorithm is actually a n*logn +n algorithm

Question 5

High-level description of a partition with linear time and no memory loss (in place)

Answer 5

See image below, go through the swapping in your mind

Question 6

For an array n what is the maximum number of inversions?

Answer 6

eVERY COUPLE you peek would bein the wrong order with i>j so it is the number of paris (n 2) n(n-1)/2

Question 7

What is the maximum and the minimum number of edges in a graph connected undirected with no parallel edges?

Answer 7

Minumum is n-1 maximum is n(n-1)/2

Question 8

What is the worst case time for a random selection algorithm if the pivot is chosen poorly?

Answer 8

It is O(n^2) like for quicksort. The size of the array you re recursing on reduce as n, n-1, n-2 .. and every time you do a partition which is an O(n) algorithm

Question 9

How does merge sort work?

Answer 9

Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See following C implementation for details.

MergeSort(arr[], l, r)

If r > l

1. Find the middle point to divide the array into two halves: middle m = (l+r)/2
2. Call mergeSort for first half: Call mergeSort(arr, l, m)
3. Call mergeSort for second half: Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)

Question 10

Karatsuba multiplication: simple way to see the formual and a bit of details

Answer 10

it is a n^log_2(3) n^1.6 algorithm compare to the simple quadratic one. Just write x= 10^n/2 a +b y= 10^n/2 c +d and go from there

Question 11

What is the best case scenario (in the choice of the pivot) in random selection? what is its time?

Answer 11

As usual, you want to reduce the size of the problem. So best case scenario is in balance, split the array in equal sizes sooo… the median

if you do that then each iteration

T(n)<t></t>

<p>note now is T(n/2) not 2*T(n/2) like in quicksort. We only need to look at one sort of the subarray</p>

<p>from master method --&gt;<strong> linear time O(n)</strong></p>

</t>

Question 12

Counting inversions: given array count how many object i,j with i>j not adjiacent!! Speed, use etc

Answer 12

with divide and conquer you can get to n*log(n) (as usual we want to have a almost linear algorithm) This is good for similarities say you rank movies and want to check how much 2 lists are close (zero inversion mean very close.)

Question 13

High level description of quick sort?

Answer 13

Question 14

Partition (around a pivot): what is the running time? what about memory

Answer 14

They are linear O(n) and need no memory needed just swap!

Question 15

What is the complexity of merge sort?

Answer 15

n*logn +n

Question 16

Quick sort worst and best case behaviour?

Answer 16

n^2 for the worst n logn for best case scenario but on average very close to best behaviours (decomposition principle)

Question 17

How many different minimum cuts are there in a tree with n nodes (ie. n−1 edges)

Answer 17

Any edge is a minimum cut if you think about it cause every vertex is connected to the graph by one edge

so there are n - 1 minimum cuts.

Question 18

What is the key of the so called decomposition principle for a randomized algorithm?

Answer 18

1. Identify what is the random variable Y you are really interested in
2. Express that as a sum of simpler (indicator i.e variables that takes the )
3. Apply linearity of expectation E[sum(x)] = sum(E(x)) that works even for dependent variables.

Question 19

What is the pivot element in quick sort?

Answer 19

It is an element of the array you pick such that all the elements to the left are smaller than the pivot while all the element on the right are bigger (note they are not ordered!)

Also, note the pivot ends up being in the right place (the finally place it will be in the array after sorting)

Question 20

What is the best way to analyze a recursive algorithm?

Answer 20

Use a recursive tree, find the number of levels (depth) it is usually log(n) at each level j you have 2^j cases that operate on array of size n/2^j then you only have to know the complexity/time of level j (hopefully it is independent of the level)

Question 21

What is O() of nested loops if for i to n; for j i+1 ..n ?

Answer 21

The same still O(n^2) you just save a factor of 2 or so

Question 22

Can integers overflow in python?

Answer 22

Short answers: No if the operations are done in pure python, because python integers have arbitrary precision Yes if the operations are done in the pydata stack (numpy/pandas), because they use C-style fixed-precision integers

Question 23

Results of master method!!

Answer 23

if the recursive time at one step T(n) is < aT(n/b) + O(n^d) i.e the recursive plus the merging step time. Now we have three cases

• 1) a=b^d time is n^d log n
• 3) ad we have O(n ^d)
• 2) a>b^d here how many recursion is crucial time is n^(log_b(a))

Question 24

Minimum cut graph random contraction algorithm!

Answer 24

First, Random sampling very efficient for sorting and graph problem.

Pick a random edge uniformly. Fuse the 2 vertexes into one. You can create parallel loops (keep) or self loop(kill them).

Once you get the last 2 vertices that is the cut: the one represented by the vertices fused with 2 vertices.

Question 25

What is the key to count inversion fast?

Answer 25

To also merge sort we want to sort and count!

Question 26

How many times would 2 objects of an array be compared in the quicksort algorithm?

Answer 26

0 or 1 no more!

because when comparing one is the pivot. Then that number the pivot is removed from the future recursive call

Question 28

What is O() of a loop?

Answer 28

O(size of the loop) it is a linear algorithm, like searching if a number is in an array

Question 29

Outline the algorithm for randomized selection!

Answer 29

It is a reduction (reduce a problem to one you already know how to solve) of quick sort.

say you look for the j-th statistics

you partition with a pivot that ends up in ith position

if i=j you stop

if i>j you look at the left array for a j statistics

i<j>
</j>

Question 30

What are some benefit of insertion sort?

Answer 30

Efficient for (quite) small data sets, much like other quadratic sorting algorithms

More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort

efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position

Stable; i.e., does not change the relative order of elements with equal keys

In-place; i.e., only requires a constant amount O(1) of additional memory space

Online; i.e., can sort a list as it receives it

Question 31

What is the meaning of being O(f(x))

Answer 31

for some large value x, you are bounded below by c*f(n)

Question 32

What is a common way to speed up exponential time algorithm 2^N for example?

Answer 32

Memorization, you want to save on disk previous results. It will increase space complexity but it will reduce your running time. One example is the Fibonacci series where you save the previous results on disk

Question 33

Pretty good way to check if a number is a power of two or not.

Answer 33

def is_power2(num): ‘states if a number is a power of two’ return num != 0 and ((num & (num - 1)) == 0) https://stackoverflow.com/questions/8556206/what-does-mean-in-python

Question 34

What is O() of nested loops?

Answer 34

O(size of the loop*size of the loop2) it is quadratic algorithm, like finding a common number in 2 arrays

Question 35

What makes a pivot in quicksort a good pivot?

Answer 35

You want it to split the array almost in half the most balanced you can!

I.e the median of the array!

Question 36

Describe selection sort

Answer 36

In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(n2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0…4]

// and place it at beginning 11 25 12 22 64

// Find the minimum element in arr[1…4]

// and place it at beginning of arr[1…4] 11 12 25 22 64

// Find the minimum element in arr[2…4]

// and place it at beginning of arr[2…4] 11 12 22 25 64 //

Find the minimum element in arr[3…4]

// and place it at beginning of arr[3…4] 11 12 22 25 64

Question 37

Matrix multiplication! How fast is a naive implementation?

Answer 37

It is n^3 you have a n^2 number in the results and those come from a row*column multiplication so n operations!. Note that you can never do better than the input size, we have n^2 elements so if they are independent (worst case scenario) that is the best we can do

Question 38

What are the 2 structures you can use to store graph? describe them

Answer 38

1) an adjacency matrix. With 1 or -,1 or x in i,j for simple direct or weighted graph when vertices i and j are connected. It is an O(n^2) structure which is optimal only for dense graph where you have n^2 link
2) adjacency list: there are various representations but Each list describes the set of neighbors of a vertex in the graph.

Question 39

What is the minimum cut problem?

Answer 39

You want to compute the cut, partition graph in A, B so that we have the minimum number of crossing edges

Question 40

Do you have a faster than cubic matrix multiplication algorithm?

Answer 40

yes, the Strassen algorithm. Remember where that comes from divding the matrix in blocks and magically using only 7 multiplication instead of 8

Question 41

How many cuts (partition) does a graph of N vertices have?

Answer 41

2^n it is a partition into 2 so every element can either stay in A or B, so 2 possibilities than raised for the N elements. 2^n -2 (to remove the emptyy set)

Question 42

What is the minimum connectivity of a vertex in a graph which minimum cut solution has k crossing edges?

Answer 42

K otherwise I can just cut that only vertex and I will have a partition with a smaller number of crossing edges!

Question 43

What is the maximum number of minimum cuts in a graph?

Answer 43

(n

2)

n chose 2. This is bigger than a tree (n-1) and smaller than the total number of cuts you have which is 2^n

Question 44

How would you choose the pivot in the quicksort algorithm?

Answer 44

You would use random algorithm!

This makes quicksort a randomized algorithm a very successful type of algorithm.

Question 45

How does insertion sort work? What is time and space complexity

Answer 45

Swapping all the element till sorted. For all element it as to go trough the array so O(n^2) but can be doone in place so space is O(1)

Function to do insertion sort

def insertionSort(arr):

Traverse through 1 to len(arr)

for i in range(1, len(arr)):

key = arr[i]

Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position

j = i-1

while j >=0 and key < arr[j] :

arr[j+1] = arr[j]

j -= 1

arr[j+1] = key

Driver code to test above

arr = [12, 11, 13, 5, 6]

insertionSort(arr)

print (“Sorted array is:”)

for i in range(len(arr)):

print (“%d” %arr[i])

Question 46

Time of quicksort on an already sorted array if we pick the pivot as always the first element!?

Answer 46

It is quadratic!! O(n^2) this is a very bad choice of pivot!

Question 47

Do you get any gain in attach recursively the integer multiplication?

Answer 47

Only if you use the Gauss tricks otherwise if you compute all the 4 products you do not gain anything.

Question 48

What is the master method or master theorem?

Answer 48

A quick and efficent way to get the running time in recursive algorithms. It has some assumptions: the most important is that you are breaking the size equally at every recursion

Question 49

Guiding principle to analyze algorithm?

Answer 49

1) worst case analysis (think about the worst case given a lenght n) other options are average case and benchmark but you have to know what is the distributions of your input 2) do not care about small constants etc only O() we do this cause we care about big problems! Also they would depend a lot on the implementation!!!!

Question 50

Find an unbiased estimator for the mean ?

How can you get the variance

Answer 50

It does not exist.

The intuition is that the median can stay fixed while we freely shift probability density around on both sides of it, so that any estimator whose average value is the median for one distribution will have a different average for the altered distribution, making it biased.

If you can sample on it you can do bootstrapping. Divinfg the dataset in batches you can get the variance as well

Question 51

Is the sample of the median unbiased?

Answer 51

Only if the distribution is simmetric.

The sample median is an unbiased estimator of the population median when the population is normal. However, for a general population it is not true that the sample median is an unbiased estimator of the population median. The sample mean is a biased estimator of the population median when the population is not symmetric.