Stack Exchange Network

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

4
votes
1answer
39 views

Find all edges in a tree whose removal doesn't separate color classes

Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$. Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected. ...
3
votes
2answers
74 views

Minimum number of adjacent swaps needed to sort a circle of elements

I have been thinking about some problems in combinatorics and I came across a problem I'm having trouble with. Suppose you have a list $L$ of length $n$ (wlog the elements of the list are 1,2,3,...,n)...
0
votes
0answers
19 views

Finding runtime of a recurrence relation with a fractional power

Consider the following algorithm and find the tightest Big-$O$: Assume $\texttt{multiplyKS}$($A,B$) is $O(n^{1.58})$ and $\texttt{Add}($A,B$)$ is $O(n)$. If my runtime is $T(n)$, I have: Lines 1 ...
1
vote
2answers
44 views

Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time?

Assume that I have the adjacency matrix representation of a graph in $0,1$ values. Does converting it to a corresponding adjacency list representation always have a time complexity of $O(n^2)$?
2
votes
2answers
96 views

How broad is the meaning of “algorithm”?

This is a purely terminological question. The word algorithm, as I have learnt it refers to something like an "effective method, a sequence of steps, for doing something". There are alternative ...
1
vote
0answers
22 views

What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?

Section 29.4 "Duality" of CLRS (3rd Edition) describes the way of reading off an optimal dual solution from the last slack form of the primal as follows: Suppose that the last slack form of the ...
3
votes
1answer
27 views

Algorithm for MST connecting a subgraph

I already know how to find the MST of a connected graph. This MST will have the least total weight and will connect all nodes in the graph. However, this is a problem I have to deal with: Given a ...
32
votes
2answers
7k views

Is there a difference between top-down and bottom-up dynamic programming?

Is there a fundamental difference between top-down and bottom-up dynamic programming? In particular, is there a problem which can be solved bottom-up but not top-down? Or is the bottom-up approach ...
2
votes
2answers
3k views

How to decode multiple-digit gamma codes and get the gap sequence?

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
3
votes
1answer
55 views

Merging balls interview problem

Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks. You are given $n$ balls on the table and all the balls are rolling towards the ...
-3
votes
0answers
22 views

it is about binary trees [on hold]

Professor George O’Jungle has a 27-node binary tree, in which every node is labeled with a unique letter of the Roman alphabet or the character &. Preorder and postorder traversals of the tree ...
0
votes
0answers
17 views

Write a python program that computes g=gcd and the integer solution to ax+by=g [on hold]

This is what i have for my program. It doesn't not print out the right numbers, and I can't figure out what it is that messes up the numbers. For example when i do Egcd(60,22) i get (22,0.0,1.0) when ...
2
votes
2answers
64 views

Algorithm for closest available resource

My apologies if question is not in correct format. I don't post here often. I don't know what tags would be appropriate for this question, or even if this is an appropriate question. Looking for ...
5
votes
2answers
455 views

Logic behind O(n) solution for 'Maximum length sub-array having given sum'

I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum (...
-1
votes
2answers
28 views

calculation of Transitive Closure

This question is not from homework, but rather as preparation for the test: The calculation of place-in is a calculation in which the algorithm does not need space beyond the output size (beyond ...
1
vote
3answers
782 views

O(1) space, O(N) complexity algorithm for buy and sell stock twice interview question

Question: Given a time series of stock prices, what is the maximum profit you can make if you are allowed to Buy and sell the stock twice. The second buy has to come after first sell. Solution: ...
1
vote
1answer
45 views

Complexity of sending an $n$-bit string

Consider a $2$-party communication model in which $A$ wish to send to $B$ an $n$-bit string. It is very easy to prove that any deterministic protocol for this problem requires $\Omega(n)$ bits to be ...
4
votes
1answer
41 views

Why integer division is of equal complexity as multiplication

I am trying to understand the fact that integer division is no more difficult than integer multiplication. I found some references - here and this lecture note. Wikipedia says if there is a way to ...
0
votes
1answer
23 views

What is a genuine atomic multicast?

What is a genuine atomic multicast? What is the difference between a genuine and non-genuine atomic multicast?
1
vote
1answer
34 views

Does the Paxos algorithm use failure detectors?

Does the Paxos algorithm use failure detectors? If not, how can it solve consensus, given the impossibility result?
2
votes
1answer
66 views

Checking the validity of a pyramid of dominoes

I came across this question in a coding interview and couldn't figure out a good solution. You are given 6 dominoes. A domino has 2 halves each with a number of spots. You are building a 3-level ...
0
votes
1answer
16 views

Defining Local Search stopping criteria

When performing a local search, for example, a 2-node exchange in a metaheuristic (like GRASP), what is the usual stopping criteria for that procedure? Some bibliography says that the local search ...
0
votes
1answer
29 views

Which BackJumping Algorithm is being used here?

This is the illustration of the Backjumping algorithm for four queens exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem .I am confused whether this is ...
5
votes
2answers
99 views

Return copy of array, each element product of all others, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. The task is as follows: Given an array $<a_1, \ldots, a_n>$ of fixed-...
2
votes
3answers
374 views

Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))

Given a sorted array $A[1,\ldots,n]$ and element $x$ that located at position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity. ...
3
votes
1answer
30 views

Can maximum matching algorithms be used for maximum weight matching?

There are two fast algorithms for maximum matching on general graphs: Micali and Vazirani in $O(E\sqrt{V})$. Mucha and Sankowski in $O(V^{2.376})$. Can these be also used for maximum weighted ...
3
votes
1answer
12k views

Time complexity of this solution to N-queens problem

I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
0
votes
0answers
12 views

Are there any Linear genetic programming tools available? [on hold]

I have been learning the concepts of linear genetic programming(lgp) lately but I am not able to find any tool which implements the concepts of lgp. Can someone suggest tools/software which ...
1
vote
1answer
34 views

Which AC-3 algorithm is being used here?

This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma,...
1
vote
1answer
26 views

Trying to understand the question(well spaced points ?) better

Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j \in S,i\ne j}...
0
votes
1answer
48 views
24
votes
7answers
36k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
2
votes
1answer
47 views

Lexicographically smallest down-right path in matrix

Here is the problem which I thought was simple dynamic programming, which is however not the case. Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path ...
4
votes
0answers
30 views

Highest covering repeated string

Let's say I have the following string: XXXXXAYYYYBYYYYCXXXXXDYYYY We can see that the substring XXXXX is 5 characters long, ...
9
votes
1answer
5k views

Find the longest repeated pattern in a string

I'm looking for an efficient algorithm to find the longest repeated pattern in a string. For example, consider the following string of numbers: ...
0
votes
1answer
22 views

What is the asymptotic complexity of the following code snippet?

for (i = 2; i < n; i = i * i) { for (j = 1; j < i / 2; j = j + 1) { sum = sum + 1; } } I know that the outer loop can run for a maximum of $n^2$ ...
1
vote
2answers
46 views

Pseudo Code optimization

Summary: I am struggling with the Pseudo code for an that algorithm assigns "least filled slot first" to a tasks on multi-core chip. Detail So far I have written following: What I do not like ...
0
votes
0answers
12 views

Algorithm to find sum of all values in a 2D matrix when i<j [on hold]

Given an array A of n integers, output an n by n array B in which B[i,j] (for all i=j values of B[i,j] are left unspecified so ignore that case). My approach: The most natural way to do this is by ...
0
votes
0answers
14 views

Did Menezes et al. switch the letters $\mu$ and $\lambda$ in Floyd's cycle detection note 3.8?

The letters $\mu$ and $\lambda$ are usually used to represent, respectively, the length of the tail of the graph and length of the cycle in the graph. But Menezes on note 3.8, page 91 (or PDF-page 6),...
0
votes
1answer
21 views

Removing max number of edges while keeping minimum distances

Suppose we have a graph with vertices from 1 to n.The graph is undirected and the starting point is 1 and we have path from 1 to any other vertex.We also have positive weight on each edge and there ...
6
votes
0answers
99 views

Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
3
votes
0answers
65 views

Polynomial time algorithms for rank 1 elliptic curves over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a ...
1
vote
1answer
25 views

Path of maximum value with bounded cost in DAG

Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is ...
0
votes
0answers
48 views

Successive shortest path without reduced costs

The successive shortest path algorithm, used to solve the minimum-cost flow problem, can be described as follows : Successive shortest path (for minimum-cost flow) : while all flow is not ...
3
votes
1answer
262 views

Difference between sequential and parallel divide and conquer

In the textbook Introduction to Algorithm, third edition, by Coremen et al. (CLRS), the following introduction has been given about divide and conquer algorithm strategy In divide and conquer, we ...
2
votes
1answer
37 views

How do I know which direction I should rotate a node in an AVL Tree?

I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL ...
0
votes
0answers
15 views

Looking for resources for coding skills [closed]

I'm a college student majoring in Computer Science and I've been learning the material for about 3 years now. I've taken most of my mandatory courses including Data Structures and Algorithms and ...
-1
votes
0answers
15 views

How do you find DES algorithm encryption and decryption time? [closed]

I'm doing a project where I need to measure encryption time and decryption time for DES algorithm to compare it to modern standards, but I don't know where to find the most accurate algorithm. There ...
0
votes
1answer
21 views

Polynomial multiplication coefficients

I was wondering about the following interesting questions: Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial. What about finding a specific ...
1
vote
1answer
21 views

How fast can we optimally cluster 1-D data?

K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) ...