Tag Info

New answers tagged

0

As written, it's O(1) because you do nothing in the loop. The compiler will optimize it away.


0

It is O(n/2)=O(n), since complexity is calculated in order of magnitude and constants can be "ignored". So, if c is a constant : O(c*n)=O(n) O(c*logn)=)(logn) etc.


0

As written, it's O(n) i.e. if you double the size of n it'll take twice as long. Any half decent compiler/JIT will, however, spot that it doesn't do anything and strip it out i.e. O(0). But I presume that's not what you're after.


1

O(n) since if n is extremely large (close to infinity), the fact that it is divided by two is negligent.


3

Your grammar will be correct if your catch-all rule only consumes a single character and if you use prioritized choice in the grammar so that static is only attempted as a last resort. Of course, these single-character tokens are terribly inefficient. There are two ways to fix this: let the catch-all rule be static : [^\{]+ | . have your parser store a ...


0

A quadtree (or octree in 3 dimensions) is also good for spatial indexing.


0

For this particular grammar, I think you can just match until you see {{. Then push {{ back on the tokens to be read. So I think the key here is just having the ability to push back onto the token list. Having a fixed buffer of tokens is generally good for error handling too, in LR parsers, but I wouldn't be surprised if it is useful in LL parsers as well. ...


0

Calculate the distances between zip codes once and cache them. Keep the restaurants list sorted by the distance to the user. Enumerating the restaurants starting from the smallest distance you can detect the point when the restaurants go out of walking range - at that point you can ignore the rest and break the loop.


6

You've discovered the need for spatial indexing. R-trees are probably the most common approach. The basic idea is a tree structure with rectangular bounding boxes computed over all the children of a given node. That way searching for a region or a point can traverse the tree, pruning out any parts of the tree (most of it) where the bounding box is not a ...


0

No, actually your 'i' value is constant for a particular 'event'. What you said does occur over multiple event, ie the probability of selecting a red ball from a bag with a mix of balls in 'first round' is NOT equal to selecting another red ball from the same bag in 'next round'. There is change in probability. To conclude, the probability value for ...


4

After fidgeting around with the code a bit, I've got some better results. I went back to the original paper and ignored the wikipedia page. I've compared the algorithm to other quick select routines with some great results. Ok, here are the methods I have been playing with. Note these are for floating point and also that I changed my method from a void. ...


0

Your problem is likely a typo: you calculate 1 / sqrt(2 * pi * sqrt(variance)), while the formula expectedly has 1 / sqrt(2 * pi * variance**2). (Square root from variance taken twice is highly unlikely in a normalizing factor.) While we're at it, I don't think rounding errors have anythig to do with your formula's problem. With usable range of a 64-bit ...


0

This is not exactly an answer, but I just didn't feel like throwing these terms at you in a comment. I have the strong feeling that this is what you are looking for. With the terminology you will be able to find existing algorithms, instead of reinventing the wheel (hopefully) What you are trying to do is related to Minkowski addition also called Minkowski ...


1

Well, this turns out to be non-trivial extension of Veldaeven's solution. For each sequence of 3 points, calculate the 2 vectors between them, as suggested by Veldaeven. Find the angle between the two vectors by adding the angles from the x axis - (nb do not use dot product which always returns an angle less than pi and hence is too symmetrical for our ...


1

The concept may be simple, but there are many devilish details. To begin with, you have to stipulate that the numbers representing the points are exact, not approximations to some real curve, and that the outline consists of straight line segments, not an actual curve. Second, boundary conditions are everywhere; if line AB touches line DEF only at point ...


2

You could argue that a curve is simple if there are no two line segments between points such that the lines intersect, meaning you could check if a curve is simple by verifying the absence of this condition. The algorithm would look something like: for each p1, p2 in pointlist for each p3, p4 in pointlist if line_segment(p1, p2) intersects ...


3

You can check each point pair P[i],P[i+1] against each point pair P[j],P[j+1] If any of the lines segments they create intersect then the curve is not simple. Naively check each line: for(int i = 0; i < n-3; i++) for(int j = i+2; j < n-1; j++) if(doIntersect(new Line(P[i],P[i+1]), new Line(P[j],P[j+1])); I skip checking P[i],P[i+1] ...


2

This is my full answer. At the end didn't understand the (i & mask >> j)part so I use an IF. To see if the elem is part of the sum. int[] elem = new int[] { 1, 2, 3, 4, 5 }; double maxElem = Math.Pow(2, elem.Length); for (int first = 0; first < maxElem; first++) { int mask = 1; int sum = 0; for (int run = 0; run < elem.Length; ...


3

You are computing the sum of all the combinations of a set of numbers. The number of combinations you have is 2n, where n is the number of numbers. For example, if your array had 5 elements, it would be 25 which is 32. The combinations that you will be iterating through are the binary representations of 0..31. 00000 00001 00010 00011 ... 11111 This has ...


1

It is a variation of Multi-armed bandit problem: In probability theory, the multi-armed bandit problem (sometimes called the K- or N-armed bandit problem) is a problem in which a gambler at a row of slot machines (sometimes known as "one-armed bandits") has to decide which machines to play, how many times to play each machine and in which order to play ...


-1

I guess this is what you are looking for because the article says PageRank is a link analysis algorithm and it assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set. The algorithm may be applied to any collection of entities with ...


5

There are a couple things to think about here - the structure of a card and the structure of the collection of cards... and all the while keeping in mind that this is Java and should be written with proper attention to object oriented principles. A card is a thing. Representing it entirely as a bit in a BitSet, or worse... doing your own bit manipulation ...


3

Siri typically doesn't "generate" sentences. She parses what you say and 'recognizes' certain keywords, sure, and for common responses, she will use a template, such as I found [N] restaurants fairly close to you or I couldn't find [X] in your music, [Username]. But most of her responses are canned, depending on her interpretation of your speech, in ...


1

The problem you are asking about is a well known problem which has a plethora of applications: For example the task to minimize material waste in furniture production: Certain pieces (your list of rectangles) have to be cut out of boards of plywood in a given size (your bounding rectangle). As you seem to have already figured out finding all possible ...


1

The problem you describe is the decision version of the longest path problem (ie. "Is there a path of length at least k?"). As Jimmy Hoffa noted, the problem is NP-complete. You could look into approximation algorithms for the LPP, particularly ones that exploit any special structure your graphs might have.


2

The worst-case is O(∞). The best-case is O(n2), because you have to generate n numbers, and for each number generated you have to search a list of length n whether or not the number is already in there.


0

You could use patterns … To find the longest repeating subsequence try this … {1, 3, 6, 17, 19, 3, 6, 5, 4, 2, 5, 6, 17, 19, 3, 6, 7, 5, 78, 100, 101} /. {___, Longest[y___], ___, Longest[y___], ___} :> y This returns Sequence[6,17,19,3,6] To find the shortest non-trivial (i.e., length 2 or greater) repeating subsequence try this … {1, 3, 6, 17, ...


2

Code doesn't infringe on patents. Code running on a computer can infringe on patents. There was a major (billion dollar) case where Microsoft wa accused of patent infringement, and it turned out that an infringing device was created at the moment when the software was installed on a computer, and not earlier. For example not when a million CDs or DVDs with ...


0

You need to speak to a lawyer before proceeding any further with this. Implementing the methods covered by this patent will constitute use of the patent, and if permission has not been given by the vendor for the exact use case proposed, then you are infringing on their rights, and are opening yourself up to legal action if they are not happy with what you ...


0

You could use something like this, Define a rule class where the regex expression to detect the tag is specified, and loop through expressions and insert html where necessary. class Rule { string tagRegEx; string htmlToInsert; } public string Process(string html,List<Rule> rules) { //for each rule, check for regex matches and insert the ...


1

As it looks like these are primarily a list of exclusion filters, something like this might get you where you want to be (example in Java, includes calls to functions that probably don't exist as parts of the test): private static List<Predicate<Node>> AD_FILTERS = Arrays.asList( (node) -> node.getPreviousSibling().isIFrame(), (node) ...


7

The short answer In order to license something to others, you have to hold the rights to it. So your ability to license your code covered by the patent may depend on what you can work out with the patent holder. The long answer There are a number of ways this can go. You can get a release from the patent holder. You can release your code and hope the ...


0

Have you considered Sphinx? http://sphinxsearch.com if you can use a 3rd party tool this would be ideal for what your're trying to achieve, its much more efficient at full text search than any RDBMS that I have personally used.


4

Indeed, a tree is a good data structure for that. You can then create a BST which will allow to find by lookup a specific action based on the c1 to cn conditions. Obviously, this has a huge benefit of avoiding ugly code such as: if (c1) { if (c2) { if (c3) { ... } ... } ... } Whether the BST can be ...


1

You already have a function that can move a stack of any size, so use it: Use original hanoi to move a stack of 3 onto the odd stick. Move disc 4 to the even stick. Recurse for the remaining stack of 3. You basically have a more complicated choice of src and dst, but it's not terribly difficult. Note that many times, when you recurse your stack will ...


2

What you are looking for is called a Spatial Index. In your case, you are looking for simplest case of getting all 2D points inside a rectangle. Even simple quad tree should be great improvement if you have lots of points. The problem of those kind of indexing algorithms and structures is that they are highly dependent of shape of the data. While they all ...


1

I'm assuming you want low amortized cost, i.e. preprocessing is acceptable. You're trying to find a data item with specific property. Don't be misled by the fact that the property is expressed as four different numeric comparisons. It's really a property of the entire item. That means you need to sort your data according to a measure that takes all ...


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 ...


2

I do not know what DP algorithms you tried, but here is one which solves your problem in O(M * N²), which is certainly better than O(N^M). The algorithm works inductively by increasing number of boxes. 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). For a given m, you solve the ...


3

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 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 ...


4

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.



Top 50 recent answers are included