Stack Exchange Network

Stack Exchange network consists of 175 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.

3
votes
0answers
73 views

Adjacent Gray code

Gray code is permutation of $\{0,1,2,\dots,2^n-1\}$ such that each of consecutive number is differs only one bit in binary representation. Example for $n = 3$ $000\\ 001\\ 011\\ 010\\ 110\\ 111\\ ...
3
votes
2answers
65 views

How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs

The Bellman-Ford algorithm on a graph with $n$ vertices, normally includes a loop executed $n-1$ times. Each time through the loop we iterate over the list of edges $(u,v)$ and relax $v$. Note that ...
2
votes
1answer
25 views

When an algorithm says Summation this, and Integral that, what does it mean in coding terms?

I'm a student at a college with only two units of mathematics and I don't know if I'm asking in the right place so please bear with me. I'm currently reading GPU Gems by nvidia and I have a question....
1
vote
1answer
65 views

Find total count of all paths starting from a fixed vertex to all other vertexes of the graph

Given an directed graph (may contain cycles) we have to find total number of simple paths from a fixed source vertex to all other vertices of the graph, i.e. $$ \text{#(paths from 1 to 2)}+\text{#(...
1
vote
1answer
83 views

To check if a chain with $n$ links can be “folded” into a size at most $L$

Given a chain of $n$ links, each of length $a_1, a_2,..a_n$, where each $a_i$ is a positive integer. $L$ defines the length of the "folded" chain. More formally, we want to decide whether there exists ...
1
vote
1answer
94 views

residual graph and augmenting path in max flow

I thought I understood max flow perfectly until I got to the exam and we got this. I know how to compute a maximum flow by means of the Ford-Fulkerson algorithm, specify the residual network and ...
3
votes
1answer
36 views

Sampling numbers from a weighted set that sum to constant value

So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to ...
0
votes
0answers
14 views

Analyze the following algorithm by computing its running time, T(n) [duplicate]

I'm trying to figure out the running time of this loop. I think it's T(n) = 0(n^4) because the loop inside is dependent on the i of the outer loop. So does that mean the inner loop will have a running ...
1
vote
1answer
55 views

Generating project network graph

I had a problem of generating project network graph (like there and there) from list of activities and their dependencies. Informal description: Every activity is represented as edge of directed ...
0
votes
0answers
41 views

Correct invariant of BFS

I am trying to find a correct invariant of BFS. If we represent a queue as $ Q = [a_0;...; a_n]$ such that : $Q.pop() = a_n$ then I found the following invariant which I think is correct (we denote ...
0
votes
0answers
24 views

Find no of acyclic paths of any length in a directed graph from a single source given that every node has at most 4 in/out degree

let A,B,C be nodes of directed graph with edges A->B,B->A,A->C,C->A,B->C,C->B then no of paths will be 5 that is A,A->B,A->C,A->B->C,A->C->B If i apply dfs and increase counter for every node i ...
1
vote
1answer
67 views

What is the complexity of the algorithm to calculate power set of a set?

Below is an algorithm to compute the power set of a set. To my understanding, for a set with cardinality n, there is a for loop ...
3
votes
1answer
52 views

Find the smallest set of strings which “covers” a given set of strings (coverage = containing as substring)

Let $S$ be a finite set of strings and $0 < k\leq l$ integers. We want to find the smallest set of strings $T(k,l)$ for which the following holds: $\forall t \in T(k,l): k \leq |t| \leq l$ $\...
2
votes
2answers
56 views

An algorithm to efficiently insert a list of elements into a binary heap (at once)

I wonder if there is any elegant algorithm for inserting a list of elements into a binary heap (at once) whose performance would be close to that of inserting elements one by one when there are only a ...
1
vote
1answer
24 views

Reading elements of a countable set with Turing machine

I have a basic question about the behavior of a potential Turing machine. Suppose that $S$ is a countable set of binary strings, so that we can enumerate $S$ as $(s_i)_{n\in \mathbb{N}}$. Suppose ...
2
votes
0answers
24 views

Gray code in Matrix

Suppose I have a matrix $m \times n$ with entry 0 or 1. Of course there is a possible $2^{m\times n}$ matrix. I want to sort all the matrices so that every two consecutive matrices are only 1 bit ...
1
vote
0answers
20 views

How can I code an algorithm (concerning networks) [closed]

my question is basic but I want to know how to code algorithms containing maths like this https://web.stanford.edu/~skatti/pubs/sigcomm15-spotfi.pdf , TY for your help !
2
votes
1answer
73 views

What is an optimal algorithm?

I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are ...
2
votes
0answers
57 views

Min no.of operations required to convert an array to which it should contain elements of equal frequency

I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
0
votes
0answers
15 views

Find whether a word is in a rational expression

You are given a word $w$ and a rational expression $R$ ($R$ is represented as a binary tree). Find an efficient algorithm that says whether $w \in L(R)$ or not. I think I found a quadratic algorithm. ...
2
votes
1answer
88 views

Greedy algorithm for even item distribution

I have this problem where I need to design a greedy algorithm. The problem is as follows: A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $...
6
votes
2answers
781 views

What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?

I’m trying to understand the time complexity of a queue implemented with a linked list data structure. My book says that we can the implement a queue in O(1) time by: enqueueing at the back ...
7
votes
5answers
526 views

Number of FLOPs (floating point operations) for exponentiation

What is the number of floating point operations needed to perform exponentiation (power of)? Assuming multiplication of two floats use one FLOP, the number of operations for $x^n$ will be $n-1$. ...
2
votes
0answers
54 views

Count number of pairs of elements in an array whose bitwise OR is equal to a given integer

Given an integer array and an integer $k$, we have to count the number of pairs of elements from the array whose bitwise OR is $k$ in $O(n)$ time complexity. How could this be done?
-2
votes
1answer
91 views

Count the number of subsets with product less than or equal to k [closed]

You are given an array $A$ of $n$ positive integers, you have to find the number of subsets the product of whose elements is less than or equal to a given integer $k$. Is there an efficient algorithm ...
2
votes
0answers
45 views

Worst case for linear-time k'th smallest element algorithm?

There's an algorithm for finding the k'th smallest element in an unsorted array similar to quickselect: kthSmallest(arr[0..n-1], k) 1) Divide arr[] into ⌈n/5⌉ groups where size of each group is ...
0
votes
0answers
15 views

What would be the line by line analaysis and construction function T[n] with Big Oh notation? [duplicate]

What would be the line by line analaysis and construction function T[n] with Big Oh notation? Thanks a lot.
2
votes
1answer
91 views

Can memoization be applied to any recursive algorithm?

I am new to the concepts of recursion, backtracking and dynamic programming. I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there ...
0
votes
0answers
26 views

Bubble sort that ignores rightmost sorted parts

Initial Bubble sort pseudocode(Typical): 1)foreach Element in array 2) initialise a flag that flips whenever a swap is done 3) Starting from the element, attempt to swap and update flag 4) If ...
3
votes
1answer
50 views

Efficient algorithm to replace list of integers with nearest bigger element

The original question was in the context of an array, but I just used a list without changing the length for easier debugging purposes of toString(). Given an ...
1
vote
1answer
19 views

Selection of dates respecting delay constraints

I encountered an issue at work that can be derived approximatively to this problem. Let say we have a machine that can be triggered to instantly do an action. There are several (between 10 to 15) ...
0
votes
0answers
19 views

Algorithm to group entities into variable sized groups based on attribute

I have the following problem: There are n entities (persons) having a common attribute (weight) and I need to build weight categories (this is for a sports event) grouping people based on their ...
0
votes
0answers
12 views

Identify row or column addition or deletion in a table

I'm looking for a solution which can able to identify the any row or column addition or deletion in a table of numbers. What I have thought of as of now by using the LCS i.e. "Longest common sub-...
1
vote
0answers
27 views

Optimal improper vertex-coloring of graph with weighted edges

I have an undirected graph with weighted edges. I want to color the vertices with a given $k$ colors. Let's assume there is no proper coloring with $k$ colors such that adjacent nodes will always have ...
1
vote
2answers
59 views

Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval

Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair? The naive approach is ...
2
votes
0answers
57 views

Finding the final state of the $1$ dimensional “split the twos” automata

This problem is from a coding competition ( Website Here ) in Mexico that does not provide solutions and has me stuck. Consider the following automata: Every state $B_k$ is an array of fixed length $...
4
votes
1answer
20 views

Finding max value algorithm with subset comparison

I have a set of $N$ different values, and my goal is to find the biggest one in the least number of comparisons. Comparing subsets (using the sum of each) is also allowed, and counts as one comparison....
1
vote
1answer
65 views

Placing items into compatible bucket types to find an optimal total value

Suppose we have a list of buckets, each with a unique type and a maximum capaciy. We also have a list of items, each with a value and a list of compatible bucket types. An item is compatible with a ...
3
votes
0answers
25 views

Split a graph into 2 components with known distribution?

I'm trying to find a method to randomly split a connected planar graph $G$ into two connected components, such that the sum of the weights of vertices in each component are relatively close. (If there ...
2
votes
1answer
41 views

Overall time complexity of Heuristical Algorithm for travelling salesman problem [TSP]

I am trying to figure out the time complexity of a heuristical algorithm used to solve the Travelling Salesman Problem in a more efficient way than by brute force, ($\theta(n!)$ or similar) The ...
0
votes
0answers
26 views

Can the average case of an algorithm be $O(n \log n)$ if the best case running time of an algorithm is $\Theta(n \log n)$? [duplicate]

Let us suppose the best case running time of an algorithm is $\Theta(n \log n)$. Can the average case run time of the algorithm be $O(n \log n)$? Since $O(n\log n)$ would imply the value going even ...
1
vote
1answer
94 views

Computing Cardinality of Sumsets using Convolutions and FFT

I read somewhere that you can compute the cardinality of sumsets by computing the convolutions of the characteristic vectors of the given sets, and that this can be done efficiently using Fast Fourier ...
1
vote
1answer
127 views

Implementation of QuickSort to handle duplicates

I have this past year question based on the following scenario: When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are ...
0
votes
1answer
54 views

Find an element in sorted 2D-array (matrix)

Given an $N\times N$ array, where elements are decreasing in every row and every column. What is the fastest way to find the $(i,j)$ of a given element if it exists in the array, or return no if it ...
3
votes
1answer
46 views

Blind sorting an array with a singular sort function?

I am doing some interview prep, and I came across a question that really stumped me, and it didn't provide an answer. The premise of the question was as follows: You are given some unsorted array A ...
1
vote
2answers
42 views

Confused about Telescoping/Domain Transformation Question

I have been working on the following domain transformation problem however, I am stuck on how to continue to receive the solution. I would greatly appreciate it if someone can explain how I can ...
2
votes
2answers
142 views

Algorithm: Given a large semiprime number N, find the smallest value of $A$ such that $N + A^2$ is a square

Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^...
2
votes
1answer
33 views

Generate a random combination in O(k) time and space?

How to generate a random combination of $k$ numbers from $n$ choices in $O(k)$ time and space, if we can generate a random number between 1 and $O(n)$ in $O(1)$ time? I know only 3 algorithms: with $...
0
votes
1answer
57 views

Autocorrect algorithm - How to implement a decent “apostrophe & elision” feature?

shorter version of the original question (as requests in comments) What is the algorithm to handle missing apostrophe as it is done in auto-correct feature of Android virtual keyboard? (If it helps /...
2
votes
2answers
66 views

Having a better complexity / adversary argument for finding if a finite automata accepts a palindrome

Let $A$ be a DFA over a finite alphabet $ \Sigma$. Find an algorithm that indicates if $A$ accepts a palindrome and give the complexity of this algorithm. Here is my solution: If we denote $^t A$ ...