|
A binary tree IS a graph. You can use a BFS quite easily on a binary tree.
|
|
|
|
|
|
You need to find out about 'recursion' techniques
|
|
|
|
|
I'm sure there must be a reasonably simple way to do this.....probably something recursive.
I have X apples and want to split them into groups with a maximum M apples in each group. I want to have the minimum number of groups, but for each group to be 'as equal as possible'.
I think the min number of groups is simply CEILING(X/M, 1)
e.g.,
X = 9, M = 4, groups would be 3, 3, 3 (not 4, 4, 1)
X = 137, M = 25 :: (23, 23, 23, 23, 23, 22)
X = 23, M = 5 :: (5, 5, 5, 4, 4)
etc.
|
|
|
|
|
Kyudos wrote: I want to have the minimum number of groups, but for each group to be 'as equal as possible'.
That is two requirements, they may (and will) be conflicting at times.
X=5 and M=2, now what is best: 2+2+1 or 1+1+1+1+1 ???
when the first requirement is dominant, then #groups=CEIL(X/M)
when the second requirement is dominant, then #groups=X/largest factor of X lessequal M
when a more complex optimum is defined, it will be somewhere in between...
|
|
|
|
|
Well, because groups are 'expensive' (I'm not actually using apples  ) minimising the number of groups trumps 'evenness'.
I think this works:
Min Number of groups G = CEIL(X/M)
Lower Bound LB = FLOOR(X/G)
Upper Bound UB = CEIL(X/G)
No. UB = (X/G - LB) * G
No. LB = (G - No. UB)
|
|
|
|
|
Correct, although I would write that as #UB=X%G
|
|
|
|
|
Suppose I have some number (say between 100 and 1000) of lines of fixed text, each containing 13 pairs of characters; each character pair will be rendered in hardware as a single glyph. The hardware supports multiple character sets of 250 glyphs each, but any particular line is restricted to using one character set.
How would one go about packing things as efficiently as possible so as to minimize the number of glyphs that have to be duplicated in multiple character sets?
Note that I am well aware that using rigid character pairs is not the optimal means of compressing text, but the display hardware that will render the text is sufficiently feeble that it can't handle much else.
|
|
|
|
|
|
hello all,
I don't seem to understand how free space is calculated in NTFS.
I have a 512MB Drive (NTFS)
Cluster size = 4k (512b per sector, 8 sectors per cluster)
$BITMAP file has 4 clusters (Last Cluster is 4032 bytes)
so the total bytes would be 3*4*1024 + 4032 = 16320
so the total clusters it can address 16320*8 = 130560
now 130560*4096 = 510MB (total usable disk space i am guessing)
now if i calculate the total bits that are 0 in $Bitmap that should
give me the total free space
But total 0 bits are only 424.. that means only 424 clusters are free i.e.1696KB
But the disk is 441MB full and 68.6MB free.
(i have really checked my free 0's code it looks ok)
Can anyone please explain this to me?
|
|
|
|
|
This is only a guess, I don't know much at all about NTFS. Is the free-space calculation also including the as-yet-unused space in the allocated clusters as well?
|
|
|
|
|
I have a problem that I'm thinking there must be a clever algorithm for. Given a set of points and a matrix that describes the distance between each possible pair of points, what I want to do is for any given point find two other points that are as far away as possible from the original point, but also as far apart from each other as possible.
I was thinking of doing something like this:
1) pick a random point, let's call it A
2) sort all other points in order of their distance from point A
3) pick the point that is furthest from A, let's call it B
4) For all remaining points (i.e. not A or B) average their distances from both A and B and sort them in order of this average distance
5) pick the point with the highest average distance from A and B, lets call it C
This should at least give me A and B as far apart as possible, but, depending on how the points are distributed, it might be possible C is quite close to A or B.
Also I'd like to extend the method to cope with picking more than three points. In other words, if I need a point D, I could basically repeat steps 4 and 5 (averaging A, B and C rather than just A and B this time), but it seems like it's not very efficient.
Any ideas?
|
|
|
|
|
You need a value function that gives a quantitative evaluation of the three (or more) points. For example, the value function could be the sum of the three distances between the three points.
Then for a given point, go through all possible pairs of other points, and select the pair that gives the highest score for your value function.
After two points are selected, for the third point (the innermost loop) you only have to calculate two distances, which is simple and fast. This avoids the complexities of sorting and averaging, which can make your algorithm slower.
|
|
|
|
|
Thanks for the suggestion. If I'm following correctly then what I have is this:
1) Pick a random point
2) For each possible pair of other points calculate a value (I actually used area - it seemed to work better than total distance) and keep track of the highest scoring pair so far
3) Once I've checked every pair I now have three points that cover a maximum area of the space
The only thing I'm not sure of is the best way to expand this into more points (it's not critical that I do this right now, but I'd like to know). It seems that it would quickly get out-if-hand to do the same thing with all possible triples and/or quadruples, etc.
|
|
|
|
|
If you want the maximum area, you need to look at all triples instead of starting with a random point.
If there are a lot of points and/or you expand this into more points, it may be slow. Here's a possible shortcut: Determine the convex hull of your point set, and look through combinations of those (fewer) points.
The convex hull is roughly the outline / most extreme points in your set, so will probably have the points that enclose the maximum area.
There are many pages of convex-hull algorithms (e.g. http://en.wikipedia.org/wiki/Convex_hull_algorithms[^]) Try to find a simple one that can be easily implemented.
|
|
|
|
|
Hi,
Wjousts wrote: find two other points that are as far away as possible from the original point, but also as far apart from each other as possible.
That is two requirements, and they may or may not contradict each other.
Assume the same problem in one dimension; our example has 5 points at coordinate 0, 1, 2, 99, 100.
Now what are the points that meet your requirements with respect to the point at 0: is it 99 and 100 (maximizing requirement 1) or is it 1 and 100 (maximizing requirement 2), or something else?
You should first give an accurate requirement; if it is really unambiguous, you can then write a mathematical equation (a "cost function") or a software method that calculates how suitable a candidate solution is.
Once that is done, a suitable algorithm can be searched. For small problems, a brute force algorithm can be sufficient (i.e. just consider all possibilities, calculate all costs, and pick the lowest one).
For some cost functions, a smarter algorithm could be found, e.g. alpha-beta pruning might reduce the solution space.
|
|
|
|
|
Looking for the opposite of Djikstra's algorithm -- which finds shortest path between two points.
modified 29-Aug-18 21:01pm.
|
|
|
|
|
Firstly I'm sorry for writing this question here,because I didn't find the Java forum.Anyway I need to help for java code of DX-Ball.(Also I have to use Eclipse editor to do it).Is there anyone can help me about it? if there is please contact with me with meagle87@hotmail.com.
|
|
|
|
|
If you are looking for people to code for you that forum is located here[^]. Otherwise people generally only reply on the forums so posting your email is generally frowned upon.
Best of luck.
|
|
|
|
|
The Java forum is here[^].
|
|
|
|
|
To sum it up, I'm stuck trying to figure out how to implement a sample OPT cache replacement policy algorithm.
Its based on look ahead, I just can't figure out how to implement it in code.
I'm supposed to remove the item that will be called the farthest away from the currently called item.
Ideas?
TIA
[edit]
This had been previously posted in the C++ forum and then this morning I realized it was in the wrong place. My apologies. I have removed the original posting so as not to double post.
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
modified on Monday, January 5, 2009 5:01 AM
|
|
|
|
|
Some more detail would be helpful. E.g. what's an "OPT" cache? (Google doesn't give any insight on this term.) What are you trying to accomplish? What distance metric is implied by "...the farthest away"?
|
|
|
|
|
This is the best description I can find[^]
Basically, the metric is the farthest memory location (or page if we're dealing with pages) is the one that gets victimized and evicted because other "nearer" locations will not cause a cache miss if they already exist.
I know exactly how the algorithm is supposed to go, I'm just having a problem translating that into code.
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
|
|
|
|
|
The OPT algorithm as described in the link swaps out the page that's going to be needed the farthest in the future.
This is highly task dependent. You must have knowledge of your task's memory-use pattern in order to implement OPT. If you can describe this pattern, maybe someone can suggest an algorithm.
|
|
|
|
|
That's precisely it.
I'm building a simulator for a trace file that I have, so that the OPT can be compared to the other policies.
Its based on look ahead and that's what I've done and ended up with a cache's cache so to speak. I'm just not sure if I've done it right.
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
