Tag Info

Hot answers tagged

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


20

Algorithms are the series of steps taken to solve a particular problem. The recipe for solving the problem, if you will. "Programs" do the same things, of course; we use "algorithm" to suggest the "generalized" or "generally applicable" recipes that are independent of specific machine designs, programming languages, and such. Algorithms are meant to be ...


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.


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


14

Algorithms and OOP are two disparate terms, which have only in common, that they are CS-terms. Simply - An algorithm is like a cooking recipe: to do x you need the following ingredients and do step 1,2,3,4,5,6... then you have your meal prepared. That said, it seems a natural fit for algortihms to be described in a procedural way. Procedural means nothing ...


12

Algorithms are independent of computer architecture. That's because algorithms define a series of processes that solves a problem. Regardless of architectures, sorting algorithms will always sort. It wouldn't suddenly render 3D drawings on some architectures. If you think about it, this is actually intuitive. Google Chrome (which is merely a collection of ...


9

First, lets define what we mean by OOP. By OOP I mean primarily : Encapsulation and hiding of details in class. Polymorphism of behavior through inheritance and virtual methods. Now, to answer your question: What is the relation between algorithms and OOP? Are they two independent topics? Yes. Are there some problems which only can be presented ...


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


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


5

That definition of "algorithm" is extremely narrow. It applies only to non-interactive deterministic digital small-step algorithms. However, algorithms need not be digital (consisting of discrete steps and operating on discrete values). They can also be continuous (consisting of discrete steps and operating on continuous values) or analog (continuous ...


5

No. It is not. Like a mathematical function, an algoritim transforms elements from a source set of information to a destination set. That works independently from the origins of the source set: Whether it stems from user (keyboard or otherwise) input, from a file containing the information or from punchcards. The input belongs to the preconditions of an ...


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


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


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


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


4

you have a problem. The business domain model describes your problem, and the concepts from the problem domain you are going do be dealing with. Algorithms describe the way you are going to solve your problems, conceptually; what will your implementation look like; and how do you deal with your problem after you translated it into "Computer Science" ...


4

"It seems like parallel algorithms depend on parallel architectures?" In my opinion the answer is simply: no. General I only get the properties parallelism word size (implicit resource limits) when thinking of hardware architecture. Referring to parallelism you can have any parallel algorithm be batch computed and any parallel arch to work serial ...


4

Algorithms doesn't depend on computer architecture, however the efficiency of running any particular algorithm does depend on the architecture. Any Turing Complete machines can emulate any other Turing Complete machines, although some machines would be better at one thing than others. What we mean by concurrent algorithms is that the algorithm plays well ...


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


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


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


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


3

Yes and no. It depends on the constraints you want to meet and the preconditions needed to run your algorithm. Ideally, an algorithm is an abstract recipe that defines step-by-step how to do something. Algorithms was defined like so with the goal of reproducibility, and later automatization. Algorithms originates from lambda-calcul, so you can easily see ...


3

In theory, algorithms are entirely independent of architecture. You can always emulate a parallel architecture on a single-issue timesliced system. You can reason about algorithms without an architecture at all. Knuth's book uses a fictional architecture. In practice there are algorithms that attempt to achieve better runtime for the same "O" complexity by ...


3

First, let's walk through the best case. You have n elements. The first one you skip because there's nothing before it to compare against, so there are only n-1 elements that might need to be moved. If an element does not need to be moved to the left, then we learn that after only one comparison. So if no elements need to be moved to the left (because the ...


3

Computers are not Turing Machines. They are Deterministic Finite State Machines. Turing Machines have infinite memory, computers have finite memory. Turing Machines have arbitrarily many (though finite) states, computers can't have arbitrarily many states, the number of different states that a computer can be in is bounded by its memory (a computer with ...


3

You may start by creating a method inside the Board class which makes your code slightly shorter: public class Board() { public bool IsPieceMissing(x, y) { return this.GetBoard(x, y).Piece == null; } } ... if (arrayX == 0) { if (board.IsPieceMissing(arrayX + 1, arrayY - 1)) { return true; } } else if (arrayX == 7) { ...


3

Set up f(n,d) as a function giving the number of permutations of (even) length n using d distinct characters (i.e d=4 in your case). Clearly f(0,d) = 1 and f(n,1) = 1 as there's only one arrangement when you have only one character, or zero spaces. Now the induction step: To make a valid string using d characters, take any shorter even-length string using ...


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


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



Only top voted, non community-wiki answers of a minimum length are eligible