Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

1
vote
1answer
33 views

Algorithm to check the distance between integers

I have the next problem, and I was wondering whether it exists a way to solve it without having to iterate around all the array in the worst case. I have a sorted array of pairwise distinct integers, ...
3
votes
0answers
27 views

Partitioning planar graphs without minimizing edge cuts

I am looking for an algorithm that, given an undirected, planar graph $G = (V,E)$ with node weights, meets the following conditions: Creates balanced (within some margin) $k$ partitions of $V$ ...
5
votes
1answer
202 views

Least number of comparisons needed to sort (order) 5 elements

Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons. Solution: There are 5! = 120 possible ...
2
votes
1answer
47 views

Fastest nth root algorithm to a lot of digits?

What is that fastest algorithm that can calculate a lot of digits of a decimal root? For example: 10,000 digits of the 3.56th root of 60.1?
6
votes
2answers
188 views

n log n = c. What are some good approximations of this?

I am currently looking into Big O notation and computational complexity. Problem 1.1 in CLRS asks what seems a basic question, which is to get an intuition about how different algorithmic ...
4
votes
1answer
64 views

What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

I was wondering as what are the specific conditions which make the A* algorithm - optimal in terms of the node expansion over the other Unidirectional algorithms: When the same heuristic ...
5
votes
1answer
36 views

Why is pure literal elimination absent in DPLL-based algorithms like Chaff?

I'm looking into various SAT-solvers and trying to understand how they work and why they are designed in certain ways. (But I'm not in a university at the moment and I do not know anyone who is a ...
1
vote
0answers
37 views

How is the problem of sorting in contiguous runs called?

I am having a bit of brain fail and I can't remeber the name of the following problem (so I can find some literature around it...). Given a sequence of values, sort it in a way that equal elements ...
2
votes
1answer
36 views

Maximum bipartite matching when some nodes must be matched

Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched. ...
6
votes
1answer
45 views

Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?

There's a way to perform fuzzy parsing (accepts strings even with typos to a certain edit distance), with a DFA and a run-time constructed Levenshtein Automata of the input word. Can something ...
3
votes
1answer
205 views

Is there a more efficient algorithm than backtracking/dynamic programming?

Consider the following game: One day a castle is attacked at sunrise (by surprise) by n soldiers. Each soldier carries a canon and a rifle. The castle has strength s. On the first day each ...
2
votes
1answer
22 views

What are algorithms for computing contours from given edges?

Let's say I have a set of edges which makes the contour, however there are too many of them and some are too long. I have to remove edges, and shorten them to make contour. I cannot add new edges! I ...
0
votes
0answers
28 views

How to make quick sort recursive? [migrated]

Currently I am trying to make a recursive quick sort. There are many different methods for quick sort but for my method, I have to take the first element of the array and always use the first element ...
-1
votes
1answer
26 views

Find variance within one pass

Given a list of real numbers. Is it possible to find the variance with no more than 1 iteration with constant space complexity? My intuition is that it is not possible. But how do I prove it ...
10
votes
2answers
140 views

When is the concatenation of two regular languages unambiguous?

Given languages $A$ and $B$, let's say that their concatenation $AB$ is unambiguous if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and ambiguous ...
-1
votes
0answers
18 views

What is a 4-way parallel algorithm? [closed]

What is the definition of a 4-way (or 8-way) parallel algorithm? What means 4-way? How can we implement such an algorithm?
0
votes
0answers
31 views

Sort graph nodes by density [closed]

Cyclic connected undirected graph. Every node in a graph has T value initially zero. Suppose there is a traverse via shortest path between every two nodes which increases every node's T value it ...
3
votes
0answers
46 views

What is the correct way to determine the width and depth of a count-min sketch?

The width (number of registers) and depth (number of hash functions) of a Count-Min sketch determine the accuracy of counts retrieved. I've found two different methods for calculating the width ($w$) ...
3
votes
1answer
41 views

Devising an Algorithm for Linear Combination with Column Restrictions

Application: We intend to factor an integer $N$ using a variation of the rational sieve. This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ ...
-1
votes
1answer
18 views

What PR stands for in Adaptive image region-growing algorithm?

I am reading the article a kind of old article entitled "Adaptive image region-growing" by Chang Y Li X, published in IEEE transactions on image processing DOI:10.1109/83.336259. Well, the problem is ...
4
votes
2answers
164 views

Good mathematical book on algorithms [closed]

I’m a sucker for mathematical elegance and rigour, and now am looking for such literature on algorithms and algorithm analysis. Now, it doesn’t matter much to me what algorithms are covered, but very ...
0
votes
0answers
40 views

Subgraph isomorphism by Ullman

I was trying to understand the subgraph isomorphism problem and I came across a slide http://oldwww.prip.tuwien.ac.at/teaching/ss/strupr/vogl.pdf In the 11'th page, the step by step description of M ...
6
votes
0answers
47 views

Edit distance of list with unique elements

Edit distance (Levenshtein-Distance) between lists is a well studied CS-problem, but I can't find much on possible improvements if it is known that an element does not occur more than once in each ...
1
vote
1answer
108 views

Dynamic Programming Travel Planning Problem

You want to visit n cities: $0 → 1 → 2 → · · · → n$. For traveling between city $i$ and $i + 1$ $(0 ≤ i < n) $ you need to choose between two modes of transportation: train or plane. You are ...
1
vote
1answer
100 views

What is the best complexity of finding a minimum in a matrix?

Given a matrix $\mathsf{a}$ of size $K\times N$, what is the best complexity of finding the minimum value? Here is a pseudo code: ...
1
vote
0answers
43 views

Who first invented and analysed algorithm of finding median in a stream of integers using two heaps?

There is popular problem: Given that integers are read from a data stream, find the median of elements read so far in an efficient way. One of possible solutions: Use max-heap for left heap ...
0
votes
1answer
58 views

Pairs distance to ordering?

Thanks to anon for contributing this wording: Every permutation $\pi:\{1,\cdots,n\}\to\{1,\cdots,n\}$ induces an $n\times n$ array $A(\pi)$ of the absolute differences, whose $ij$ entry is ...
4
votes
5answers
104 views

Please explain a greedy algorithm in a naive manner [closed]

I am a beginner in the topic of algorithms. I have a query about Greedy Algorithms. From what I understand, if there is a function and we are supposed to find its maxima/minima, if we find the local ...
3
votes
1answer
35 views

How can an approximation ratio be less than 1?

A question in my algorithms text-book requires that we, Describe an efficient $(1 - \frac{1}{k})$ -approximation algorithm for this problem. It is my understanding that $(1 - \frac{1}{k})$ ...
0
votes
1answer
44 views

Merge two series of sorted number, one much longer than the other

This is the problem: Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$ comparisons. I have come up ...
0
votes
1answer
54 views

How to sort fractions (small numbers) [closed]

We have 100,000 fractions: $\frac{p}{2^q}$ such that $0 \leq p,q \leq 10$. Task is about finding a fast algorithm to sort fractions. I ask you to look at my proposition and tell me your ideas. ...
1
vote
3answers
60 views

minimum subset of dominating 2D points

From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ? $M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) ...
5
votes
1answer
129 views

Combining two infinite algorithms to create a single infinite algortihm

Suppose I have an algorithm $F$ that, given a numeric input $x$, generates an infinite sequence of numbers that converges to a $f(x)$, where $f$ is some continuous real-valued function. Similarly, I ...
0
votes
1answer
31 views

pseudo clique with at least connectivity x and maximum weight of the nodes

Let $G=(N,E)$ be a undirected graph of nodes $N$ and edges $E$. Each node $n \in N$ has a weight $w(n)$. The weight of a graph is defined as the sum of the weights of its nodes, i.e., by $w(G) = ...
2
votes
0answers
36 views

Memory testing algorithms? [closed]

What am I doing? I have been digging more and more and googling more than often finding very small amount of results I am trying to make a RAM testing program that can do memory testing with the ...
1
vote
1answer
56 views

Analysing Space Complexity

I have to compute the space complexity of this function: ...
2
votes
1answer
38 views

Proving algorithm for removing nodes from a complete graph with two kinds of edges

Lets say $G$ is complete undirected graph with a set of edges coloured either black or red. The problem is to find an algorithm answering if it is possible to remove a subset of nodes from $G$ in a ...
2
votes
1answer
65 views

Encircling randomly distributed points

I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly p points. We also (randomly) place c circle centres. I'm trying to find an algorithm that will allow ...
2
votes
1answer
37 views

In the Gas-Up problem, how is the amount of gas the same up to a cyclic shift regardless of starting city?

I'm working through Elements of Programming Interviews as practice for finding a job. I've spent a ridiculous amount of time on Problem 18.7. In the gas-up problem, $n$ cities are arranged on a ...
1
vote
1answer
69 views

Getting the sorted sequence from a level-wise sorted min-heap

A heap sorted by levels is a heap which: Every parent is smaller than its children. The nodes in each level are sorted from the smallest to the greatest. I need to describe an algorithm with ...
1
vote
0answers
39 views

Possible paths in pipe network, without loops and with some one-way valves

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit I have to ...
0
votes
1answer
47 views

Karloff's algorithm applied to sparse graphs

I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c >0$. $G$ is called a $c$-dense graph. Karloff [1, p.6] has given a map-reduce algorithm called ...
10
votes
0answers
134 views

Is there no sorting algorithm with all specific desired properties?

On the Sorting Algorithms website, the following claim is made: The ideal sorting algorithm would have the following properties: Stable: Equal keys aren't reordered. Operates in place, ...
-1
votes
1answer
69 views

Computing the number of squares which are intersected by a line internally

There's a line from (x1,y1) to (x2,y2) in a grid of squares of unit length. Write a program to compute the number of squares which are intersected by the line internally, i.e squares which are only ...
1
vote
0answers
23 views

Algorithms for operating on tape storage [closed]

Old algorithm textbooks often covered algorithms that did well on tape drives, since tape drives used to be a common storage type on almost all computers. Since memory on modern CPUs with data ...
1
vote
0answers
20 views

Boundary tracing of simple closed curves? [closed]

I have some heavy calculations that essentially takes a point in the plane as input and gives an integer as output. Points in the same region gives the same integer (think about the regions as pieces ...
1
vote
1answer
27 views

Complexity of finding these original parameters

I am given (or rather, generate randomly) three positive integers $a, b, c$. I want to know if there exist integers $m \ge 2, s \ge 1$ such that $ms+m = a, ms+1 = b, 2s+1 = c$. If there are multiple ...
1
vote
0answers
39 views

Non-Uniform Random Number Generation, from Uniform Random Number Generater [closed]

The project I am currently working on (in C#) requires generating random integer between 0 and Int64.MaxValue. I have access to a Uniform RNG, which for pseudo-code purposes in the question, I will ...
6
votes
1answer
34 views

Does the Rabin-Karp really need me to care about applying a mod Q operation on the rolling hashes?

I have been reading about the Rabin Karp algorithm and I kept wondering what's the big deal with keeping our rolling hashes values bounded by a value Q? I'd thought that as our integer number ...
1
vote
1answer
43 views

Divide and Conquer 3D Convex Hull [closed]

http://cs.jhu.edu/~misha/Spring14/Preparata77.pdf This is a divide and conquer algorithm for computing the convex hull in 3 dimensions. I am having trouble understanding the merge step, which is ...