Section 4.2 Connecting computational thinking and program design (22 hours)

Unit 4 Computational thinking, problem solving and programming

Unit 4.1: Computational thinking

Jeanette Wing (Vice President of Microsoft Research, and previously President’s Processor of Computer Science at Carnegie Mellon University, Pittsburgh) wrote a short but highly influential paper outlining the importance of computational thinking. That paper forms the basis of this unit within the IB course.

You should read it… https://www.cs.cmu.edu/~15110-s13/Wing06-ct.pdf

There are competing thoughts as to how best categorize computational thinking processes. The IB uses these six:

• Thinking procedurally
• Thinking logically
• Thinking ahead
• Thinking concurrently
• Thinking abstractly
• Thinking recursively (HL)

Others, such as Google and Code.org use the following alternative labels:

• Decompose – Break a big problem into it’s constituent parts.
• Patterns – Identify what pieces have in common, and what remains distinct
• Abstraction – Create an abstraction around the patterns
• Algorithms – Write an algorithm so that resolves are easy to achieve.

They all achieve the same point – a set of thinking skills that guides you through solving a problem.

Thinking procedurally

• Turning the solution to your problem into a set of steps that can be followed.
• Following those steps should reproduce the correct solution each time.
• Each step may call upon a sub-procedure with its own list of steps.
• Divide and conquer – take the one overwhelming whole and break it down into manageable pieces.
• Sequencing (ordering) of steps is usually an important consideration.

Example: Cleaning the entire house/apartment, against cleaning the kitchen, bathroom, living room, bedrooms

• Tackle it one task at a time, and eventually the whole will be done.
• Each task identified can also be broken down into sub-tasks. Using the cleaning analogy, this could be vacuum, dust, sweep, put rubbish in the bin, pick clothes up from the floor.
• One important consideration is the order of tasks. Look back at that list of cleaning tasks - is that the order that will achieve the cleanest bedroom? What should the order be?

Finally, Look for familiar things. Do not reinvent the wheel. If a solution exists, use it. If you have solved the same or a similar problem before, just repeat the successful solution. We usually do not consciously think, “I have seen this before, and I know what to do” - we just do it. Humans are good at recognizing similar situations. We do not have to learn how to go to the store and buy milk, then to buy eggs, then to buy candy. We know that going to the store is always the same and only what we buy is different.

Thinking logically

Thinking logically is all about making decisions, and formalising the conditions that will affect those decisions. There are generally three steps:

• Identify when decision making is required.
• Identify what is the decision that needs to be made.
• Identify the conditions which will form the basis of each decision.

Decisions may be multi faceted. Compare these two:

The question we ask ourselves in the “if” statement is known as the condition. We can use “boolean logic” to create multiple conditions for a single “if”. Both of these do the same thing:

if (time is 6:00am) and (day is weekday) then
    wake up for school 
end if

if (time is 6:00am) and ((day is Monday) or (day is Tuesday) or (day is Wednesday) or (day is Thursday) or (day is Friday)) then
      wake up for school
end if

Logical decisions can also be applied to things of a repetitive nature

while (hungry) then 
   raid pantry eat 
end 

for (each episode of Game Of Thrones) 
   watch the episode 
end 

Activity: Logical thinking with a flow chart

On 1st June 2009, Air France flight 447 left Rio de Janeiro heading to Paris. It was a routine international flight. In the early hours of the morning, over the Atlantic Ocean, contact was lost, and the aeroplane vanished.

On investigation, the plane showed signs of a high-speed impact with water as the nose cone was flattened. This ruled out a bomb or structural break-up. It was determined that the plane crashed into the water due to pilot error.

The plane flew through a thunderstorm. Other aeroplanes had diverted that night, as is standard practice in bad weather. The pitot tubes (speed sensors) had frozen over as a result. This caused the autopilot to switch off and incorrect readings to be sent to the cockpit. This is expected behaviour, and pilots are trained to recognise this. Believing that the plane was losing altitude, the pilot pulled back on the stick to raise the nose, in an attempt to gain height. The instruments continued to show the plane falling. If an aircraft’s nose is pointed up too far, it loses speed, causing the engines to stall. The correct action is to point the nose down, gaining speed, before levelling off.

With the aid of a flowchart, show how logical thinking could have avoided this accident.

​

​

Activity: Film canister sort

You will be divided into groups. Each group will receive 8 film canisters and a balance scale. Your task is to sort the canisters from lightest to heaviest.

Use your procedural and logical thinking skills to devise the most efficient instructions for sorting the canisters. Count the number of “comparisons” your procedure makes. The winning team are the ones with the least comparisons (most efficient algorithm)

Thinking ahead

Thinking ahead is all about pre-planning and attempting to anticipate future needs.

What are the pre-conditions to solving the problem?

• What has to be in place, or known, in order to be able to solve the problem? ie: what are the inputs going to be? Prepare sample testing data to test the algorithm with

What are the post-conditions of the problem?

• What will be in place, or known, after the problem has been correctly solved? ie: what are the outputs going to be?

Anticipate exceptions to the rule

• What are the likely exceptions we are going to need to deal with? How do we want to handle them?
• Test anticipated exceptions to verify your responses work as intended.

Examples of thinking ahead in daily life:

• Pre-ordering.
• Shopping lists. You know you want to bake a cake, so you make sure you have all the necessary ingredients ahead of time.
• Pre-heating an oven. You know you’re going to need it in a few minutes, start getting it warm now.
• Grabbing books/files from your locker and putting them into your bag for the lessons until the next break.
• Gantt charts.
• The cache on a computer is an example of thinking ahead.

Activity: Die Hard movie challenge

Can you solve the puzzle in Die Hard?

• Introducing the problem (play up to 1:05)
• Solution (play from 1:05)

https://www.youtube.com/watch?v=6cAbgAaEOVE

Activity: Egg drop

You are given two eggs, and access to a 100-storey building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

Hint

Whilst it’s not strictly part of the puzzle, let’s first imagine what we’d do if we had only one egg.

Once this egg is broken, that’s it, no more egg. So, we really have no other choice but to start at floor 1. If it survives, great, we go up to floor 2 and try again, then floor 3 … all the way up the building; one floor at a time. Eventually the egg will break* and we’ll have a solution. For example, if it breaks on floor 57, we know that the highest floor that an egg can withstand a drop from is floor 56.

There’s no other one egg solution. If we’d been feeling lucky we could have gone up the floors in two’s but imagine if the egg broke on floor 16; we have no way of knowing if it would have also broken on floor 15!

Hint part 2

At the other extreme, what if we had an infinite number of eggs? (Or at least as many eggs as we need). What would our strategy be here? In this case we’d use one of a programmer’s favorite tools, the binary tree.

First we’d go to floor 50 and drop an egg. It either breaks, or it does not. The outcome of this drop instantly cuts our problem in half. If it breaks, we know the solution lives in the bottom half of the building (floor 1 – floor 49). If it survives, we know the solution is in the top half of the building (floor 51 – 100). On each drop, we keep dividing the problem in half and half again until we get to our solution.

The mathematicians in the audience will quickly see that the number of drops required for this solution is log2 n, where n is the number of floors of the building. (This is like asking how many powers of two there are). ie: log2 100 = 6.644, or 7.

Hint part 3

It does not take much imagination to see why a binary search solution will not work (optimally) for two eggs. Let’s imagine we did try a binary search and dropped our first egg from floor 50. If it broke, we’d be instantly reduced to a one egg problem.

What happens if we started off with our first egg going up by floors ten at a time? We can start dropping our egg from floor 10; if it survives we try floor 20, then floor 30 … we carry on until the first egg breaks. Once we’ve broken our first egg we know that the solution must lay somewhere in the nine floors just below, so we back off nine floors and step through these floors one at a time until we find a solution.

The question really comes down to: what is the optimal number of floors to skip with the first egg?

Hint part 4

What we need is a solution that minimizes our maximum regret. We need is a strategy that tries to make solutions to all possible answers the same depth (same number of drops). The way to reduce the worst case is to attempt to make all cases take the same number of drops.

Activity: Ball bearings

You have 10 boxes of ball bearings (each ball weighing exactly 10 gm) with one box with defective ball bearings (each one of the defects weigh 9 gm). You are given an electronic weighing machine and only one chance at it. How will find out which box has the defective ball bearings?

Thinking concurrently

Concurrency = dealing with multiple things happening at the same time.

Tasks are broken down into subtasks that are then assigned to separate processors to perform simultaneously, instead of sequentially as they would have to be carried out by a single processor. (Oracle)

A non-computing example is the GANTT chart where multiple processes occur simultaneously. For example project managing the construction of a new house.

GPU’s are a popular and powerful way to do multithreaded programming on computers.

Syllabus note: Students will not be expected to construct an algorithm related to concurrent processing (but you may be expected to be able to interpret/understand/recognise one presented to you)

Activity: Multi theaded sorting

How long (comparisons) does it take to sort a deck of cards with:

• 1 thread (1 person)
• 2 threads (2 people)
• 4 threads (4 people)?

​

Thinking abstractly

Being able to create a meaningful model, or way to represent, a real world “thing” in a way that contains everything that is relevant, and nothing that isn’t.

Video: Robotics Academy (2016) Abstraction - Computational Thinking (2:28)

Real world examples:

• Maps – An abstraction contain pertinent information about a physical place. Different maps contain different information dependent on their purpose.
• Daily planners – An abstraction to represent hours, days, weeks and months in a simple manner that allows us to stay organised.
• Schools – People are abstracted into groups such as teachers, students, year 1, year 2, etc

When you take a real-world situation and are writing a program or algorithm for it, you are creating an abstraction: a way to represent that situation within the computer. As such you will make decisions about how that abstraction should be created such as what variables you need, what you will call them, what data type they will be, and how your algorithm will behave in response.

To succeed at thinking abstractly, you need to be able to take a problem and identify the parts that are relevant to your solution.

Exercises

Jake & Jill’s weekly food shop

Jake and Jill are quite fed up of how long they spend in the supermarket each week doing their weekly food shop. They decide what they want when they are actually walking around the supermarket and they often have to go back multiple times in the week as they run out of items. This method of shopping is also resulting in a very expensive total weekly shopping bill!

How could they use the principles of computational thinking to make their weekly shopping experience as efficient as possible. There overall aims are to:

• Spend as little time as possible in the supermarket each week
• Save as much money as possible

Taxi driver

A taxi driver uses his experience, a GPS navigation system and radio tuned to traffic information to work out how to get passengers from A to B.

In what ways is the taxi driver able to:

• Think abstractly
• Think ahead
• Think logically

Unit 4.2: Program design

4.2.1 Describe the characteristics of standard algorithms on linear arrays. 

​

Visualization Click Here 

Visualization Click Here 

Visualization Click Here 

Sorting Activities

Given an array sortmeplease = [3,6,9,2,7,0,8]

Create a solution in pseudo code to perform a selection sort ( set start position = 0 then compare the element the start position with the rest of the elements  ( performing  a swap ) if next is smaller than current at then end of the first iteration the smallest element should be in position 0, but you need to sort all elements.

Open Jupyter Notebook and write program to perform the selection sort

Post both pseudo code and  python code to your google site:

4.2.6 Construct pseudo code to represent an algorithm.

Link to Pseudo Code Simulator Click here

IB expectations

You need to be able to create as well as interpret/analyse pseudo code.

Where answers are to be written in pseudocode, the examiners will be looking for clear algorithmic thinking to be demonstrated. In examinations, this type of question will be written in the approved notation, so a familiarity with it is expected. It is accepted that under exam conditions candidates may, in their solutions, use pseudocode similar to a programming language with which they are familiar. This is acceptable. The markscheme will be written using the approved notation. Provided the examiners can see the logic in the candidate’s response, regardless of language, it will be credited. No marks will be withheld for syntax errors … for answers to be written in pseudo code

IB syntax

Given the statements made above about there not being a “correct” way to write it, there is a set syntax that the IB will use when they write pseudo code questions for you in the exam. As per the expectations comments above, you are not obligied to follow their syntax in your responses, and you will not lose credit for doing so, but you should be familiar enough with their syntax to be able to properly interpret the questions they give you.

These methods, in their pseudocode format, may be used without explanation or clarification in examination questions. Teachers should ensure that candidates will be able to interpret these methods when presented as part of an examination question.

The following comes from the IB documents

• “Approved notation for developing pseudocode” available at https://pbaumgarten.com/dp-compsci/dp-compsci-ib-pseudocode-flowcharts.pdf
• “Pseudocode in Examinations” available at https://pbaumgarten.com/dp-compsci/dp-compsci-ib-pseudocode-in-detail.pdf

Pseudo Code Exercises 1D Arrays and While condition

If you can not find the command if the pseudo code handout please make up your own pseudo code high level English. remember the conventions . Variable names all capitals, pseudo code keywords/commands lower case for example loop

Question 1 Write pseudo code that will sum all the even numbers in an array. 

Question 2 Write pseudo code that iterates thru an array of numbers and stops if it finds the number 10 or reaches the last element in the array 

Question 3 Write pseudo code that will perform the following:

• process an array of 5 integers
• Calculate the average of the five numbers.
• Find the smallest (minimum) and largest (maximum) of the five numbers.
• Output the results found from steps 2 and 3.

After you complete ask your partner to check your pseudo code solutions. Please add you name to completed activity and hand in for marking.

Pseudo Code next Level ( with function call ) 

// FirstLetter(“CITY”) will return the first letter of the word “CITY” // Elements are stored in an array called CITYNAMES

// Elements are stored in an array called CITYNAMES

A geography teacher is searching an array, CITYNAMES, containing 100 names of cities and wants to print out the names of the cities beginning with D. 

Construct pseudo code to indicate how this may be done:

Pseudo Code Exercises 2D Arrays 

Review of 2 D Arrays click here

Question 1)  Write pseudo code to output the average rating of the movie in column 2 

Pseudo Code Collections

The face plate of a car stereo has six buttons for selecting one of six preferred radio stations. As part of the internal representation of a microprocessor there is an array with six positions, carrying the information about the radio frequencies, as follows.

(a) State the information at Radio[2]. [1]
(b) Outline how a numerical frequency could be stored in a fixed-length string. [2]
(c) Construct an algorithm in pseudocode that calculates the range of frequencies
(ie the difference between the highest and lowest frequencies) of any set of six selected radio stations.

The two-dimensional array Stats provides an indication of how often a specific station is listened to by the user. For each button in the faceplate it records how often it has been clicked in the last 48 hours. Stats is ordered by the second column.

Both Radio and Stats are used by a procedure that allows the user to access the radio frequencies that are listened to most often, as recorded in Stats, by flicking a lever on the steering wheel. The frequencies are accessed cyclically, ie after the least used frequency the procedure returns to the most used. For this reason a queue Q is used.

Construct an algorithm in pseudo code that, by using the structures Radio and Stats, performs the following steps:

• it inserts the radio frequencies in the queue Q, following the actual order of preference;

 and then

• it uses the queue Q, cyclically, to output an element each time the lever is flicked. [6]      

From Pseudo Code to Programming Code

When you have completed and handed in the pseudo code exercises above From Wednesday and Handed it in to me for marking proceed to activity below

ACTIVITY: Convert the pseudo code from Question 2  into Executable JavaScript "Write pseudo code that iterates thru an array of numbers and stops if it finds the number 10 or reaches the last element in the array 

Extension : Write pseudo code that iterates through an array of numbers and stops if it finds the number 10 or the number 5 

Implement in code a recursive solution to find the Factorial of a number assume positive integers only.

Activity C Following Pseudo code

Array Exercises

Given an array of N integers ranging from (0,20). Write pseudo code to iterate thru and print out the average value and the number of zero values.  

Assume array contains the following integers [1,6,18,20,0,1,7,9,8,6,2,1,3,0]

4.3.12 Construct algorithms using predefined sub-programmes, one dimensional arrays and/or collections

Link to slide Show Click here

Procedures / Functions / Modules / Sub programs

Functions are the building blocks of readable, maintainable, and reusable code. A function is a set of statements to perform a specific task. Functions organize the program into logical blocks of code. Once defined, functions may be called to access code. This makes the code reusable. Moreover, functions make it easy to read and maintain the program’s code.

Create a  simple function in Typescript to print out student id number and name

 function disp_details(id:number,name:string) {
 console.log("ID:", id);
 console.log("Name",name);

 }

 disp_details(123,"John");
 disp_details(111,"mary");

Find the Factorial of the Number 4

We could write the code to calculate factorial 4 as below.

 // find factorial of 4

 factorial=1 // init variable
 for (i = 1; i <= 4; i++) {
     factorial = factorial * i;
 }
 console.log(factorial)

​

What are the limitations of this approach ?

A better approach is to encapsulate it within a Function ( so that it can be called and passed any number that you wish to find the factorial of )

 // call function to find factorial of a number

 function findfact(number){
     for (i = 1; i <= number; i++) {
           factorial = factorial * i;
      }

 }

 factorial=1
 findfact(9);
 console.log(factorial)

Another Approach Recursion

Factorial Rule   n! = n × (n−1)!

 // call a function recursively to find factorial of a number



 function findfact(number){
    if (number == 1) {
         return 1;   // base case
    }
   else {
      return number * findfact(number-1);

    }


 }


 factorial = findfact(9);
 console.log(factorial);

​

Screen Cast of Program running Click Here

Recursion or Iteration Which is the best Solution ?

Which one is more Eloquent (clearly expressing or indicating something)?  Which is easier to understand ?

https://slideplayer.com/slide/12782837/

Collections

A collection — sometimes called a container — is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data. Typically, they represent data items that form a natural group, such as a poker hand (a collection of cards), a mail folder (a collection of letters), or a telephone directory (a mapping of names to phone numbers).

Collection methods

Collection methods in Pseudocode are

• .addItem( new data item )
• .resetNext( ) start at beginning of list
• .hasNext( ) checks whether there are still more items in the list
• .getNext( ) retrieve the next item in the list
• .isEmpty( ) check whether the list is empty

For Loop   -

Determinate

While Loop  - Indeterminate

Solutions