# Algorithmic Thinking

# Overall Class Structure ( proposed)

Review Previous learning and intro to current class activities or new learning 15 - 20 mins

Independent work 20-30

Teacher one to one check progress ( we can swap this around )

12:00 Get together - Set final Activity / Home work / Grade Book

12:20 Get together - Completed may leave else stay for further guidance on activity / topic

# Lesson Block 1 26th August 2021

### Review 10mins

4.3.1 State the fundamental operations of a computer.

4.3.2 Distinguish between fundamental and compound operations of a computer

Operations on a collection ?

Operations on a stack ?

Operations on a array?

Operations on a queue?

### 30 mins - 15 Minutes 10 Mins Activity 5 Discussion

**Q8 [3marks]**

List the output from the following input ( 10mins )

2,6,8,9,12,15,20

Loop Count from 0 to 7

INPUT Number

If NUMBER div 2 = NUMBER /2 then

if NUMBER div 3 = NUMBER/ 3 then

OUTPUT Number

Programming Activity (15 mins)

Create a working program based on the Pseudocode in Python or language of your choice.

# Lesson Block 2 02 Sep 2021

**MOD Operator **

The modulus operator - or more precisely, the modulo operation - is a way to determine the remainder of a division operation. Instead of returning the result of the division, the modulo operation returns the **whole number remainder**.

**Question:**

What is 5 divided by 2?

**Dividing Numbers**

ivision is one of the four main operations in math. When you divide a number, you are basically just splitting it into even groups. For example, 24 divided into 3 even groups would mean you have 8 groups (24 / 3 = 8). Sometimes a number divides evenly, but other times you have numbers left over. These numbers are called the remainder.

**Answer and Explanation:**

The number 5 divided by 2 is 2 with a remainder of 1 **(5 / 2 = 2 R.1). This is also written as 5 /2 = 2.5**. When you divide 5 by 2, it does not come out evenly. For example, you can't split five oranges into even groups of two, so you would have two groups of two oranges each, with one orange left over.

** It may be helpful to think back to your early math lessons, before you learned fractions and decimals. Mathematics with whole numbers behaves differently - when dividing numbers that arenโt even multiples, thereโs always some amount left over. That remainder is what the modulo operation returns.

Some examples may help illustrate this, as itโs not necessarily intuitive the first time you encounter it:

`5 % 1 = 0 // 5 divided by 1 equals 5, with a remainder of 0 `

5 % 2 = 1 // 5 divided by 2 equals 2, with a remainder of 1

5 % 3 = 2 // 5 divided by 3 equals 1, with a remainder of 2

5 % 4 = 1 // 5 divided by 4 equals 1, with a remainder of 1

5 % 5 = 0 // 5 divided by 5 equals 1, with a remainder of 0

What is 100 mod 10 ?

What is 233 mod 10?

what is 2005 mod 100

Remeber ask yourself how many groups of 10's are there what is left over is the MOD

Link to Jupyter JupyterLab

#### Starter Past paper 2015

A sub-program all_even() accepts a positive integer N and outputs true if all digits of N are even, otherwise it outputs false. For example, all_even(246) outputs true and all_even(256) outputs false.

The following algorithm is constructed for the sub-program all_even(N).

EVEN = true

loop while (N > 0) and (EVEN = true)

if (N mod 10)mod 2 = 1 then

EVEN = false

end if

end loop

output EVEN

(a) Explain why this algorithm does not obtain the correct result. [2]

(b) Outline what should be changed in the algorithm to obtain the correct result. [3]

**Challenge**

### 30 mins (high Level) - 15 Minutes Pseudo 15 Mins Programming Activity

*For reference Past Paper May 2021*

14. The following flowchart is intended to represent an algorithm in which numbers that are input cannot be negative.

The flowchart contains a logic error that will affect the algorithm's functionality

14 a (i) Identify the logic error [1]

14 a (ii) Outline how the error in part Ii) can be corrected [1]

14 a (ii) Outline how the error in part Ii) can be corrected [2]

A further change has been requested to enable the calc of the average of the numbers entered. The avaerage should be output at the end of the program.

Based on flow chart construct an algoroithm using pseudocode. That inlcudes the required changes. [8]

**Convert pseudo code into a working program **

# Lesson Block 09 Sep 2021

4.2.3 Discuss an algorithm to solve a specific problem.

Students should be expected to discuss the differences between algorithms, including both standard and novel algorithms. For example, discussing the advantages and disadvantages of using a binary search as opposed to a sequential search.

4.1.2 Evaluate whether the order in which activities are undertaken will result in the required outcome

4.1.3 Explain the role of sub-procedures in solving a problem

This means TESTING an algorithm using SAMPLE DATA.For example, the following should add up all positive numbers in an array containing 5 numbers. Test with NUMS = [ 5 , 5 , 0, 2 , 2 ]

Loop C from 0 to 4

SUM = 0

SUM = SUM + NUMS[C]

end loop

OUTPUT SUM

1) The algorithm has 1 issues which is the order of activities, identify the problem it and write correct code in Python

2) The algorithm requirement has changed in that it should accept an array of positive and negative integers, but only output sum the positive integers

3) Is your program well structured? Can it be compartmentalised and reused ? If not rework your program, so it is well structured

4) List 4 advantages of a well structure program.

## How to implement a Queue using a Linked List

We will implement Queue using linked list. Queues maintain two data pointers:

Queue is a very simple data structure, you only have to manipulate FRONT and REAR to get Queue property.

### Basic Operation:

Main Queue Operations:

1)**EnQueue()**: Inserts an element at the rear of the Queue.

2)**DeQueue()**: Remove and return the front element of the Queue.

Define two Node pointers 'front' and 'rear' and set both to NULL.

Queue is very simple data structure, you only have to manipulate FRONT and REAR to get Queue property.

`Step 1 : Create a newNode with given value and set 'newNode โ next' to NULL.`

`Step 2 : Check whether queue is Empty (rear == NULL)`

`Step 3 : If it is Empty then, set front = newNode and rear = newNode.`

`Step 4 : If it is Not Empty then, set rear โ next = newNode and rear = newNode.`

### EnQueue

Inserting an element in Queue.

- Initially, both of our pointers pointing to the front and rear are NULL.
- Now,If We enter the 12 in Queue we will checking weather there is any element present or not. If rear is NULL, We make our front and rear pointers to point our newly inserted Node with having data '12'.
- Now, again if we want to enter new data, Let say 45. We will check for rear NULL or not. Now our rear would be pointing to '12' .So 45 will added next to the rear Node and 45 would be our rear Node.
- Same way if i add 26, it would be added after 45 and rear will point to the Node having data '26'.

`Step 1 : Check whether queue is Empty (front == NULL).`

`Step 2 :`

`If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from`

`the function`

Step 3 : If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.`Step 4 : Then set 'front = front โ next' and delete 'temp' (free(temp)).`

## Complexity

- Time complexity of DeQueue and EnQueue operation is O(1),Because there is no loop in those operation.
- Time complexity of Display operation is O(n), Since we are traversing to print each n(number of elements) elements.
- Space complexity is O(n), Where n is number of elements.

**Stack Using Linked List**

Explain why a stack is not an appropriate data structure for managing queues.

Draw a diagram or diagrams to show how a stack can be implemented using a linked list.

# Lesson Block 16 Sep 2021

### 4.3.3 Explain the essential features of a computer language.

For example, fixed vocabulary, unambiguous meaning, consistent grammar and syntax

What is the difference between a Syntactical and a Semantic error in a program?

### 4.2.1 Describe the characteristics of standard algorithms on linear arrays

These are: sequential search, binary search, bubble sort, selection sort

### PASS PAPER QUESTION 2021

### Task Complete part A by 11:30

Work on 13 part a and share your pseudo code solution on forum link here

### Task Complete part B, C and D by 12:15

Work on 13 part b ,c and d and share your pseudo code solution on forum link here

### BUBBLE SORT

### SELECTION SORT

### Task Last 20 mins or homework

The code below is close but will not work, it has a semantic error. Your task is to get the program to working in PYTHON.

LINK to IB Pseudo Code Rules

## Selection Visual Representation

Given a list of five elements, the following images illustrate how the selection sort algorithm iterates through the values when sorting them.

The following image shows the unsorted list

**Step 1)**

The first value 21 is compared with the rest of the values to check if it is the minimum value.

3 is the minimum value, so the positions of 21 and 3 are swapped. The values with a green background represent the sorted partition of the list.

**Step 2)**

The value 6 which is the first element in the unsorted partition is compared with the rest of the values to find out if a lower value exists

The value 6 is the minimum value, so it maintains its position.

**Step 3)**

The first element of the unsorted list with the value of 9 is compared with the rest of the values to check if it is the minimum value.

The value 9 is the minimum value, so it maintains its position in the sorted partition.

**Step 4)**

The value 33 is compared with the rest of the values.

## Bubble Sort Visual Representation

Given a list of five elements, the following images illustrate how the bubble sort iterates through the values when sorting them

The following image shows the unsorted list

**First Iteration**

**Step 1)**

The values 21 and 6 are compared to check which one is greater than the other.

21 is greater than 6, so 21 takes the position occupied by 6 while 6 takes the position that was occupied by 21

Our modified list now looks like the one above.