3
votes
2answers
63 views

Trivially Sortable Encoding for Arbitrary-Precision Decimals

I'm looking for a reasonably(*) space-efficient way to encode arbitrary-precision decimals (e.g. BigDecimal), such that when sorting the bit-pattern of the encodings lexicographically, the numbers ...
0
votes
1answer
60 views

How can I approach creating an efficient algorithm for maximizing value with these specific constraints?

I'm having trouble coming up with an approach that isn't n^2 for this problem. Here's a contrived, simplified version I've come up with: Let's say you're a company that needs 4 employees to launch in ...
0
votes
3answers
179 views

Least Change Problem with Thousands of Denominations

In a hypothetical economy there are currency units that can represent thousands of different values. So, for example there might be coins worth 1c, 3c, 5c, 7c, 7.5c, 80c, 8001.5c etc. Given a list of ...
0
votes
2answers
267 views

Quick algorithm to find matches between two arrays

I'm faced with the following problem: I have an array which is produced by the parsing of a yaml file which contains patterns in the following structure. "Programming books" Title: a ...
1
vote
2answers
150 views

Making an algorithm more efficient

I have a question about the efficiency of an algorithm: You have a list of x,y points Now I want to get all the points that are up to 5 units away from a reference x,y point How do you calculate it ...
4
votes
2answers
556 views

How much logic can be put into an object-pooling factory class before it does more harm than good?

The main language I'm interested in doing object pooling in is AS3, which is known to need it in many cases. In the past I've always made a brand new factory class for every type I was going to try ...
2
votes
2answers
252 views

When is a code considered tight and how does it increase efficiency of the code?

I have read many times that insertion sort has tight code and hence the hidden constant factor in its asymptotic complexity is smaller. I just read yesterday that quick sort has tight code just like ...
3
votes
1answer
180 views

Processing every leaf under a node in a tree efficiently

Short version: In a tree (non-binary) with many levels of children, where each node can have multiple leaves, what is the best way to tally leaves that meet a certain condition given a node? Long, ...
6
votes
6answers
3k views

Why is binary search,which needs sorted data, considered better than linear search?

I have always heard that linear search is a naive approach and binary search is better than it in performance due to better asymptotic complexity. But I never understood why is it better than linear ...
7
votes
2answers
271 views

What is an efficient algorithm for randomly assigning a pool of objects to a parent using specific rules

I need some expert answers to help me determine the most efficient algorithm in this scenario. Consider the following data structures: type B { A parent; } type A { set<B> children; ...
3
votes
2answers
1k views

Amortized Analysis? (Worst-case Performance Guarantees)

What is Amortized Analysis? And how can it help me achieve worst-case performance guarantees in my programs? I was reading that the following techniques can help the programmer achieve Worst-case ...
1
vote
2answers
145 views

Using replacement to get possible outcomes to then search through HUGE amount of data

I have a database table holding 40 million records (table A). Each record has a string a user can search for. I also have a table with a list of character replacements (table B) i.e. i = Y, I = 1 ...
8
votes
1answer
594 views

Subset sum problem is NP-complete?

If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
2
votes
2answers
418 views

How do we know if a problem is hardest in NP

I read that the definition of NP-complete is : These are the hardest problems in NP. Such a problem is NP-hard and in NP How do we know if a problem is hardest in NP, and no harder problem ...
6
votes
3answers
241 views

NP hard/complete

I have never been very clear on this concept. Please help: At the end of the day, we should want to identify useful problems for which we don't have polynomial solution so far and only have ...