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
16
votes
2answers
28k views

How does an admissible heuristic ensure an optimal solution?

When using A* (or any other best path finding algorithm), we say that the heuristic used should be admissible, that is, it should never overestimate the actual solution path's length (or moves). How ...
14
votes
3answers
3k views

An efficient data structure supporting Insert, Delete, and MostFrequent

Assume that we have a set $D$ and each member of $D$ is a data and key pair. We want a data structure that would support the following operations: Insert $(d,k)$ into $D$, Delete member $e$, (no need ...
13
votes
2answers
1k views

What is a lay explanation for universal search?

I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply ...
13
votes
4answers
8k views

Transitive reduction of DAG

I am looking for O(V+E) algorithm for finding the transitive reduction given a DAG. That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still ...
11
votes
1answer
6k views

Generate scale-free networks with power-law degree distributions using Barabasi-Albert

I'm trying to reproduce the synthetic networks (graphs) described in some papers. It is stated that the Barabasi-Albert model was used to create "scale-free networks with power-law degree ...
9
votes
2answers
29k views

Dijkstra algorithm vs breadth first search for shortest path in graph

I have asked this question in StackOverflow. I was asked to move in here. so here it is: I need some clarifications and inputs regarding Dijkstra's algorithm vs breadth first search in directed ...
7
votes
2answers
4k views

What is the no free lunch theorem?

I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser ...
5
votes
2answers
4k views

Selection, crossover and mutation function choice in genetic algorithms

I have been developing a GA for one of the projects I'm working on. I have everything implemented with no problems and I really like how GAs work in general, it's a really cool and relatively new ...
4
votes
1answer
6k views

Shortest path with exactly $k$ edges

From Skiena's book The Algorithm Design Manual, chapter 6, problem 22: Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ ...
47
votes
2answers
7k views

Order of growth definition from Reynolds & Tymann

I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines). The second chapter introduces algorithms with an example of a ...
23
votes
3answers
21k views

Why is Radix Sort $O(n)$?

In radix sort we first sort by least significant digit then we sort by second least significant digit and so on and end up with sorted list. Now if we have list of $n$ numbers we need $\log n$ bits ...
20
votes
3answers
1k views

How to formulate a computational problem rigorously?

I often interact with people who want to ask for an algorithm for a computational problem (or its complexity), but they don't express it in a rigorous way for us (computer scientists) to understand. ...
19
votes
3answers
416 views

How many cookies in the cookie box? — Tiling stars

With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit ...
17
votes
1answer
1k views

Find a polynomial in two or three queries

Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point. Input: A black box of monic polynomial $f(x) \in\mathbb{Z}^+[x]$ of degree $d$. Output: The $d$ coefficients of polynomial ...
15
votes
3answers
13k views

Computing the longest common substring of two strings using suffix arrays

After I learned how to build a suffix array in $O(N)$ complexity, I am interested in discovering the applications of the suffix arrays. One of these is finding the longest common substring between two ...
14
votes
2answers
11k views

Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree

There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover). For each ...
11
votes
3answers
2k views

Is there any proof that quantum computers are more efficient than classical computers?

Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also ...
10
votes
2answers
250 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$...
7
votes
2answers
140 views

Computability of equality to zero for a simple language

Suppose we have a tree in which leaves are labeled with a set of numbers $L$, and internal nodes with a set of operations $O$. In particular $L$ can be $\mathbb{N}, \mathbb{Z}$ or $\mathbb{Q}$, and ...
7
votes
1answer
5k views

Complete examples of program correctness proofs

Does anyone have any complete example of a proof of program correctness? I'm talking about something that includes the usual predicate, base case, inductive hypothesis, and inductive step. But also ...
5
votes
1answer
26k views

How can I prove algorithm correctness? [closed]

How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the ...
5
votes
1answer
3k views

Why does Kadane's algorithm solve the maximum sub-array problem?

I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms". it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A[i], ...
22
votes
4answers
951 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, ...
21
votes
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 ...
17
votes
4answers
1k views

Finding a pair of non-overlapping bit vectors

I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists. For example, if I give you ...
14
votes
1answer
11k views

Expected number of swaps in bubble sort

Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that ...
14
votes
1answer
2k views

Counting inversion pairs

A classic application of divide and conquer is to solve the following problem: Given an array $a[1\dots n]$ of distinct, comparable elements, count the number of inversion pairs in the array: pairs $(...
14
votes
4answers
10k views

Computing set difference between two large sets

I have two large sets of integers $A$ and $B$. Each set has about a million entries, and each entry is a positive integer that is at most 10 digits long. What is the best algorithm to compute $A\...
13
votes
2answers
1k views

Quantum Supremacy Task

I’m trying to understand the task performed by Google’s Sycamore that recently achieved alleged Quantum Supremacy. I’ve read the paper in Nature but the actual task that would have taken 10,000 years ...
12
votes
3answers
8k views

Finding the element that occurs the most in a very large file

I've heard this interview question asked a lot and I was hoping to get some opinions on what good answers might be: You have a large file 10+ GB and you want to find out which element occurs the most, ...
11
votes
4answers
316 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 ...
11
votes
1answer
4k views

Directed union-find

Consider a directed graph $G$ on which one can dynamically add edges and make some specific queries. Example: disjoint-set forest Consider the following set of queries: ...
11
votes
4answers
23k views

Evaluating the average time complexity of a given bubblesort algorithm.

Considering this pseudo-code of a bubblesort: ...
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 ...
9
votes
2answers
250 views

Peer grading design - choosing a graph, to get accurate rankings/ratings

Background. I am writing some code for semi-automated grading, using peer grading as part of the grading process. Students are given pairs of essays at a time, and the students have a slider to choose ...
7
votes
10answers
51k views

Computer Program vs. Algorithm

It's said that a program include algorithms, however if we refer to their definition, an algorithm is a sequence of instructions written to perform a specified task and a computer program is also a ...
6
votes
1answer
4k views

What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a "...
6
votes
2answers
4k views

Understanding DPLL algorithm

I'm trying to understand DPLL algorithm for solving SAT problem. And here it is: ...
6
votes
4answers
34k views

How to check whether a graph is connected in polynomial time?

I have to solve the following problem: Consider the problem Connected: Input: An unweighted, undirected graph $G$. Output: True if and only if $G$ is connected. Show that Connected ...
5
votes
2answers
2k views

How does one formulate a backtracking algorithm

I am new to learning algorithms. I was reading backtracking algorithm for generating all strings for n bits. If I dry run the program I know the program is giving right result. But I didn't understood ...
4
votes
1answer
1k views

Find all cycles through a given vertex

Given a directed graph $G$ and a vertex $v$, how can we enumerate all simple cycles that pass through $v$? I found a question that describes how to enumerate all simple cycles in $G$, but I want only ...
3
votes
2answers
8k views

Dijkstra's algorithm for edge weights in range 0, …, W

Suppose I want to run Dijkstra's algorithm on a graph whose edge weights are integers in the range 0, ..., W, where W is a relatively small number. How can I modify that algorithm so that it takes ...
3
votes
2answers
2k views

Minimum path between two vertices passing through a given set exactly once

Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes $\...
19
votes
1answer
1k views

Generating inputs for random-testing graph algorithms?

When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness....
19
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 ...
16
votes
2answers
884 views

Compute a max-flow from a min-cut

We know that computing a maximum flow resp. a minimum cut of a network with capacities is equivalent; cf. the max-flow min-cut theorem. We have (more or less efficient) algorithms for computing ...
14
votes
5answers
1k views

How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

I have an algorithmic problem. Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $a\in S$, $a\geqslant |S|$. For example: If $T$=[1, 3, 4, ...
13
votes
1answer
2k views

Why doesn't Knuth's linear-time multiplication algorithm “count”?

The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of ...
11
votes
1answer
1k views

Indexing into a pattern database - Korf's Optimal Rubik's Cube solution

As a fun project, I've been working on a C# implementation of Richard Korf's - Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. https://www.cs.princeton.edu/courses/archive/fall06/...
11
votes
1answer
890 views

What type of algorithms are faster with a quantum computer?

I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $n\log n$ time. However, I also know that ...