# Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

10,130 questions
Filter by
Sorted by
Tagged with
2answers
283 views

### Ordering elements so that some elements don't come between others

Given an integer $n$ and set of triplets of distinct integers $$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$ find an algorithm which either finds a permutation $\pi$...
1answer
226 views

### Efficiently selecting the median and elements to its left and right

Suppose we have a set $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ of $N$ coders. Each Coders has rating $R_i$ and the number of gold medals $E_i$, they had won so far. A Software Company wants to hire ...
1answer
5k views

### Why does the splay tree rotation algorithm take into account both the parent and grandparent node?

I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why ...
3answers
2k views

### The space complexity of recognising Watson-Crick palindromes

I have the following algorithmic problem: Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes. Watson-Crick palindromes are strings whose reversed ...
2answers
2k views

### How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible?

I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the ...
4answers
3k views

### Loop invariant for an algorithm

I have developed the following pseudocode for the sum of pairs problem: Given an array $A$ of integers and an integer $b$, return YES if there are positions $i,j$ in $A$ with $A[i] + A[j] = b$, NO ...
4answers
374 views

### Introductory books on nature sciences behind bioinformatics

My question goes to those who are concerned with computational biology algorithmics. I'm going to take a course on bioinformatics this fall; the problem, however, is that I have too little background ...
2answers
6k views

### Where to get graphs to test my search algorithms against?

I am implementing a set of path finding algorithms such as Dijkstra's, Depth First, etc. At first I used a couple of self made graphs, but now I'd like to take the challenge a bit further and thus I'...
3answers
16k views

### dynamic programming exercise on cutting strings

I have been working on the following problem from this book. A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves ...
2answers
8k views

### Complexity of computing matrix powers

I am interested in calculating the $n$'th power of a $n\times n$ matrix $A$. Suppose we have an algorithm for matrix multiplication which runs in $\mathcal{O}(M(n))$ time. Then, one can easily ...
2answers
8k views

### How does the NegaScout algorithm work?

On Alpha-Beta pruning, NegaScout claims that it can accelerate the process by setting [Alpha,Beta] to [Alpha,Alpha-1]. I do not understand the whole process of NegaScout. How does it work? What is ...
2answers
4k views

### How to construct the found path in bidirectional search

I am trying to implement bidirectional search in a graph. I am using two breadth first searches from the start node and the goal node. The states that have been checked are stored in two hash tables (...
1answer
1k views

### How to implement the details of shotgun hill climbing to make it effective?

I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a shotgun (or random-restart) hill climbing algorithmic idea seems ...
5answers
9k views

### How to approach Vertical Sticks challenge

This problem is taken from interviewstreet.com We are given an array of integers $Y=\{y_1,...,y_n\}$ that represents $n$ line segments such that endpoints of segment $i$ are $(i, 0)$ and $(i, y_i)$. ...
3answers
2k views

### Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time?

I want to prove or disprove the existence of an algorithm which, given an array $A$ of integers, finds three indices $i, j$ and $k$ such that $i < j < k$ and $A[i] < A[j] < A[k]$ (or finds ...
1answer
1k views

### How many shortest distances change when adding an edge to a graph?

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in ...
1answer
903 views

### Supporting data structures for SAT local search

WalkSAT and GSAT are well-known and simple local search algorithms for solving the Boolean satisfiability problem. The pseudocode for the GSAT algorithm is copied from the question Implementing the ...
2answers
7k views

### How to implement AO* algorithm?

I have noticed that different data structures are used when we implement search algorithms. For example, we use queues to implement breadth first search, stacks to implement depth-first search and min-...
2answers
12k views

### Branch and Bound explanation

I have a test about the branch and bound algorithm. I understand theoretically how this algorithm works but I couldn't find examples that illustrates how this algorithm can be implemented practically. ...
1answer
4k views

### Most efficient know way to match orders

Consider two 2D-Array $B_{ij}$ (the buy array) and $S_{ij}$ (the sell array) where each $i^{th}$ element is associated with an array of floating-point values and each of the floating point value, in ...
1answer
960 views

### Optimal algorithm for finding the girth of a sparse graph?

I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity. I thought about some modification on Tarjan's algorithm for ...
1answer
2k views

### distributed alpha beta pruning

I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see ...
1answer
457 views

### About Codd's reduction algorithm

Codd's Algorithm converts an expression in tuple relational calculus to Relational Algebra. Is there a standard implementation of the algorithm? Is this algorithm used anywhere? (It seems that the ...
1answer
169 views

### In Constraint Programming, are there any models that take into account the number of variable changes?

Consider a CSP model where changing the value of a particular variable is expensive. Is there any work where the objective function also considers the number of changes in the value of the variable ...
5answers
61k views

### Adding elements to a sorted array

What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)? I was thinking something along the following lines. I could add to the end of an array ...
6answers
4k views

### Examples of sophisticated recursive algorithms

I was explaining the famous deterministic linear-time selection algorithm (median of medians algorithm) to a friend. The recursion in this algorithm (while being very simple) is quite sophisticated. ...
1answer
1k views

### Solving Recurrences via Characteristic Polynomial with Imaginary Roots

In algorithm analysis you often have to solve recurrences. In addition to Master Theorem, substitution and iteration methods, there is one using characteristic polynomials. Say I have concluded that ...
4answers
1k views

### How To Best Learn About Algorithms In Depth

I have been reading this site with a great deal of interest, but I find a lot of it goes over my head. This has made me wish to learn a lot more about algorithms and CS in general. As far as I can ...
3answers
741 views

### Error in the use of asymptotic notation

I'm trying to understand what is wrong with the following proof of the following recurrence $$T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n$$  T(n) \leq 2\left(c\left\...
1answer
382 views

### Research on evaluating the performance of cache-obliviousness in practice

Cache-oblivious algorithms and data structures are a rather new thing, introduced by Frigo et al. in Cache-oblivious algorithms, 1999. Prokop's thesis from the same year introduces the early ideas as ...
4answers
2k views

### Finding exact corner solutions to linear programming using interior point methods

The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior ...
3answers
1k views

### How to convert an NFA with overlapping cycles into a regular expression?

If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as ...
3answers
5k views

### Logarithmic vs double logarithmic time complexity

In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ? This is the case when one use for instance van Emde Boas ...
3answers
17k views

### Deciding on Sub-Problems for Dynamic Programming

I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer....
1answer
1k views

### Find shortest paths in a weighed unipathic graph

A directed graph is said to be unipathic if for any two vertices $u$ and $v$ in the graph $G=(V,E)$, there is at most one simple path from $u$ to $v$. Suppose I am given a unipathic graph $G$ such ...
1answer
743 views

### Improve worst case time of depth first search on Euler graphs

How to improve the worst case scenario for a depth first search on an Euler graph, starting at some point and ending at that same point? I need to do the whole search but it is not fast enough for ...
8answers
5k views

### Algorithmic intuition for logarithmic complexity

I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$. In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
1answer
511 views

### What is the complexity of these tree-based algorithms?

Suppose we have a balanced binary tree, which represents a recursive partitioning of a set of $N$ points into nested subsets. Each node of the tree represents a subset, with the following properties: ...
1answer
555 views

### Expressing an arbitrary permutation as a sequence of (insert, move, delete) operations

Suppose I have two strings. Call them $A$ and $B$. Neither string has any repeated characters. How can I find the shortest sequence of insert, move, and delete operation that turns $A$ into $B$, ...
9answers
20k views

### Generating uniformly distributed random numbers using a coin

You have one coin. You may flip it as many times as you want. You want to generate a random number $r$ such that $a \leq r < b$ where $r,a,b\in \mathbb{Z}^+$. Distribution of the numbers should ...
2answers
564 views

### BigO, Running Time, Invariants - Learning Resources

What are some good online resources that will help me better understand BigO notation, running time & invariants? I'm looking for lectures, interactive examples if possible.
2answers
835 views

### Creating a Self Ordering Binary Tree

I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the ...
1answer
411 views

12answers
38k views

### How to verify number with Bob without Eve knowing?

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob ...
2answers
5k views

### What is the height of an empty BST when using it in context for balancing?

Suppose the datatype for a BST is defined as follows (in SML) datatype 'a bst_Tree = Empty | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree; So there are two ...