 What are we going to learn today?[edit]
Hello Class!
- We are going to review arrays
- We will create some arrays and access the elements in an array
- We will then process a problem-set from MIT course entitled "Introduction to Computational Thinking and Data Science".
- We will end with yet another Mr. MacKenty experiment. You'll fill out a google classroom formative check
Introduction[edit]
A colony of Aucks (super-intelligent alien bioengineers) has landed on Earth and has created new species of farm animals! The Aucks are performing their experiments on Earth, and plan on transporting the mutant animals back to their home planet of Aurock. In this problem set, you will implement algorithms to figure out how the aliens should shuttle their experimental animals back across space.
Transporting Cows Across Space[edit]
The aliens have succeeded in breeding cows that jump over the moon! Now they want to take home their mutant cows. The aliens want to take all chosen cows back, but their spaceship has a weight limit and they want to minimize the number of trips they have to take across the universe. Somehow, the aliens have developed breeding technology to make cows with only integer weights.
Be Greedy[edit]
One way of transporting cows is to always pick the heaviest cow that will fit onto the spaceship first. This is an example of a greedy algorithm. So if there’s only 2 tons of free space on your spaceship, with one cow that’s 3 tons and another that’s 1 ton, the 1 ton cow will still get put onto the spaceship.
- The order of the list of trips does not matter. That is, [[1,2],[3,4]] and [[3,4],[1,2]] are considered equivalent lists of trips.
- All the cows are between 0 and 10 tons in weight
- All the cows have unique names
- If multiple cows weigh the same amount, break ties arbitrarily
- The spaceship has a cargo weight limit (in tons), which is passed into the function as a parameter
Example:
Suppose the spaceship has a weight limit of 10 tons and the set of cows to transport is {“Jesse”: 6, “Maybel”: 3, “Callie”: 2, “Maggie”: 5}.
The greedy algorithm will first pick Jesse as the heaviest cow for the first trip. There is still space for 4 tons on the trip. Since Maggie will not fit on this trip, the greedy algorithm picks Maybel, the heaviest cow that will still fit. Now there is only 1 ton of space left, and none of the cows can fit in that space, so the first trip is [“Jesse”, “Maybel”].
For the second trip, the greedy algorithm first picks Maggie as the heaviest remaining cow, and then picks Callie as the last cow. Since they will both fit, this makes the second trip [“Maggie”, “Callie”].
The final result then is [[“Jesse”, “Maybel”], [“Maggie”, “Callie”]].
The collection of cows[edit]
[[Maggie,3],[Herman,7],[Betsy,9],[Oreo,6],[Moo Moo,3],[Milkshake,2],[Millie,5],[Lola,2],[Florence,2],[Henrietta,9]]
|
 What is our homework?[edit]
In our next class I will expect you to describe to the class one aspect of computational thinking.
|
