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.

Filter by
Sorted by
Tagged with
14 votes
1 answer
394 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 ...
user avatar
  • 22k
11 votes
4 answers
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 ...
user avatar
  • 421
12 votes
3 answers
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 ...
user avatar
  • 375
9 votes
3 answers
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 ...
user avatar
41 votes
3 answers
18k 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....
user avatar
12 votes
1 answer
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 ...
user avatar
  • 467
1 vote
1 answer
751 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 ...
user avatar
  • 119
61 votes
8 answers
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 ...
user avatar
  • 1,381
5 votes
1 answer
516 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: ...
user avatar
  • 53
9 votes
1 answer
557 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$, ...
user avatar
  • 191
29 votes
9 answers
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 ...
user avatar
5 votes
2 answers
566 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.
user avatar
20 votes
2 answers
856 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 ...
user avatar
10 votes
1 answer
423 views

Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?

Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$. Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $...
user avatar
  • 203
11 votes
3 answers
2k views

How Do Common Pathfinding Algorithms Compare To Human Process

This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different ...
user avatar
  • 303
31 votes
1 answer
10k views

Which combinations of pre-, post- and in-order sequentialisation are unique?

We know post-order, post L(x) => [x] post N(x,l,r) => (post l) ++ (post r) ++ [x] and pre-order ...
user avatar
  • 70.8k
6 votes
1 answer
109 views

An indexing function for graphs

Definition from wikipedia: A graph is an ordered pair $G = (V, E)$ comprising a set $V$ of nodes together with a set $E$ of edges, which are two-element subsets of $V$. The set of all finite ...
user avatar
30 votes
1 answer
12k views

How hard is counting the number of simple paths between two nodes in a directed graph?

There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search). However it seems that, ...
user avatar
  • 1,370
28 votes
4 answers
2k views

How to find a superstar in linear time?

Consider directed graphs. We call a node $v$ superstar if and only if no other node can be reached from it, but all other nodes have an edge to $v$. Formally: $\qquad \displaystyle $v$ \text{ ...
user avatar
  • 70.8k
51 votes
12 answers
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 ...
user avatar
  • 4,017
4 votes
2 answers
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 ...
user avatar
  • 621
65 votes
3 answers
14k views

In-place algorithm for interleaving an array

You are given an array of $2n$ elements $$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$ The task is to interleave the array, using an in-place algorithm such that the resulting array looks like $$...
user avatar
  • 6,131
40 votes
1 answer
10k views

Do you get DFS if you change the queue to a stack in a BFS implementation?

Here is the standard pseudocode for breadth first search: ...
user avatar
  • 1,276
83 votes
8 answers
58k views

Graph searching: Breadth-first vs. depth-first

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are ...
user avatar
  • 955
10 votes
2 answers
1k views

How is the loop invariant obtained in this square root bound finding algorithm?

Originally on math.SE but unanswered there. Consider the following algorithm. ...
user avatar
  • 2,998
38 votes
2 answers
26k views

Hash tables versus binary trees

When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL ...
user avatar
29 votes
4 answers
5k views

How to determine likely connections in a social network?

I am curious in determining an approach to tackling a "suggested friends" algorithm. Facebook has a feature in which it will recommended individuals to you which it thinks you may be acquainted with. ...
user avatar
  • 621
13 votes
1 answer
2k views

Analyzing a modified version of the card-game "War"

A simple game usually played by children, the game of War is played by two people using a standard deck of 52 playing cards. Initially, the deck is shuffled and all cards are dealt two the two players,...
user avatar
  • 12.6k
13 votes
2 answers
836 views

Identifying events related to dates in a paragraph

Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph? Example, consider the following paragraph: In June 1970, the ...
user avatar
  • 530
20 votes
1 answer
3k views

Implementing the GSAT algorithm - How to select which literal to flip?

The GSAT algorithm is, for the most part, straight forward: You get a formula in conjunctive normal form and flip the literals of the clauses until you find a solution that satisfies the formula or ...
user avatar
  • 303
54 votes
4 answers
8k views

Why polynomial time is called "efficient"?

Why in computer science any complexity which is at most polynomial is considered efficient? For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms ...
user avatar
  • 20.3k
20 votes
5 answers
2k views

A Case Distinction on Dynamic Programming: Example Needed!

I have been working on dynamic programming for some time. The canonical way to evaluate a dynamic programming recursion is by creating a table of all necessary values and filling it row by row. See ...
user avatar
  • 70.8k
28 votes
4 answers
38k views

The time complexity of finding the diameter of a graph

What is the time complexity of finding the diameter of a graph $G=(V,E)$? ${O}(|V|^2)$ ${O}(|V|^2+|V| \cdot |E|)$ ${O}(|V|^2\cdot |E|)$ ${O}(|V|\cdot |E|^2)$ The diameter of a ...
user avatar
  • 2,133
39 votes
5 answers
118k views

How to come up with the runtime of algorithms? [duplicate]

I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site. I've seen in many sites and books, the big-O notations like $O(n)$ which tell the ...
user avatar
  • 513
20 votes
5 answers
588 views

Efficient compression of unlabeled trees

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $...
user avatar
  • 70.8k
20 votes
2 answers
4k views

Type-checking algorithms

I am starting a personal bibliographic research on type-checking algorithms and want some tips. What are the most commonly used type-checking algorithms, strategies and general techniques? I am ...
user avatar
17 votes
4 answers
1k views

Is this finite graph problem decidable? What factors make a problem decidable?

I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is ...
user avatar
  • 2,133
23 votes
1 answer
1k views

How fundamental are matroids and greedoids in algorithm design?

Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy ...
user avatar
34 votes
2 answers
3k views

Are there improvements on Dana Angluin's algorithm for learning regular sets

In her 1987 seminal paper Dana Angluin presents a polynomial time algorithm for learning a DFA from membership queries and theory queries (counterexamples to a proposed DFA). She shows that if you are ...
user avatar
10 votes
3 answers
4k views

Algorithm to test whether a binary tree is a search tree and count complete branches

I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) ...
user avatar
24 votes
2 answers
330 views

Is Smoothed Analysis used outside academia?

Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?
user avatar
13 votes
2 answers
5k views

Random Sudoku generator

I want to generate a completely random Sudoku. Define a Sudoku grid as a $9\times9$ grid of integers between $1$ and $9$ where some elements can be omitted. A grid is a valid puzzle if there is a ...
user avatar
  • 263
97 votes
3 answers
32k views

How does one know which notation of time complexity analysis to use?

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
user avatar
  • 1,273
11 votes
4 answers
26k views

Evaluating the average time complexity of a given bubblesort algorithm.

Considering this pseudo-code of a bubblesort: ...
user avatar
  • 561
30 votes
7 answers
13k views

Generating Combinations from a set of pairs without repetition of elements

I have a set of pairs. Each pair is of the form (x,y) such that x,y belong to integers from the range [0,n). So, if the n is 4, then I have the following pairs: <...
user avatar
  • 1,287
368 votes
12 answers
338k views

Why is quicksort better than other sorting algorithms in practice?

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...
user avatar
  • 5,295
16 votes
1 answer
137 views

Methods to evaluate a system of written rules

I was trying to come up with a system that would evaluate bylaws for an organization as to determine their underlying logic. I think a first-order predicate system would work for representing the ...
user avatar
  • 561
8 votes
1 answer
142 views

Find all the special graphs which can reduced to the shortest paths graph

I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative ...
user avatar
  • 237
8 votes
1 answer
3k views

Subset sum, pseudo-polynomial time dynamic programming solution?

I found the P vs NP problem some time ago and I have recently worked on the subset sum problem. I have read Wikipedia article on the Subset Sum problem as well as the question Subset Sum Algorithm I ...
user avatar
36 votes
2 answers
14k views

Is there a difference between top-down and bottom-up dynamic programming?

Is there a fundamental difference between top-down and bottom-up dynamic programming? In particular, is there a problem which can be solved bottom-up but not top-down? Or is the bottom-up approach ...
user avatar