CIT 596 2025 - HW8 Oral
This homework deals with the following topics
* Greedy algorithm
* MST
Please read these instructions
• WEAPARTE = Write an Efficient Algorithm in Pseudocode or Plain English, Analyze its Run Time, with an Explanation.
• The homework has to be submitted in electronic form as a pdf file. You can use any editing software you want in order to produce the pdf. Handwritten solutions get a 0.
• If a question asks you for an algorithm (and a time complexity is not specified in the question itself), we expect you to write pseudocode and analyze the algorithm in terms of big-O time complexity.
• As with all HWs, remember not to sacrifice correctness while striving for efficiency.
• We will not worry about the distinction between O and Θ . As long as you provide a tight bound (for example if an algorithm is actually O(nlog n) and you say O(n3 ) you will lose points) you are fine.
• If you are explaining the running time of a graph, it is important to mention whether your graph is being stored in an adjacency list representation or an adjacency matrix representation.
• If you have any doubts on whether you are making assumptions about ‘in-built’ func- tions, please ask us on Piazza. You are also strongly advised to read Piazza.
• The number of points associated with a question is a general guideline for toughness and/or amount of writing we expect. Sometimes a question might be worth 4 or 5 points only because it is lengthy.
• A result shown in class and/or provided by the textbook (Algorithms Unlocked) can be used as is. The same goes for pseudocode that you want to just use as is.
• You are allowed to write things like ”Run bfs” or ”Run dfs”. Remember that if you do so, we will assume you mean the standard (as per the textbook/lecture) algorithm. If you want to modify an algorithm then it is your job to write out the full pseudocode. You are allowed to use the pseudocode from the textbook/notes as a starting point.
1. (10 points) Khutulun was a heroic warrior and wrestler of Mongolia
(https://en.wikipedia.org/wiki/Khutulun). She once had to ride a horse through a desert while her enemies were in pursuit. Once she crossed the desert she knew she would be safe.
She knew that she and her horse could last a maximum of 10 miles in the desert before dehydration would set in. She knew that water sources (streams, lakes, wells) were all along a particular straight route. Finally, she also knew the location of each of these places that had water. These water sources were not evenly spaced.
She also knew the length of the road was R miles.
For the purposes of this problem we are also going to assume that there is a way that Khutulun can cross the desert and survive. That is, we will not deal with the morbid situation where the last source of water is 30 miles from the end.
In order to evade her enemies, she obviously wanted to stop to drink water the fewest number of times possible. Each water source had enough water in it for her and her horse to be able to quench their thirst and last 10 miles from that point.
Khutulun was able to figure out a greedy strategy that helped her make the fewest number of stops (while obviously not dying of dehydration).
What was this strategy? Describe it first in plain English.
Now, assume that Khutulun started from the beginning of this route. The water sources’ locations are in an array called ws. ws[0] gives you the number of miles (from the origin of the desert) to the first location. ws[1] gives you the number of miles to the second location from the origin of the desert. There are n such locations.
Write an algorithm to figure out the places where Khutulun should stop for water. Your algorithm should return a boolean array called stop. stop[i] should be true if Khutulun should stop and false if she should skip that water source.
Remember to analyze the runtime of your algorithm.
2. (10 points) A graph G is called a Phillytree (totally made up term) if it is connected and has at most n + 76 edges, where n is the number of vertices. WEAPARTE to get a O(n) runtime algorithm that takes as an input a graph G that is known to be a Phillytree and returns a minimum spanning tree of G. You are allowed to assume that edge weights are distinct. You are not allowed to assume anything else about the weights.
Hint : The correct algorithm is not a modification of Prim’s or Kruskal’s so please do not think along those lines.
3. (10 points) You have already computed a minimum spanning tree on some graph. As- sume this MST is given to you as a list of edges. Now your annoying teacher increases the weight of one of the edges (u, v) in the graph. You are given what u and v are. How would you recompute the minimum spanning tree efficiently? What is the run time of your algorithm? Please explain briefly.