New answers tagged

0

See the answer here. The problem turned out to be with my multivariate normal sampling function. The step size was being squared when it shouldn't have been which decreased it. This meant that everything was smaller, making the evolution path of sigma to be less likely to be higher than the expectation.


3

What are some reasons you may choose a worse runtime algorithm? By far the most common reason is that the "worse" algorithm is a lot simpler, or is the first solution I think of, and getting mathematically optimal performance just doesn't matter in the part of the code I'm currently working on. Which is most parts of the code. Another common reason is ...


0

One possibility is to (ab)use maps and sets (or lists). You have a map with "current word" as key and "list or set of successor words" as value. You can then populate your map using something like the following: for word in dictionary: for 0 <= position < length(word): key = drop_letter(word, position) ## drop_letter("bath", 3) -> bat ...


4

As I said in my comment to Doc Browns (otherwise excellent) answer, there is a matter of choice of square->triangle division which makes it slightly harder to device an algorithm. Also, you don't have to make it serially, but can do it in parallell, as some of my suggestions show. I made several heuristic approaches at first. Voronoi: Choose N points ...


2

The general strategy should be to remove the first piece of area A/n from your polygon P0 (where A is the total area), leaving you with a new polygon P1 of area A-A/n. Then repeat this producing a polygon P2, then P3, and after n repetitions, you have your solution. Note that it is possible at each step that you cannot find such a new piece where the ...


4

Not solvable. I tried a number of methods until i realized it couldn't be done. Assume a shape with area 4, which should be divided in 2 parts with area 2 each: The leftmost triangle and square must be part of shape 1, but it needs another triangle. The only place that could be taken from is the square to the right, but then the remainder is split in two ...


1

I've just been tasked with doing this for homework, and I thought I had a neat epiphany: Strassen's algorithm sacrifices the "breadth" of its pre-summation components in order to use less operations in exchange for "deeper" pre-summation components that can still be used to extract the final answer. (This isn't the best way to say it, but it's hard for me to ...


2

Common design Algorithmic Paradigms: Divide and conquer : Recursively breaking down a problem into two or more sub-problems of the same (or related) type. Dynamic programming : breaking it down into a collection of simpler subproblems. Example: Tower of Hanoi puzzle Greedy algorithm : the problem solving heuristic of making the locally optimal choice ...


-1

There are much better answers at the SO. Basically, you provide some data collection and criteria to search. Sound algorithm catches you only the fish that matches the criteria but it may miss some data items. Complete algorithm produces a superset of requested results, which means that you receive some garbage on top of requested results. Sound algorithm is ...


-2

Adding another answer as have not seen a reference to build systems like make which uses DAG to find out dependencies for building. More details here


-1

I recommend you take a look at several algorithms for tree traversing and finding the shortest path. The only ones I can think of at the moment are Dijkstra's algorithm and Primm's algorithm.


0

While extrapolating the "40 LoC vs 200 LoC" example, saying "well, only a fifth of the total LoC is obviously faster to write so it must be better" may seem tempting, I really think there is little truth to be found there. Optimizing for fewest LoC is almost never a good idea in my opinion. Yes, every LoC written is a potential for bugs, and you never have ...


0

You're going to need a list of days closed and possibly even make it group specific. Writing an algorithm to predict the date of the Superbowl next year is just not worth it. This allows you to create a list of all the days in a given time range in your code to exclude. Some database-centric solutions have a table with all the days already in it for a ...


0

I'd model a calendar (ie an array of 365 elements). the difficulty using this system is that a block of days gets allocated as many individual days rather than a single entry, however I expect you'll be assigning a tag or some label to each logical entry that can be used to identify each block of days so that you can edit a single (logical) entry. The ...


1

Your questions are very abstract and therefore mostly quite difficult to answer precisely, but here are some thoughts you may not have considered. Where is the list stored in memory? Is it literally stored in a way where first element is at memory index k, next element k+1, etc. That depends on what you mean by "list"! A C++ vector is stored ...


0

You can't map the surface of a sphere onto a plane square grid, whilst at the same time preserving distance, area and angles - there has to be some sort of compromise. See here for more details. If you really want "equal sized elements", a better solution might be to use a spherical co-ordinate system - latitude and longitude with elements of equal arc ...


1

This is not a direct answer but it does not fit in a comment. I just want to elaborate MSalters comment - internally, NTFS already does what you are trying to do. It is a wrong impression about huge NTFS folder being slow. The wrong impression is usually due to the way some users interact with the folder - windows file explorer, which loads all entries when ...


1

It's not entirely obvious, but the type of algorithm you're looking for is called a space filling curve. The space here is the namespace of folders. XKCD had a 2D example a long time ago. It shows how the first 4 files would end up in /00/00 to /01/01 and the first 16 in in /00/00 to /03/03. Expanding the algorithm, the first 256 files end in /00/00 to ...


3

The easiest way to resolve this is to shift how you're defining the end of their license term. Currently, I suspect you're using the natural approach of "User purchased base item for $N, so user has an expiration date of ..." In other words, the expiration date is determined at the time of purchase. The challenge with that approach comes about when you ...


2

You could do that. But as mentioned by Robert in the comments you could avoid a lot of trouble by using a library, such as Lucene. In your case (.NET) you should pick the Lucene.net port.


0

The worst case gives us an upper bound on performance. Analyzing an algorithm’s worst case guarantees that it will never perform worse than what we determine.


0

Just an intuition. I haven't gone through the details and may be embarrassingly mistaken. As your vectors all have the same dimensionality d and their distance is defined as their hamming distance you can represent each vector as a point on a d-dimensional hyper cube. The path between two points will be the hamming distance of their coordinates. All points ...


1

I did a stint at a huge printing company. I believe we ran into the same problem. Let me rephrase it. The constraints: An industrial printing plate costs X dollars to layout and fabricate. It's not an insignificant amount. Each printed sheet costs Y dollars. It's a smaller number but can add up. There are N unique "rectangles" to print. For the sake of ...


4

What you are trying to do is variation on a Bin packing problem. Effectively you are placing items into bins (plaques) and trying to minimize the wasted space, since in your example wasted space directly corresponds to lost money. The wikipedia article shows how this can be done/solved. You may end up with an optimization problem on top of this, because you ...


4

It's not necessarily as bad as you think and may even be the most optimal representation if you have an index on parent_id. Let's say you're interested in the descendants of B above. In that case, you would first query for nodes which have parent_id matching the ID of B. That gives you D,E. Now query for nodes which have the parent ID of either of these. ...


2

With an index on parent_id, I actually think this is a good way to organize the relationship, and we have been using it that way in many places. Also, I see no obvious better way, as the relationship is 1:N, so if you try to store parent->child, you need an extra table, and you end up with the same logic again. The core point is having the index on ...


3

A heuristic worth considering: Pick a random name and add it to a group. Scan the remaining names for the highest point match and add it to the group. Scan the remaining names for the highest total point match against the two grouped names and add it to the group. Scan the remaining names for the highest total point match against the three grouped names ...


6

First, reduce the problem to a test of availabilities "per day". All your examples are using ranges for only one day, but if you also want to support a range like "Monday 10:00 to Wednesday 14:00", break this down into three tests for "Monday 10:00 to 23:59", "Thursday 00:00 to 23:59" and "Wednesday 00:00 to 10:00". For each day, store an interval ...


1

This is simpler than a tree because your result can only have one level. All you want is to group your array by category and then map each group into objects. The map part will just be rearranging things a little bit into your final desired structure. You won't need to filter the full list of videos inside the map like you're currently doing. Unfortunately, ...


3

The fact that a node can have two parents shouldn't prevent you from using a standard depth first search. As you describe it, a child with two parents is still independently part of two "solutions". The fact that there are at most two edges leaving each node simplifies things further. search(node): if node is null: // maybe a non-terminal parent's left ...


3

The indentation in the code is important: if uncle.color == red: # Handle case else if z == z.p.right: # Handle case 2 # Handle case 3 The syntax is a bit quirky, because they squished the if to appear on the same line as the else, but case 2 is indented further inward compared to the remaining case 3, indicating that they do not ...


0

While the advice being given here about not implementing your own sorting algorithm in the real world is, I think, sound, you still have to choose among initial data structures, and a List is not always the best starting point for sorting/searching. Searching the List once is one thing, but searching it many times is another. In the latter case, the List ...


0

Sorting algorithms are fundamental in computer science and any decent programmer should be familiar with. You are a student, which means you are learning, calling list.Sort() wouldn't contribute to your algorithmic thinking. So go and implement them yourself, understand time/space complexities and benchmark various sorting and search algorithm . This ...


2

If your language's standard library provides a feature you need, and you have no reason to believe there is something wrong with its implementation or API, then use the standard. Re-implementing the feature yourself will at best be a waste of time, since you'll be duplicating work other people have already done for you. At worst, your version will be slow ...


7

Generally speaking, if the language or standard library provides a function to do what you want done, use it until or unless you have a specific reason you need to use something else. That latter can happen, but it's fairly unusual as a general rule. Of course, in at least some cases it can make sense to consider some middle ground, such as writing a ...


2

Build a hash based on the following formula... 2 A(d) + B(d) + 1 A(d) is a hash of the date in the range 0 to 2 inclusive. B(d) is the least significant bit of a day-number representation of the date. Because consecutive values of 2 A(d) never differ by exactly 1 (or any odd number), and because consecutive values of B(d) always differ by precisely 1, ...


2

Produce the number in two steps: Step 1: ensure that no consecutive dates have same number Step 2: make it hard to guess For step 1 choose a serial number for each date (e.g. number of days since 1.1.2000). If this number is even, let the result be even, if the serial number is odd let the result be odd. This ensures that even and odd days alternate, ...


5

A compromise between Bent and Doc Brown's approaches might be to take the julian date modulus of a multiple of 6 (eg. 36), then lookup the corresponding value (between 1 to 6) in a quasi-random list that satisfies the "consecutive constraint". For 36, such a list might be: 246531451362532614364125615243123456 - which corresponds to the end word order ...



Top 50 recent answers are included