|
If T1 was chosen in the middle of a range, then whichever result Algorithm1(T1) gives, half of the range will be uninteresting (either all False or all True).
|
|
|
|
|
@harold aptroot -
Sorry, but I'm not sure I got your point.
I agree if you mean the following: In case we've divided S by 2, and Algorithm1(T1) == TRUE, then we know for sure that T_Optimal <= T1.
So the algorithm should go as I described before, no? With the division each time by 2. But it's probably not sufficient as we may skip on some T1 which gives FALSE, and from there we don't know the amount of time units to add up...
|
|
|
|
|
When the result for T1 is False, that also cuts off half of the current range: the first half.
|
|
|
|
|
Genius. It reminds me a little bit the procedure of Partition in QuickSort.
So we sort with Algorithm1(S), if it returns TRUE we call Algorithm(0.5 * S), and so on...
If at some point (after i steps) we call Algorithm1(0.5^i * S), and it returns FALSE, we call Algorithm1(0.5 * (0.5^i * S + 0.5^(i-1) * S)), and so on...
Hmmm actually now I'm not sure about my suggestion.
Should I actually initialize an array of size S with all the natural numbers from 1 to S?
Thank you!
modified 26-Jun-20 16:56pm.
|
|
|
|
|
Member 14873814 wrote: It reminds me a little bit the procedure of Partition in QuickSort.
It has a bit of that flavour. What it reminds me of is Binary Search (well that's what it is, but a specific variant).
Member 14873814 wrote: Should I actually initialize an array of size S with all the natural numbers from 1 to S?
No need, you can pass the index itself straight into Algorithm1.
|
|
|
|
|
What index exactly if there is no an array?
|
|
|
|
|
If it was a "by the book" Binary Search, there would be an index into the array of data. In this case the data does not explicitly exit, the array is replaced by a function (Algorithm1).
|
|
|
|
|
But I'm not sure how I should treat the data in this case.
Let's suppose our sum of job times is S = 100.
We have k = 3 assignees.
We start by calling Algorithm1(100) == TRUE of course
Now we are calling Algorithm1(50) == TRUE
Now Algorithm1(25) == FALSE
So in this case we want to check the middle between [25, 50], so we can get that by calculating 0.5(*25 + 25*2), so that now we call Algorithm1(38) which returns TRUE
But what now? We would divide again 38 by 2 and go out of the range [25, 50].
See the problem?
|
|
|
|
|
If the range was [25, 50] and 38 was picked as the midpoint and Algorithm1(38) is True, then the next range is [25, 38]. No problems, just updating the endpoint of the range. Taking the average of 25 and 38 ("divide by 2" is only what happens when the startpoint is zero) also does not cause a problem. Taking an average never "escapes" from the range.
|
|
|
|
|
@harold aptroot
For some reason I can't explain I don't see your last comment on this topic, where you mentioned the idea of saving the start-point and end-point. (I see it through the notifications on the site and in my mail)
Amazing, simple and genius.
So we actually suggested a polynomial greedy algorithm.
BTW, how do you approach to prove the correctness, specifically the optimality of this algorithm?
Thank you so much!!
|
|
|
|
|
The "sub problem" is to not assign more "job time" than T1 to any one assignee.
Since there was no constraint that said an assignee could not be "idle" (or "optimal"), one can simply read contiguous jobs (in say reverse time order) and assign "blocks" until they're used up or assignees are at capacity.
The "dynamic" part is the looping through the job list and assigning them (depleting the job list while adding to an assignee's jobs.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
Hey Gerry,
I'm not sure you refer to the next section of the problem we're dealing with now:
The next section of the problem asks us for the following:
Use the first algorithm (...at most T1...) to describe a polynomial algorithm calculating the optimal time T to accomplish all the jobs.
I think you've suggested a greedy algorithm for the first section of the problem which is written at the main post.
|
|
|
|
|
Hi,
I was wondering if anyone knew whether the implementation of the
hash function in a hash map is the same as in a hash table, i.e. are
the same implementation options available for a hash map?
Also, I wonder why Hash tables were deprecated in Java 5 other than
having multiple locks in the ConcurrentHashMap class and whether
ConcurrentHashMap implements the same hash functions as a Hash Table.
This is likely a question for Oracle or Microsoft or for someone who has worked there. If anyone knows, please share.
Thanks,
Saad
|
|
|
|
|
The hash function should be identical for a hash table and a hash map; in both cases you go from a key to a table index.
|
|
|
|
|
I have algorithms work to do and I am willing to pay for this if someone could do this for me, just a few questions.
Contact me via PM for details.
|
|
|
|
|
Nope. Not going to happen.
This is not a "for hire" site. If you want to pay someone to do your work for you, go to Freelancer.com.
|
|
|
|
|
Bidding starts @10k/month. PM for details.
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Eddy Vluggen wrote: 10k/month
You forgot "... or part thereof". 
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
For part of the work, maybe 
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
What does that even mean? Writing code? Designing algorithms?
Social Media - A platform that makes it easier for the crazies to find each other.
Everyone is born right handed. Only the strongest overcome it.
Fight for left-handed rights and hand equality.
|
|
|
|
|
I always considered an algorithm to be at a rather abstract level: A principal method of solving a problem, way ahead of the coding. An algorithm can be described in prose, or if you want it in a more formal way, in pseudocode. Developing new algorithms is to develop new methods. A different way of doing sorting. Or load distribution. Or image compression. Or...
When that new method is described in sufficient detail in free prose or pseudocode, the algorithm design work is complete. You may hand it over to an implementor, who might realize the pseudocode in lisp, or Prolog, or APL, or Javascript, or Fortran IV, whatever he chooces. (He might even choose K&R C!) That is implementation, not algorithm design.
So when someone asks for new algorithm designs, they essentially ask for research work. Developing principally new methods for solvin a given problem.
I certainly don't think that Member 14843185 is inviting you to participate in a research work aimed at finding new solutions. His project is somewhere on the long line between basic research and homework. Honestly I suspect that it is leaning over to the homework side. Or at least implementation of known methods, not developing new methods.
Coding for pay. You may be cynical enough to say: Even if it turns out to be to do his homework, if he pays me for it, it is his problem that he is not learning what he should learn. Or your morals may say that it isn't right - he is fooling himself and you should not contribute to it.
If he really represents some serious development company in search of consultants to take on a project with them, you might consider it. But I think this looks like a rather strange way of hiring consultants.
|
|
|
|
|
Member 7989122 wrote: So when someone asks for new algorithm designs, they essentially ask for research work.
Anything that is not a reusable from a previous work, is research work.
Member 7989122 wrote: Even if it turns out to be to do his homework, if he pays me for it, it is his problem that he is not learning what he should learn
Not just his; if he creates a bug in a hospital system that may kill a few thousand..
Member 7989122 wrote: Or your morals may say that it isn't right
Not as much moral as reality. Depending on the pay, those morals are for hire.
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Means he's here to find grunts, because those companies that supply them are too expensive.
Point is, he's not here asking questions about code. Find-a-grunt is another website 
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
Your question is extremely vague, you need to give more detail, just to let us know the kind of work you want.
To hire a programmer, try: Freelancer[^]
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Your task is to develop an algorithm that would sort data such as these from least to greatest. Specifically, given an unsorted set of N decimal values, your algorithm should sort them to give an answer of the sorted data. For this set of N = 6, your algorithm should produce:
-0.12
0.53
0.98
1.36
1.92
3.18
Execute your algorithm for a different set of data, such as a subset of the given data, data you make up, or another month's climate data, such as February 2017: https://www.ncdc.noaa.gov/sotc/global-regions/201702
Does your algorithm work for any N? Have you thought of corner cases it might need to handle, such as N = 0 or N = 1?
Reply·Email·View Thread
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
