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

### How to find a crticial edge in a flow network?

The complete question is as follows: An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Give an efficient algorithm that ...
13 views

### Create a Turing machine for this interactive game

Given two players $A, B$ and some natural number $n \ge 2$, let $\#(A,B,n)$ denote the following algorithm: $A$ thinks of some number $a \in \{1,\ldots,n\}$ Until the game ends: $B$ thinks of some ...
1 vote
20 views

### Rank in a Convex Combination

Given vectors $A, B \in \mathbb{R}^{n}$, $w \in [0,1]$ and $x \in \mathbb{R}$, let $$Rank(A,B,w,x)=\sum_{i=1}^{n} \boldsymbol 1 \{w A_{i} +(1-w) B_{i} < x\}$$ denote the number of elements in the ...
13 views

### Viterbi algorithm for object tracking

I want to solve a problem of object tracking along time. The problem is - I have a sequence of images, and I need to find and track the creation of the objects, than their movement, and than their ...
46 views

### What are the methods to prove the correctness of an algorithm?

I want to know the major methods to prove the correctness of a program/algorithm. Recommendations on books are appreciated too. This is a general question. TIA. Edit: I'm not looking to detailed ...
• 101
1 vote
24 views

### shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/). Everything in the first part of the proof (The section ...
65 views

### Algorithm that finds 4 "O"s or 4 "X"s on a diagonal, horizontal, or vertical

My algorithm homework revolves around matching 4 "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical. ...
• 123
51 views

### Given two strings ABC and CBA, find A, B and C

Given two strings ABC and CBA, find A, B and C. Input: abcacab, cabcaab Output: ab, ca, cab The time complexity of brute force is O(n^3). Are there any better algorithms to solve this problem? Thanks!
19 views

### Algorithms for finding closest graph node within set of nodes

Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$? Furthermore, say we are doing many ...
28 views

### Inversion array of a given array

Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i ...
14 views

### Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?

I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.
36 views

1 vote
40 views

### Optimizing placing items in containers across a path

I'm searching for the generic name of an algorithm/method that would allow me to solve this type of problem efficiently. I have a continuous line which I traverse, from one side to the other. Along ...
• 111
70 views

### Diffie-Hellman with offline attack

There is a protocol that aims to transfer a password securely between the user and the server. The protocol is based on the Diffie-Hellman method. In the protocol, p is a prime number, g is a ...
1 vote
88 views

### Algorithm to generate points uniformly at random from a ball

Consider a 2-dimensional version of generating points in the circumference of a unit radius circle, independently generate each coordinate uniformly at random from the interval [-1,1]. How to generate ...
• 11
1 vote
61 views

### A different algorithm called the 'bubble sort'?

In Robert Lafore's book "Object Oriented Programming in C++, Fourth Edition", on page 450, he has a section on the bubble sort. The way he describes it is as follows: Here's how it works, ...
22 views

### Is this A* pseudocode taking the condition of admisible ad consistent heuristic function hypothesis for granted?

This is the pseudocode for A* from wiki: ...
61 views

### Using topological sort to find inconsistencies represented by cycles in directed graphs

Consider the following scenario. Let $x_1,...,x_n$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $x_1$ starts driving strictly ...
36 views

### What is algorithm fairness?

I am not getting the meaning of algorithm fairness. Consider the RAM model, quicksort, mergesort,all pair shortest algorithms they all are not biased as per my understanding. Please provide a ...
• 11
18 views

### Landau Notation/Big O notation

In our class the following exercises/examples were given: Compute/find $n_0$ and c from the formal definition of each Landau symbol to show that: $n^{2/3} \in \Omega(log^8(n))$. Then in the Solution ...
• 173
80 views

### Is there a working O(1)-space flood fill algorithm?

This is a purely theoretical question: among the known flood fill algorithms, there is one which does not require any dynamically-sized data structures, explicit or implicit: the so-called Walk-based ...
• 109
54 views

• 5,726
1 vote
18 views

### Negotiating a connection between two devices that can't transmit and receive simultaneously

I've got a bit of a puzzle here that sits at the intersection of mathematics and technology. Hopefully this doesn't fall into brainteaser territory - I'm not sure a neat solution is possible! I have ...
1 vote
65 views

### LWE with a low rank matrix

Consider the decision LWE setting, where we have to distinguish between $(A, As + e)$ and $(A, u)$, for a randomly chosen $m \times n$ matrix $A$, an $n \times 1$ secret vector $s$, an $m \times 1$ ...
• 219
1 vote
30 views

### What is the circuit depth of asymptotically fast multiplication algorithms?

I know the circuit depth (i.e. amount of sequential operations on the longest path) for long multiplication can easily be made $O(\log(n))$ (possibly at the cost of increasing the computational ...
• 111
10 views

### Editing facial features

Photoshop offers some great image processing filters under the term "Face-Aware Liquify". I want to integrate such techniques into an automated processing system I am currently implementing (...
• 121
38 views

### Weigher problem

I got interested in one problem. I have $N$ rocks, where rock with minimum weight have number equal to $1$, the next heaviest stone has a number equal to 2, etc.. So a rock with maximum weight have a ...
1 vote
34 views

### Relation between algorithms and models

I have found this question some time ago. While reading it, I had a problem with understanding the following idea: Question, part 1: Is one allowed to talk about the time/space bound of any algorithm (...