Questions tagged [greedy-algorithms]
Questions about algorithms that make at each step the locally optimal choice.
1
vote
2answers
45 views
Putting as many items as possible with weight and size limit
I am trying to design a greedy algorithm that has to take in multiple factors when making a greedy choice.
Any item has an item weight of Iw and item size of <...
2
votes
1answer
73 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 $...
0
votes
0answers
18 views
Greedy Approach without constraint and a feasibility function
We know that the Greedy Approach in general, picks an element from a set of candidate elements that satisfies a predefined criteria (selection function) and is added to the solution if it satisfies ...
1
vote
1answer
37 views
Carpet into Box
Given a carpet of size a * b [length * breadth] and a box of size c * d, one has to fit the carpet in the box in the minimum number of moves. A move is to fold the carpet in half, either by length or ...
3
votes
1answer
42 views
Length of shortest codeword in Huffman encoding
Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1?
I thought of 2 cases where this ...
1
vote
1answer
29 views
Minimum Spanning Tree with one particular edge minimised(continued)
I have recently encountered a coding problem, specifically, the CCC problem S4.
In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each ...
1
vote
2answers
47 views
Minimum spanning tree such that one edge can be minimised
During a computer coding exam, I have encountered such a problem.
Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...
3
votes
2answers
86 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 ...
1
vote
1answer
46 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
146 views
Is my proof of my greedy algorithm to find subsequence correct?
Credit to KleinBerg and Taros Book
Some of your friends have gotten into the burgeoning field of time-series data mining, in which one looks for patterns in sequences of events that occur over time. ...
-2
votes
1answer
47 views
Number Theory Problem from Local Selection Contest EPFL | ETHZ
This was a question from the 2016 local (selection) contest in ETHZ, You have a high-precision alarm clock with three operations:
1) reset wake-up time to midnight (00:00:00.000000)
2) modify the ...
2
votes
1answer
52 views
Greedy Solution for Selecting Prefix Sum
Given $n$ arrays. Each has size of $h$. Let $a_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a_{i, j}$, you have to ...
0
votes
0answers
30 views
findining the smallest sum of squared lengths of the intervals I_{k}
Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is $Z^{+}$ . The goal is to find k intervals
$I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one ...
2
votes
4answers
127 views
A greedy algorithm for the bottle filling problem
(There’s no need to write the algorithm, I just need help with the greedy choice).
Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We ...
0
votes
1answer
48 views
Given n drinks, find optimum way to spend money if for each drink the price and the expiration date is given
Let's say we are given $n$ types of drinks, integer $m$ representing the budget we have and integer $d$ representing the cost of delivery when we order some drinks. For each of the $n$ drinks we are ...
0
votes
1answer
60 views
How this proof of fractional knapsack works?
I don't understand a step in my book proving the fractional knapsack problem:
Let value of items $v_1\ge v_2\ge \dots\ge v_n$, and assume $X=\langle x_1, \dots,x_n\rangle$ are the solution by ...
1
vote
2answers
54 views
set cover where only certain special subsets are allowed
I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
1answer
37 views
Greedy Algorithm Proof Min Swaps
Problem to get the min. no. of swaps required for arranging pairs togethe.
There exists an array of size 2N with integers ranging from 0 to 2N-1 arranged at random. Each integer is paired with ...
1
vote
0answers
26 views
directed edges in an undirected graph [duplicate]
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 the total outdegree of every vertex is even.
For example, consider a graph ...
1
vote
1answer
80 views
What is the optimal way to solve the following optimization problem
You are given a function $F$, which can take one or more positive integer operands.
Let $L=\{a_1,a_2\ldots a_n\}$.
We need to compute the function $F(L)$ using the least number of transformations/...
0
votes
2answers
38 views
MST Proof (Kleinburg & Tordos)
Consider the Minimum Spanning Tree Problem on an undirected graph
G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all
be different. If the costs are not all distinct, there can in ...
1
vote
1answer
108 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?
1
vote
1answer
89 views
Solving “coin exchange” for coins of power values by greedy algorithm
When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$?
For ...
0
votes
1answer
43 views
interval scheduling algorithm
can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this ...
1
vote
1answer
49 views
Variant of interval scheduling with varying task durations
I am probably just missing the correct term for my problem to find the solution but here it goes:
I have a set of tasks with a given duration and an interval for each task in which it has to be ...
1
vote
1answer
66 views
Algorithm to organize a tournament where the team componentes change each round
So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
2
votes
0answers
43 views
Weighted Sorting Algorithm
Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation.
Is there any ...
1
vote
1answer
159 views
Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?
Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
1
vote
1answer
96 views
Correctness proof for greedy algorithm based on ratio
I've an issue stated as follows:
We have 10000 jobs to do, each with some length $l_i$ and weight
(importance) $w_i$. Our goal is to arrange the schedule of doing these
jobs (in other words, ...
1
vote
2answers
88 views
FInding the combination with the least number of elements from and array of integers, given an integer sum
I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
1answer
72 views
Minimum Number of Integers From a List that Add up to N (Dynamic Programming)
A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically:
Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where ...
3
votes
2answers
113 views
Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?
I came across this problem in Tim Roughgarden's course on Coursera:
In this problem you are given as input a graph $T=(V,E)$ that is a
tree (that is, $T$ is undirected, connected, and acyclic). A ...
1
vote
1answer
278 views
Proof of a greedy algorithm concerning “Buy and Resell Problem”
"Buy and Resell Problem" can be described in the following way:
There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from ...
2
votes
2answers
542 views
Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value
GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T.
This question is a simplification of ...
2
votes
0answers
59 views
Maximum number of non-overlapping rectangles where each contains a minimum number of points
Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap. Each point is distinct from every other ...
2
votes
1answer
56 views
Designing a greedy scheduling algorithm for two sets of non-mutually exclusive tasks
Lets just say I have two lists of the running time of tasks A and B. Formally, I would have:
A = {a_1, a_2, a_3 ... a_n}
B = {b_1, b_2, b_3 ... b_n}
I can only ...
1
vote
1answer
32 views
Is there a generic algorithm to optimally combine elements by some arbitrary scoring method?
I'm looking for a generic algorithm to optimally combine elements of a list. I'm not sure if it even exists, but I believe some kind of divide-and-conquer algorithm could exist. In my specidifc case, ...
1
vote
1answer
48 views
Candy Problem for k size window
I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) ...
2
votes
1answer
54 views
Mimimum spanning tree with a constraint on number of certain types of edges
I have the the following problem.
Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning ...
1
vote
1answer
44 views
what is the significance of the word “Sub-problems” in Greedy Method?
With respect to Dynamic Programming we make a statement that :
Greedy algorithm have a local choice of the sub-problems whereas
Dynamic programming would solve the all sub-problems and then ...
0
votes
1answer
182 views
Can Tug of war problem be solved by DP or greedy approach?
For problem explanation: https://www.geeksforgeeks.org/tug-of-war/
I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ...
2
votes
1answer
58 views
How to restore diagonal-symmetric matrix that has been shuffled?
I have a square matrix M, which originally looked like this:
133 199 101 121
142 133 199 101
156 142 133 199
108 156 142 133
(so symmetric around the diagonal). ...
1
vote
1answer
97 views
Why this greedy algorithm does not return the optimal solution to this NP-hard problem?
Problem:
In the generalized assignment problem with unit-value items, there are $m$ bins of capacity $C$ each. There are $n$ items where each item $i$ has weight $w_{ij}$ with bin $j$. The objective ...
2
votes
2answers
65 views
Shortest travelling cost if we have bunch of points in 2D plane
I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane ...
0
votes
1answer
39 views
Minimum square side length to enclose n circles of radius r
I thought of a problem but have no idea how to solve it. The problem is as follows:
Given 2 numbers, n and r, find the side length (S) of the smallest square that encloses n circles each of radius r ...
0
votes
1answer
211 views
proof of correctness for greedy knapsack algorithm
I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement ...
1
vote
1answer
170 views
Does an algorithm exist for scheduling jobs on two processors?
I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found ...
1
vote
1answer
35 views
Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit
I have such a task at university:
we have n tasks, i-th of them can be done between moment b(i) and e(i). If we decide to perform a task in moment x, we finish performing it in moment x+1. We can ...
0
votes
0answers
73 views
How to approach solving this variation of the Job Scheduling Problem?
Question: Given N processes with Arrival times and Processing times, calculate and print minimum number of CPUs required if maximum allowed Turnaround time for each process is 10 units.
Turnaround ...
0
votes
1answer
22 views
Interval Scheduling Confusion
I am reading some notes about interval scheduling. I gives the following diagram:
and states that:
r2 is compatible with r3, while r2 and r1 are conflicting. Similarly, the set {r1, r3, r4} is ...
