# 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,208 questions
Filter by
Sorted by
Tagged with
408 views

### Applying algorithms on large data

Is there any book or tutorial that teaches us how to efficiently apply the common algorithms (sorting, searching, etc.) on large data (i.e. data that cannot be fully loaded into main memory) and how ...
52 views

### Solving $\text{key}=(\sum_{K=0}^n\frac{1}{a^K})\bmod m$ with High limits

I was solving this equation: $$\text{key}=\left(\sum_{K=0}^n\frac{1}{a^K}\right)\bmod{m}.$$ Given $$1,000,000,000 < a, n, m \; < 5,000,000,000,$$ $$a, m \text{ are coprime}.$$ I solved it by ...
9k views

### Given a set of sets, find the smallest set(s) containing at least one element from each set

Given a set $\mathbf{S}$ of sets, I’d like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I’d also like $M$ to contain as few elements as possible ...
354 views

### What is the complexity of this subset merge algorithm?

Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath. The ...
276 views

### Find any of the 3 largest among $n$ elements

I have two questions. Both are about finding any of the 3 largest among $n$ elements. How to show that $n-3$ comparisons suffice to find any of the $3$ largest among $n$ given numbers $(n \geq 4)$? ...
4k views

### Graphs that cause DFS and BFS to process nodes in the exact same order

For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-...
395 views

### Can abstract syntax trees be unparsed in subexponential time?

Abstract problem description The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. ...
13k views

### Uniform sampling from a simplex

I am looking for an algorithm to generate an array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should ...
893 views

### Is every linear-time algorithm a streaming algorithm?

Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear ...
3k views

3k views

### Why use comparisons instead of runtime for comparing two algorithms?

I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. ...
273 views

### How to compute linear recurrence using matrix with fraction coefficients?

What I'm trying to do is generate Motzkin numbers mod a large number $10^{14} + 7$ (not prime), and it needs to compute the $n$th Motzkin number as fast as possible. From Wikipedia, the formula for ...
20k views

### Is it possible to find the nth term of a Fibonacci sequence using a definitive for loop?

I'm using the book Introduction to Computer Science by John Zelle and at the end of Chapter 3 (Computing with numbers), I'm asked to find the nth term of a Fibonacci sequence presumably using a ...
50k views

### Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$. I have ...
349 views

### Worst-case sparse graphs for Hopcroft-Karp Algorithm

Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
680 views

### Why does Prim's algorithm keep track of a node's parent?

There is an obvious similarity in workings between Prim's algorithm and Dijkstra's algorithm, however I see no reason for Prim's algorithm to keep track of a node's parent. In Dijkstra's algorithm, ...
628 views

### Problem similar to set packing

Call a family of sets $\mathcal{F} = \{S_1, \dotsc, S_k\}$ "diverse" if each set $S_i \in \mathcal{F}$ has at least one unique element. What are possible approaches for finding the largest diverse ...
166 views

I'm not even sure if this is the right StackExchange to post this, but it seems like sentiment analysis would go here. What would be the best approach to determine if two people on Twitter are ...
606 views

### name matching algorithms from partial input

There are a lot of algorithms out there that solve this particular problem. My main problem is in trying to understand how they work; where to start. Most of the algorithms are academic in nature. ...
95 views

### Run time of product of polynomially bounded numbers

Let $M$ denote a set of $n$ positive integers, each less than $n^c$. What is the runtime of computing $\prod_{m \in M} m$ with a deterministic Turing machine?
16k views

### Maximum Independent Set of a Bipartite Graph

I'm trying to find the Maximum Independent Set of a Biparite Graph. I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow": Problem: ...
2k views

### Maximum Independent Subset of 2D Grid Subgraph

In the general case finding a Maximum Independent Subset of a Graph is NP-Hard. However consider the following subset of graphs: Create an $N \times N$ grid of unit square cells. Build a graph $G$ ...
16k views

### What is the novelty in MapReduce?

A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1] The name is ...
136 views

### Seeking "gold standard" to evaluate accuracy of network clustering algorithm

I'm currently looking at network clustering algorithms (we're currently looking at both directed and undirected, unweighted networks). The algorithms we've tried produce visually nice clusters. ...
10k views

### Time complexity formula of nested loops

I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides. ...
739 views

### Micro-optimisation for edit distance computation: is it valid?

On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus: ...
215 views

427 views

### Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...
470 views

### Which method for ODE instead of Euler's?

I need a super-fast method for ordinary differential equations. Should I use the midpoint method? I need this for a reaction-diffusion system (Gray-Scott).
913 views

### What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms?

I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary. The standard binary golden ratio notation works but is horribly space inefficient. The Balanced ...
2k views

### Standard or Top Text on Applied Graph Theory

I am looking for a reference text on applied graph theory and graph algorithms. Is there a standard text used in most computer science programs? If not, what are the most respected texts in the ...
957 views

### Greedy choice and matroids (greedoids)

As I was going through the material about the greedy approach, I came to know that a knowledge on matroids (greedoids) will help me approaching the problem properly. After reading about matroids I ...
1k views

### An edge that connects more than two nodes in a graph?

Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y ...
602 views

### From in-order representation to binary tree

Is there a way to reconstruct a binary tree just from its in-order representation? I've searched the internet, but I could only find solutions for reconstructing a binary tree from inorder and ...
1k views

### Tighter analysis of modified Borůvka's algorithm

Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$. The pseudo-code is: ...
619 views

### Reason for global update steps in the push-relabel algorithm

I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?
588 views

### Finding a minimal containing rectangle from a given set of rectangles

The problem is as follows: Given a finite set of rectangles ($S\subset\mathbb{R}\times\mathbb{R}$), build a data structure that will support the following operations: Check, receives a rectangle \$r\...