Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

9
votes
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 ...
8
votes
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 ...
10
votes
3answers
599 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\...
14
votes
1answer
346 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 ...
11
votes
4answers
1k 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 ...
11
votes
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 ...
9
votes
3answers
4k 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 ...
35
votes
3answers
13k 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....
12
votes
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 ...
1
vote
1answer
643 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 ...
59
votes
8answers
4k 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 ...
5
votes
1answer
452 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: ...
9
votes
1answer
501 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$, ...
22
votes
9answers
13k 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 ...
5
votes
2answers
546 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.
18
votes
2answers
722 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 ...
10
votes
1answer
374 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 $...
11
votes
3answers
1k 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 ...
25
votes
1answer
7k 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 ...
6
votes
1answer
104 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 ...
26
votes
1answer
9k 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, ...
27
votes
4answers
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{ ...
49
votes
12answers
33k 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
votes
2answers
3k 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 ...
58
votes
2answers
9k 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 $$...
31
votes
1answer
7k 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: ...
76
votes
8answers
51k 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 ...
10
votes
2answers
886 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. ...
26
votes
1answer
15k 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 ...
28
votes
4answers
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. ...
13
votes
1answer
1k 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,...
13
votes
2answers
578 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 ...
19
votes
1answer
2k 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 ...
50
votes
4answers
4k 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 ...
18
votes
5answers
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 ...
26
votes
4answers
24k 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 ...
36
votes
5answers
89k 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 ...
19
votes
5answers
443 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.) $...
17
votes
2answers
3k 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 ...
16
votes
4answers
620 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 ...
22
votes
1answer
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 ...
31
votes
2answers
2k 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 ...
10
votes
3answers
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) ...
22
votes
2answers
287 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?
13
votes
1answer
4k 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 ...
87
votes
3answers
20k 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 ...
11
votes
4answers
20k views

Evaluating the average time complexity of a given bubblesort algorithm.

Considering this pseudo-code of a bubblesort: ...
24
votes
6answers
7k 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: <...
284
votes
11answers
268k 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)$ ...
16
votes
1answer
111 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 ...