In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning.

learn more… | top users | synonyms (1)

3
votes
3answers
800 views

Algorithm to figure out appointment times?

I have a weird situation where a client would like a script that automatically sets up thousands of appointments over several days. The tricky part is the appointments are for a variety of US time ...
13
votes
3answers
1k views

Initialize array in amortized constant time — what is this trick called?

There is this data structure that trades performance of array access against the need to iterate over it when clearing it. You keep a generation counter with each entry, and also a global generation ...
5
votes
2answers
136 views

Automated tests for differencing algorithm

We are designing a differencing algorithm (based on Longest Common Subsequence) that compares a source text and a modified copy to extract the new content (i.e. content that is only in the modified ...
45
votes
4answers
9k views

Which algorithms/data structures should I “recognize” and know by name? [closed]

I'd like to consider myself a fairly experienced programmer. I've been programming for over 5 years now. My weak point though is terminology. I'm self-taught, so while I know how to program, I don't ...
1
vote
2answers
309 views

What is wrong with my logic for the divide and conquer algorithm for Closest pair problem?

I have been following Coursera's course on Algorithms and came up with a thought about the divide/conquer algorithm for the closest pair problem, that I want clarified. As per Prof Roughgarden's ...
7
votes
5answers
541 views

Are proofs worth the effort?

I bought the de-facto book for learning about data structures and algorithms (CLRS). The book is though quite good but the singularity is in the proofs. The book is filled with Lemmas, theorems, ...
1
vote
1answer
384 views

Minimizing use of paper

I've recently faced this problem in a dynamic programming curriculum, and I honestly have no idea about how to determine the appropriate state. You're given N (1 <= N <= 70) paragraphs and M (1 ...
2
votes
1answer
142 views

How to identify a PDF classification problem?

We are crawling and downloading lots of companies' PDFs and trying to pick out the ones that are Annual Reports. Such reports can be downloaded from most companies' investor-relations pages. The PDFs ...
-3
votes
1answer
568 views

Construct an array from an existing array

Given an array of integers A[1...n-1] where 'N' is the length of array A[ ]. Construct an array B such that B[i] = min(A[i], A[i+1], ..., A[i+K-1]), where K will be given. Array B will have ...
15
votes
2answers
6k views

Conflict resolution for two-way sync

How do you manage two-way synchronization between a 'main' database server and many 'secondary' servers, in particular conflict resolution, assuming a connection is not always available? For example, ...
7
votes
2answers
2k views

How to get better at solving Dynamic programming problems

I recently came across this question: "You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the ...
1
vote
3answers
4k views

Big O(n log n) and Quicksort number of operations

I have an Array with 1,000,000 unsorted elements. I need to calculate expected number of operations that needs to be performed to sort array using Quicksort algorithm in common situations (not the n^2 ...
2
votes
1answer
399 views

Is there an specific way or algorithm to decode protocols?

I am designing a simple logic analyzer, I know that the best way to decode a protocol like I2C, SPI, UART is whit something like an FPGA but I want to do it by software by now :) I am running on an ...
1
vote
1answer
363 views

Sorting Algorithm : output

I faced this problem on a website and I quite can't understand the output, please help me understand it :- Bogosort, is a dumb algorithm which shuffles the sequence randomly until it is sorted. But ...
3
votes
3answers
2k views

Partitioning set into subsets with respect to equality of sum among subsets

Let's say I have {3, 1, 1, 2, 2, 1, 5, 2, 7} set of numbers, I need to split the numbers such that sum of subset1 should be equal to sum of subset2 {3,2,7} {1,1,2,1,5,2}. First we should identify ...
8
votes
3answers
905 views

What Is The Formula for the 3 of 9 Bar Code Alphabet?

Background: 3 of 9 Barcode Alphabet A simple syntax for 3 of 9 bar codes What is the formula behind the alphabet and digits in a 3 of 9 bar code? For example, ASCII has a relatively clear ...
2
votes
1answer
5k views

faster algorithm for finding all subsets

This is the algorithm (pseudocode) I have right now for finding all subsets for a given set with length k: void allSubsets(set[]) { for (i = 0; i<k; i++) { for (j = i + 1; j<k; j++) ...
5
votes
3answers
492 views

Is there a phrase or word to describe an algorithim or program is complete in that given any value for its arguments there is a defined outcome?

Is there a phrase or word to describe an algorithim or programme is complete in that given any value for its arguments there is a defined outcome? i.e. all the ramifications have been considered ...
3
votes
2answers
17k views

How to calculate checksum?

I am developing instrument driver and I want to know how to calculate checksum of frame. Explanation: Expressed by characters [0-9] and [A-F]. Characters beginning from the character after ...
5
votes
1answer
474 views

What does path finding in internet routing do and how is it different from A*?

Note: If you don't understand this question then feel free to ask clarification in the comments instead of voting down, it might be that this question needs some more work at the moment. I've been ...
5
votes
5answers
840 views

How does one unit test an algorithm

I was recently working on a JS slideshow which rotates images using a weighted average algorithm. Thankfully, timgilbert has written a weighted list script which implements the exact algorithm I ...
3
votes
3answers
365 views

questions on a particular algorithm

Upon searching for a fast primr algorithm, I stumbled upon this: public static boolean isP(long n) { if (n==2 || n==3) return true; if ((n&0x1)==0 || n%3==0 || n<2) return false; ...
7
votes
4answers
1k views

finding houses within a radius

During an interview I was asked given the following: A real estate application that lists all houses that are currently on the market (i.e., for sale) within a given distance (say for example the user ...
0
votes
2answers
246 views

Given number which equals the sum of some of the 10 numbers. How to determine that given number contains one of 10 numbers?

I have: ten numbers: +1, +2, +4, +8, +16, +32, +64, +128, +256, +512. flag == sum of some of this ten numbers. How to determine that sum contains 2 or 32?
10
votes
3answers
394 views

Efficient Bus Loading

This is something I did for a bus travel company a long time ago, and I was never happy with the results. I was thinking about that old project recently and thought I'd revisit that problem. Problem: ...
8
votes
4answers
3k views

How common are generic-case exponential time algorithms in production software?

I know that exponential time algorithms should generally be avoided but are sometimes necessary. A case being the Traveling Salesman. How common are such algorithms in production software? Are these ...
7
votes
2answers
545 views

What is the algorithm for expiring items in key-value storage?

I was thinking on how current key-value storages implement "expire date" for items. Currently I have 2 variants for that in my mind: they don't do anything (keep expired data), and only do check ...
9
votes
5answers
4k views

Improving performance for grepping over a huge file

I have FILE_A which has over 300,000 lines and FILE_B which has over 30 million lines. I created a Bash script that greps each line in FILE_A over in FILE_B and writes the result of the grep to a new ...
17
votes
8answers
2k views

Strategy/algorithm to divide fair teams based on history

We are a group of people playing floorball together on a regular basis. Every session starts with the daunting task of dividing teams... So what would be better than an application to pick teams ...
24
votes
5answers
8k views

Return random `list` item by its `weight`

I have, for example, this table +-----------------+ | fruit | weight | +-----------------+ | apple | 4 | | orange | 2 | | lemon | 1 | +-----------------+ I need to return random ...
22
votes
6answers
18k views

Why is quicksort better than other sorting algorithms in practice?

This is a repost of a question on cs.SE by Janoma. Full credits and spoils to him or cs.SE. In a standard algorithms course we are taught that quicksort is O(n log n) on average and O(n²) in the ...
3
votes
1answer
366 views

Grouping numbers to minimize group-means

I need to find a way or an algorithm that groups members of a given data set (of positive integers) so that the difference between group means is minimized (not maximized, as usual). There are two ...
2
votes
2answers
481 views

Algorithm to minimize distance variance between 2D coordinates

I've been looking around for an algorithm that would optimize the distance between 2 list of coordinates and choose which coordinate should go together. Say I have List 1: 205|200 220|210 200|220 ...
8
votes
6answers
1k views

How do the algorithms to solve problems encountered in interviews translate into real world solutions? [closed]

I have recently finished an undergraduate course in computer science and I am looking for a job. During the search I encountered several interesting (and tough) problems that needed clever algorithms ...
11
votes
5answers
380 views

Convert list of 24-hour-precipitation values into total-by-hour

Let's say I have a list of precipitation values by hour, each showing how much rain happened in the prior 24 hours, ordered by date. For example: { '2012-05-24 12:00': 0.5, // .5" of rain from ...
3
votes
1answer
202 views

Algorithms for pairing a rating system to an assignment queue

Attempting to research how to allow a group of people to effectively rank a set of objects (each group member will have contributed one object to the group), and then assign each member an object ...
3
votes
4answers
381 views

How to implement a system to hide spammed user content?

I'm trying to work out a good way to manage user submitted content and create a method to determine when spammed/poor content should be hidden. The aim is to create comment voting similar to youtubes ...
7
votes
2answers
2k views

Algorithm for finding overlapping times

Part of our ERP system is a sub-system for running background jobs. We track a variety of meta-data about our jobs in a table including timestamps for submitted, started, and end times. I'm creating ...
3
votes
1answer
215 views

Logic required to solve a problem relating to location of objects

I have raised a question on dba.stackexchange.com but as the heart of my question is in fact to do with logic I have raised a more general representation of my issue here. I think it is the right ...
2
votes
4answers
5k views

What sorting algorithm does STL use?

I recently started using <vector.h> library and I was wondering, since all the operations are already implemented, IF the method of the sorting algorithm is the most efficient one. Everything ...
3
votes
1answer
792 views

How can this deterministic linear time selection algorithm be linear?

I'm trying to understand the basic concepts of algorithms through the classes offered at Coursera (in bits and pieces), I came across the deterministic linear time selection algorithm that works as ...
2
votes
1answer
327 views

What alogrithm is used on the smart cards for the DNSSEC Trusted Community Representatives?

I've been doing some reading about DNSSec and am interested in the algorithm that they chose to use when splitting the trusted key up between the 7 Trusted Community Representatives (TCR). I ...
5
votes
1answer
448 views

Firefighting allocation problem

I'm trying to develop a model to work on an assignment problem in the firegifhter area. Given n firefighters, m trucks and z ongoing fires, each with a danger level, try and allocate the resources in ...
1
vote
2answers
247 views

Fuzzy search for a sub-string without tokens

Let's say I have the following lines: Lorem ipsum dolor sit amet, (tag) consectetur adipiscing elit. Phasellus congue nisi vel lorem dignissim tristique. (tag) Etiam vulputate lacus nec velit ...
13
votes
5answers
5k views

What would be the Impact of P=NP? [closed]

I am preparing for a test and I can't find a clear answer on the question: What would be the impact of proving that PTIME=NPTIME. I checked wikipedia and it just mentioned that it would have "profound ...
7
votes
2answers
1k views

Are nested loops always O(n^k)?

If I have a loop within another loop, yet I know the inner loop will only run once, will this algorithm still be O(n^2)? For i = 1 to n do For j = 1 to i do If (i==j) do ...
6
votes
3answers
3k views

What algorithm(s) can be used to achieve reasonably good next word prediction?

What is a good way of implementing "next-word prediction"? For example, the user types "I am" and the system suggests "a" and "not" (or possibly others) as the next word. I am aware of a method that ...
2
votes
3answers
914 views

How do programs like subversion detect when a file has been edited as opposed to created/deleted?

This is my first question here so I hope it is not off topic. Although I am using the Linux inotify library to listen for changes to files, and I compare use of that against the Subversion program, I ...
3
votes
4answers
415 views

What is the algorithm to copy a region of one bitmap, into a region in another?

In my project (and I am sure many others), I need to copy a subset (R2) of one bitmap image (R1), into a region (R3) in another, where the destination region can be any size (stretching and scaling ...
3
votes
3answers
1k views

Algorithm which suggests synonyms based on some term?

Is there an algorithm which I can use in order to generate synonyms for some term (word) in respect of a spam. I am writing a simple spam filter. For example, I set that the app must omit a word ...