greedy Questions
1
Solved
Consider a question to find a minimum dominating set of an interval graph. In the context of interval scheduling, it is converted to the question below:
There are multiple intervals which may or m...
1
Solved
I am trying to solve the following SPOJ problem.
The input is:
1. Total weight of a certain amount of money in coins,
2. values and corresponding weights of the coins of used currency.
The goal...
5
Solved
What's the difference between greedy and heuristic algorithm?
I have read some articles about the argument and it seems to me that they are more or less the same type of algorithm since their mai...
Roentgenology asked 3/2, 2014 at 20:26
3
Solved
I came across this problem quite recently.
Suppose there are n points on x-axis, x[0],x[1] .. x[n-1].
Let the weight associated with each of these points be w[0],w[1] .. w[n-1].
Starting from any ...
Nimbus asked 19/2, 2014 at 9:13
2
I have an array of n service stations D[] on a highway such that D[i] is the distance of the station i from the start of the highway.
I also have an array of costs C[] such that C[i] is the cost o...
Tropo asked 27/1, 2014 at 6:41
1
Solved
On Wikipedia page it is said that greedy algorithms are ideal only for problems which have optimal substructure.
Questions:
What is optimal/non-optimal substructure?
What is local and global opt...
2
Solved
I have two sentences as input. Let's say for example:
<span>I love my red car.</span>
<span>I love my car.</span>
Now I want to match every textpart inside the span-tags ...
Newmown asked 18/9, 2013 at 7:16
4
Solved
I'm having trouble figuring out my last section of code for a Dynamic Coin Changing Problem. I have included the code below.
I can't figure out the last else. Should I just use the greedy algorith...
Exserviceman asked 7/11, 2011 at 1:18
1
Solved
There are [at least] three algorithms which find minimum vertex cover in a tree in linear (O(n)) time. What I'm interested in is a modification of all of these algorithms so that I'll also get numb...
Tarantula asked 31/8, 2013 at 17:55
4
Solved
I've been working on an abstract chess algorithm using Haskell (trying to expand my understanding of different paradigms), and I've hit a challenge that I've been pondering about for weeks.
Here's...
Wasting asked 5/2, 2013 at 15:45
3
Yesterday, I appeared in an interview. I was stuck in one of the question, and I am asking here the same.
There is an array given that shows points on x-axis, there are N points. and M coins also ...
Conger asked 8/9, 2012 at 7:12
1
Solved
Most of the times the confusing fact is whether to go for an exhaustive search (dynamic programming or back tracking or brute force) to solve the problem or to go for the greedy approach.
I...
2
You know who knows who among n people that you would like to have come to a party. Assume "knows" is symmetric: If I know you, you know me. You make further requirements that you want each person t...
3
I am reading a tutorial about "greedy" algorithms but I have a hard time spotting them solving real "Top Coder" problems.
If I know that a given problem can be solved with a "greedy" algorithm it ...
3
Solved
For the common problem of matching text between delimiters (e.g. < and >), there's two common patterns:
using the greedy * or + quantifier in the form START [^END]* END, e.g. <[^>]*&g...
Barbiturism asked 29/8, 2011 at 8:12
3
I have a problem with one algorithm.
There are given n boxes, each one has fixed weight and strength (both given in kg). Box's strength tells us what is the maximum weight it can bear. We have t...
2
Solved
What is Greedy Token Parsing in PHP? I was reading a PHP coding guide which said the following...
"Always use single quoted strings unless you need variables parsed, and in cases where you do need...
4
Solved
Recently I've been looking at some greedy algorithm problems. I am confused about locally optimal. As you know, greedy algorithms are composed of locally optimal choices. But combining of locally o...
5
Solved
I've a input string like "===text=== and ===text===" and I want to replace wiki syntax with the corresponding html tag.
input:
===text=== and ===text===
desirable output:
<h1>text</h2...
Rosewater asked 11/3, 2011 at 16:59
3
Solved
Ok, I have a problem. I have a set "A" of bottles of various sizes, all full of water.
Then I have another set "B" of bottles of various sizes, all empty.
I want to transfer the water from A to B,...
Assamese asked 27/2, 2011 at 13:40
3
Solved
How can I get all the matches in the following example:
// Only "abcd" is matched
MatchCollection greedyMatches = Regex.Matches("abcd", @"ab.*");
// Only "ab" is matched
MatchCollection lazyMatch...
Dibromide asked 9/10, 2010 at 22:48
2
Solved
I recently had this problem on a test: given a set of points m (all on the x-axis) and a set n of lines with endpoints [l, r] (again on the x-axis), find the minimum subset of n such that all point...
3
Solved
I thought that by default my Regex would exhibit the greedy behavior that I want, but it is not in the following code:
Regex keywords = new Regex(@"in|int|into|internal|interface");
var targets ...
Procurable asked 7/3, 2010 at 2:23
5
Solved
I thought I understood Perl RE to a reasonable extent, but this is puzzling me:
#!/usr/bin/perl
use strict;
use warnings;
my $test = "'some random string'";
if($test =~ /\'?(.*?)\'?/) {
print ...
Kugler asked 3/4, 2009 at 7:27
6
Solved
I have the following line:
"14:48 say;0ed673079715c343281355c2a1fde843;2;laka;hello ;)"
I parse this by using a simple regexp:
if($line =~ /(\d+:\d+)\ssay;(.*);(.*);(.*);(.*)/) {
my($ts,...
Structuralism asked 1/11, 2008 at 17:35
© 2022 - 2024 — McMap. All rights reserved.