|
Kindly help me out to solve this question fro the book "Foundation of Algorithm"
There are two algorithms called Alg1 and Alg2 for a problem of size n. Alg1 runs in n2 microseconds and Alg2 runs in 100n log n microseconds. Alg1 can be implemented using 4 hours of programmer time and needs 2 minutes of CPU time. On the other hand, Alg2 requires 15 hours of programmer time and 6 minutes of CPU time. If programmers are paid 20 dollars per hour and CPU time costs 50 dollars per minute, how many times must a problem instance of size 500 be solved using Alg2 in order to justify its development cost?
thanks
|
|
|
|
|
This is a mathematics question, nothing really to do with algorithms.
|
|
|
|
|
If we would do this exercise for you, it would defeat its purpose which is to teach you how to develop and apply your analytical/mathematical skills.
"Five fruits and vegetables a day? What a joke!
Personally, after the third watermelon, I'm full."
|
|
|
|
|
I've come very close a couple of times, but I just can't get it right.
I know one person on Code Project that knows how, but I don't think he's telling. Fair enough.
Does anyone know of any resources on this? Something not math heavy, or at least not math exclusive. I'd prefer sample code or a high level description at least. Any programming language, though I prefer C family languages except java. I'll take java though, as it's what most of academia uses, and this is an academic exercise primarily.
I really would like to solve this for the parser generators I've built.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
I am looking for the stat-of-the-art solver for the 0-1 knapsack problem, Do any one know how to find such a solver? better if it will be written in python or matlab.
Do you know what is limitation of current solver?
Thanks Tomer
|
|
|
|
|
Here is the question requirement:
There is a map shown in below
WWWWWWWWWWDW
WWWW S W
WWWW WWWW W
WWWWSWWWW S
WWWW WWWW W
B ES E W
WWWWWWWWWWWW
W is the wall that the player cannot move to
S is the score can the player option
E is the energy can gain
B is beginning point
D is the ending point
First, player has 0 energy and they need to go to E to gain energy first. Then when they gain energy, they can go to S to gain score. However, every E and S contains different energies, energies required and scores. Here is the clear description of the map:
<5 0> is B (Begining point)
<5 4> is E (energy point, contain 20 energy)
<3 4> is S (Score, require 6 energy to gain and contain 30 scores)
<5 5> is S (Score, require 2 energy to gain and contain 230 scores)
<5 8> is E (energy, contain 30 energy)
<3 10> is S (Score, require 16 energy to gain and contain 30 scores)
<1 8> is S (Score, require 8 energy to gain and contain 10 scores)
The final score is in this formula:
energy + scores - steps*2
The best path is B -> <5 4> -> <3 4> -> <5 5> -> <5 8> -> <3 10> -> D
The key point is that how to let the program or algorithm detect the optimal path (With the minimum steps and know which score should get as in the above example, the <1 8> Score is ignored.)
I am now figuring how can let the computer know going the <3 4> and go back the <5 4> and go to <5 5> is the best path instead of going to <5 5> -> <5 4> -> <3 4> -> <5 5>. I know the later one is a stupid path. But what I can think of is that to do the best path, we may need to search all path with factorial times loop which is not accepted in term of running time.
|
|
|
|
|
This kind of problem is basically solved by brute force because you have to check all paths.
But some techniques allow reducing the workload, like memorizing partial results to avoid recalculating them every time.
Memoization - Wikipedia[^]
For example, all path will start with 'B -> <5 4>' because of the map.
You must put some thinking to understand how the problem works and what simplifications can be done.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Performance shouldn't be a consideration when the problem is "small" to start with. "Optimum" is the same as exhaustive in this case.
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
|
|
|
|
|
how to set soft requirments in the input file ?
|
|
|
|
|
Looks like this question relates to an article[^]. It doesn't make sense outside of the context of that article.
I see you've also posted your question in the forum at the bottom of that article, which is the correct place for it.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Here is the question requirement:
There is a map shown in below
WWWWWWWWWWDW
WWWW S W
WWWW WWWW W
WWWWSWWWW S
WWWW WWWW W
B ES E W
WWWWWWWWWWWW
W is the wall that the player cannot move to
S is the score can the player option
E is the energy can gain
B is beginning point
D is the ending point
First, player has 0 energy and they need to go to E to gain energy first. Then when they gain energy, they can go to S to gain score. However, every E and S contains different energies, energies required and scores. Here is the clear description of the map:
<5 0> is B (Begining point)
<5 4> is E (energy point, contain 20 energy)
<3 4> is S (Score, require 6 energy to gain and contain 30 scores)
<5 5> is S (Score, require 2 energy to gain and contain 230 scores)
<5 8> is E (energy, contain 30 energy)
<3 10> is S (Score, require 16 energy to gain and contain 30 scores)
<1 8> is S (Score, require 8 energy to gain and contain 10 scores)
The final score is in this formula:
energy + scores - steps*2
The best path is B -> <5 4> -> <3 4> -> <5 5> -> <5 8> -> <3 10> -> D
The key point is that how to let the program or algorithm detect the optimal path (With the minimum steps and know which score should get as in the above example, the <1 8> Score is ignored.)
I am now figuring how can let the computer know going the <3 4> and go back the <5 4> and go to <5 5> is the best path instead of going to <5 5> -> <5 4> -> <3 4> -> <5 5>. I know the later one is a stupid path. But what I can think of is that to do the best path, we may need to search all path with factorial times loop which is not accepted in term of running time.
|
|
|
|
|
This requirement is incomplete, you only fave a vague description of what is the best path, how you compare 2 path op see which 1 is better.
and the map look weird.
We can't workout something from this.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Here is the refine question:
There is a map shown in below
<pre>WWWWWWWWWWDW
WWWW S W
WWWW WWWW W
WWWWSWWWW S
WWWW WWWW W
B ES E W
WWWWWWWWWWWW
W is the wall that the player cannot move to
S is the score can the player option
E is the energy can gain
B is beginning point
D is the ending point
First, player has 0 energy and they need to go to E to gain energy first. Then when they gain energy, they can go to S to gain score. However, every E and S contains different energies, energies required and scores. Here is the clear description of the map:
<5 0> is B (Begining point)
<5 4> is E (energy point, contain 20 energy)
<3 4> is S (Score, require 6 energy to gain and contain 30 scores)
<5 5> is S (Score, require 2 energy to gain and contain 230 scores)
<5 8> is E (energy, contain 30 energy)
<3 10> is S (Score, require 16 energy to gain and contain 30 scores)
<1 8> is S (Score, require 8 energy to gain and contain 10 scores)
The final score is in this formula:
energy + scores - steps*2
The best path is B -> <5 4> -> <3 4> -> <5 5> -> <5 8> -> <3 10> -> D
The key point is that how to let the program or algorithm detect the optimal path (With the minimum steps and know which score should get as in the above example, the <1 8> Score is ignored.)
I am now figuring how can let the computer know going the <3 4> and go back the <5 4> and go to <5 5> is the best path instead of going to <5 5> -> <5 4> -> <3 4> -> <5 5>. I know the later one is a stupid path. But what I can think of is that to do the best path, we may need to search all path with factorial times loop which is not accepted in term of running time.
|
|
|
|
|
I recently messed up this question and I can't quite figure out how to solve it. With divide and conquer we can easily tell if the substrings are palindromes (and counting them alone would be easy). But we're not supposed to count them. The long string below should yield "3" as is has 3 levels of palindromes. Not wrapping my head around how to keep track of the rank when unwinding.
"yx xy yx xy yx xy yx xy" // -- not all are palindromes, so nothing here
"yxxy yxxy yxxy yxxy" // all 4 are palindromes - level 3
"yxxyyxxy yxxyyxxy" // both are palindromes - level 2
"yxxyyxxyyxxyyxxy" // whole string is palindrome - level 1
bool isPalindrome( const std::string& str ){
}
int palindromeCount( const std::string& str ) {
if ( !isPalindrome( str ) ) return 0;
int l = palindromeCount( firstHalfofStr );
int r = palindromeCount( secondHalfofStr );
int x{0};
if (l && r ) {
}
return 1 + x;
}
|
|
|
|
|
Maybe you should post the "original question" because your explanation isn't making much sense; particularly the "level" part. Or who said you need recursion? And what does "not counting" to get a count mean?
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
|
|
|
|
|
Sorry for the confusion. I posted as best as I could remember. Actually was something quite silly on my part that was pointed out. WIll post the udpate soon.
|
|
|
|
|
When automatically checking coding exercises, we often run the programs in
question against test cases, which are made up of one input and one output file. As expected,
the program is fed the input file and then its output is compared with the output file. If these
match for all test cases, we deem the program correct.
Coming up with these test cases is tricky. Specifically, we want to create test cases for the
following problem: ‘Given a complete weighted graph G, compute its minimum spanning tree
T’. We have already created the desired output files containing the different minimum spanning
trees, we now want to find the corresponding input files.
It is known that a graph can have many different MST’s. To make testing easier, we want
to ensure that the minimum spanning tree in every output file is unique for the graph described
in the respective input file. The test cases also need to be able to tell apart algorithms that
are wrong, but happen to find the correct MST by chance. For example, if all edges not in the
MST have very large weights, a naive algorithm could find the MST by including only the light
edges. Of course this algorithm would be incorrect in general. To avoid this, we want the input
files to contain complete graphs G whose sum of edge weights is minimum. You need to design
a program that can generate these input files.
Goal: Given a weighted tree T with n nodes, find the complete graph G of minimum weight
such that T ⊆ G and T is the unique minimum spanning tree of G. Assume all edge weights
are integer.
1. Find an algorithm whose run time is polynomial in n.
2. Improve the complexity to O(n · log n).
Hint: One way to do this is by thinking of Kruskal’s algorithm and the cut property of minimum
spanning trees.
can you help me to find a solution ?
|
|
|
|
|
As I said to your other copy of this:
Quote: We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.
So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.
And posting again because it didn't get through immediately never improves your chances of getting an answer: they stay at zero, only because they can't go down from there ...
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Philip decided to supplement his income by participating in the popular game
show ‘Open the Boxes and keep the Best!’. The game is played in turns. At every turn, the
host shows Philip a box that can be opened by paying ci > 0. The box will contain a random
prize: in particular its value could be anything in {0, 1, 2, . . . , n}, uniformly at random.
At every step, Philip can stop playing and keep only one prize, the best found so far. Of course,
the costs he paid are not refunded. All of the boxes are known in advance, as well as the order
the host will present them. Help Philip find the optimal strategy and calculate his expected
payoff, which is the prize he keeps minus the total cost paid.
Goal: Given as input the number of boxes k, the number of different rewards n as well as
the cost ci (which is guaranteed to be integer) of every box:
1. Design a O(n^2· k) algorithm to find the expected optimal reward.
2. Improve the complexity to O(n · k).
Hint: One way is to use dynamic programming
can you help me to find a solution?
|
|
|
|
|
We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.
So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Hello guys, I'm new here I was trying to learn more about algorithm by solving as much as I can from different sources anyway I found a question which makes me think about it every day and I couldn't find a proper solution for it check this link out and if you can give me ideas how to tackle this it will be great
infinite_recursive_shape_challenge
Thanks.
|
|
|
|
|
The ideas are all in the problem description.
|
|
|
|
|
I'm trying to convert a finite state machine back to a regular expression.
I'm looking for some help with one of two algorithms that i just don't have the math background to transfer to code. I've so far had no luck wrapping my head around it and it's frustrating.
Theory of Computation | Generating regular expression from finite automata - GeeksforGeeks[^]
I don't necessarily need actual code. I can deal with pseudo code. or pretty much any language (except java - for reasons having to do with the way their containers/collections work)
I'm trying to do this in C# though so some pointers would be helpful.
I know the basics of DFA and NFA machines enough to implement a regex engine. I simply cannot do this one thing.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
For a coding project I'm working on I need to predict the amount of workers that are necessary to finish a task within a limited time frame T. Lets rephrase it a bit...
Given a collection of object X; that implements a blocking function that takes object Y as a parameter; from a queue of said Y objects; that does work for anywhere between TimeX1 < Time < TimeX2 ms.
Given the fact that the pool of Y objects is vastly larger then the X objects;
And that every time an object X finishes working on an object Y it takes another object Y from said queue.
And Given that the total amount of work time of all X objects combined cannot exceed MaxTime
What formula would predict the least amount of X objects necessary to work on the whole queue of Y objects?
|
|
|
|
|
Sounds like a simple maths problem. 
To guarantee that the queue will be processed in time, you have to assume the worst-case scenario - that each Y takes TimeX2ms to process.
Therefore, the total time to process the queue will be:
TimeX2 * Count(Y) / Count(X) You want that value to be less than or equal to the MaxTime, so:
MaxTime >= TimeX2 * Count(Y) / Count(X)
Count(X) >= TimeX2 * Count(Y) / MaxTime Therefore, the minimum number of Xs required will be the ceiling of the number of Ys multiplied by the maximum time to process a Y divided by the maximum time allowed.
NB: If you were willing to accept that the queue might not be fully processed within the time limit, and you had more information about the distribution of processing times, then you might be able to bring that number down a bit. You could also consider an adaptive approach, where you increase or decrease the number of Xs over time based on the number of Ys waiting to be processed and the amount of time remaining.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
