So there are plenty of other difficult algorithms to implement. I am sure Dynamic programming tops the list when it comes to competitive programming. But after you do a few questions, it sort of becomes less painful. There are like 5 ~ 6 standard DP problems. More or less every DP question that is asked in a 45-minute interview is a variation of that.
But! D&C! I have never been able to "conquer" anything that is "divide and conquerish", be it binary search or merge sort. Those off by 1 error are so painful to debug. Like all of my array sorts fine, but the middle two elements are out of order. Or I am trying to find a 0 in an array, and it finds the left most zero instead of the rightmost zero. I've spent nearly 10 hours on an easy binary search question in Leetcode and I still managed to get to 40/44 case passing. And I am pretty sure if someone asks me to implement Binary search/Quicksort in an interview, I won't be able to. The only thing I can do is mug up the code and type it out exactly in the interview and pray that it works. Why is this so freaking hard?
In my opinion, it isn't. In fact, you get the solution for the current problem before performing the division in two subproblems. You don't conquer at the end of the algorithm
I'm currently studying for an exam and I have a question I can't find an answer to.
- Why would I not use a recursive divide and conquer algorithm on a small data set?
My friend has a question they came across while studying and don't know the answer to. (The question is looking at running times of algorithms.) There isn't anything in the book to see how to work this question out. Their guess, when it says find the best case or worst case, plug either of the values 0 or ((n/2)-1) into k. Zero seems to be slower.
But the question asks for /any/ value, so that's why I'm posting this.
I posted the question on IMGUR and I'll link it here: https://imgur.com/a/KP2o10y
def merge (A , B): i = 0 j = 0 C =  while i < len(A) and j < len(B): if A [i] <= B [j]: C.append(A[i]) i += 1 else: C.append(B[j]) j += 1 return C + A[i:] + B[j:]
Lets say we have [,,,]
I want [1,2,3,4]
Given merge takes in 2 lists at a time and sorts AND merges them.
Example: [,] after merge = [1,2]
since here [,,,], p=4 and number of elements in each sublist=1
Using D&C we want p/2 calls
so how can I get [,,,] into [1,2,3,4] in just two merge calls?
Think for example of the Cooley-Turkey FFT, or Merge Sort. Say we have an input size of N, with M processors/compute-units available for multithreading.
For a simple O(N^2) DFT, which does N dot products of vectors of length N, we can make parallel the output of every element of the vector X, where X = Wx (W is the Vandermonde matrix). So our running time can become: O(N^2 / M). One of those simple "throw more CPUs at the problem".
But for those more complicated divide-conquer-merge algorithms, I'm wondering how throwing more CPUs at the problem can help. These algorithms will have run times looking like O(NlogN), but I don't see clearly that we can improve this to O(NlogN / M) like in the simpler algorithm.
Assuming we can't parallelize, then this would suggest sticking with the NlogN algorithms until M approaches N/logN, right? ;)
Would love to know what you guys think, cheers.
Suppose that each person in a group of n people votes for exactly two people from a slate of candidates to fill two positions on a committee. The top three finishers both win positions as long as each receives more than n / 2 votes.
Devise a divide and conquer algorithm that determines whether the three candidates who received the most votes each received n / 2 votes, and if so, determine who these three candidates are.
I have previously calculated closest pair by brute force iterating through my matrix of points (n-by-3), which was 'ok', but slow and required some simple parallelisation-I am in Matlab so this constituted using a parfor loop.
However, the problem I now face is I have a new data set where n is ~2e6, so brute force isn't an option.
Anyone have advice or a suggestion? I would love to get this working and prove my post-doc wrong, who said letting me loose on using a recursive was like giving a monkey a hand grenade! ಠ_ಠ
Apologies if this is the wrong place to post.