Tag Info

16

There is no fundamental difference. The function map has O(n) complexity, because it iterates over a list of size n and applies an operation to each element. The loop which is explicit in your first example just happens inside the map function. A typical implementation of map could be: map f [] = [] map f (x:xs) = f x : map f xs Here it is easy to see ...

7

That's an interesting question: can popular compression algorithms still make use of the redundancy in frames after they've been individually compressed, or is the individual compression too good to "leave traces"? I don't know, and you'd have to try it out to get a reliable answer. However, it's almost certainly a better idea to store all these frames as a ...

7

Big O notation is absolutely relevant for any program which will be executed on physical hardware. As an example, Clojure is a functional programming language, and its own documentation lists the Big O notation for operations on its data structures (particularly the collections - list, vector, and map). Knowing the Big O factors for each collection will ...

7

Is it possible to do a binary search tree if the data does not possess natural ordering? I don't know what the word "natural" means in your context; it seems vague. Moreover, images, videos, executables and sound files all seem perfectly obviously orderable to me. Order them by byte ordinal comparison, in the event of a tie, the shorter file is ...

5

I see where most readings online derive that the Big-Oh notation of a Binary Search is O(log(n)), but doesn't this assume a balanced tree? What if the tree is completely unbalanced (i.e. similar to a linked list). In this case the height of the tree is not log(n) it is n. Binary Search doesn't assume a tree at all. Binary Search assumes a data ...

4

Take the third loop: It is absolutely unneccessary. You check whether (a*i+b*j+c*k)==n. That means k must be equal to (n - a*i - b*j) / c. So a trivial change is to just calculate this one k and check whether it is a solution. Sort a, b, c such that a ≥ b ≥ c. Now its obvious that as j grows, k must shrink as much or more, so the sum j + k cannot grow. ...

4

Your proof that you will always reach a previously used 'i' appears to imply that your mapping function is topologically mixing. This in turn suggests that your function is probably chaotic. If it is chaotic, then by definition there is no faster way of producing the result than iterating your mapping function. Looking at it less rigorously, the modulus ...

4

I think the operations you're doing are variations of SQL joins, because in most cases you're taking tuples of data, picking a kind of value from each one to associate, and returning the combination(s) that could be linked. I'd suggest you look into the jargon, algorithms, and research-papers of RDBMs systems as your first place to mine for more ...

4

What are the asymptotic functions? What is an asymptote, anyway? Given a function f(n) that implements an algorithm, we define up to three asymptotic notations for measuring its performance. An asymptote is simply some other function (or relation) g(n) that f(n) gets close to, but never quite reaches. This is used to determine bounding functions that ...

4

It doesn't matter that you pick the next coin randomly rather than systematically. You're still potentially trying out all subsets of a multiset of size N, so it may take as many as 2^N tries, and that's your (upper bound) complexity.

3

An order is just a relationship between two elements in a set. The relationship is not always "is greater than". For example the relationship "is the son of" is, mathematically speaking, an order. It is not the order you need for a binary search because it is not well defined for all the elements: what if I pick two siblings? This relation exist only for ...

2

The key property of the Burrows-Wheeler-Transform that makes it useful is that it's reversible, without storing any metadata about what the transform did. If you simply pick "AAABNN^|" because it compresses better than the other columns, instead of using a consistent rule like "always pick the last column", then when it came time to reverse the process, ...

2

If you want to analyze these algorithms you need to define //dostuff, as that can really change the outcome. Let's suppose dostuff requires a constant O(1) number of operations. Here are some examples with this new notation: For your first example, the linear traversal: this is correct! O(N): for (int i = 0; i < myArray.length; i++) { myArray[i] ...

2

Is my simulated annealing algorithm correct? This is not Simulated Annealing, what you describe is called Stochastic Hill Climbing. SA will also accept new configurations with a certain probability when they are worse than the old configuration (and lower that probability over time). You did not specify how exactly you calculate "error count", ...

2

This is an NP-Hard problem There has been lots of research on approximations to the TSP. You should look up "traveling salesmen approximations". These will be fast, but not guaranteed optimal/correct. If you manage to solve this correctly/optimally in polynomial time, then you will be an eternal CS hero.

2

Methods of data compression that exploits redundancy between individual data groups of a set (usually a set of similar images) are named Set Redundancy Compression (SRC was proposed firstly by Kosmas Karadimitriou in 1996). There are four well-known types of SRC techniques: Min-Max differential method (MMD) Min-Max predictive method (MMP) centroid method ...

2

What about in a functional language? map (*2) prev How is the complexity calculated for this? Obviously, each call to a subroutine adds another instruction, but there are no "steps" to measure. There are steps we can measure! In Haskell, map can be defined like this: map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (a:as) = f a : map ...

2

First of all: this has nothing to do with "Big O". Big O has nothing to do with complexity, algorithms, programming, computer science, etc. Big O simply compares growth rates of functions. It doesn't care what the functions describe, or whether they even describe anything at all. What you are asking about, is simply figuring out the cost (runtime cost, ...

2

Yes, the assumption is that it is a balanced binary tree, or at least one that is randomly loaded. The linked list scenario is only one configuration of many, and your odds of getting it by chance are vanishingly small, unless you sort your nodes first, before inserting them into the tree. Searches in a balanced binary tree are O(log(n)) in the worst ...

2

This is an example where the forward links in the graph are difficult to calculate, but the reverse links are quite easy, so index those instead. Go through the word list and create entries for every link back to the word. For example, the word "cat" would generate the following index entries: ".at" -> Set("cat") "c.t" -> Set("cat") "ca." -> ...

2

You have a Directed Acyclic Graph and you need to operate a Topological Sorting to order your graph. The details of implementation depends to the programming language and platform you are working on so it's up to you to find a graph library and so on to use in your application. Alternatively Tsort can be helpful also.

2

There's orderable data (which may be unordered), but it can be sorted by a variety of sorting algorithms. All of these sorting algorithms depend on the ability to perform a basic comparison ordering test between arbitrary given elements. Such a comparison must return the relative ordering of any two of the elements, for example, usually as -1 for less, 0 ...

2

I think the answer you're looking for was alluded to in the comments by @MattiasÅslund and it's known as a count sort. A deck of some number of cards (whether it's a double deck, missing cards, etc). has the important property that you can know its absolute order based on some portion of its state. So, you make an array of length N initialized to zeros. ...

1

I guess in the case the 'set of smaller problems' will be : maximise(i,j,k) for n - x where x is some number which is harder to compute So. off the top of my head, I would calculate: n mod a, n mod b, n mod c giving me a set of x for which I can easily maximise the corrosponding i,j or k ie. (n - (n mod a) )/i etc. and store them along with the ...

1

First, I'd start with a combinations generator. Mine (shown below) is an iterator that you initialize with the number of total items to choose from (up to 64, e.g. 26), and the combination size you want (e.g. 6). It is written in C# and uses bit positions in a ulong to indicate selections. On to the larger algorithm: I'd generate the combinations for ...

1

All you can really do is profile—any general advice is going to be very, well, general. You should try to keep your working set small so that it fits in the first levels of cache, and avoid redundant memory accesses. If it’s expensive to compute an intermediate value, precompute it and store the result. If you know you will need data, prefetch it from RAM. ...

1

You may not have the ability to store what was picked the previous day, but you undoubtedly have the current date available in your code. Take the current date as "number of days since the epoch", and return "number of current day % number of items in the array."

1

What I've meant with my comment was the following simple algorithm. Let n ∈ N and V = {1, …, n} be your set of items. To generate n × n matrices M(1) , … M(n) with the desired property, pick the elements of M(1) randomly from V without repetition. Then generate M(i + 1) by rotating the rows and columns of M(i). By rotating the rows of ...

1

What I would do. Repackage the data on disk in small cubes, a few KB each. That is, if the data are represented as a typical array of arrays of arrays, the points that are close in the 3D space are not close in the representation. I'd try to overcome that. The result would be a the same amount of data, addressable in two steps. First step would be finding ...

1

As has been mentioned repeatedly, it is an NP-hard problem. If your problem is limited to 5 vertices, then you can most certainly brute-force your way to the solution as Eric Tressler mentioned above. I would like to add my own two cents, though, because I find hard problems to be fascinating... If you wish your algorithm to be tractable, this solution ...

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