|
A[0..n − 1] is an array of n distinct numbers. A pair of array elements (A[i], A[j]) is
called an inversion if A[i] > A[j] for i < j.
1.1 Design a brute force algorithm to count the number of inversions in an array, analyze the
number of executions of its basic operation, and determine the efficiency class.
1.2 Design a recursive divide-and-conquer algorithm of Θ(n log n) to count the number of
inversions in an array, set up a recurrence to analyze the number of executions of its basic
operation of the best case, and determine the efficiency class. Use the Master Theorem
to verify the efficiency class in your analysis result.
Anyone help me in finding the solution of this question.
|
|
|
|
|
It would help if you would post where you are stuck. It's unlikely anyone is going to do it all for you.
|
|
|
|
|
Show your work and explain where you are stuck.
The 1.1 should be rather easy.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
In a card game involving 2-4 computer players, does an algorithm exist for determining which of the player(s) has the highest card (e.g., 2 < 3 <...< K < A)? With two players, it's simply:
if (player1 > player2)
player1 wins
else if (player2 > player1)
player2 wins
else
tieBut that does not scale well at all for 3 or 4 players. When I tried something for 3 players, it was ugly and nearly unmanageable. 4 players was not even attempted.
Thanks.
DC
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
|
|
|
|
|
It sounds for me you need something like a sorting algorhythm ...
Now you can sort the Players according to their points ...
|
|
|
|
|
You don't need a full sort. It would work, but it's overkill.
Essentially you have an array (or list, or collection of some sort) of card values, indexed by player.
The standard linear-time algorithm for finding the max or min of an array and remembering where you saw it...
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
Very roughly in pseudo-code for traditional languages (no particular language)
nPlayers = 7;
int cardForPlayer[nPlayers] = (cards for each of the players);
int bestPlayerNo = 1;
int bestScore = cardForPlayer[0];
for (int playerIndex = 1; playerIndex++; playerIndex < nPlayers)
if (cardForPlayer[playerIndex] > bestScore)
{
bestScore = cardForPlayer[playerIndex];
bestPlayerNo = playerIndex + 1;
}
For a simple functional style language (no particular language)
cardForPlayer = List p1card, p2card, ..., p7card
bestScore = max cardForPlayer
bestPlayerNo = (FindIndex cardForPlayer bestScore) + 1
|
|
|
|
|
Give OP's seniority and rep, I didn't condescend to spelling out the algorithm.
I've lost track of the number of times and different languages I've implemented it...
There is a useful variant where you start with a sentinel value ("minus infinity" or whatever) and compare every one including the first.
This handles the case where there is no item that qualifies for selection.
In this example, it would be easy to skip a player if he has no card. What if nobody had any cards?
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
You have a "list" of players.
The list is always processed in order; so the "first" element in the list should be the the player that plays first, etc.
After the last player, you cycle back to the first. A "pass" just bumps the player index.
I wrote a GO game on that basis; for 2 to 7 players; humans and bots. 7 was an arbitrary limit (The Warring States).
The "top" player is the one with the .Max something; unless it's tied.
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
|
|
|
|
|
Suppose your operations on arrays were constrained as follows:
- .get(i) accesses the element at index position 𝑖 in read-only fashion.
- .length() returns the length of the array.
- .flip(i) flips the array up to index position 𝑖. Thus, the {1,2,3,4}.flip(2) operation changes the array to {3,2,1,4}.
Only these three operations are available to you. Also assume that the three operations are in 𝑂(1).
Develop an algorithm that sorts a given array in 𝑂(𝑛 × 𝑙𝑜𝑔 𝑛).
Suppose you have an array of length 𝑖 + 1. You want to correctly sort the element at position 𝑖. The array is already sorted up to 𝑖 - 1. The correct position of the element at position 𝑖 is index position 𝑗. Find a sequence of flip operations that inserts the element in the correct location.
Problem: I have no idea how to begin
modified 14-Dec-20 13:06pm.
|
|
|
|
|
If you can figure out the last paragraph, you'll have a way to move an element into the correct position when it's out of place. That element might only be part way down the array, in which case you can move it up by only doing flips as far as that element, leaving the elements after it alone.
Start with an actual example, say 1235674. You want to move 4 up into the position currently occupied by 5. Clearly, 4 must be included in the first flip, else it'll never move. So flip(6) is the first operation, which yields 4765321. Now the ball is in your court.
|
|
|
|
|
They don't say to flip one way or another. Looks more like a rotate. Poor spec.
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
|
|
|
|
|
|
Read on the lines of bubble sort. That should help solving this
|
|
|
|
|
Could help me solve this problem pls?
The job is to calculate the degree of discontent of passengers on a bus.
Passengers get on the bus, all at the same point and say at which point they want to stop (that point is the mileage from the point where they get on the bus to where they want to disembark), but the bus can only make k stops, that is, it is a value limited number of stops. The discontent will be calculated as follows (x-y) * 2 where x is the place that each passenger chose to stay and y where the bus stopped. The K will be defined after calculating the discontent of each passenger
|
|
|
|
|
1. Nobody here is going to do your homework for you.
2. That's a maths problem, not a programming problem.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
|
If we do not take into account the growth of passenger dissatisfaction due to an excessively large number of stops, then in a first approximation the formula will look like this ((x - y) / k) * 2 But this is just my opinion.
|
|
|
|
|
Hi,
I am building a small web app that allow stamp collectors to swap their stamps. The main problem I am trying to solve is 1-on-1 (direct) swap. Since usually A needs something from B, but B not always need something from A.
But the solution is to find a circular swap, for example:
A needs from B
B needs from C
C needs from A
result: everyone is happy.
I have a list of collectors, and for each a list of stamps they got, and a list of stamp they are looking for.
I am trying to find a way, to create a circle, by matching the "have" and "want". The problem is that this may take a very long time with lots of collectors and lots of stamps  .
What would be the best approach for this?
The straight forward algorithm I think (which is obviously not optimized) is to:
1) look what "B" want.
2) find who got what B want (stamp after stamp)
3) for each one, see if he (C) needs something from A
4) if yes, YAY
5) if not, see what C want (stamp after stamp)
6) for each one, see if (D) has something from A
... and so on ...
long procedure...
Any suggestions will be very welcome. Thank you
|
|
|
|
|
Just advertise stamps (for sale) and what the seller wants. Period.
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
|
|
|
|
|
In mathematical terms your problem can be stated as finding the cycles of a directed graph. Collectors A, B, C... are nodes in graph and what they want are graph arcs.
Now, if you Google for "finding graph cycles" one of the first results should be Tarjan's strongly connected components algorithm - Wikipedia[^]
You might have already found a solution but anyways...
Mircea
|
|
|
|
|
Thanks!
Yes, you right, I already find this path of solution and working on it.
Thank you for taking the time to answer 
|
|
|
|
|
This is my first question in this forum, so suggestions for improvement are welcome.
I have a data set of arrays which contain Floats between -1 and 1 and a new array of the same format.
The arrays have a length of up to 300.
I have to find the array from the data set that has the smallest distance to the new array.
IMPORTANT: The values of the arrays must remain on their position, while it's alowed to sort the arrays in the data set.
How can I achieve this while keeping an acceptable trade-off between accuracy and scalability?
Of course I could just go through every array but that wouldn't be scalable I guess.
PS: Usually adjacent values have a similar value (so [-0.8, 0.3, -0.7, 0.9] would be very unlikely).
|
|
|
|
|
CLOSED
modified 16-Nov-20 11:38am.
|
|
|
|
|
By identical, I assume you mean isomorphic. See here[^], which speculates that the problem may be NP-intermediate (between P and NP-complete).
Let's call the two graphs G1 and G2. On the surface, the problem seems NP-complete because you have to compare G1 and G2 after renaming the n vertices in G2 using names from G1, so there are n! combinations to try. However, some combinations can be filtered out quickly. For example, a vertex in G2 has to have the same degree (number of edges) as the one it is being compared to in G1. But if this check passes, there's still more checking to do, as in the case of the graph with 6 vertices shown in your link.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
