IB Computer Science Year 2 Higher Level - September 11 2017 Lesson Notes

From Computer Science Wiki
Jump to navigation Jump to search

Class plan.png What are we going to learn today?[edit]

Hello Class!

  • We will review computational thinking (per our homework)
  • 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]]

Homework.png What is our homework?[edit]

In our next class I will expect you to describe to the class one aspect of computational thinking.

Target.png How am I being assessed today?[edit]

I will assess you formatively today, and make a professional judgement to what extent you understand our learning material. I will use observation, your written work, answers to questions, and contribution to class discussions as data to make my decisions. I normally record my observations in a "evidence of learning" spreadsheet, which I will happily share with you privately if you so wish. I usually need a day or two notice.

Computer1.png As a computer scientist, you have:[edit]

  • Confidence in dealing with complexity
  • Persistence in working with difficult problems
  • Tolerance for ambiguity
  • The ability to deal with open-ended problems
  • The ability to communicate and work with others to achieve a common goal or solution

Credit.png Credits[edit]

A unit of abstract mathematical system subject to the laws of arithmetic.

A natural number, a negative of a natural number, or zero.

Give a sequence of brief answers with no explanation.

Give a detailed account or picture of a situation, event, pattern or process.

Consider the merits or otherwise of an argument or concept. Opinions and conclusions should be presented clearly and supported with appropriate evidence and sound argument.