微信客服：xiaoxionga100
微信客服：ITCS521
CSE101-csc代写
时间：2022-11-09
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-4
• Homework solutions should be neatly written or typed and turned in through Gradescope
by 11:59pm on the due date. No late homeworks will be accepted for any reason. You will be
able to look at your scanned work before submitting it. Please ensure that your submission
is legible (neatly written and not too faint) or your homework may not be graded.
• Students may consult their textbook, class notes, lecture slides, instructors, TAs, and tutors
when they need help with homework. Students should not look for answers to homework
problems in other texts or sources, including the internet. Only post about graded homework
questions on Piazza if you suspect a typo in the assignment, or if you don’t understand what
the question is asking you to do. Other questions are best addressed in office hours.
• Your assignments in this class will be evaluated not only on the correctness of your answers,
but on your ability to present your ideas clearly and logically. You should always explain
how you arrived at your conclusions, using mathematically sound reasoning. Whether you
use formal proof techniques or write a more informal argument for why something is true,
your answers should always be well-supported. Your goal should be to convince the reader
that your results and methods are sound.
• For questions that require pseudocode, you can follow the same format as the textbook, or
you can write pseudocode in your own style, as long as you specify what your notation means.
For example, are you using “=” to mean assignment or to check equality? You are welcome
to use any algorithm from class as a subroutine in your pseudocode.
• Students can work in a group of 1-4. Each group should submit only one homework.
• For all the questions in this homework, we will use as a cycle a closed walk that does not
repeat edges or vertices except for the starting/ending vertex.
There are 4 questions for a total of 50, points.
1. (16 points) Its Laundry Day!!! You have just cleaned and dried all of your black socks. Oh no!!! you
had dropped a little bit of bleach in the washing machine so your socks are no longer all black! Now
your socks are all different shades of grey. You wish to pair the socks in such a way so that their shades
of grey are not too different. What is the maximum number of pairs you can make.
You have n socks numbered 1 through n and each sock i is given a value ci ranging from 0 to 100 with
0 meaning black and 100 meaning white. Any number in between is a shade of grey.
In order for two socks to be a “passable” pair, the difference of their shades c and c′ is less than or equal
to a given threshold value T , i.e., |c− c′| ≤ T . Otherwise, the two socks is not a passable pair. The goal
is to maximize the number of passable pairs of socks.
a) Describe this problem as we have done in class in terms of:
• Input:
• Solution Format:
• Constraints:
• Objective:
b) Candidate Greedy Strategy I: Find the pair of socks that are closest in shade (Break any ties
by choosing the darker colored socks.) Remove those socks and recurse on the remaining socks.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
c) Candidate Greedy Strategy II: Sort the socks in increasing order by shade: c1 ≤ c2 ≤ · · · ≤ cn.
• If |c1 − c2| ≤ T then pair (c1, c2) and recurse on the remaining socks (c3, . . . , cn).
1 of 4
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-4
• If |c1 − c2| > T then throw away c1 and recurse on the remaining socks (c2, . . . , cn).
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
d) Candidate Greedy Strategy III: Sort the socks in increasing order by shade: c1 ≤ c2 ≤ · · · ≤ cn.
Find the lightest sock i that makes a passable pair with c1, i.e. find the greatest index i such that
ci − c1 ≤ T . Pair up (c1, ci) and recurse on the remaining socks.
If there are not any socks that make a passable pair with c1 then throw c1 away and recurse on the
remaining socks.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
2. (16 points) There are n castles and n barracks that are positioned along a straight horizontal road. Each
barrack holds one army. Oh no, the enemy is coming to attack the castles!!!!
Each army goes to a castle. The amount of provisions is directly proportional to the distance the army
must travel (so for example, in order for an army to travel 10km, they would need 10 units of provisions.)
Your goal is to assign the n barracks to the n castles that minimizes the total units of provisions needed.
For example, if the castles are at positions: C = [10, 25, 30, 60, 80, 100] and the barracks are at positions
B = [20, 35, 40, 50, 70, 90] then one solution would be to pair up the barracks and castles in the following
way: (20, 25), (35, 30), (40, 10), (50, 60), (70, 100), (90, 80). This would require 90 units of provisions:
|20− 25|+ |35− 30|+ |40− 10|+ |50− 60|+ |70− 100|+ |90− 80| = 5 + 5 + 30 + 10 + 30 + 10 = 90
(Note that this may not be the optimal solution.)
The Castles are given as a list of positions in increasing order: [c1 ≤ · · · ≤ cn] and the barracks are given
as a list of positions in increasing order: [b1 ≤ · · · ≤ bn]. You can assume that all positions are different.
a) Describe this problem as we have done in class in terms of:
• Input:
• Solution Format:
• Constraints:
• Objective:
b) Candidate Greedy Strategy I: Start at the first (leftmost) barracks (at position b1) and send
its army to the leftmost castle. Remove this (barracks,castle) pair from the list and recurse on
the rest.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
c) Candidate Greedy Strategy II: Start at the first (leftmost) barracks (at position b1) and send
its army to the closest castle. Break any ties by selecting the castle on the left.) Remove this
(barracks,castle) pair from the list and recurse on the rest.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
2 of 4
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-4
d) Candidate Greedy Strategy III: Start at the first (leftmost) barracks (at position b1) and send
its army to the furthest castle. Break any ties by selecting the castle on the left.) Remove this
(barracks,castle) pair from the list and recurse on the rest.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
3. (9 points) You are given an increasing sequence of integers: (A[1], A[2], . . . , A[n]). Design an algorithm
that determines (returns TRUE or FALSE) if there exists an index i such that A[i] = i.
Your algorithm should run in O(log n) time.
(4 points for clear algorithm description, 2 points for algorithm being correct, 3 points for runtime
analysis. [No Justification necessary.])
4. (9 points) You are given a list of intervals (each interval is a pair of values [a, b] such that a ≤ b.)
Design and algorithm that returns the length of the maximum overlap among all pairs of intervals. (If
there are no overlapping pairs then you can return 0.)
(An interval [a, b] signifies the set of all values that are between a and b inclusive. The overlap of two
intervals is the set of values that are in both intervals. For example, the overlap of [2, 9] and [5, 16] is
[5, 9] and has length 4.)
Your algorithm should run in O(n log n) time.
(4 points for clear algorithm description, 2 points for algorithm being correct, 3 points for runtime
analysis.[No justification necessary.])
• Homework solutions should be neatly written or typed and turned in through Gradescope
by 11:59pm on the due date. No late homeworks will be accepted for any reason. You will be
able to look at your scanned work before submitting it. Please ensure that your submission
is legible (neatly written and not too faint) or your homework may not be graded.
• Students may consult their textbook, class notes, lecture slides, instructors, TAs, and tutors
when they need help with homework. Students should not look for answers to homework
problems in other texts or sources, including the internet. Only post about graded homework
questions on Piazza if you suspect a typo in the assignment, or if you don’t understand what
the question is asking you to do. Other questions are best addressed in office hours.
• Your assignments in this class will be evaluated not only on the correctness of your answers,
but on your ability to present your ideas clearly and logically. You should always explain
how you arrived at your conclusions, using mathematically sound reasoning. Whether you
use formal proof techniques or write a more informal argument for why something is true,
your answers should always be well-supported. Your goal should be to convince the reader
that your results and methods are sound.
• For questions that require pseudocode, you can follow the same format as the textbook, or
you can write pseudocode in your own style, as long as you specify what your notation means.
For example, are you using “=” to mean assignment or to check equality? You are welcome
to use any algorithm from class as a subroutine in your pseudocode.
• Students can work in a group of 1-4. Each group should submit only one homework.
• For all the questions in this homework, we will use as a cycle a closed walk that does not
repeat edges or vertices except for the starting/ending vertex.
There are 4 questions for a total of 50, points.
1. (16 points) Its Laundry Day!!! You have just cleaned and dried all of your black socks. Oh no!!! you
had dropped a little bit of bleach in the washing machine so your socks are no longer all black! Now
your socks are all different shades of grey. You wish to pair the socks in such a way so that their shades
of grey are not too different. What is the maximum number of pairs you can make.
You have n socks numbered 1 through n and each sock i is given a value ci ranging from 0 to 100 with
0 meaning black and 100 meaning white. Any number in between is a shade of grey.
In order for two socks to be a “passable” pair, the difference of their shades c and c′ is less than or equal
to a given threshold value T , i.e., |c− c′| ≤ T . Otherwise, the two socks is not a passable pair. The goal
is to maximize the number of passable pairs of socks.
a) Describe this problem as we have done in class in terms of:
• Input:
• Solution Format:
• Constraints:
• Objective:
b) Candidate Greedy Strategy I: Find the pair of socks that are closest in shade (Break any ties
by choosing the darker colored socks.) Remove those socks and recurse on the remaining socks.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
c) Candidate Greedy Strategy II: Sort the socks in increasing order by shade: c1 ≤ c2 ≤ · · · ≤ cn.
• If |c1 − c2| ≤ T then pair (c1, c2) and recurse on the remaining socks (c3, . . . , cn).
1 of 4
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-4
• If |c1 − c2| > T then throw away c1 and recurse on the remaining socks (c2, . . . , cn).
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
d) Candidate Greedy Strategy III: Sort the socks in increasing order by shade: c1 ≤ c2 ≤ · · · ≤ cn.
Find the lightest sock i that makes a passable pair with c1, i.e. find the greatest index i such that
ci − c1 ≤ T . Pair up (c1, ci) and recurse on the remaining socks.
If there are not any socks that make a passable pair with c1 then throw c1 away and recurse on the
remaining socks.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
2. (16 points) There are n castles and n barracks that are positioned along a straight horizontal road. Each
barrack holds one army. Oh no, the enemy is coming to attack the castles!!!!
Each army goes to a castle. The amount of provisions is directly proportional to the distance the army
must travel (so for example, in order for an army to travel 10km, they would need 10 units of provisions.)
Your goal is to assign the n barracks to the n castles that minimizes the total units of provisions needed.
For example, if the castles are at positions: C = [10, 25, 30, 60, 80, 100] and the barracks are at positions
B = [20, 35, 40, 50, 70, 90] then one solution would be to pair up the barracks and castles in the following
way: (20, 25), (35, 30), (40, 10), (50, 60), (70, 100), (90, 80). This would require 90 units of provisions:
|20− 25|+ |35− 30|+ |40− 10|+ |50− 60|+ |70− 100|+ |90− 80| = 5 + 5 + 30 + 10 + 30 + 10 = 90
(Note that this may not be the optimal solution.)
The Castles are given as a list of positions in increasing order: [c1 ≤ · · · ≤ cn] and the barracks are given
as a list of positions in increasing order: [b1 ≤ · · · ≤ bn]. You can assume that all positions are different.
a) Describe this problem as we have done in class in terms of:
• Input:
• Solution Format:
• Constraints:
• Objective:
b) Candidate Greedy Strategy I: Start at the first (leftmost) barracks (at position b1) and send
its army to the leftmost castle. Remove this (barracks,castle) pair from the list and recurse on
the rest.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
c) Candidate Greedy Strategy II: Start at the first (leftmost) barracks (at position b1) and send
its army to the closest castle. Break any ties by selecting the castle on the left.) Remove this
(barracks,castle) pair from the list and recurse on the rest.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
2 of 4
CSE101: Design and Analysis of Algorithms (CSE, UCSD, Fall-2022) Homework-4
d) Candidate Greedy Strategy III: Start at the first (leftmost) barracks (at position b1) and send
its army to the furthest castle. Break any ties by selecting the castle on the left.) Remove this
(barracks,castle) pair from the list and recurse on the rest.
Either prove that this strategy always yields an optimal solution or give a counterexample to show
that it is not always optimal.
3. (9 points) You are given an increasing sequence of integers: (A[1], A[2], . . . , A[n]). Design an algorithm
that determines (returns TRUE or FALSE) if there exists an index i such that A[i] = i.
Your algorithm should run in O(log n) time.
(4 points for clear algorithm description, 2 points for algorithm being correct, 3 points for runtime
analysis. [No Justification necessary.])
4. (9 points) You are given a list of intervals (each interval is a pair of values [a, b] such that a ≤ b.)
Design and algorithm that returns the length of the maximum overlap among all pairs of intervals. (If
there are no overlapping pairs then you can return 0.)
(An interval [a, b] signifies the set of all values that are between a and b inclusive. The overlap of two
intervals is the set of values that are in both intervals. For example, the overlap of [2, 9] and [5, 16] is
[5, 9] and has length 4.)
Your algorithm should run in O(n log n) time.
(4 points for clear algorithm description, 2 points for algorithm being correct, 3 points for runtime
analysis.[No justification necessary.])
