Questions about algorithms that make at each step the locally optimal choice.
1
vote
1answer
46 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
26 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
38 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 ...
0
votes
0answers
37 views
How we can minimize number of boxes for packing objects
Imagine we have n objects with different weights.
We know the order in which objects come into the packing machine. Packing machine have two boxes, their capacity are equal and constant. When an ...
0
votes
0answers
32 views
Designing a greedy algorithm concerning “Machine Allocation Problem”
There are $m$ machines and $n$ tasks. Each task $i$ contains a time interval $[a_i,b_i]$ and a specified machine $c_i$ denoting that we should choose one day $a_i \le t_i \le b_i$ ($t_i$ must be an ...
1
vote
1answer
46 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
27 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
71 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
34 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
1answer
29 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
57 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
1answer
51 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
238 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
252 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
47 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
50 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
28 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
45 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
42 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
31 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
69 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
37 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
73 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
58 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
37 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
96 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 ...
0
votes
1answer
113 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 ...
0
votes
0answers
51 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
21 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 ...
0
votes
1answer
52 views
Efficient traffic allocation
Users can be assigned to one experiment on my site. I have an API that developers use to trigger logic for each experiment. They call ExperimentEngine.run() to trigger the code logic for the ...
0
votes
0answers
52 views
Gas Station Problem Variation
My friend challenged me with this question. I've enjoyed two weeks with ocassional problem-solving sessions but it became such bug in my head that I needed to sign up :)
We have:
car with fuel ...
0
votes
0answers
30 views
Algorithm to check if exists a valid streaming sequence in O(n)?
Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 ...
1
vote
0answers
53 views
Is there any greedy solution for bitonic tour
I have found dynamic solution for Bitonic tour but I could not find any greedy approach for this problem. Is it possible to solve it in a greedy manner?
2
votes
1answer
54 views
Activity Selection and Matroid Theory
Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property.
I was trying to understand this. So far, I was ...
1
vote
1answer
123 views
How does the nearest insertion heuristic for TSP work?
In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson ...
0
votes
2answers
65 views
Greedy Heuristic for the Traveling Salesperson Problem
We're studying Heuristic in my Theoretical CS class, more specifically Greedy-Algorithms for the Traveling Salesperson Problem. The first one is the "next neighbor heuristic", where you start at any ...
3
votes
1answer
265 views
Find the minimum set of intervals for given set of numbers
For any given set of real numbers, find the minimum set of intervals with length 1 that include all elements. For example, for the set: $${\{1.5,2.3,2.4,2.5,2.8,3.3,3.6,3.8}\}$$
the answer is $${\{[1....
1
vote
1answer
43 views
What do we call a greedy algorithm that tracks the best $n > 1$ solutions?
A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima.
To avoid this problem, we may keep track of the best $n > 1$ ...
1
vote
2answers
60 views
Online set filling with redistributions
Edited: Suppose we have 4 sets $A, B, C, D $ which can can hold a maximum of two elements, each.
Now, elements ($E_i$) arrive serially with properties such as:
...
1
vote
0answers
75 views
Algorythm for creating Number-Rows
Given is a list of numbers.
Now you build different permutations of that list while there must not be two permutations where the sum of the numbers from any point of the row to the end/beginning is ...
1
vote
1answer
69 views
Why does the given solution to this problem works? How can it's correctness be proven?
This is a question asked in Adobe interview:
Given heights of n towers and a value k. We need to either increase or
decrease height of every tower by k (only once) where k > 0. The task
is to ...
0
votes
0answers
60 views
Two Pointer Algorithm Proof (Greedy) Roadblock
I am practicing some competitive programming problems and encountered a version of the two pointer algorithm that I got stuck trying to prove its correctness. Here is the outline.
Input : An array of ...
2
votes
1answer
89 views
Algorithm for finding the binary sequence with no 3 consecutive ones and with highest point?
The problem is, we are given points $p_1,\ldots,p_n$ on positions of a length-$n$ binary sequence $x_1,\ldots, x_n$, and if the $i_{th}$ position of a sequence is $1$, then we "earn" $p_i$ points. So ...
0
votes
0answers
29 views
Table of incompatible turns in an intersection (steps to writing a program)
I just began reading Data Structures and Algorithms (Aho, Hopcraft, and Ullman). At the beginning, there is an example that discusses designing a traffic light for a complicated intersection of roads.
...
0
votes
1answer
204 views
Will a Greedy algorithm give a correct result for minimum partition?
Will a greedy method of picking the item that causes the largest difference each time lead to the optimal result in the minimum partition problem?
Let's say I have a set $\{a_1,a_2,a_3,...a_n\}$, now ...
0
votes
0answers
77 views
Time Management Scheduling Problem
I am interested in solving a problem related to time management.
Suppose you are given $N$ intervals, where the $i$th interval has start time $s_i$ and end time $e_i$, as well as amount $a_i$. Each ...
1
vote
1answer
60 views
Can LP for matroid polytopes be solved using the greedy algorithm?
For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, ...
0
votes
2answers
168 views
greedy algorithms - minimizing total payment
The question:
I want to buy $n$ books. In the book store there's a big sale according to which, if you buy three books, then the cheapest book in any triplet costs only 20% of its full price. Let $...
1
vote
1answer
19 views
Group values up to a threshold and minimize groups
Given a threshold $t$ and a list of numbers $N$. $\forall n \in N: n \leq t$
Now group the numbers so that the sum of the numbers $s$ is lower or equal $t$. Minimize the amount of groups.
Example: $...
1
vote
2answers
243 views
Stable matching problem is greedy or Dynamic?
Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.
