|
I have this Insertion Sort algorithm analysis:
[^]
And here is the function in best and worst case scenarios
http://s32.postimg.org/gjgb7n5s5/Untitled2.png[^]
My question would be, how did they get these functions? What is a, what is b? Why in the worst case scenario a is powered by two?
|
|
|
|
|
'a' and 'b' are the standard names of the constants used in the standard representation of a linear function.
Linear Functions[^]
|
|
|
|
|
I am currently working on a procedurally generated game, and vaguely remember having read a book/paper/article in which it was said that there exists a published algorithm which can generate high quality game board games with a random set of rules, which are as good as human designed game board games. The algorithm was NOT limited to a single game such as Sudoku or Crossword puzzles, it rather would generate a set of rules for the players to play by, so it could potentially generate tic tac toe, checkers or 4 in-a-row wins and variations of all 3 games.
I think the article was published between 1980's and 2006ish
and that it was published in a journal.
Sadly I cannot remember where I read the article, only that it must've been in the last 8 months. If you know about this algorithm or something similar to it, please post.
Thanks a bundle,
Mark io
|
|
|
|
|
Hi i have this Algorithm, could anyone help me figure out the answer to it, and how?
Create a recurrence function to represent the following algorithm's time complexity and use the master method to analyse the following algorithm:
/* The function f(x) is unimodal over the range [min, max] and can be evaluated in Θ(1) time
* ε > 0 is the precision of the algorithm, typically ε is very small
* max > min
* n = (max - min)/ε, n > 0, where n is the problem size */
Algorithm(max, min)
{
if ((max - min) < ε)
{
return (max - min)/2 // return the answer
}
leftThird = (2 * min + max) / 3 // represents the point which is 1/3 of the way from min to max
rightThird = (min + 2 * max) / 3 // represents the point which is 2/3 of the way from min to max
if (f(leftThird) < f(rightThird))
{
return Algorithm(leftThird, max) // look for the answer in the interval between leftThird and max
}
else
{
return Algorithm(min, rightThird) // look for the answer in the interval between min and rightThird
}
}
|
|
|
|
|
Your homework is set to test what you know, not how good you are at convincing strangers to do your work for you!
The questions will be based on the material you have covered in your course. If you really don't know where to start, then you need to talk to your teacher.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
|
This is your HomeWork. You are the one that have to work, not us.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
If you are familiar with idle game or incremental games like Adventure Capitalist or Clicker Heroes you know that after a while you are dealing with very large numbers. If you are not aware basically you earn points in these games which you invest so that you can earn more points even quicker, rinse and repeat.
I wrote a small game of this style myself but didn't leave the range that a double couldn't handle but it did get me thinking on how to deal with extraordinarily large numbers.
Just to play around I figured a quick and easy way was to just keep a list with ints, each index represents a higher power and you can easily go higher if needed. index zero keeps numbers between 0-999 and index 1 then starts at 10^3. So index 5 would be ^7 etc.
Except for numbers 0-999 if you want to increase the number I have a function where you specify what number 1-9 you want to add and to which power. If you add say 9^5 to 3^5 it sorts this out by becoming 2^5 and 1^6.
So far I haven't accounted for subtraction yet in my little project but that should be fairly easy in a similar manner.
I think this shouldn't be too computationally heavy unless if used to run addition between several large lists.
Should I want to use this in a game I think it could also be easily adapted to use some approximation to reduce unnecessary work. For example if you have an entity in the game which adds 10^15 points per second and one that adds 10^3 and you show 5 decimals instead of doing all the background computations of adding those smaller numbers every second you just approximate how many seconds before they add as much so that it shows and then go from there if I made myself clear.
public void AddNumber(int value, int power)
{
if (power == 0)
{
NumberContainer[0] += value;
while (NumberContainer[0] >= 1000)
{
NumberContainer[0] -= 1000;
AddNumber(1, 1);
}
} else if(power < mPower)
{
NumberContainer[power] += value;
while( NumberContainer[power] >= 10)
{
NumberContainer[power] -= 10;
AddNumber(1, power + 1);
}
}else
{
}
}
public static NumberControl operator +(NumberControl c1, NumberControl c2)
{
int mMaxp = c1.mPower;
if (c2.mPower > mMaxp) mMaxp = c2.mPower;
NumberControl nc = new NumberControl(mMaxp);
for(int i = 0;i < c1.NumberContainer.Count;i++)
{
nc.AddNumber(c1.NumberContainer[i], i);
}
for (int i = 0; i < c2.NumberContainer.Count; i++)
{
nc.AddNumber(c2.NumberContainer[i], i);
}
return nc;
}
Here is how I add numbers. Thinking about this really got me wondering about how others would choose to solve it instead.
Number container is just a list<int>.
I'm planning on profile how well it handles a few different scenarios, for example if you have a list that goes to the power of 100 and have say 80 "generators" which adds a number at different power levels each second how will it will hold out compared to if I approximate those that are smaller than a certain range from the biggest number.
Reading the numbers is done by specifying how many decimals I want shown and then just walk backwards in the list and adding to a string so unless I want full precision it also works fairly well.
|
|
|
|
|
This forum is for asking questions. What you've got there looks more like a Tip.
Submit a new Article - CodeProject[^]
You might also want to see how your code compares to the built-in BigInteger structure[^].
Eric Lippert did a series of blog posts[^] covering how you could implement integer operations without using the built-in number types, which is also worth a read.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Maybe but then it would need a bit more polish and I'm not sure it would fit, maybe a small blog post and carry with it some test results and discussion around it.
When I started thinking about how to solve this I had a nagging suspicion that there already was something readily available but I couldn't figure out what search terms to use to find it so I turned it in to code instead. That blog post was interesting I admire how some people can go so in-depth in a subject.
|
|
|
|
|
Member 11683251 wrote: Thinking about this really got me wondering about how others would choose to solve it instead. My solution here[^].
Not the most efficient way
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
|
|
|
|
|
|
It may be a good idea to create a struct or class I'll call it LN which has a private vector with intergers VEC in the range of 0 to 9. The class has functions for Algebraic operations (+,-,*,/) to add two LN together. These functions must:
- determine the sizes of both VEC and resize accordingly.
- iterate though both VEC and execute the operation digit by digit.
Since vectors are dynamically allocated, you have virtually no cap on how many digits the number has (accept for RAM).
You'll have to replace all score related constant values in your code with LN 's
I'm not sure how your game mechanics are designed, but if you have many hundreds of entities which add some constant value per second, it might be a good idea to have a single variable X which is added to the game score S every second, instead of iterating through all entities and adding the constant value to S . That is, when an entity is created, it adds it value per second constant E to X and when the entity is destroyed it subtracts E from X .
In every game step you then add X to S . This therefore only requires a single addition operation per game step and of course an addition operation when creating or destroying an entity.
|
|
|
|
|
Concerning the situation that might arise if you have hundreds of entities I figured that I could just do some approximations. The most important parts would be those entities that's closest to the current largest number in the bank so to speak.
If you have one entity that adds say 10^70 you it I could just go over everything below say 10^60 to calculate what to add per second for all those entities instead of doing 60 different calculations.
So far I'm not working on creating a game but this kinda grew from curiosity but I did some testing and 100 different entities, one for each level up to 10^100 was just a few ms. No graphics or anything else but even if I kept increasing it would be a while before there would be a performance hit. For a mobile app it might me more important but my home computer doesn't have a high end cpu so I was quite happy with the current performance.
There is a game called clicker heroes and the highest I ever came in that game was in the span of 10^130.
There are so many of these games out there and they mainly target mobile with in game purchases which costs exorbitant amounts of money. While I see the allure of these games where the amount of in game points you accumulate while you are idle and can just pop in every once in a while to spend and increase the gathering rate I find it hard to comprehend how people can justify dropping 100$ > for in game credits.
I'll see if I make an implementation of your suggestion of vectors if I got the time but it's always interesting to compare different solutions. If I do I'll make a comparison with one of the string based methods too.
|
|
|
|
|
It sounds like you need arbitrary-precision numbers.
With C-1999 or C++2011, you are guaranteed to have a 64-bit built-in type. If you limit yourself to "digits" containing 9 decimal digits (they fit into 32 bits), you can perform the four basic arithmetic operations with "digits" that are easily converted to decimal notation.
The following article (printed in Dr. Dobb's Journal in August 1992; includes source code) should get you started: Multiple-Precision Arithmetic in C | Dr Dobb's[^]
If you have an important point to make, don't try to be subtle or clever. Use a pile driver. Hit the point once. Then come back and hit it again. Then hit it a third time - a tremendous whack.
--Winston Churchill
|
|
|
|
|
i've got this homework problem which i tried to solve and didnt succeed so far. it goes like this:
Given k sets of integers A1,A2,..,Ak of total size O(n), you should determine whether exist a1A1, a2A2,...,akAk, such that a1+a2+..+ak-1 =ak. Your algorithm should run in Tk(n) time, where Tk(n) = O(n^(k/2)*log n) for even k, and O(n^((k+1)/2)) for odd values of k.
|
|
|
|
|
If you want help then you need to make some effort. No one here is going to do all your work for you.
|
|
|
|
|
I have to implement 3 data compression algorithms. I was thinking about LZW, Deflate and Bzip2. I can't find any good documentation for these algorithms. Do you know any data compression algorithms with good documentation, samples etc.?
|
|
|
|
|
I find that extremely hard to believe. A TON of documentation and discussion comes up with a simple Google for "LZW compression algorithm" "Deflate compression algorithm" and "bzip2 compression algorithm".
If you were looking for copy'n'paste code, yeah, that's going to get you a failing grade in class.
|
|
|
|
|
Agreed
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Member 12146827 wrote: I can't find any good documentation for these algorithms. Learn to use Google ! really !
Member 12146827 wrote: Do you know any data compression algorithms with good documentation, samples etc.? Yes, but your claims are just impossible, so you will have to search again. Don't fool us, April fools was 1 week ago.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Run-length encoding is a very simple one. It will save you some work by substituting it for one of the complex ones you mentioned.
|
|
|
|
|
|
Can anyone say which subjects and chapters in mathematics I need to know (thorough or basic) for learning algorithms? Also help me find a book on this mathematical subjects and a good book on algorithms for beginner?
|
|
|
|
|
If you type "algorithms" into Google you will find a wealth of information.
|
|
|
|