Tag Info

New answers tagged

0

Do a "binning" of the initial black box stack into N groups of equal proportions (your A-D, D-K...). At that point you can use any O(n log n) algorithm to sort each group in turn. Actually, you could pop items from the black-box stack directly into a group of N red-black trees. But if you have lots of identical elements... could you not just store a ...


0

I do not know what DP algorithms you tried, but here is one which solves your problem. The algorithm works inductively by increasing number of boxes (each time for all n below N). In each step, you store the maximum of f1+...+f_m, where m is the number of boxes in the particular step (0<=m<=M). Use the solutions for m-1 boxes to solve the problem for ...


2

If you need not strictly the global maximum but just a “fairly good” solution, you can approach this kind of problem by an approximation technique known as local search. The idea is that you start with a given solution and try to improve it by making “simple small steps”. In your case, such a step could be moving one ball from one box to another. Here is ...


3

Finding a factorization of a (usually large) number (often some bignum in practice) is an intractable problem : there is no known efficient (polynomial time) algorithm for that. But it is of course a decidable problem: you can try to divide that number N by every positive integer number I whose square I2 is not larger than N, and there is a finite (but often ...


8

No, it is not an impossible problem. There is a finite number of prime-numbers smaller than a given natural number, which means there is a finite number of ways they can be multiplied with while still being equal or less than the number. You can simply try them all until you found the correct solution. There are several algorithms for integer factorization ...


2

Using a binary tree for collision handling in a hash table isn't just possible - it has been done. Walter Bright is best known as the inventor of the D programming language, but also wrote an ECMAScript variant called DMDScript. In the past, a headline claim of DMDScript (or possibly an ancestor - I seem to remember the name DScript) was that its hashtables ...


5

What you are asking for is possible given your constraints. Analysis A hash table's strength is its fast lookup and insertion speed. To get that speed, one must forsake any semblance of order in the table: i.e. entries are all jumbled up. A list is acceptable to use as a table entry because while traversal is O(n), the lists tend to be short assuming the ...


0

I would simply use a sorted array. Biggest number to the left for the example. When you decrease the biggest element you do this: If the next smaller element is the same size, use that instead. Loop until the next smaller element is actually smaller. Then decrease the current value by one. The list is still sorted. Insert is n log n, same as any sorted data ...


0

I don't remember i ever encountered a real life situation when a heap was the best solution. It sounds to me that what you need is a self balancing Self-balancing binary search tree . You should probably look into AVL trees, and Red-Black Trees. Binary Search Trees have very similar performance characteristics to a Heap, but they are much more useful, and ...


3

1. No. You can do a LOT in game development with only the most shallow knowledge and understanding of Computer Science. You don't need CS knowledge to do graphic design, nor do you need it for most 3D design. You don't need CS to tell a story, which is essentially what most quest games do. You don't need CS to think about game-play and usability, and design ...


3

The short answer is yes. It depends on the complexity and innovation of the game being designed. Some games, say, Gravity Master, looks simple enough but actually requires a rigid body physics solver. All games involve programming; software with increasing functionality requires more programming, which I hope is obvious to you. The majority of games ...


2

For the max stuff I'd use a heap, for the min a simple variable (to be potentially updated when the decrease operation lets the previous maximum fall all the way to the bottom of the heap).


0

I guess you don't need this anymore, but since I realized gnasher's bump only after thinking about this, I'll leave some imho nicer code here anyway: def check_distance(X, k): A = merge_sort(X) return all(b-a >= k for a, b in zip(A, A[1:])) I'm interested in the teacher's solution. Did he just have this braindead sort and sweep in mind, or ...


0

The obvious solution is to sort the array in O (n log n), and then the elements can be checked sequentially in O (n). I wonder what is going on in the teachers mind when he asks for a "divide and conquer" algorithm.


1

It looks like all your items have the same size, in which case the solution is trivial. Count the total number of items, let's say that number is c. Say there are n buckets. Calculate x = floor (c / n) and y = c - n*x. Then y bins get filled with x+1 items, and n-y bins filled with x items. To make this an interesting problem, assume that the different ...


0

I don't know of a formal algorithm. I implemented this once long ago. The algorithm depends on not only the enumeration of line segments, but also on the "side" of the line segments that the parallel path is meant to follow. Assume you know the "side". My set of line segments was (as you describe) a list of 2d points (x,y). For each point p, I looked at ...


4

You basically have a tournament. In a round-robin tournament, 40 players can play 39 rounds and meet each player exactly once. The Wikipedia article on round robin tournaments has a description of a simple algorithm to generate the pairings for each round. There are also pre-computed tables on the Internet (look for Berger tables, for instance), but not ...


1

Wouldn't you want to iterate through the number of total items and not buckets^2? For example, item[0] goes into bucket 1. item[1] goes into bucket 2. item[2] goes into bucket 3. item[3] goes into bucket 4. item[4] goes into bucket 1. Some things to think about: Does each item have a property, item-type as part of its definition? For example, you know a ...


3

For item quantities A, B, C and buckets quantity N, each bucket should keep close to A/N + B/N + C/N items, respectively of each kind. Actual putting the items should take O(N). You can distribute A mod N + B mod N + C mod N items slightly unevenly among buckets using round-robin choice: put a remaining item of type A into bucket #1, remaining item of type ...


1

For example for the number of ways to go from 10 to 1000: Let A (N) = number of ways to get from N to 1000. Calculate and store A (N) for N = 1000, 999, ..., 10. For N = 1000, 999, ..., 501, A (N) = 1 because you cannot double the number. For N ≤ 500, A (N) = A (2N) + A (N + 1), because you can either double and get from 2N to 1000, or increment and go ...


1

See http://stackoverflow.com/q/5527437/10396 for an implementation of a rolling median that uses a min-max heap to process each new sample in O(lgN). The heap keeps the data loosely sorted into two groups, one bigger than the median, one smaller. For each new sample, it swaps the the oldest item in the heap with the newest one. Rebalancing the heap takes ...


0

My suggestion would be to slurp the large list into a hash set, then use that to match items from the small list. A hash set is a structure that stores elements in an indexable memory structure, like an array, where the position of the element is equal to some hash value calculated using the object. That means that looking for a value in the hashset is a ...


0

Thanks to @Kilian Foth I have a solution: [...] if you just want to collect all interval boundaries into a single list, uniquely sort it and then construct new intervals from every two values in the list. [...] Array of overlapping intervals: [ {0,7}, {8,12}, {13,17}, {0,3}, {4,9}, {10,17} ] Single list, uniquely sorted: ...


2

Sort both lists with an efficient sorting algorithm (or ensure that the lists are "pre-sorted" by whoever/whatever created them). Then, if the first name in both lists is the same you've found a match, otherwise discard whichever name is "earlier"; and do that until one of the lists are empty. Some crude pseudo-code: do { status = ...


1

Sort the small list with an efficient sorting algorithm, traverse the big list and for every item in the big list use a binary search to find whether there's a matching item in the small list.


0

Finding things in one set that match those in another set and merging data is something that relational databases excel at. If this is something you need to do a lot, loading your lists into tables in your choice of SQL DB is probably your best option.


0

We were told numbers could be up to about 10^12 and about 20% of numbers would be used. That is 2 * 10^11 numbers actually used. With these numbers, the best you can do is a bitmap of about 125 GBytes, and if you can't afford the RAM, an SSD drive and virtual memory will have to do. You should probably measure whether "normal" file access is faster than ...


-3

Just to add a suggestion to the other solutions. In the biomedical world we often search for specific strings of data (ie genetic patterns). Research has shown that attacking the parent string in the reverse direction, the last entry to the first, is faster that going forward through the string. I guess this is some how related to slurping in all the data ...


1

For the first card you have 52 options for the second you have 51 and so on. You need to encode a sequence c1, c2, c3, c4 and c5 where there are 52, 51, 50 ,49, 48 options resp. You can adjust the numbers by counting how many of the previous numbers are smaller: a5 = c5 - sum(x < c5 for x in [c1, c2, c3, c4]) you can simply encode it as a single integer ...


1

I would try to go for the bitfield too, but if the data is sparse and the range too great to make this work, a splay tree might be a good data structure to use. Splay trees are modified on each access (so they are not thread-safe, which could be an exclusion reason for you) to optimize repeated access to the same element. Often-used elements bubble to the ...


2

You could generate a binary tree (radix tree aka trie). To prepare for the search, for each number in your array, starting with the least significant bit, if it is 0, you look to the left node. If it is 1, you look to the right node. You follow the tree until you find no more nodes, and from there you create the tree one node at a time. To search, ...


2

For certain types of data, you can achieve constant time median filtering (Perreault et al, 2007). That paper describes 2D median filtering on images, assuming the pixels are 8-bit integers. Note that "constant time" refers to constant time in the size of the window; it is not constant time in the size of data, or in the precision (bits) of data. As ...


8

If there is a known maximum N, you can use a Bit array for really fast lookup time. Simply keep an array of size N/8 (rounded up) around, with each bit corresponding to a number, 1 if it is in the set, 0 if it isn't. Lookup the relevant bit to check whether a number is in the set. If this is too slow, and you have the megabytes ("millions" doesn't sound ...


2

Lets assume N=100. You have the raw values in chronological order raw[1],...,raw[100] and you have the ordered list of the same values as ordered[1],...,ordered[100]. What is the median? The median will be (ordered[50]+ordered[51])/2. Lets now move the window one position so raw data will be raw[2],...,raw[101]. How do you generate an updated list for ...


6

In this specific case, you can replace the variables with their minimum and maximum values to find the number of steps for each loop. The first loop goes from 0 to n, the second loop goes from 0 to n*n and the inner loop goes from 0 to n*n. So there are n2 iterations of the innermost loop, times n2 iterations of the second loop, times n iterations of the ...


0

Is there any table giving the average of comparisons of these algorithms for a few N numbers The exact number of comparisons needed may depend on the specific implementation of the algorithm, not on the algorithm itself, and so will the average number. So even if you find something like what you requested, I find it very unlikely that you can compare it ...


0

But, why does it work? Since XOR works bitwise, it is enough to assume that a and b are just one bit long. In this case, XOR is just the same thing as the addition modulo 2. Now if a[0] and b[0] denote the value of a and b before the calculation and a[1] and b[1] their value after, we have (modulo 2): a[1] = b[0] + 2*a[0] = b[0] b[1] = a[0] + 2*b[0] ...


0

Yes, there is a lot of them! This is just the theory of even and odd part of functions adapted to this context. Take any function h defined on pair of strings and set ĥ(a,b) = h(b,a). Then the odd and even part of h are respectively h- = (h - ĥ)/2 and h+ = (h + ĥ)/2. Now, if you take any function h defined on pair of strings, then its odd part h- suits ...


5

You could do this with any string distance function. For example, consider the following distance function: distance(a, b) { return calc(a, b); } If you make the order of the arguments significant, then you can invert the sign of the result as needed: distance(a, b) { var first = getFirstAlphabetically({a, b}); var isNegative = (a != ...


0

I will answer your question. So why don't we just read raw binary in the memory? But we are reading raw binary - calculations, netowrking, it is all binary-based representation. I will go a step further and say that computers ultimately use only binary representation. Isn't it much easier and faster? If possible, how to do that in C or Assembly? ...


1

Yes, it's true. Both strings and decimals, as well as all other types, are represented in binary. However, the problem lies in the significance of the binary. You cannot simply read a string as a decimal, or at least you shouldn't if you were looking to get the decimal representation of that decimal. Take for example this string in ASCII: "1.5" In ...


1

We do work with binary representations of numbers internally, but ultimately people want to use a computer program, and there the format isn't usable. So we do need to have code for converting string representations of things into binary, but only for new data entered by the user. People are extremely bad at remembering information-dense representations - ...


3

When you find a statement like "M number of comparisons" about sorting algorithms in literature, the author typically means the number of comparisons between the sorted elements, not the comparisons of something like loop indexes. So if you are asked this in a university assignment, I would guess that this is the number which is meant (but to make that ...


2

One great resource: http://bigocheatsheet.com/ I can tell you right off the bat that: Bubble Sort is in worst case, O(N2) Insertion Sort is in worst case, O(N2) Selection Sort is in worst case, O(N2) Quick Sort is in worst case, O(N2), yet is typically O(n log n) Merge Sort is in worst case, O(n log n)


1

It is possible for each variable to be uniformly distributed on an interval while the joint distribution is satisfies a codimension 1 constraint. For example, if you pick (x,y,z) so that it is uniformly distributed on a unit sphere, then each coordinate is uniformly distributed on the interval [-1,1]. The coordinates are just not independent. Even if you ...


0

I could see this being a recursive function in which you seek the top-left corner of the next possible rectangle. Scan right and down, keeping track of the new rectangle width and height to determine the length to check in your next scan row/column. When you've hit on both left edge and bottom edges, add result to result list, mark those "cells" as used, ...


1

Dynamic programming is much better than brute force plus a few heuristics. Try to determine the minimum number of digits so that some 0-1 integer is a mod n. For example, you could make a dictionary whose keys will be integers mod n, and whose values are the least number of digits so that there is some 0-1 integer equal to the key mod n. Start with (0,0). ...


3

It's not that "(n² + n)/2 behaves like n² when n is large", it's that (n² + n)/2 grows like n² as n increases. For example, as n increases from 1,000 to 1,000,000 (n² + n) / 2 increases from 500500 to 500000500000 (n²) / 2 increases from 500000 to 500000000000 (n²) increases from 1000000 to 1000000000000 Similarly, as n increases from ...


1

if n was a 1,000,000 then (n^2 + n) / 2 = 500000500000 (5.00001E+11) (n^2) / 2 = 500000000000 (5E+11) (n^2) = 1000000000000 (1E+12) 1000000000000.00 what? While the complexity gives us a way to predict a real-world cost (seconds or bytes depending on whether we are talking about time complexity or space complexity), it doesn't ...


0

Big-O is all about "how complicated" an algorithm is. If you have two algorithms, and one takes n^2*k seconds to run, and the other takes n^2*j seconds to run, then you can argue about which one is better, and you might be able to make some interesting optimizations to try to affect k or j, but both of these algorithms are dead slow compare to an algorithm ...



Top 50 recent answers are included