12826 Algorytmy
zł10-40 PLN
Paid on delivery
4. The famous internet guy \"Tchesio\" is planning an excursion along some desert route. The route consists of n intervals, and on the beginning of each interval there is a stopover with a big (infinite) stock of candies, the only \"fuel\" accepted by our sweet man. Tchesio\'s capacity is c candies, and his fuel consumption is f candies per mile (independent of the amount of sweets he just consumed). Assume that the lengths of consecutive intervals are given in an array A[n].
(a) Design a best strategy for Tchesio that tells him how many candies he should consume at each stopover
(b) Give an algorithm that checks if Tchesio can successfully reach the end of the route.
6. You are given a family of n intervals on the line. The i\'th interval is specified by two integers: the starting point S[i] and the ending point E[i]. Your task is to assign colors 1,2,3,... to intervals in such a way that:
- if two intervals intersect then they are assigned a different color (if they share an endpoint only then they do not intersect)
- the number of colors is the smallest possible
Hint: some greedy strategy works.
7. Consider problem 6. Prove that the following strategy is incorrect (just show a counterexample - a suitable family of intervals F for which the result is not optimal):
1. Sort F on ascending right endpoint, set k0
2. Compute Ga maximum size set of disjoint intervals (use Greedy-ASP)
3. k++
4. Assign color k to all intervals in G
5. FF-G
6. If F is empty then stop, otherwise go to 2.
8. Show that each of the following greedy strategies for the ASP does not work, by finding a list of activities for which it produces a solution that is not optimal. Give both the solution by the strategy and an optimal solution.
(a) Strategy A: Scan the activities by sorted increasing starting time. Choose the next activity that is compatible with already chosen activities.
(b) Strategy B: Always select the compatible activity that overlaps the fewest other remaining activities.
(c) Strategy C: Always select the activity of least duration from those that are compatible with previously selected activities.
Project ID: #5588906
