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
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
45 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
42 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
18 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
12 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
36 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
31 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
34 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
35 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 ...
2
votes
2answers
53 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
9 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
13 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
83 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
35 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
61 views

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

What are other algorithms that use the divide-and-conquer paradigm aside from merge sort and quicksort?
0
votes
1answer
27 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
41 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
22 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, ...
1
vote
1answer
42 views

algorithm to find all values that occur more than n/10 times

I took an algorhytm course on coursera and there some optional questions for student enrichment. I can't solve the following task: Decimal dominants. Given an array with n keys, design an algorithm ...
0
votes
0answers
26 views

How to modify Bellman-ford to account for a max-number of edge-traversals allowed

How can i modify Bellman-ford to account for this restriction?: only allowed a certain number of edge-traversals (k) to go from source-node to target-node? The algorithm runs on graphs with: 0, 1 ...
0
votes
1answer
13 views

In the shor's quantum circuit, what is the transformation of the modular operating gates?

I know different parts of this circuit, just I have a problem with that part that I circled in picture. I want to know the function of that part. If you have useful information about it, please ...
3
votes
1answer
440 views

How binary search works in real world scenario?

In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers. But in real world, we may search for a name of an employee ...
1
vote
1answer
20 views

Color a graph using k colors, k>4, with the most equal distribution of colors

Given a planar graph G with $N$ nodes, 4 colors are enough to color each node, so that adjacent nodes have different colors. Let $k > 4$. Is there an algorithm to color the nodes with $k$ colors, ...
3
votes
1answer
67 views

Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time

Given a parameter $k$ and an array (not sorted) of length $n$ return all values which repeat more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time. I've managed this in $O(nk)$ time, but can't ...
4
votes
2answers
48 views

Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

I'm struggling with the following question: Let $\langle a_0, a_1,\dots,a_n\rangle$ be a sequence of real numbers, and let $ M = \max\{a_0, a_1, .... a_n\} $ and $ m = \min\{a_0, a_1, .... a_n\} $....
0
votes
0answers
18 views

Find xor sum of all pairs raised to power of 3

We are given array $A$ of $N$ integers each in the range $1 \leq A_i \leq 2^{30}$, that is we can write each integer with at most 30 bits. The target is to compute $\sum_{1\leq i \leq N,1\leq j<i} (...
1
vote
1answer
42 views

Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first?

I am trying to implement the nearest insertion TSP heuristic. However, I am wondering if it matters which node I insert into the subgraph first. For example, should I start with one node; calculate ...
0
votes
0answers
11 views

KMP Number of Comparisons

So I have a homework assignment where I'm supposed to find out the total number of comparisons (both successful and unsuccessful) the will be made by using the KMP sting matching algorithm when ...
-2
votes
0answers
16 views

weighted median algorithm

what is the general idea of this algorithm for example if I have an array s={3,4,8,5,7,2} with weight for each is w={1,2,3,4,5,6} how the algorithm will calculate the median weight? it could be by ...
0
votes
0answers
23 views

Help with understanding Kleitman–Wang algorithm

I have a problem in which I need to solve the realization for a directed graph when I am given the in and out degrees for n number of vertices. A hint was to use network flows. I know that the ...
1
vote
1answer
20 views

Find total number of assignment in the worst case?

I have this algorithm Algorithm (A[1..n]) for i <- 1 to n do if (A[i] < 0) then A[i] <- 1 * A[i] End if End for I ...
1
vote
1answer
27 views

Linear ordering of all subsets of size k

I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into ...
0
votes
1answer
15 views

Forming polylines from a list of individual lines

I want to optimize a SVG path made entirely of lines. Given a list of lines, each made of two 2D points connected together, I want to find an equivalent list of polylines. For example: ...
0
votes
2answers
36 views

Formula for finding number of colors to color a map such that no two adjacent counties have the same color

Is there a formula for determining the minimum number of colors to color a map with n counties such that no adjacent county have the same color?
1
vote
1answer
32 views

Amplification for Randomized Algorithms

I'm trying to show Amplification works for randomized algorithms, and for randomized approximation algorithms. Amplification for randomized algorithms: Given a randomized algorithm with time ...
0
votes
0answers
28 views

Help with understanding the type of task

I am stuck with a problem I want to solve, and I cannot understand which approach to use to solve it efficiently. The problem sounds as follows: "There are initial (x,y) = (0,1). We can move left or ...
-1
votes
0answers
5 views

how do I add a list with the same variable to another list with that list already being there? Python [migrated]

I'm doing my programming coursework, and I've come across an issue gamecentre1 = [winnerscore, winner] organise = [] organise.extend([gamecentre1]) from operator import attrgetter, itemgetter ...
1
vote
0answers
52 views

How does prefix summing the count histogram in counting sort result in an array of output indices?

My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is: ...
0
votes
0answers
20 views

Find largest subset of compatible indices using $O(n^2)$ DP algorithm

Past year paper question We are given a set $S$ of $n$ pairs of real numbers $S = \{(a_1,b_1),...,(a_n,b_n) \}$ such that $a_1 \leq a_2 \leq ... \leq a_n$. We say that a pair of indices $(i,j)$ is ...
-1
votes
0answers
14 views

Is it possible to convert a CNN into a Decision Tree?

transformation of Convulutional neural networks into Decision Tree possible or not?
2
votes
1answer
27 views

Does simultaneously finding max/min in array of coordinates by x and y increase comparisons?

I have an unsorted array of (x,y) coordinates and need to find the min/max for both (x) and (y) separately so that I can build a bounding box using $O(\frac{3n}{2})$ comparisons. If I use this ...