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.

2
votes
0answers
11 views

How to prune branches in a branch-and-bound solution for Flow Shop Scheduling?

I am implementing a Branch-and-Bound algorithm to find the optimal solution for the Flowshop Scheduling Problem, but I am stuck on the optimization phase, here is a rundown of the problem and what I ...
-1
votes
0answers
46 views

Approximation Algorithms

Atleast give the reason for downvoting.I am crying. vijay vazirani -approximation algorithms I am trying to understand max sat approximation algorithm from https://doc.lagout.org/science/0_Computer%...
0
votes
0answers
45 views

How to find the length of maximum subarray sum in segment tree query?

Problem: Given an array with size$\ n $: for each$\ a[i] $, it denotes the value of the house. You are given the task to build the wall that saves the house that is not exceed$\ w $ length. What is ...
3
votes
1answer
63 views

Stacking things of different thickness to approximate desired thickness

I have $N$ objects of different thickness. Is there an algorithm to determine which of those objects should be stacked on each other to get as near to a desired thickness as possible? (I don't want to ...
2
votes
1answer
39 views

Algorithm for identifying correct subset

My raw data is composite, but for simplicity sake let's say they consist of three elements. One might consider a sample set thusly. ...
0
votes
0answers
18 views

Finding an optimal machine assigning

I have $m$ machines and $n$ jobs. Each machine has a load capacity. Each job can be only handled by either one or two machine, and each job takes some time to finish. After it finished, new jobs can ...
1
vote
0answers
13 views

Can Expectation-Maximization algorithm with batch update diverge?

I am using EM to uncover a continuous hidden variable $z$ (E-step), then maximizing the model prediction (M-step) with parameters $\theta$. The complete data are $[x,z]$. I can formulate the E-step ...
5
votes
0answers
54 views

Minimum Number of Edges Added to a DAG to get Unique Topological Order

The question is simple: Given an unweighted directed acyclic graph, $G = (V, E)$, what is the minimum number of directed edges we need to add to $E$ such that the resulting graph $G = (V, E')$ has ...
0
votes
1answer
38 views

Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint

I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
0
votes
0answers
23 views

Looking for an esoteric graph theory algorithm

So I'm sure this is an unusual question for this type of site, but I am to give a talk on algorithms for discrete graphs in a few weeks. It has been specified that the talk is to be on some algorithm ...
0
votes
1answer
48 views

How to divide a line of numbers into N groups such that the sums of each group are closest to their mean using dynamic programming? [duplicate]

I have M numbers arranged into a line. I need to divide the line into N groups without changing numbers order such that the sums of the numbers of each group are closest to the mean of these sums by ...
0
votes
0answers
23 views

how to compute order statistic for union of sorted arrays?

I'm not sure why this solution holds: http://www.zrzahid.com/kth-smallest-element-in-two-sorted-arrays/ For example, $A=[1, 1, 2, 3, 10, 15]$ and $B=[-1, 2, 3, 4, 6, 7]$ then *k=8*th smallest ...
1
vote
1answer
52 views

Djikstra's algorithm to compute shortest paths using at least k edges

I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s ...
6
votes
0answers
90 views

Algorithms to generate random nowhere-neat rectangulation?

I want to generate random rectangular partition of a given $m*n$ rectangle under the constraint that it must be nowhere-neat partition. Nowhere-neat partition means that a dissection of a rectangle ...
0
votes
0answers
24 views

Algorithm to find possible variables in multiple connected equations

I am new here. I am trying to come up with an algorithm that can give me the unknown values in the following equation. ...
0
votes
0answers
38 views

Unite a forest if you know each tree's parent

I have a forest of Tries, each forest[i] is a Trie. forest[0] contains the root node to all the others. I want to recursively ...
1
vote
1answer
21 views

Explanation for the proof “Every 2-thread consensus protocol has a bivalent initial state”

From the book 'the art of multiprocessor programming': A protocol state is bivalent if the decision value is not yet fixed: there is some execution starting from that state in which the threads ...
2
votes
0answers
29 views

Heuristic for searching for solutions on an 8-puzzle variant with non-unique tiles

I'm trying to perform an A* search on a particular N-puzzle variant in which some tiles are identical. More specifically, assuming an $m \times m$ grid, there are m colors with m tiles of each. The ...
0
votes
0answers
9 views

loop invariant help

Hi I'm trying to identify my loop invariant in my modification of this graph search algorithm to prove the correctness. We're given a graph where each vertex has a weight of either a 0 or a 1. This ...
1
vote
1answer
26 views

Repeated String Match: need help to understand the maximum number of repeats needed to be looked at

There's this question on LeetCode (link): Given two strings A and B, find the minimum number of times ...
-1
votes
1answer
30 views

Is there any way to find the nodes in the each subtree of each node having distance equal to height of the subtree?

We are given a tree of N nodes from 1 to N where node 1 is the root of the tree. For each node i from 1 to N, you have to find the numbers of nodes which are in the subtree of i and are at distance ...
1
vote
1answer
27 views

Recurrence Relation Mergesort

I was reading Algorithms 4th Edition by Sedgewick et al. and I found this statement when discussing about the analysis of mergesort: The number of compares is at most n and no less than $\lfloor n/...
1
vote
1answer
33 views

How to correctly describe this action, deleting an edge that “shortcut” some vertices

Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below: 1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
1
vote
2answers
385 views

Why CLRS example on residual networks does not follows its formula?

I am learning algorithms to solve Maximum Flow problem by reading the CRLS book and confused by the following figure: That is: A flow in a residual network provides a roadmap for adding flow to ...
-1
votes
0answers
35 views

divide a gold bar into minimum number of pieces so that it can be divided equally among 7,8 or 9 people

One night nine gangsters stole a gold bar. When the time came for dividing the bar, they faced a problem: two of the criminals put guns to each other's faces. Now it's up to fate whether one of them ...
1
vote
0answers
31 views

Algorithm for detecting a finite limit of time-series numbers

Is there a well known and proven algorithm to find the TOP (finite) limit of a set of points, which are time based metrics? I'm looking for an existing implementation, in order not to invent the wheel ...
1
vote
1answer
31 views

Interpretation of an asymptotic notation

Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
1
vote
0answers
18 views

maximum matching in general graph [duplicate]

How to justify the role of blossom in Edmond's blossom algorithm for maximum matching? odd cycles also can be covered in augmenting path.
3
votes
2answers
251 views

The Clique vs. Independent Set Problem

Suppose you have an undirected graph $G = (V, E)$, known to both Alice and Bob, Alice gets an independent set of $G$. Bob gets a Clique $B ⊆ V$. Is there any algorithm in $O(\log^2 n)$ bits that ...
1
vote
1answer
27 views

Turing machine algorithms for $\{0^n1^n\}$ using one and two tapes

I was tasked with finding a way to decide the language $A=\{0^k1^k \mid k\ge 0\}$ in $O(n\log n)$ time, and then to implement it on a deterministic Turing machine with one tape. Additionally, I was ...
2
votes
1answer
40 views

Task Distribution Algorithm

Different machine has different efficiency on different tasks, like: ...
0
votes
1answer
77 views

Dynamic programming approach for finding perfect square subsequence

Given an array of numbers $a_i$ with length $n$, such that $0<a_i<30$, how can we find the number of subsequences that the product of numbers is perfect square. I have tried to find a dynamic ...
0
votes
1answer
22 views

How does KMV (k minimum value) perform set intersection better than hyperloglog?

In this paper, the author seems to suggest that theta sketches(a variant of kmv) outperforms hyperloglog in cardinality estimation on the intersection of n way streams. ...
0
votes
1answer
44 views

How to find the best exploration parameter in a Monte Carlo tree search?

I've developed a Monte Carlo tree search algorithm in checkers. Here is my question. What should be the value of $C$, the exploration parameter in the following formula described in Monte Carlo Tree ...
1
vote
2answers
57 views

Assigning books to boxes

I am trying to model the following problem correctly as a min-cut network flow problem. I have $n$ books and 2 boxes. I also have books that I know must go in one of the two boxes. In addition, each ...
0
votes
0answers
75 views

Maximum matching blossom algorithm

https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf Why do we use blossom contrast in maximum matching? The examples that I have seen can easily be solved by just ...
1
vote
1answer
59 views

Which algorithm is this?

I'm looking for someone who can tell me which algorithm this is and help me to clearify what the variable mean. $g_j$ : the shortest path length from $1$ to $j$ $t_{i,j}$: the length from $i$ to $j$ $...
3
votes
1answer
40 views

Reversible Merge of Integer Hash Values

Context: I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's ...
4
votes
2answers
356 views

Linear Path Optimization with Two Dependent Variables

Alright, so this is a fairly interesting problem I have but also slightly difficult to explain so I will try my best. There are two runners on a line that goes from $x=0$ to $x=100$. The two runners ...
1
vote
0answers
21 views

What approach to solve an open shop problem with following constraints

Say we have an open shop scheduling problem with following constraints : No wait-time between operations of a job Multiple job types (meaning each job type has different set of operations eventhough ...
2
votes
1answer
23 views

Consensus/ranked ordering algorithm

Say I have a set of numbers, for example {1, 2, 3, 4, 5}. Is there an algorithm that allows these numbers to be put into a consensus ordering based on a ranked vote?...
3
votes
1answer
43 views

Distinct elements count of huge multiset

I know that HyperLogLog can approximate the distinct elements count of a huge multiset but I was wondering if it was possible, using a method I saw mentioned on an IRC channel, to get an exact answer ...
1
vote
1answer
30 views

Finding the Range of Solutions for KSum Variation

Preface I asked a question before where I was looking to understand the complexity class of the following problem: Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such ...
3
votes
1answer
41 views

Maximal Minimum Spanning Tree by Removing $k$ Edges

The problem is as follows: Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0 < k < |E| - |V| + 1$. Describe and analyze and efficient algorithm to remove ...
1
vote
2answers
74 views

When binary search algorithm will be $O(1)$

I had an exam today, and there was a question that said: Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $O(\log(n))$. I'm ...
1
vote
1answer
36 views

A problem to maximize the number of edges in a cycle while minimizing the total weight

I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this? ...
0
votes
1answer
93 views

Maximize the sum of chosen numbers

I have 2 problems that derive from a simple problem. I'll explain the simple one with the solution I found and after that the modified problem. Suppose there is a game with 2 players, A and B and a ...
0
votes
1answer
23 views

Loop-Invariant for a program fragment

Q) Consider the following program fragment: var x,y:integer; x:=1; y:=0; while y < x do begin x:=2∗x; y:=y+1; end; For the above fragment , ...
1
vote
0answers
29 views

Divide and conquer algorithm to find points beneath certain (x, y) coordinates

Let's say you have a bunch of points on a cartesian plane. For a few of these points you would like to find how many of the other points lie within their (x, y) coordinate, see below for an example: ...
0
votes
1answer
24 views

Coprimes satisfying a pair

We know that number of coprimes less than a number can be found using Euler's totient function. But if there are two numbers $p$ and $q$ and we need to find number of numbers less than $q$ ...