New answers tagged

0

The OP remarked in a comment that he found the problem tagged as "brute force and DP". Which is absolutely ridiculous. Here's the linear time solution: Observe that the order of a, b, c is quite irrelevant, so sort them to make a ≥ b ≥ c. Calculate g = gcd (a, b, c) (greatest common divisor). If n is not divisible by g then there is no solution. ...


0

To answer your "DP" question: this can be done in three steps: Find the solutions for a*i==m, where 1<=m<=n: this is simple, just check if m%a==0, then the solution is i=m/a. If not, then there is no solution. Store these in an array. Find the solutions for a*i + b*j==m where 1<=m<=n, maximizing (i+j): loop over all j with 1<=j<=m/b, ...


0

For recursion, you can redefine your initial problem f (n,a,b,c ) where ai+bj+ck=n to f (n,a,b,c) = ai + f (n-ai,b,c) where f (n,a) becomes finding divisors of n. I can add more detail if you are interested. Answering on mobile is a challenge.


0

You should be able to so this with a form of Bucket Sort in O(N) time. Create an array of cards with N elements (buckets), with each bucket initialized to empty1 Iterate the cards examine card calculate bucket number as card rank + X * card suit put card into bucket In one pass, you can place all cards into the correct bucket. The sort time is ...


0

First I have to say there is a need for algorithms and finding efficiency opportunities in basic algorithms. I'd proceed on requirements of this nature is finding the class libraries that are considered standard for your programming language (collections) and if those libraries cannot satisfy the requirement then look to works produced by organizations like ...


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

If we look beyond the simple example where the end result is known (and there wouldn't be any need for sorting, just generate the end result) and look at having a list of cards that are sorted and we add one card to the end of that list. Now we want to sort this list. Should we use quicksort? No a simple bubblesort (adjusted so that it moves from the end of ...


-1

This looks like two circles and and_not operation on them. Filled circle is simply x^2+y^2<r^2 and you need two of them with different r. Then it's just matter of and_not operation: x \in (A and_not B) <=> (x \in A) && !(x \in B)


6

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


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


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


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

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


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


0

Related Reading Computer Science.SE - Algorithms Stack Overflow - Plain English explanation of Big O


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


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


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

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


0

Beyond @53777A's fine answer, your before & after information is "interesting". You don't need both before and after information, so I wonder why you bother to capture both. When we do have both before and after information, in a canonical form, the information would appear symmetric, which is to say that if Task1 should be before Task3 then Task3 ...


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.


0

Use [SipHash][1]. It has many desirable properties: Fast. An optimized implementation takes around 1 cycle per byte. Secure. SipHash is a strong PRF (pseudorandom function). This means that it is indistinguishable from a random function (unless you know the 128-bit secret key). Hence: No need to worry about your hash table probes becoming linear ...


0

Starting from permutations and combinations, I think we're interested in combinations: For 30 topics, you would have the followng count of combinations for each size: (In other words there are 30 combinations of size 1, and 435 combinations of size 2 (also 435 of size 28 as it turns out)). 30 435 4060 27405 142506 593775 2035800 5852925 14307150 30045015 ...


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


0

If you want to create an array, you can use a slightly modified algorithm which runs in O (n). Fill the array with the numbers from 1 to n. Repeat for i = 0 to n - 1: Generate a random number r such that 0 ≤ r < n - i. Exchange array [i] and array [i + r]


0

Sure the three main notations are: "Big-Oh" meaning your function is always <= c*f(x) for some constant c and values greater than some x. "Big-Omega" meaning your function is always >= c*f(x) for some constant c and values greater than some x "Big-Theta" which is used to describe a tight upper and lower bound, meaning it is both Big-Oh and Big-Omega. ...


1

I would say that this problem would be solved using probabilistic analysis. So you would need to consider the probability that a random number selected was already in the list. In order to do this you may need to make an assumption about your random number generator, specifically that it generates numbers with a uniform distribution, meaning any number ...


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


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

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


0

There are (n x m)! permutations of the elements, which we can assign an index to each: 1, 2, 3, ..., (n x m)! For example if we have a 2 x 2 matrix, we will have (2 x 2)! or 24 permutations: 1. A B C D 2. A B D C 3. A C B D 4. A C D B 5. A D B C 6. A D C B 7. B A C D 8. B A D C 9. B C A D 10. B C D A 11. B D A C 12. B D C A 13. C A B D 14. C A D ...


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


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

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


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


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


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


-3

I'm assuming that you are looking for a slight generalisation of route planning: You have a large map with a huge number of possible connections, you want to drive from A to E (which Dijkstra's algorithm would handle), but you also want to touch points B, C and D. Obviously you can run the "shortest distance" algorithm six times. You'd want to do better ...


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.


0

Interesting problem…. Firstly a van/driver has a fixed cost for shift so you will wish to put enough items in the van to use up all the capacity you have. Then if a driver is going to the same property often, they will be able to find it faster. You have to take into account what you do if your customer is not in, for example I find it easy to pickup an ...


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


1

Alright, for starters, I guess I would precompute several spinemap lists in advance, and keep them immutable during execution of the calculations, instead just picking the right one to use for each case. To finish up, I'd use array of int instead of array of string for the spinemaps. I'd transform the levels from string form to an enum, and use that enum ...


1

It doesn't look like you need a "nearly accurate count" - you say you need to know that there are at least 25 objects in a state. To achieve this, you can for example have one method that counts the objects in that state, and possibly stops counting once it reaches 1,000 for example, and decrease the counter every time you move an object away from the ...


0

This is a classic problem to be solved with a schedule algorithm, many PHd and research papers have been written about this sort of problem. Therefore it is impossible to provide a short answer and a long answer would cost you days of my time. Firstly check how many possible options of appointments you have, if that is reasonable low, you could use back ...


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


0

I am not sure I understood your problem (if at all) and/or your desired type of solution, but... I'd start by sorting and reassigning on appointment lengths, instead of start time. For instance, let's consider another "even worse" scenario of overlapping; same as in your example, but for the last appointment, that we'll make 2 hour-long instead: ...


0

Working code (not pseudocode as I said, duh! but this is more explicative): I have two file desciptor, one for client and another for server, both opened with socket(AF_INET, SOCK_STREAM, IPPROTO_TCP); the select() checks if client of server sent something, the fd_set is only for reading (from client and server). Warning: I'm not sure if I close correctly ...


0

QOS Algorithm If possible, you can solve this with multiple threads (or processes): One thread/process receives requests and puts the request into the queue with the right priority. Another thread/process blocks waiting for requests arriving in any of the queues. When the thread/process wakes, it sends the messages that are in the queues, first checking ...


0

I would consider the problem as: a parsing problem. read some good compiler text book like the Dragon book. So parse your expression into some Abstract Syntax Tree sitting in the virtual address space of your process. then, evaluate that AST (in some environment). The above approach fits for any expression-like language (not only postfix, but also ...



Top 50 recent answers are included