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
0 votes
0 answers
13 views

Recurrence relation of multiply two $n$ bit numbers

Suppose given two $n$ bits numbers $A$ and $B$. Also suppose there is a machine that compute multiply two $\sqrt{n}$ bits numbers in $O(1)$. What is time complexity of multiplying two $n$ bits number ...
user avatar
0 votes
2 answers
24 views

Correctness vs Proof of Correctness

Assuming we are observing an algorithm.I am confused as to how one needs to proof correctness. What exactly the correctness represent for a given algorithm? And why do we have to proof correctness, in ...
user avatar
  • 173
0 votes
1 answer
16 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 ...
user avatar
  • 101
2 votes
0 answers
17 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 ...
user avatar
3 votes
1 answer
53 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 ...
user avatar
0 votes
0 answers
14 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 ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
  • 101
1 vote
1 answer
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 ...
user avatar
2 votes
3 answers
67 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. ...
user avatar
  • 123
3 votes
1 answer
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!
user avatar
0 votes
1 answer
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 ...
user avatar
-2 votes
1 answer
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 ...
user avatar
-1 votes
1 answer
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.
user avatar
0 votes
1 answer
36 views

Tiling a simple polygon with hexagons

Let $T$ be a hexagonal tiling of the plane and assume we are given a simple polygon $P$ (we define $P$ as the union of the points on its boundary and its interior). The task is to find the subset of $...
user avatar
  • 1
5 votes
0 answers
91 views
+150

Prove: Self-organizing list that uses Move-to-Front is 2-Competitive

Preparing for my finals in my "advances algorithms" course. Usually there is a question to prove one of the theorems that was given over the course. I'm currently trying to write a full ...
user avatar
  • 209
3 votes
1 answer
33 views

Algorithm for maximum non-crossing edge set in bipartite graph with a fixed permutation

I'm trying to identify an algorithm to solve this computational problem Input: Bipartite graph (V, W, E), with E ⊆ V×W A fixed ...
user avatar
  • 53
0 votes
0 answers
16 views

Give examples of data structure usage which can be used and cannot be used in amortized analysis

Preparing for my finals in my "advance algorithms" course. In one of the previous exams, there was the following question: Let there be some arbitrary data structure (it is not known ...
user avatar
  • 209
1 vote
0 answers
17 views

Minimizing operations to reach a set of goal stack states

I'm trying to sort the elements of a set of "goal" stacks to minimize the number of pushes/pops to reach each state. The inputs and outputs can be some other structure rather than stacks, ...
user avatar
  • 11
1 vote
1 answer
31 views

Are there adaptive algorithms/data structures for sparse and non sparse vectors?

A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value. A dense 1D array is commonly encoded as a linear array of values [value1, value2, ...
user avatar
  • 121
2 votes
1 answer
79 views

Find if a given number must be in a set that is closed under gcd and lcm with some given elements

Source: https://oj.vnoi.info/problem/cryptkey (problem statements are in Vietnamese, so here it is translated). There is a set $S$ of positive integers. If $A$ and $B$ are in $S$, then $\gcd(A, B)$ ...
user avatar
0 votes
0 answers
33 views

How to read and interpret these expressions?

I am reading a research paper in which following equation is given: $\underset{\small{X}\\\text{s.t}\sum_{(i,k)\in \mathcal{A}}x_{ik}=1, \forall i\in \mathcal{M}}{\operatorname{max}} u$ where $\small{...
user avatar
  • 1
1 vote
0 answers
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 ...
user avatar
  • 111
0 votes
0 answers
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
  • 11
1 vote
1 answer
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, ...
user avatar
0 votes
0 answers
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: ...
user avatar
0 votes
0 answers
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 ...
user avatar
-2 votes
0 answers
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 ...
user avatar
  • 11
0 votes
1 answer
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 ...
user avatar
  • 173
1 vote
1 answer
84 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 ...
user avatar
  • 119
2 votes
0 answers
54 views

Playing with boxes: NP-hard? [Graph Theory]

You are playing with boxes on a $K_{1, n}$-$\textbf{subdivision}$ graph $G:=(V, E)$ whose number of vertices is odd, i.e., $|V| \equiv 1$ (mod $2$) with a given central point $C$ such that $\forall v \...
user avatar
2 votes
1 answer
22 views

Fast algorithm for Graph Edit Distance to vertex-labeled Path Graph

Let $G$ be a vertex-labeled directed graph with unique labels $L$. Let $G_P$ be a path graph with the same vertex labels and the same number of vertices as $G$. I know that in the general case ...
user avatar
  • 23
1 vote
1 answer
19 views

Finding articulation points

I have learnt about both articulation points and bridges and I have understood the algorithm used to find the number of bridges in O(n) time which is Tarjan's algorithm. But now, can I simply say that ...
user avatar
  • 127
-1 votes
0 answers
28 views

Please suggest an efficient algorithm to process around tenthousand orders per second for a financial system

Can you guys recommend me a fastest algorithm which can process more than ten thousand orders per second.The purpose of the algorithm is to process these orders and thus to update or save those data ...
user avatar
-1 votes
0 answers
21 views

Design a protocol that issues O(√n log n) many OR-queries and finds the indices of all √n many 1’s

Consider a Boolean string x ∈ {0, 1}^n to which you have OR-query access: You can send an oracle a subset S ⊆ [n], and the oracle will answer if there is any 1 in the entries of x indexed by S or not. ...
user avatar
  • 1
1 vote
1 answer
30 views

How is slope error calculated for Bresenham’s Algorithm for both 2D and 3D?

I've been working with Bresenham’s Algorithm in 2D and understand it is derived from the following logic: y = mx+c To get the slope error at a given point, the following equation is used: d2 is the ...
user avatar
0 votes
1 answer
38 views

A* pseudocode problem

What is the difference between this two pseudocode and which one should i implement? ...
user avatar
-1 votes
0 answers
24 views

Hungarian Assignment Algorithm Implementation - Why not work on this matrix? [duplicate]

I implemented the Hungarian algorithm according to this guide: 16:48 and there is one matrix that The application I wrote does not bring a result, Can you go through my code in Hungary algorithm ...
user avatar
  • 1
1 vote
2 answers
48 views

Existence of some search algorithms

The lowest time complexity of search algorithms for sorted lists is $$O(n)=logn$$. The lowest time complexity of sorting algorithms is $$O(n) = nlogn$$ So in order to be able to use a search ...
user avatar
-2 votes
0 answers
18 views

how to achieve the maximum height in red black trees?

As we know, the maximum height of a red black tree is 2* log (n+1). So lets say we have six nodes [1,2,3,4,5,6]. How to insert them to achieve the maximum height ?
user avatar
  • 1
3 votes
0 answers
85 views

Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of strings? [migrated]

As a subroutine for an algorithm we’re working on, we need to compute the lexicographically minimal rotation (or least circular shift) of a list of strings. The problem is well-known and several ...
user avatar
1 vote
1 answer
30 views

Find the placement of gates on 2D points that minimizes the total distance of all paths to be made

Suppose we have a 6 vertices graph. We also have 6 gates. Each gate is attributed a path. For example, Gate 'A' will have to go to 'B'- 'C' - 'D' and 'E' Gate 'B' will have to go to 'D' Gate 'C' will ...
user avatar
  • 113
1 vote
2 answers
47 views

Can this algorithm for 2-dimensional points be generalized to 3 dimensions?

There is a list of 3-dimensional points $(x_1,y_1,z_1),\ldots,(x_m, y_m,z_m)$, where all coordinates are non-zero integers. I would like to decide whether there exist positive real weights $w_x, w_y, ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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$ ...
user avatar
  • 219
1 vote
0 answers
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 ...
user avatar
  • 111
0 votes
0 answers
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 (...
user avatar
-1 votes
1 answer
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 ...
user avatar
  • 1
1 vote
1 answer
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 (...
user avatar
-3 votes
1 answer
119 views

Identify the missing number in a set given its superset

Given a set B and B’s superset A, if B is missing 1 number (let’s y) but don’t know which number it is, how to find that number? That is, B’ = B \ {y}, for some unknown element y B = A \ {x}, for ...
user avatar

1
2 3 4 5
213