Tag Info

New answers tagged

1

Your problem addresses the pidgeonhole principle (http://en.wikipedia.org/wiki/Pigeonhole_principle). It simply sais that if you got N items and you want to put them into M containers, where N is greater than M, then at least one container has to hold at least ceil(N/M) (Where ceil(x) is the smallest integer greater than or equal to x) items. You can solve ...


0

I would check out http://www.fusu.us/2013/07/printing-binary-tree-boundary.html. It uses additional data structures but is but runs in linear time with a single traversal. The stacks used in the linked solution would not be necessary if you were not worried about the order in which the boundary is printed. In this case you could do your favorite linear tree ...


0

You could try something like: Grab the whole 2d array Remove first column / first row / last column / last row Stack each of the four resulting subarrays. Store the biggest one that meets the condition, if it's bigger than the biggest one that currently does (if any). Repeat procedure for each subarray in the stack By doing this you would have checked ...


-5

I'm currently doing the same thing. However, when i ran into the issue you point out, I opted for simply ending the function if the tool was clicked over an area of the same color you're trying to paint (this also seems to be the behavior of ms-paint). The queued method should be extremely intuitive for anyone with some programming experience. If painting ...


1

As this is an excersize, I'll just give you a hint. Look at the traveling salesperson dynamic programming algorithm. Its solving a similiar problem, and you should be able to adjust it to fit this problem.


1

To make it short: The first sentence of amon's answer is important. But your guess is correct, too: 1000^2 is 4 times more than (2*1000)^2. I.e. if 1000^2 are equal to 10 seconds on a given hardware, then (2*1000)^2 are equal to 40 seconds. It's simply the rule of three. One more note: If you are dealing with the running time of the implementation of an ...


5

Complexity classes such as O(n) or O(n²) are not meant to calculate actual running time. Instead, they are meant to compare how different algorithms scale when we change the input size. For example, here we have two algorithms that apply frobnicate(a, b) to each matching item: void algorithm1(Set<int> items) { for (int i in items) { for (int j ...


0

You indicated that you don't want to do row/column traversal, but that could be a useful method. Calculate an index change value for the array so each new index translates into a row/column position that samples a different area of the matrix. The only requirement is that the index change value must be coprime with the array length. This guarantees that each ...


1

So Esoteric's solution worked but it still bothered me since it feels kinda bruteforce-ish. I knew there had to be a solution that only looked at the relevant data (start, end and qty) and didn't need to translate it into a different form. Then I remembered order by and a solution hit me. Ordered edge tally Create a list of edges and their quantities ...


0

Another solution generally used when performing tasks in parallel is that: You start by giving the first element to the first process, the second element to the second process,... and the nth element to the nth process. Once one of the processed finishes the task for the given element, it is given the task to deal with the next element. Once there are no ...


0

This is a possibility with SQL, however it needs to generate a sequence of numbers, since SQL server i was testing this does not support it I had to fetch the sequence from sys.all_objects ROW_NUMBER() function, SELECT n = ROW_NUMBER() OVER (ORDER BY [object_id]) FROM sys.all_objects the approach is to generate a view with number of time intervals small ...


3

If you think about it, this problem is very similar to the variation of the Boolean satisfiability problem of 3-satisfiability aka 3-SAT. Take each set within S into individual boolean expressions separated by "or" gates. Then each of these expressions would then be separated by "and" gates. For example {{A}, {A, B, C}, {C, D}, {E, F}} could be ...


5

This is tricky, because you've modeled your bookings as time intervals with granularity as fine as your DB allows. Perfectly natural to do, but as you've found out it makes some comparisons difficult. Max of For each booking that overlaps given timeRange return sum of each booking that overlaps this booking and given timeRange The ...


0

What kind of formal analysis do you mean? If you look at Big O notation, the complexity does not change when you change a constant factor. What I mean is: a cache may be faster than RAM, but that does not change your complexity from O(n) to O(log n). I think the problem is that things like cache optimization are so much dependent on the specific hardware ...


4

This is a question you need to ask on a case-by-case basis. You should not be using a general assumption that 64-bit arithmetic will not overflow, because even when correct quantities will be in a much smaller range, a malicious data source could end up giving you unreasonable quantities which could overflow, and it's better to be prepared for this situation ...


18

You don't even need to go cosmic when combinatorics are involved. There are 2^95 possible deals in a game of bridge and that's on the small side of complexity.


2

Is it POSSIBLE for a physical quantity to not fit in 64 bits? Of course. Others have pointed out counting the number of atoms in the sun or the number of millimeters to the next galaxy. Whether such cases are relevant to your application depends on what your application is. If you're counting the number of items in any given bin in your warehouse, 16 bits ...


4

First I would answer the question what physical values can/should be represented by an integer number? Integer is a representation of a natural number (and differences between them) in a computer system, so applying it to anything else is wrong. Thus, invoking distances or other quantities that belong to continuous domain is not an argument. For such ...


1

Here's an algorithm I invented myself. I don't know if it already exists or is actually the round robin implementation: 1 4 1 5 1 6 1 3 1 2 2 5 4 6 5 3 6 2 3 4 3 6 2 3 4 2 5 4 6 5 basically you start with and always keep the 1 in the same position and rotate the rest. That way you will always get a schedule of unique ...


0

Another solution would be to simulate your own stack and not rely on the implementation of the compiler + runtime. This is not a simple solution nor a fast one but theoretically you'll get StackOverflow only when you're out of memory.


0

It is unreasonable to assume a 64 bit integer can hold all numbers. Multiple reasons: The max and min 64 bit integer are finite numbers. For every finite number a larger and smaller finite number exists. Calculations with 128 bit and 256 bit numbers are currently used in various places. Many processors have specific instructions that operate on 128 bit ...


6

Your assumption won't handle physical quantities that can only be represented by floating point numbers. And even if you decided to scale all numbers, say by multiplying all numbers by 10000 (so the values are still integers but can be represented in ten-thousandths), this scheme still fails for numbers very close to zero, for example the electron mass ...


4

In addition to Jerry101's answer, I would like to offer this very simple and practical test for correctness: Suppose you allocate some memory via malloc, in an 64-bit OS. Let's suppose the memory allocator decides to return to you a valid memory block, of the size you requested, but where the 63-th bit is set. In other words, let's suppose there exists ...


16

The most relevant physical quantity for your question is computer RAM. Windows Server 2012 supports up to 4 TB of physical memory. That's 242 bytes. If RAM capacities continue doubling about every year, then in only 17 years from now "Windows Server 2032" will support 262 bytes of physical memory, at which time your low + high will reach 263 - 2 and kiss ...


57

The short answer is no. However, for some applications your assumption might be correct. Assuming a signed int, 2^63, with commas added for some clarity, = 9,223,372,036,854,775,808. So it's roughly 9 * 10^18. 10^18 is an "Exa". Wikipedia says "As of 2013, the World Wide Web is estimated to have reached 4 zettabytes.[12]", which is 4000 Exabytes. ...


9

Is it reasonable to assume that any physical quantity can be represented by a 64-bit integer without overflow or underflow? Not exactly. There are plenty of numbers that are both bigger and smaller than that, which is why we have floating point numbers. Floating point numbers trade off lesser precision for better range. In the specific example that ...


1

The right answer in practice may depend on the rough proportion of vertices that are active. If most vertices are active, I would modify the graph structure by stripping out all links to inactive vertices (trivial in adjacency matrix form, very parallelizable in adjacency list form) and then run a standard weakly-connected-components algorithm (which should ...


2

The Boyle-Moore algorithm only works if there is a majority, indeed. It is useful if you can assume that there is a majority, for instance when processing binary strings composed of 0 or 1: if the length of the string is odd, then you must have a majority. The sequence A A A A B B B B C has 9 elements, so you need at least 5 occurences of an element to have ...


0

Input count majority A 1 A A 2 A A 3 A A 4 A B 3 A B 2 A B 1 A B 0 A C 1 C Count is not ...


1

in the MIDI control thread, you update the control values as soon as the complete MIDI control change message (0xB0) is received. that control value remains constant until it is updated by another control change (for the very same control). in the audio processing thread, you always refer to the current value of whatever control you're using. you'll ...


3

From your requirements it rather sounds like you should be using a secure (cryptographic) hash. To your actual question: Is FNV-1A supposed to be an extremely discontinuous function? i.e., the output changes drastically for small changes in the input; it exhibits the Avalanche effect. we can quickly get an answer of No by looking at the FNV test ...


2

The trick is in the first three digits. The last 14 digits are guaranteed to be unique within a certain domain, (say, a server,) so the first 3 digits must uniquely identify each domain. Therefore, every 17-digit number is guaranteed to be unique.


0

You've got quite hard a problem here. I'm thinking of a method resembling Sieve of Eratosthenes . First, you can "name" or "number" each link. Let's assume we just have 5 nodes, so we'll have 10 links. Number each one from 1 until 10. Now, we can put them all into an array. Let's assume we have this list represents two links who intersect each other: 1 ...


0

To cut down on the count of recursive calls I thought of introducing a strict ordering of links to be able to eliminate duplicates in the initialization phase (before any recursion): on the links define any (arbitrary) strict ordering order on the links define a method doesNotCrossWith() returning the set of links of higher order which this link does not ...


1

Uniform_real_distribution had a closed range until 2006, after which it was changed to a half-open range because developers are said to be more comfortable with it.


1

Closed intervals "feel" more natural in a discrete setting. Half-open intervals "feel" more natural in a continuous setting (well, they feel more natural even for rationals, but...). I would be surprised by a "generates integer numbers" function that didn't use intervals if I gave it an explicit minimum and maximum, but I'm essentially OK with a ...


4

It doesn't make sense to talk about the step complexity of an algorithm without defining what a "step" is first. Algorithmic complexity is always relative to a model of computation, whether that be transitions of a Turing Machine, reductions in λ-calculus, instructions of a Random Access Machine or the number of comparisons when talking about ...


2

When defining or talking about algorithmic complexity, you always have an (implicit) target abstract machine in mind (e.g. the RAM machine, the SECD machine, etc). Then the elementary steps are those of that target machine. Bubble sort is O(n2) only with the assumption that compares are constant time. If you imagine sorting bignums it probably is no more ...


0

After more research, I have created some pros/cons on each algorithm. It's easier to visualize in a table, but that is currently seemingly unsupported by markdown. However, I've separated these pros/cons into 6 categories (Structure, Control, Condition, Update, Speed, and Space). Depending on the project at hand this should be able to determine the best ...


1

If your language processor (compiler or interpreter) properly implements tail recursion optimization, then there winds up being no difference between a properly-coded tail-recursive binary search and an iterative binary search. The language processor will turn the recursive calls into simple loops. At that point, choice of recursive vs. iterative ...


1

Don't get afraid by words : Abstraction is the process of removing every aspect of the issue that is not useful to solve it. -So you can concentrate on only what matters- Abstraction is so widely used because there exist a number of 'patterns' in programming that keeps repeating in every application. Find the pattern corresponding to your issue, find ...


0

In general an abstraction is a simplification or a simplified representation of something, so to produce an abstraction of an algorithm would be state its form in the simplest way - for a sort this would be state it without the details of how the comparisons or the substitutions worked, for instance.


3

No, you're not correct about what that person meant; your reference to objects is a rather technical detail of OO languages (which concerns abstractions the code is modelling), and talking about an algorithm only in terms of input and output is a different level of abstraction, one step too high (but at the same time too low because you seem to think about ...


5

If it is truly an ordered linked list, this should be a fairly bad choice because you have to traverse the list one by one until you find the right place to insert the item. In other words O(N). This is ok if the list is small but can get out of hand for big graphs. Usually, what you will need for that kind of stuff is a heap: ...


0

I think recursive functions belongs to the declarative paradigm: Define the base: Factorial(1) = 1; Define Factorial n : Factorial(n) = n* Factorial(n-1); However, any recursive function shouldn't be a complete declarative function. You can define the base and relate (define) the solution of the main problem to solution (definition) of sub-problems. But ...


5

Broadly speaking, declarative programming concerns itself with telling the computer what to do. Imperative programming concerns itself with telling the computer how to do it. Any non-trivial program will necessarily contain both. Imperative programming is typically associated with control flow, loops and mutable state. Programs written in the procedural ...


1

Algorithms are a sequence of steps. They don't depend on what is (or isn't) executing them. However, the time complexity of an algorithm can depend on what is executing it. That's why detailed analysis of an algorithm requires a "model of computation", such as a random-access machine. Whether or not memory is randomly accessible certainly affects how long ...


1

Since you say that approximations will work for you, what I would do is that I would pick a time interval like 1 second and I would treat it as a quantum. I would record all information of interest from every event happening during the quantum, and at the end of the quantum I would summarize everything that happened and discard the details in preparation ...


1

A lot of answers are missing the fact that an algorithm can be defined in terms that are either abstract from or in direct, literal relation to an architecture. An algorithm has to be unambiguous, but there's still room for it to be more or less specific. An algorithm for converting a string to all-caps can be easily described in pseudocode that is ...


1

In general, algorithms are designed to some particular problems at while minimizing some measure of "cost". Historically, many algorithms were designed on the assumption that the relative costs of common operations would be relatively similar on many architectures, and thus some typical machines would run one algorithm would run better than another, then on ...



Top 50 recent answers are included