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,999
questions
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 ...
- 374
10
votes
3
answers
6k
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 ...
- 283
43
votes
3
answers
19k
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....
- 1,470
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 ...
- 467
1
vote
1
answer
768
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 ...
- 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 ...
- 1,391
5
votes
1
answer
525
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: ...
- 53
9
votes
1
answer
560
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$, ...
- 191
29
votes
10
answers
21k
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 ...
- 1,721
5
votes
2
answers
569
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.
20
votes
2
answers
876
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 ...
- 435
10
votes
1
answer
449
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 $...
- 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 ...
- 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
...
- 71.6k
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 ...
- 1,460
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, ...
- 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{ ...
- 71.6k
51
votes
12
answers
39k
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 ...
- 4,047
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 ...
- 621
66
votes
3
answers
15k
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
$$...
- 6,191
42
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:
...
- 1,296
84
votes
8
answers
59k
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 ...
- 965
10
votes
2
answers
2k
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.
...
- 3,028
38
votes
2
answers
27k
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 ...
- 8,986
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. ...
- 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,...
- 12.7k
13
votes
2
answers
880
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 ...
- 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 ...
- 303
55
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 ...
- 20.5k
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 ...
- 71.6k
28
votes
4
answers
41k
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 ...
- 2,163
40
votes
5
answers
119k
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 ...
- 523
20
votes
5
answers
609
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.) $...
- 71.6k
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 ...
18
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 ...
- 2,163
23
votes
1
answer
2k
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 ...
- 3,857
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 ...
- 4,792
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) ...
- 435
24
votes
2
answers
337
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?
user20
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 ...
- 263
100
votes
3
answers
34k
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 ...
- 1,313
11
votes
4
answers
26k
views
Evaluating the average time complexity of a given bubblesort algorithm.
Considering this pseudo-code of a bubblesort:
...
- 561
30
votes
7
answers
14k
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:
<...
- 1,307
376
votes
12
answers
342k
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)$ ...
- 5,415
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 ...
- 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 ...
- 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 ...
user1094566
38
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 ...
- 783
24
votes
1
answer
1k
views
Compression of domain names
I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
- 349