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)

11
votes
3answers
925 views

Please explain the statement that the function an+b belongs to O(n^2) and Θ(n)?

Let's say I have a linear function f(n)= an+b, what is the best way to prove that this function belongs to O(n2) and Θ(n)? I do not need mathematical rigor here. I need a programmers answer. Some ...
1
vote
1answer
89 views

Algorithm to find the closest summation of elements in a list to a given number [duplicate]

Say I have a list {1,3,7,2,11,8,2} and I want to take x elements from the list and get the value 15.5. Is there an algorithm that would give me x elements in a list that, when added together, get ...
0
votes
1answer
215 views

How can I rank teams based off of head to head wins/losses

I'm trying to write an algorithm (specifically in Ruby) that will rank teams based on their record against each other. If a team A and team B have won the same amount of games against each other, then ...
1
vote
2answers
80 views

How to randomly get or find a sub-tree (include root node) from a given tree that contains n leaf-nodes

I have a non-binary tree. I want to randomly find a "sub-trees" that are connected from root to leaf which must have at least n leaf-nodes (leaf-nodes of sub-tree must be leaf-nodes of given tree). ...
1
vote
2answers
134 views

Lower and Upper bound of an algorithm

I am learning about analysis of algorithms. I came across the term "upper bound" and "lower bound" in "worst-case" running time of an algorithm. Are they applicable to only the "worst case" or can ...
1
vote
2answers
361 views

Is it possible to protect client side algorithms 100%?

If you had a pretty novel idea that involved a new algorithm. Like lets say you were the first person to think of orbitz.com or kayak.com (travel sites) and you were able to and wanted to implement ...
0
votes
0answers
29 views

Syncing different nosql datasources efficiently

I have two dbs I am dealing with right now - Elasticsearch and Mongodb. Mongodb is legacy in the application in that I am not happy for its presence but it is there and in use, I am interested in ...
0
votes
2answers
95 views

Big O of 2 interesting Algorithmic functions [closed]

This is my homework(I have attempted it, and there are no references for questions like these) Determine whether or not these functions are polynomial run time and determine the constant c for ...
1
vote
1answer
93 views

saving connectivity information in a nodes/edges network

I want to implement the A* algorithm. I have a network with Nodes and Edges, both are classes. Now, I am unsure how to approach the connectivity information. Should a node know which edges depart ...
0
votes
1answer
225 views

Which weak algorithmic strategies I have that lead me to failing coding this simple algorithm? [closed]

I am a graduate student in computer science who graduated recently from a famous university. I applied to my first software engineering job and I failed the technical interview by failing to answer ...
0
votes
1answer
265 views

run time of nested while loop inside for loop

I'm here to clarify my understanding of the run times of these 2 algorithms: Algorithm1(n): For i = 1 to n j = 1 while i+j < n j = j+1 and Algorithm2(n): For i = 1 to n j = ...
0
votes
1answer
110 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 ...
1
vote
1answer
77 views

find the minimum number of sets

Let's explain my question with example I have some integer sets for example S1 = {2,3} S2 = {2, 5} S3 = {4, 5} S4 = {4} S5 = {5} And I have sample set Ssample with 4 elements {2, 3, 4, 5}. So ...
-3
votes
0answers
12 views

Recursive solution for 3n+1 [migrated]

I just like to do simple recursion. For a number if it is even then it'll approach to (number/2) and if odd then to (3*number+1). How many time it'll occur to reach 1. for 10 10-> 5-> 16-> 8-> 4 ...
0
votes
1answer
191 views

Calculate reachability of one point from another

I have an array which stores a set of positive x coordinates in sorted way, say arr={1, 4, 5, 9, 12, 45} etc. And I have a maximum distance k which I can go from one point to another point let ...
0
votes
1answer
60 views

Min weight feedback edge set with DFS?

Exercise from The Algorithm Design Manual 6-10. [4] Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. ...
1
vote
1answer
46 views

What is the minimum cost graph inside a strongly connected component, which connects every vertex?

So for MST there are 2 possible definitions in an undirected graph. Keep in mind that in an undirected graph the MST algorithm always has n - 1 edges and no cycles. In an undirected graph, it doesn't ...
1
vote
3answers
178 views

Is there an algorithm to determine the amount of work needed to keep workers busy?

I wrote a multi-threaded program that randomly generates strings, and after generating, checks to see if the string contains a certain value. Namely, StringGenerator and StringChecker. What I'm trying ...
2
votes
2answers
129 views

On-the-fly, random partition of a range of numbers [0,N] in groups of max M size

Suppose that you have a range of numbers from 0 to N that you want to randomly separate in groups of max M sequential numbers. This is easily done with a bitmap and a random number generator, but it ...
2
votes
4answers
132 views

Range of values based on key values

I'm trying to implement a method of searching trough a large amount of 2D points for those that match a certain range. I'm thinking of creating HashMaps for <X, Point> and <Y, Point> but ...
2
votes
1answer
118 views

Silverlight-based “area of influence” algorithm

I am in the process of developing a tool for a game called MechWarrior: Online which defines a map of an area of space called the Inner Sphere. Essentially, this map is a set of points (planets) on a ...
3
votes
1answer
58 views

Creating a tree of objects based on the commonness of its properties?

I have an algorithm problem. I'll simplify the issue, because most of what I'm dealing with has nothing to do with the algorithm I need. Basically, I have a list of objects that each have properties. ...
0
votes
0answers
39 views

Global relabeling heuristic: Push-relabel maxflow

I have a correct, working implementation of the preflow-push-relabel maxflow algorithm [2]. I am trying to implement the global relabeling update heuristic [3], but have run into some issues. I have ...
15
votes
2answers
1k views

Algorithm to merge two sorted arrays with minimum number of comparisons

Given are two sorted arrays a, b of type T with size n and m. I am looking for an algorithm that merges the two arrays into a new array (of maximum size n+m). If you have a cheap comparison ...
2
votes
0answers
102 views

Design an algorithm with network flow

Given a matrix A with 0 and 1 entries. Neighbours of a[i,j] are a[i-1,j], a[i+1,j], a[i,j-1] and a[i,j+1] (if exists any). Tow neigbour entries are an Improper pair if they have not equal values. if ...
2
votes
1answer
145 views

Hash function with uniqueness guarantees and controllable entropy

Is there a class of hash functions that meets the following specs: Upper and lower bound can be specified Uniqueness is guaranteed as long as the input is between the upper and lower bounds Amount ...
1
vote
0answers
98 views

Algorithm for sweeping a 2d shape along a curve?

I am trying to create a graphics application where the user can use an arbitrary shape as a "brush", which will be swept along the drawing path. The shape may be transformed along the path (rotated, ...
0
votes
1answer
167 views

Shortest path to visit all nodes [duplicate]

I am given a set of tourist attractions(nodes identified by x, y) and i need to find the shortest path to visit them. The way i thought of it, is i will ignore if there are streets available and ...
1
vote
4answers
276 views

Application qos involving priority and bandwidth

Our manager wants us to do applicaiton qos which is quite different from the well-known system qos. We have many services of three types, they have priorites, the manager wants to suspend low priority ...
2
votes
3answers
151 views

How to code a one-sided virtual economy

I'm attempting to make an online game with a mini-economy in it. The challenge is that the only person selling anything will be the website itself, and hence the supply and demand curve doesn't apply ...
0
votes
3answers
168 views

How to do “image shifting” faster?

I have a grayscale matrix (implemented as a simple array) to be shown on a display: line 1: | a | b | c | line 2: | d | e | f | a-f are grayscale values. This pattern has to be shifted by a ...
1
vote
1answer
65 views

Algorithm to find the fewest number of values (from a set of values) where the sum equals a value (+ one more condition)

The simplest way to explain this is with an example. You're given then number 19 and you have a set of numbers to choose from: 1, 2, 3, 4, 6 When choosing values from the list (which can be ...
2
votes
4answers
2k views

How do you find the first common element in two arrays

The way I did it was to loop through each at the same time and add the current value to a separate set for each of the lists. Also, check if the current element is already in the other list's set. I ...
11
votes
6answers
5k views

Can we technically un-blur images?

Since there is an algorithm to blur images, so that part of it cannot be recognised, can we reverse the algorithm and unblur part of than image? Is there a program that already does that, is that ...
18
votes
6answers
2k views

How to turn truth table into smallest possible if / else block

How can I take a truth table and turn it into a compacted if block? For instance, let's say I have this truth table where A and B are conditions and x, y and z are possible actions: A B | x y z ...
29
votes
7answers
4k views

Is there any algorithm pattern to protect any content in the web to ensure I am the first one who created it?

A few years ago there was this hacker (don't remember who he was) that full disclosed a vulnerability in a given system, but to make sure nobody took credit for that, he created some kind of PGP key. ...
0
votes
3answers
119 views

Concept for dealing with recurring appointments

Our company implemented a calendar system a few months back with recurring appointments, using iCal strings to store the recurring appointment criteria. We are starting to run into performance ...
7
votes
1answer
4k 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. ...
10
votes
8answers
1k views

Is there a subset of programs that avoid the halting problem

I was just reading another explanation of the halting problem, and it got me thinking all the problems I've seen that are given as examples involve infinite sequences. But I never use infinite ...
2
votes
0answers
47 views

Merge directed acyclic graphs minimizing number of nodes

I have some DAGs (directed acylic graphs) and I want to merge them in order to minimize the number of nodes (we could say that every node has a cost, while edges are free). These four different DAGs ...
2
votes
3answers
183 views

Count unique visitors by group of visited places

I'm facing the problem of counting the unique visitors of groups of places. Here is the situation: I have visitors that can visit places. For example, that can be internet users visiting web pages, ...
0
votes
1answer
85 views

Permutting a list of numbers in order to get a list which satisfies given condition

Here is algorithmic problem I'm trying to solve: Given a list [x_1,x_2,...,x_n] return a permutation of elements of the list [y_1,y_2,...,y_n] (where for each i we have y_i = x_j for only one j) ...
2
votes
1answer
153 views

Matching algorithms in context of data quality problems

I work for an organization that has lots of databases containing person information. The data quality is poor. One case was a surname I found like this (this is the worst-case scenario): Mark ...
-1
votes
1answer
130 views

Finding all subsets of a set running time

Given a set {1,2,3} output { {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} } I have only been able to find as fast as O(2^n), is there any techniques for achieving faster results (besides ...
0
votes
2answers
95 views

Porting an algorithm implementation licensed under GNU GPL v3

I'm working on a JavaScript port of a red-black tree implementation in Java from the book Algorithms 4th Edition, by Sedgewick and Wayne. I believe that my JavaScript port qualifies as a derivative ...
7
votes
5answers
9k views

How to handle large numbers?

Well, I've just started doing puzzles and it's so annoying to see puzzles which are easy to do but also need to handle very large numbers. That's the problem. Say I have to deal with numbers like 10 ...
0
votes
2answers
93 views

Track a series of choices with a single number

I want to track a series of scored questions in a single number (the total score). Is that possible? and how? For example, I have 30 questions with either 3 or 2 choices. For any given question, the ...
0
votes
0answers
73 views

Test if a point is inside or outside a 3D polygon

I'm wondering if there is an algorithm (or a code written in FORTRAN) that gives whether a 3D point is inside or outside a polygon having triangles as faces (an .stl file from gmsh for example). Most ...
2
votes
1answer
139 views

moving around virtual keyboard

I'm creating virtual keyboard using javascript/html/css. And I can't find a good algorithm for moving from one button to another in different directions (top-bottom, left-right). Lets say I ...
7
votes
3answers
933 views

What is the Bible of Hashing?

Is there a Cormen-like reference on Hashes and Hashing? This particular structure has seen little attention in my CS education for some reason but I'd like to learn more as they seem to be everywhere. ...