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)

1
vote
1answer
245 views

Is this still a Greedy Algorithm

As a preface I will state this is for a homework assignment. I have already discussed this with the professor and will not be using this design. This purpose of this question is whether or not the ...
2
votes
1answer
185 views

Build a map with city blocks and road

Is there a design pattern or well known algorithm to build a simple map with roads and city blocks? To have an idea of what's my target i describe some of the constraints and the context: a matrix ...
1
vote
7answers
13k views

Merge sort versus quick sort performance

I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two ...
5
votes
2answers
327 views

Why Do B+ Trees Have a Minimum Occupancy of 50%?

As far as I can tell, the basic operations (add, delete, search) on a B+ Tree would function the same if minimum occupancy was 1, or 1/3, or any other function on node size. All the sources available ...
23
votes
8answers
6k views

Function guaranteed to never return the same value twice [closed]

This is a question I was asked at a job interview, and I can't figure out the answer they were looking for, so I'm hoping someone here might have some ideas. The goal is to write a function that is ...
2
votes
2answers
323 views

Finding shortest path between nodes with a twist

Note: if you feel that I should include code, please tell me. I am solving a problem of finding shortest path between nodes. I am given the vertices between nodes, however they are one sided (ie you ...
4
votes
2answers
5k views

What makes for a bad case for quick sort?

I am learning about quicksort and want to illustrate different arrays that quicksort would have a hard time on. The quicksort I have in mind does not have an initial random shuffling, does 2 ...
0
votes
1answer
72 views

Simulated Annealing Contradiction?

The entire idea of simulated annealing is to avoid getting stuck in local optimums, which is why sometimes, a worse solution is accepted. However, simulated annealing will automatically accept a ...
1
vote
1answer
255 views

Rideshare algorithm to be used for scheduled and adhoc journeys

I need some help writing some pseudo code for a rideshare system for taxi drivers. The idea behind it is that it would combine real-time incoming taxi journeys and pre-bookings in real-time. The ...
3
votes
2answers
278 views

An algorithm that spreads similar items across a list

I need an algorithm that distributes same items across a list, so maximizing the distance between occurrences. E.g. I have a list of 15 items: {a,b,c,c,c,d,e,f,f,f,g,h,h,i,j} The algorithm should ...
1
vote
1answer
72 views

Find common ancestor

Given X number of leaves (the ringed leaves in the picture) in an unbalanced tree with depth aroun 100-1000 and total number of nodes around 15 000 000. I'm looking for the first common ancestor for ...
2
votes
2answers
498 views

How deep is enough to represent an algorithm in UML sequence diagram?

I have three simple classes. LoginController, UsersCatalog and User. UsersCatalog has an array of User. I have to represent a simple process of login. LoginController has a method login(username, ...
0
votes
1answer
145 views

What is the justification for the running time of this loop?

I don't understand why the running time of the following loop is n+2 ? Also why the running time of the statements inside the loop is n+1 ? Double test(int n){ int sum=0; -> 1 time ...
3
votes
4answers
302 views

Mark x% items in stream

There are n items (n is known and > 1,000,000,000). I want to randomly 'mark' x% of n-items in stream. (n and x are known) Items are in stream ,one directional (you can't go back) processed item ...
2
votes
1answer
100 views

Finding the fewest sets which contain all items

I am wondering if there is a known algorithm for solving the following. Data: There is a number of sets containing items. An item can be a member of more than one set. Aim: return the minimum number ...
3
votes
0answers
164 views

Walk Tree vs Zhang and Sasha Algorithms

I need some help understanding how two tree comparing algorithms differ. I am working with Microsoft's XmlDiffPatch (http://msdn.microsoft.com/en-us/library/aa302294.aspx) which compares two xmls. The ...
4
votes
2answers
236 views

Extracting first and last name from a single name field

I'm working with the Twitter API which provides only a single field called name, which includes the full name of a person. The application that we're constructing requires a first name and a last ...
0
votes
1answer
96 views

Handling the process of large-scale lists [closed]

What are the efficient ways to process huge lists (+10 millions), and things to consider while manipulating huge lists. First question, when should I use recursion, and when I shouldn't. In both ...
1
vote
2answers
333 views

How to construct a cubie representation of a rubik's cube, given an array

Just to get this out of the way, I have seen this, and it is not what I'm looking for. So, let's say you are programming a Rubik's Cube. (I know, very unoriginal, but bored programmers have to do ...
12
votes
2answers
1k views

How to calculate figure rotation efficiently?

I have a Figure represented through a matrix of bytes (bitmap-like matrix). Example Figure is shown on the Picture 1. The goal is to find the best rotation angle of some given Figure. When Figure ...
1
vote
1answer
654 views

How to find duplicate strings

I allow my user to create profiles, meaning they potentially could create some with duplicate names. This can be problematic so I want to prevent them from doing so. I coded up this first pass ...
3
votes
1answer
327 views

What advantages are there to using Flex/Bison over just writing a compiler straight in a programming language?

I have written an Interpreter / Compiler simply as a programming algorithm using features such as recursive functions and concepts from finite-State machines. To me, these things are ideally suited to ...
0
votes
0answers
88 views

Does multiple Bloom filters make sense?

In order to decrease the number of false positives, I came up with a couple of possible solutions. Create two different types of Bloom filters; eg. filter1 using 3 different hash algorithms, filter2 ...
2
votes
1answer
557 views

Quickest sorting algorithm for sorting a low number of integers

I am making a program on my spare time that I want to run as quickly as possible. The program is written in C. A large set of the procedures operate on pointers to 7 integers that are sorted by their ...
1
vote
2answers
90 views

multiple comparison sorting

I have a set of songs where I want to sort them by a particular quality. In order to do this (by crowdsourcing) I will present users with a comparison between two songs. The user will then choose ...
0
votes
1answer
110 views

Method ordering

This is the type of question that one would probably get in an exam, but now it happens to be in the real word. :-) I would appreciate some advice regarding the datastructure/algorithm that can be ...
1
vote
4answers
807 views

Order by different Enum property each row

So I have a list of DefaultSearchModal items that have an enum called TypeSearch in every list item. I would like to order the list to have a different enum property each row. So if you have an ...
0
votes
1answer
107 views

How to compute data for charting?

I'm building a charting component that displays data directly from the raw data records. It should be able to filter data (subset) and then perform some rudimentry maths on the data (sum, avg, etc). ...
2
votes
0answers
142 views

Incorporating custom Algorithm in SOLR-LUCENE , before Indexing?

CURRENT FLOW: I am using a custom algorithm(presently in php) to rank the MYSQL records before INDEXING it to SOLR . WHAT I WANT : Is it possible implementing this ALGORITHM(may be in JAVA) inside ...
0
votes
1answer
556 views

problem on calculating Big O complexity

i have this function on which i have to calculate the time complexity with the Big O notation: public void print(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> ...
0
votes
1answer
433 views

Find possible variations of one item out of multiple baskets.

I have three baskets of balls and each of them has 10 balls which have the following numbers: Basket 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 Basket 2: 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ...
2
votes
0answers
582 views

How to find minimum weighted vertex cover of a tree, and confused about a solution

Studying for my algorithms test by spamming Algorithm Design Manual exercises, but I'm stuck on this one. I know I have to keep score somehow. Let G = (V,E) be a tree with arbitrary weights ...
1
vote
1answer
336 views

Safe serial numbers generation

I want to generate a 6 digits serial number, ranged from A-Z (only uppercase allow), e.g. serial = "ABCDEF" the problem is, some letters are considered confusing to others letters/numbers, e.g. U ...
0
votes
2answers
172 views

Permutation tests for large sequences

I would like to perform a permutation test on a particularly large data set, i.e. around 4 million entries. Basically, I need to get some number of random permutations of this data set. Usual way to ...
0
votes
1answer
926 views

How is a floating point number represented in Java?

Which algorithm does java uses to convert floating point number (Ex:0.15625) into binary(0.00101)? Whether java uses normalized form or denormalized format? If I type float ab=0.15625 in Java source ...
1
vote
1answer
368 views

Is it possible to apply Master Theorem for finding the square and cube root

I was asked to calculate the running time of an algorithm which finds the square root and cube root of a given number. Is it possible to apply Master theorem with regards to this? First, I need to ...
0
votes
3answers
668 views

How would you go about compressing a list of integers that are non unique and retain the original order?

Let's start out with an example [1,1,1,5,3,1,1,2,78,2,3,1,1,...,1] As you can tell by the example, 1 is repeated a lot, but there will be outliers (like 78, and really anything that isn't 1). The ...
3
votes
2answers
647 views

Algorithm for mapping users to a schedule based on time availability

I have a project where I must map employees to a schedule. The basic concept is: Company Opens between 08:30 and 17:00. Employee 1 can work from 08:30 to 12:00 then from 13:00 to 1700; Employee 2 ...
3
votes
2answers
499 views

Process to generate hierarchical structure based on relational data?

I have a csv of employee ids, names, and a reference column with the id of their direct manager, say something like this emp_id, emp_name, mgr_id 1,The Boss,, 2,Manager Joe,1 3,Manager Sally,1 ...
2
votes
1answer
590 views

How to Detect Sprites in a SpriteSheet?

I'm currently writing a Sprite Sheet Unpacker such as Alferds Spritesheet Unpacker. Now, before this is sent to gamedev, this isn't necessarily about games. I would like to know how to detect a sprite ...
2
votes
1answer
181 views

Algorithm to match timestamped events from two sources

I have two different physical devices (one is camera, one is other device) that observe the same scene and mark when a specified event occures. (record timestamp) So they each produce a serie of ...
1
vote
3answers
2k views

How do I approach this PHP/MYSQL query?

I have a reservation system that I have coded and my final task is to allow the user to enter a set of dates and then show them all available options. The reservation table is set up with unit_id, ...
1
vote
1answer
149 views

Algorithm to “de-rasterize” a voxel image of a polyhedron

Rasterizing a polygon in this question consists of creating an array of binary pixels that "represent" the polygon. The reverse of this process is easy to approximate in linear time to the perimeter ...
4
votes
1answer
61 views

How to diversify an optimal solution set?

If given a list of players, their salaries, and their projections, one can easily find the top 'n' projected teams (where a team is a combination of players), such that every team is under the salary ...
1
vote
1answer
71 views

Sorting list and changing same values to nearly the same

I have a list of doubles that need to be sorted and changed so that there are no two numbers that are the same (difference smaller then 0.05) and I need to do it fast. I don't care about preserving ...
-1
votes
3answers
426 views

Generate unique integer from two integers with algorithm

I am currently trying to come up with an algoritm which would take at least two numbers (say user IDs) and then come up with an unique number which is generated based on these two numbers. Each ...
2
votes
0answers
69 views

Calculating “instability score” for connection quality, programmatically

First of all, apologies if this is posted in the wrong site. I thought it is more suitable here than SO because the question is quite generic, more an algorithm question than a specific programming ...
0
votes
0answers
119 views

Similar problem to word break

I have a list of strings say L and an array of words say A. I want to find a string from the list L that is a best match to a string created from the permutations of the words in the array. The ...
4
votes
4answers
948 views

How to rotate an array of bits

I currently have a PIL Image object which I store as an array of bits (1's and 0's). However I now would like to be able to rotate that image 45 degrees. One way to do it is take the original PIL ...
0
votes
4answers
466 views

How to manually detect deadlocks

I understand the concepts of deadlock well enough, but when I'm given a problem like the one below I'm not sure how to go about solving it. I can draw a resource allocation graph, but I'm not sure how ...