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)

2
votes
4answers
592 views

How to discriminate from two nodes with identical frequencies in a Huffman's tree?

Still on my quest to compress/decompress files with a Java implementation of Huffman's coding (http://en.wikipedia.org/wiki/Huffman_coding) for a school assignment. From the Wikipedia page, I quote: ...
2
votes
2answers
467 views

About insertion sort and especially why it's said that copy is much faster than swap?

From Lafore's "Data Structures and Algorithms in Java": (about insertion sort (which uses copy + shift instead of swap (used in bubble and selection sort))) However, a copy isn’t as time-consuming ...
1
vote
1answer
160 views

Does it matter the direction of a Huffman's tree child node?

So, I'm on my quest about creating a Java implementation of Huffman's algorithm for compressing/decompressing files (as you might know, ever since Why create a Huffman tree per character instead of a ...
2
votes
1answer
317 views

Why create a Huffman tree per character instead of a Node?

For a school assignment we're supposed to make a Java implementation of a compressor/decompresser using Huffman's algorithm. I've been reading a bit about it, specially this C++ tutorial: ...
3
votes
1answer
128 views

Assignment of roles in communication when sides could try to cheat

Assume two nodes in a peer-to-peer network initiating a communication. In this communication, one node has to serve as a "sender", another as a "receiver" (role names are arbitrary here). I'd like ...
4
votes
1answer
594 views

What types of programming contest problems are there? [closed]

Basically, I want to make a great reference for use with programming contests that would have all of the algorithms that I can put together that I would need during a contest as well as sample useage ...
4
votes
3answers
658 views

Round Table - Minimum Cost Algorithm

Problem Link - http://www.iarcs.org.in/zco2013/index.php/problems/ROUNDTABLE It's dinner time in Castle Camelot, and the fearsome Knights of the Round Table are clamouring for dessert. You, the ...
0
votes
1answer
308 views

Number Game Algorithm

Problem Link - http://www.iarcs.org.in/inoi/2011/zco2011/zco2011-1b.php The task is to find the maximum score you can get in the game. Such problems, based on games, where you have to simulate, ...
-2
votes
1answer
298 views

Grid Game Algorithm

Problem Link - http://www.iarcs.org.in/inoi/2009/zco2009/zco2009-1a.php You have to find the path with the maximum weight, from the top-left cell to the bottom-right cell. It could've been solved ...
5
votes
2answers
263 views

Is it possible (and practical) to search a string for arbitrary-length repeating patterns?

I've recently developed a huge interest in cryptography, and I'm exploring some of the weaknesses of ECB-mode block ciphers. A common attack scenario involves encrypted cookies, whose fields can be ...
2
votes
1answer
262 views

Filling array with numbers from given range so that sum of adjacent numbers is square number

Problem: Fill all the cells using distinct numbers from <1,25> set, so that sum of two adjacent cells is a square number. (source: http://grymat.im.pwr.wroc.pl/etap1/zad1etp1213.pdf; numbers 20 ...
0
votes
2answers
167 views

When modeling a virtual circuit board, what is the best design pattern to check for cycles?

To make it simple assume you have only AND and OR gates. Each has two inputs and one output. The output of two inputs can be used as an input for the next gate For example: A AND B -> E C AND D -> F ...
3
votes
3answers
504 views

Is there a way to add unique items to an array without doing a ton of comparisons?

Please bare with me, I want this to be as language agnostic as possible becuase of the languages I am working with (One of which is a language called PowerOn). However, most languanges support for ...
4
votes
3answers
438 views

Equal Gifts Algorithm Problem

Problem Link - http://opc.iarcs.org.in/index.php/problems/EQGIFTS It is Lavanya's birthday and several families have been invited for the birthday party. As is customary, all of them have brought ...
1
vote
2answers
187 views

Quickly compute added and removed lines

I'm trying to compare two text files. I want to compute how many lines were added and removed. Basically what git diff --stat is doing. Bonus points for not having to store the entire file contents in ...
30
votes
7answers
5k views

When to use DAG (Directed Acyclic Graph) in programming?

I recently found a framework named ecto. In this framework, a basic component named "plasm", which is the ecto Directed Acyclic Graph.In ecto, plasm can be operated by ecto scheduler. I am ...
2
votes
2answers
235 views

How to detect two moving shapes overlapped?

Given a list of circles with its coordinates (x and y) that are moving every second in different direction (South-East, South-West, North-East and North-West), and the circle will change direction if ...
5
votes
1answer
340 views

Writing algorithm on 2D data set in plain english

I have started an introductory Java class and the material is absolutely horrendous and I have to get excellent grades to be accepted into the master's degree, hence my very beginner question: In my ...
0
votes
0answers
134 views

How to find optimal path visit every node with parallel workers complicated by dynamic edge costs?

Say you have an acyclic directed graph with weighted edges and create N workers. My goal is to calculate the optimal way those workers can traverse the entire graph in parralel. However, edge costs ...
1
vote
4answers
875 views

algorithm to print the digits in the correct order

I've been trying to write an algorithm that will print separately the digits from an integer. I have to write it in Pseudocode. I know how to write an algorithm that reverse the digits. digi(n): ...
6
votes
1answer
1k views

What is the usage of Splay Trees in the real world?

I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world? In this Cornell: ...
26
votes
4answers
2k views

Can you use Pi as a crude random number generator?

I recently saw this question over at math.SE. It got me thinking. Could Pi be used as a crude random number generator? I mean the results are well known(how long has pi been computed to now?) but, Pi ...
2
votes
1answer
415 views

One dimensional cutting algorithm with minimum waste

Can anybody point me to some resources about "cutting algorithm"? The problem: have rods with length of L meters, e.g. 6 m need cut smaller pieces of different lengths, e.g. need: 4 x 1.2m 8 x ...
-2
votes
2answers
463 views

Java Alphabetize Algorithm Insertion sort vs Bubble Sort [closed]

I am supposed to "Develop a program that alphabetizes three strings. The program should allow the user to enter the three strings, and then display the strings in alphabetical order." It's instructed ...
7
votes
3answers
357 views

Is there a 'design pattern' type listing of common algorithms? [closed]

Is there a 'design pattern' styled listing of common/popular algorithms anywhere? Specifically, something that has a similar format along the lines of: Algorithm Name: e.g., Quick Sort, Bubble Sort, ...
-2
votes
1answer
171 views

Arranging the colors on the board in the most pleasing form [closed]

Given a rectangular board of height H and width W. N colors are given and each color occupies Xi percentage of area on the board. Sum of Xi's is 1. The colors on the board must be placed in ...
3
votes
2answers
179 views

Taking a Projects Development to the Next Level

I have been looking for some advice for a while on how to handle a project I am working on, but to no avail. I am pretty much on my fourth iteration of improving an "application" I am working on; the ...
0
votes
2answers
435 views

Detect duplicate in a subset from a set of elements

I have a set of numbers say : 1 1 2 8 5 6 6 7 8 8 4 2... I want to detect the duplicate element in subsets(of given size say k) of the above numbers... For example : Consider the increasing ...
2
votes
3answers
283 views

Distance from point to n-dimensional line [closed]

The solution for the 3-d case can be found here; I would like to get the generalized version. There's no simple generalization of the Mathworld algorithm since the cross product is defined only for 3 ...
5
votes
1answer
976 views

What are algorithmic paradigms?

We generally talk about paradigms of programming as functional, procedural, object oriented, imperative etc but what should I reply when I am asked the paradigms of algorithms? For example are ...
7
votes
4answers
382 views

How/where to run the algorithm on large dataset?

I would like to run the PageRank algorithm on graph with 4 000 000 nodes and around 45 000 000 edges. Currently I use neo4j graph databse and classic relational database (postgres) and for software ...
8
votes
3answers
759 views

How to calculate Sin function quicker and more precisely?

I want to calculate y(n)=32677Sin(45/1024•n), where y is an integer and n ranges from 0 to 2048. How can I make this process quicker and more precisely? Now I want to show you a reference answer: ...
14
votes
4answers
758 views

What algorithms can I use to detect if articles or posts are duplicates?

I'm trying to detect if an article or forum post is a duplicate entry within the database. I've given this some thought, coming to the conclusion that someone who duplicate content will do so using ...
44
votes
7answers
3k views

How important is it for a programmer to know how to implement a QuickSort/MergeSort algorithm from memory?

I was reviewing my notes and stumbled across the implementation of different sorting algorithms. As I attempted to make sense of the implementation of QuickSort and MergeSort, it occurred to me that ...
2
votes
1answer
252 views

Tiling Problem Solutions for Various Size “Dominoes”

I've got an interesting tiling problem, I have a large square image (size 128k so 131072 squares) with dimensons 256x512... I want to fill this image with certain grain types (a 1x1 tile, a 1x2 ...
5
votes
2answers
662 views

Efficient Data Structure for holding a graph

Problem Link - http://opc.iarcs.org.in/index.php/problems/NUMTRIPLE In my opinion, the problem can be solved by a data structure, that shows how each number is connected to another, and via recursion ...
3
votes
1answer
290 views

Amazon Kindle - Whispersync implementation?

For those who are not aware of Kindle's whispersync, here is how it works (from amazon.com): "...Whispersync synchronizes the bookmarks and furthest page read among devices registered to the same ...
7
votes
3answers
319 views

Algorithm to use for shop floor layout?

I ran into a classroom problem yesterday (business oriented class, not computer science) and I found it interesting from an algorithmic perspective. The problem goes something like this: Assume there ...
13
votes
4answers
994 views

How can I estimate the entropy of a password?

Having read various resources about password strength I'm trying to create an algorithm that will provide a rough estimation of how much entropy a password has. I'm trying to create an algorithm ...
3
votes
2answers
207 views

Looking for a dynamic programming solution

Given a sequence of integers in range 1 to n. Each number can appear at most once. Let there be a symbol X in the sequence which means remove the minimum element from the list. There can be an ...
0
votes
2answers
220 views

Why the bound of a linear function is same as that of a quadratic equation

I am learning algorithms, and I came across something very interesting. The asymptotic bound of the linear equation (a * n)+b is O(n^2), for all a > 0. This is same bound as a * n^2 + b * n + c, ...
1
vote
1answer
364 views

Developing a search algorithm

I want to create a basic search engine, and I want you to give me some ideas how to filter out the best results for my visitors. I have three fields regarding a product the user can search in: ...
2
votes
1answer
82 views

String patterns that can be used to filter and group files

One of our application filters files in certain directory, extract some data from it and export a document from the extracted data. The algorithm for extracting the data depends on the file, and so ...
4
votes
1answer
374 views

How do you write a linearithmic algorithmn?

Write psuedocode to determine the number of pairs of values in an input file that are equal. If your first try is quadratic, think again and develop a linearithmic solution. I found this ...
1
vote
2answers
4k views

Generic Adjacency List Graph implementation

I am trying to come up with a decent Adjacency List graph implementation so I can start tooling around with all kinds of graph problems and algorithms like traveling salesman and other problems... ...
0
votes
1answer
124 views

What is a good algorithm to distribute items with specific requirements?

I have to programmatically distribute a set of items to some entities, but there are rules both on the items and on the entities like so: Item one: 100 units, only entities from Foo Item two: 200 ...
2
votes
2answers
1k views

Designing Algorithm Flowchart Application

I need to develop an GUI application in C# where users can freely add conditional/statement blocks on the algorithm flowchart like the one shown below. By freely, I mean users can add a block on ...
6
votes
1answer
2k views

Shortest Common Superstring: find shortest string that contains all given string fragments

Given some string fragments, I would like to find the shortest possible single string ("output string") that contains all the fragments. Fragments can overlap each other in the output string. ...
1
vote
2answers
286 views

Subset whose sum gets closest to saturating some bound

I have a problem that boils to down having a set of integers and wanting the subset of those integers whose sum is closest to some target without going over. What's a good algorithm for doing this? ...
0
votes
1answer
414 views

Removing occurrences of characters in a string

I am reading this book, programming Interviews exposed by John Wiley and sons and in chapter 6 they are discussing removing all instances of characters in a src string using a removal string... so ...