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.

0
votes
0answers
2 views

How can I find an object with a certain property value in a recursive branched nest of objects?

In my example, all objects represent layouts with arrays of components where components can have arrays of components themselves. A component does not always have an array of components and it also ...
1
vote
1answer
4 views

Approximation factor shorthand clarification

I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the approximation factor. I know that an approximation ...
1
vote
0answers
12 views

Determining a value in an algorithm on its first run

I was given the following algorithm as a solution to one of my problems. However, I am baffled at understanding how c' is ever initialized. The first if statement can never be reached, as c' is never ...
3
votes
2answers
62 views

Is it possible to write a program that calculates an algorithm's time complexity? [duplicate]

Title is self explanatory. I have searched here on this site and haven't found any discussion about this. Is it somehow related to Turing's Halting problem (which is undecidable)?
0
votes
0answers
11 views

Distribution of pointer keys in a Skip-list node

Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$. We construct a skip list over the keys. Now if I pick a key (e.g. 31 in the ...
0
votes
0answers
21 views

Joint Probabilistic Data Association Filter (JPDAF)

I am trying to learn about data association algorithms, and I came across the Joint Probabilistic Data Association Filter (JPDAF). I have read about the algorithm from multiple papers, and am looking ...
-3
votes
0answers
16 views

Need algorithm to determin whether A>B>C>D expressions are legal [on hold]

I need to define function parameter priority, such as function Func(A, B, C, D, E) Others can write rules to define this priority, I need a algorithm to check ...
0
votes
0answers
11 views

Finding the intervals containing the query interval

Intervals are represented by two numbers, let's say integral numbers. At the beginning we have sequence of given intervals, for example [1, 5], [4, 8], [3, 5]. After that, we have sequence of queries, ...
0
votes
0answers
57 views

Convert undirected graph to directed graph with specific condition

undirected graph is given which has M edges and N vertices we have to convert every edge from u-v to u->v or v->u such that indegree of every vertex is even.Which method or algorithm is suited for ...
1
vote
1answer
30 views

How to minimize the average distance between pumps and cities?

There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k...
-1
votes
0answers
15 views

Context free grammar to Turing Machine

I have the following problem: Draw the diagram of a TM for the language : of all binary strings of odd length with a 1 in the middle. My approach to this in CFG is as follows: ...
0
votes
0answers
23 views

Why it is important to understand when a particular problem is algorithmically “unsolvable.” How should I deal with this type of problems?

So I learned that there are some problems that cannot be solved in computer science but I want to know why is it important to understand the unsolvable algorithm and how should I deal with it.
1
vote
1answer
9 views

Reducing optimization problem to its decision version

There are two problems that need to be solved. Both problems use a compatibility matrix $C$, where $C[a, b]$ is how compatible students $a$ and $b$ are. (1) Given an $n \times n$ compatibility matrix ...
0
votes
2answers
30 views

Sorting in a Priority Queue

Does a priority queue Queue<K,V> always sort its elements based on the value of each element or its key? I know than the priority in the queue is based on ...
3
votes
3answers
86 views

Undirected graph with exponential number of simple cycles

Hey I am new to graph theory and this question has me stuck for hours. What is an example of undirected graph with n nodes where the number of simple cycles is exponential in n. I was looking at ...
0
votes
0answers
4 views

8 puzzle admissible heuristic where tiles are in correct position

For the 8 puzzle problem, it has been proved that if h(n) = number of tiles on wrong place. h(n) is an admissible heuristic as every tile which is in wrong place must be moved out at least once. But ...
1
vote
2answers
44 views

Smallest possible sorting network for given permutation

I need to build a sorting (comparator) network using comparators for a specific permutation on a set $x_1, \dots, x_n$. The solution should not be a general sorting network that sorts every ...
0
votes
0answers
16 views

Feasible algorithm to find interpolating complex polynomial based on absolute value

Consider a complex degree-$(n-1)$ polynomial $p(z) = \sum\limits_{i=0}^{n-1} a_i z^i$. Given a number $0 > m > 2n$ of positions in the complex plane with absolute value requirements, i.e. $|p(...
0
votes
0answers
11 views

Find the direction of monotone polygon (if exists) in linear time

Implement a program that checks if there is a direction in which a simple polygon is monotone and,in that case, reports such a direction. Upper bounds: O(n) time, where n is the size of the ...
0
votes
2answers
36 views

Shortest distance from multiple points to one point

I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $v_1,v_2,\dots,v_r$ be the nodes on a graph with distance $d_1,d_2,\dots,d_r$ to the ...
0
votes
1answer
43 views

Counting the number of multiples of number A that perfectly divides the number B

What is the best way of counting the number of multiples of number A that perfectly divides the number B. This is the sub problem for one of the questions I am solving on codechef. This is the best I ...
0
votes
0answers
19 views

Aproximation of longest path in undirected graph from given point

I'm looking for a algorithm suitable to find possibly the longest path (by count of nodes) in given undirected graph and starting node in some time resime. Is there any know algorithm for that?
0
votes
0answers
13 views

Find the Maximum rows having all ones in the binary if you are allowed to toggle columns in the matrix for exactly k number of times

A binary matrix of nxm is given, you have to toggle any column k number of times so that you can get the maximum number of rows having all 1’s. for eg, n=3, m=3, ...
-1
votes
0answers
14 views

Use the maximum-flow, minimum-cut theorem and the Ford-Fulkerson algorithm

Consider a city with m parallel horizontal streets and n parallel vertical avenues. These lines cross in m × n intersections. On k ∈ {1, . . . , m × n} of these intersections, special checkpoints are ...
0
votes
0answers
44 views

Intuition behind Floyd-Warshall being faster

I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm: Let $dp[i][j][n]$ denote the shortest path from $...
0
votes
0answers
39 views

Graph Implementation Problem - Shortest Path/Dijkstra's (?)

Have this small graph problem to do for today, was wondering if anyone had any possible solutions/insight for it. Given two containers, one of which can accommodate a liters of water and the other b ...
1
vote
1answer
17 views

Tracing a polynomial algorithm for the problem of maximum-weight independent set

It should be a very easy question, but I am a little bit confused. According to party optimization post, the Maximum-weight Independent Set for trees can be found in the poly-nominal time using ...
0
votes
0answers
11 views

4 Points with 2 different colors and 2 Lines partitioning the plane - Combinatorial geometry algorithm problem

We have 4 different points on the x-y plane and we know NO three of them are collinear. The coordinates are $p_1 (x_1 ,y_1) , p_2 (x_2 , y_2) , p'_1 (x'_1 , y'_1) , p'_2 (x'_2, y'_2)$. The first two ...
0
votes
0answers
10 views

Yao's Minimax Principle with error

In Yao's paper proving Yao's principle, he equates the lower bound of a randomized Las Vegas algorithm with the expected run time of the best deterministic algorithm on the worst input. He goes on to ...
0
votes
1answer
23 views

Minimizing sum of recursive pairwise sums

What is the best algorithm for this? We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at ...
0
votes
1answer
34 views

Proving that a spanning tree of graph is not a minimum

Let $G$ be an undirected and connected graph. Let $T$ be a spanning tree of $G$ with edges weights: $w_1 \le, w_2 \le ... \le w_{n-1}$ which are responing to the edges. $e_1,e_2,...,e_{n-1}$. Now I ...
0
votes
1answer
29 views

Distribute a number of tasks into multiple days (scheduling)

This is about scheduling. I have N tasks of different length and I have to schedule them into M days. Indeed, each day has a max capacity (usually they are the same). Parameters are tight in the sense,...
0
votes
1answer
33 views

How can I create zero-collision-free strings more efficiently?

$S$ is a symmetric set If $|S|=3$ such that $S=\{n_1, n_2, n_3\}$ then $n_1+n_2 = n_3$, If $|S|=4$ such that $S=\{n_1, n_2, n_3, n_4\}$ then $n_1+n_3=n_4$ and $2n_2=n_4$, If $|S|=5$ such that $S=\{...
0
votes
0answers
46 views

What will be an O(n) solution for this?

Suppose a given piece of work can be done at two processors. One at r and another at v. The job can run only at one processor at ...
0
votes
1answer
29 views

More efficient maximum bipartite matching

I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and ...
0
votes
0answers
12 views

How to unify two sources

Suppose we have two independent algorithms. Each algorithm solves the same problem, which consists on answering a multiple-choice question. To be specific, each algorithm will return a list of ...
2
votes
2answers
49 views

Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm'

I'm working on solving an algorithm problem defined as follows (important parts in bold): Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a ...
0
votes
0answers
8 views

How do I extend bellman-ford, to limit the number of edge-traversals (k), that are permitted?

How do I extend this bellman-ford, so I can limit the number of edge-traversals (k), that are permitted? And no, it's not just a matter of limiting the outer loop to run k times, since BF updates ...
0
votes
0answers
11 views

Fairly partitioning workload using network flows

I have the following question to answer: A fraternity has n student members. In Fall’18, m courses are being offered and for each course i, some subset $S_i$ of the fraternity members are taking the ...
1
vote
1answer
12 views

Confusion About Min-Cut Probabilities

Currently going through a video on Counting Minimum Cuts by Tim Roughgarden. $(A_{i},B_{i}) = \big((A_{1},B_{1}), ..., (A_{t},B_{t})\big) \forall i \in \Bbb{R}$ $P\big((A_{i},B_{i})\big) \geq \frac{1}{...
3
votes
2answers
78 views

Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?

Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$. Now let $T'$ be some other spanning tree of $G$ (...
1
vote
1answer
33 views

Getting N top scores from a matrix

I start with a matrix, lets say 4x4. So I want the N top scores, with the sum of one element of each row. For example: ...
0
votes
0answers
10 views

How to use HITS algorithm in a web search engine?

I implemented the classical non-weighted converged version of HITS algorithm. I create a root set and a base set from the root set and then I applied the HITS algorithm and got the authorities and ...
0
votes
1answer
28 views

Showing that algorithm has STOP property and finding its computational complexity function

The task is to show that given algorithm has STOP property and to find its computational complexity function. $\alpha:$ $n \ge 0$ ...
0
votes
0answers
4 views

When does a task inherit the priority ceiling in Multiprocessor PCP

In detail: does a task inherit the priority ceiling, only when it is executing the critical section or already when it is selected to run the critical section next (after being blocked for example). I ...
-1
votes
1answer
60 views

Applications of divide-and-conquer outside of merge sort and quicksort [on hold]

What are other algorithms that use the divide-and-conquer paradigm aside from merge sort and quicksort?
0
votes
1answer
25 views

Find the cheapest combination of raw foods that fulfill nutritional requirements

I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples ...
0
votes
2answers
38 views

Big O notation for finding duplicates in a list using binary search

I've written an algorithm to find duplicate integers in a sequential list of integers, but I'm running into issues when trying to calculate it's worst case complexity. Given a sequential list of ...
1
vote
1answer
29 views

Greedy algorithm to find Minimum Dominating Set in a tree

Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?
0
votes
2answers
21 views

How to traverse a graph in reverse with dfs

So I'm watching Stanford's algorithm lectures and I'm on Kosaraju's algorithm. In the lecture, the algorthm was given in 3 steps: calculate the graph with all arcs reversed, run dfs on reversed graph, ...