Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Outline
Tuesday, 4 October 2016

6:41 PM

Topic 4—Computational thinking, problem-solving and programming (45
hours)
4
...
2 Connecting computational thinking and program design (22 hours)
4
...
Return yes/true because we know v is in S
...

Then, repeat this trick on those remaining elements
...
Binary Search
Array of int or string
Input of int or string
2
...
Bubblesort
Inputs
- Unsorted array
Outputs
- Sorted Array
4
...
An algorithm deciding what next chess move to make
Inputs
- Your positions
- The opponents' positions
- What possible moves there are and the consequences
Outputs
- A move
6
...
An algorithm which calculates the sum of the first 107 prime nuumbers
Inputs
- nothing
Output
- Sum
Example precondition: array input is not null
Binary Search
Pre: array is sored
...
Cleaning your teeth
Precondition
- Teeth exist
Post-condition
- Teeth are clean
3
...

Precondition
- They exist and are available
Post-condition
- Meal is edible
5
...

Precondition
- N is an integer greater than 1
Post-condition
- The output is actually the output

21/02/17
Wake up at 10:00 am
Run washing machine at 10:10 am
Stack dishwasher at 10:15 am
Run dishwasher at 10:20 am
Watch Maths lecture and do tutorial questions sheet at 10:25 am
Hang out clothes at 10:50 am
Unstack dishwasher at 11:00 am
Wash wooden spoons and cutting boards at 11:05 am
SUMOFSQUARES=0
Loop INDEX from 1 to 100:
Topic 4 Page 3

Loop INDEX from 1 to 100:
Output INDEX^2
SUMOFSQUARES = SUMOFSQUARES + INDEX^2
End loop
Output SUMOFSQUARES
Cached algorithm
SUM = 0
Loop index from 1 to 100
SQUARE = INDEX^2
Output SQUARE
SUM = SUM + SQUARE
End loop
Output sum

23/02/17
Write as many details about yourself as you can
...
I store all my notes on my computer
...

I have moved house 3 times
...
Write which of the above details would probably be
recorded if you enrol at that university
...

Went to QASMT
...

check = false
loop i from 0 to n-2 <- worse case n-1 times
loop j from i+1 to n-1 <- worst case n-1 times
if NAMES[i] = NAMES[j] <- this gets done <=(n-1)2 times (n2-2n+1)
check = true;
end if
end loop
end loop
output check
Given a sorted array S of integers, find whether a value v, in in S
i=0
loop while i < S
...
length
if v = S[i] <- happens s
...
length
running tie: 3n
running time is proportional to n

Binary search halves search space every step
Binary search
...

input v
result = false
loop j from 0 to s
...
length-1 <- n times
if s[j] + s[i] = v <- 4
result = true
Topic 4 Page 5

result = true
break
end if
end loop
end loop
output result
~4n2
Efficiency: running time ∝ to n2
O(n2)
n times
log n (Binary search)
∝ n log n
HW: Find a linear algorithm to solve the "two sum" problem
...
length
i=0
j=n-1
loop while i <= j <- loop runs n times
sum = s[i] + s[j]
if sum = v
return true
if sum > v
j=j-1
else
i=i+1
return false
Overall:
7n + 4 operations
Running time ∝ n
O(n)

20/07/17
INPUT A, B, C, D
maximum = A
if B > maximum
then maximum = B
if C > maximum
then maximum = C
if D > maximum
then maximum = D
output maximum
22 fundamental operations to do this one thing

1/08/17
N

SUM

COUNT

OUTPUT

3

0

0

-

13

3

1

-

33

16

2

-

33

49

3

16

SUM = 0
Topic 4 Page 6

SUM = 0
COUNT = 0
Input N
loop while N is not empty
SUM = SUM + N
COUNT = COUNT + 1
Input N
end loop
Output SUM/COUNT
IB Past Paper Question
K

P

K>1

output

3

1

yes

3 (K)

2

2

yes

2 (K)

1

2

no

2 (P)

K=3
P=1
loop while K>1
output K
K=K-1
P=P*K
end loop
output P
Algorithm on the board
A

B

B =/= 0 TEMP

A mod B

168

86

-

-

-

86

82

true

86

82

82

4

true

82

4

4

2

true

4

2

2

0

true

2

0

false

2/08/17
A

B

B =/= 0

2442

1128

yes

1128

186

yes

186

12

yes

12

6

yes

6

0

no

MAX

SUM

COUNT

output

10

0

0

10

6

7

10

3

7

OK

10

4

7

OK

Total = 13
Topic 4 Page 7

Total = 13
Max = 8
FIRST

SECOND COUNT output

12

14
1

Identify the error in this algorithm
The error in this algorithm is that it outputs all the factors that both of them have and not the ones
they share
...

N

ROW

COLUMN K

3

9

3

0

0

8

3

0

1

7

3

0

2

6

3

1

0

5

3

1

1

4

3

1

2

3

3

2

0

2

3

2

1

1

3

2

2

0

9

8

7

6

5

4

3

2

1

3/08/17
Problem:
Given an array of n integers, develop an algorithm that will output (print) the numbers of the array
and their frequencies
...

Consider the following algorithms
...

Algorithm A:
SUM = 0
input N = 5
loop I from 1 to N
loop J from 1 to I
SUM = SUM + 1
end loop
end loop
output "The Sum is:" + SUM
Algorithm B:
SUM = 0
input N = 5
loop I from 1 to N
SUM = SUM + I
end loop
output "the Sum is:" + SUM

Topic 4 Page 8

Algorithm C:
SUM = 0
input N = 5
SUM = N * (N+1)/2
output "The Sum is:" +SUM
Flag
FOUND = False
FOUND = True
FOUND = False

4/08/17
A = 10
B=4
Runs infinite times
A=4
B = 10
Runs 0 times
A = 10
B=9
"com" "sci" "ftw"
A = 10
B=0
Com, ftw
A

B

20

2

19

2

9

2

4

2
--

8/08/17
4
...
6 -> 4
...
8
Learning Intention: The basic terms of programming including variable, constant, operator and
objects and when to use variables vs constants in algorithms
Variable
- An identifier of a memory location to store data in a program
...

- Has a name and data type determined at its creation and cannot be changed
...
3
...
3
...

Success Criteria: You will be able to understand the characteristics and applications of collections
and be able to construct pseudocode algorithms using access methods of collections
...
addItem(VEHICLE1)
VEHICLES
...
addItem(VEHICLE3)
loop while VEHICLES
...
getNext()
if TEMPVEH
...

(These are the absent students)
Create a collection of arrays
Add the weeks arrays to the collection
Write an algorithm to check how many times
"Benson" was absent and also how many times "Andrew" was absent
...
addItem(MONDAY)
ABSENT
...
addItem(WEDNESDAY)
ABSENT
...
addItem(FRIDAY)
AA = 0
BA = 0
loop from i to 5
CURRENT = ABSENT
...
length
if Andrew was absent
then AA = AA + 1
else if Benson was absent
then BA = BA + 1
end if
end loop
end loop
output "Benson was away " + BA + " times"
output "Andrew was away " + AA + " times"

10/08/17
Define the term sub-program
performs a specific and predefined task
sub-program is a section of computer instructions
Topic 4 Page 10

sub-program is a section of computer instructions
Discuss the importance and advantages of subprograms
...
[2 marks]
One advantage of a collection is that it allows for categorisation of certain data
...

Have predefined actions/algorithms which programmers can immediately use
Allows for easy iteration through a collection
Allow for the storage of an unknown number of data items
no memory is wasted which can increase computer performance

11/08/17

Topic 4 Page 11

4
...
1 General principles (10 hours)
The basic ideas and their application should be illustrated with non-computer examples
...
The teacher support material illustrates examples such as the home/locker/ knapsack for
thinking ahead
...
1
...


Binary Search
A sorted array has its elements
arranged in a specific order
First compare v to the element 'x'
which is in the middle of S
If v = x then we're done
...

If v < x then we can
immediately throw away the
upper half of S
If v > x then we can throw
away the lower half of S

Organised Notes
Binary search is a sorting algorithm where the input array has its element arranged in a specific order (often
alphabetical or ascending numerically)
...

The outcome of thinking procedurally is to:
Identify the components of a problem
...
g
...

e
...
pour water into tea pot… pour tea into cup etc…

Determine the order of steps needed to solve a problem
...
g
...

e
...
boiling kettle can be turned into a sub-procedure

In the second and third cases
we have at most n/2 elements
left to consider
...

•
4
...
2 Evaluate whether the order
in which activities are
undertaken will result in the
required outcome
...


4
...
3 Explain the role of subprocedures in solving a problem
...
1
...


Organised Notes
Thinking logically is using decisions and conditions to solve a problem
...
Computers process data logically but this is not
“thinking”
...
In order for these instructions to
work then the programmer must think logically in order to design the program
...


4
...
5 Identify the decisions
required for the solution to a
specified problem
...
1
...

4
...
7 Explain the relationship
between the decisions and
conditions of a system
...
1
...


Topic 4 Page 14

Thinking ahead
6:56 PM

Topic

Class Notes

Organised Notes

4
...
9 Identify the inputs and
outputs required in a solution
...


4
...
10 Identify pre-planning in a • Gantt charts
Caching is the storage of data which could/will be used at a later point in an algorithm
...
• Caching - the storage of data which algorithm much faster by avoiding duplicate calculations
...
g
...
1
...


• Explain the need for preconditions
Exam Question: Explain why an algorithm might need a precondition
...
An algorithm might need a
precondition to function correctly and to prevent potential errors
...
1
...

must be true immediately before
execution of an algorithm
• A post-condition is a condition
which will be true after the
execution of an algorithm
• An algorithm needs a precondition
to be true
• An algorithm makes the postcondition true
• Preconditions are things you can say
about inputs
(e
...
Array has to be sorted)

•

4
...
13 Identify exceptions that
need to be considered in a
specified problem solution
...
An algorithm needs a precondition in order to be true
...
An algorithm makes the
post-condition true
...
1
...


• Gant chart
• Concurrent processing =/= parallel
processing (IB is concerned with
concurrent)
• Concurrent processing - a style of
executing an algorithm in which
multiple tasks are completed during
overlapping time periods
• Different TO parallel processing

Concurrent processing is a style of executing an algorithm in which multiple tasks are completed during
overlapping time periods
...
1
...

4
...
16 Evaluate the decision to
use concurrent processing in
solving a problem
...

Think about if you’ve saved or wasted time?
Have you saved money or had to spend more money?
Is it physically possible to do the things concurrently?
What would be the consequence of NOT doing things concurrently?

Topic 4 Page 16

Thinking abstractly
Topic

Class Notes

4
...
17 Identify examples of
abstraction
...

details from those users / clients
who don't need to know about
them
• e
...
Maps are examples of
abstraction
• Abstract can be used as a verb
• Example of abstraction in code, One
big function /\ A function that calls
on smaller functions

Organised Notes

4
...
18 Explain why abstraction is
required in the derivation of
computational solutions for a
specified situation
...


4
...
19 Construct an abstraction
from a specified situation
...

A koala might be interested in the tree, but not the specific carvings, only the fact that it is a gum tree
A farmer might be interested only in the fact that it is a tree which must be cleared
...
1
...


Topic 4 Page 17

4
...
2 Connecting computational thinking and program design (22 hours)
The focus of this topic is how an understanding of programming languages enhances the students’ understanding of
computational thinking and provides them with opportunities for practical, hands-on experience of applying
computational thinking to practical outcomes
...
Answers will only be required in pseudocode
...

Working code will not be assessed in the externally assessed components
...
2
...


Organised Notes
Sequential Search works by starting at the first element and then comparing each element to the
one it is looking for until it finds it
...
If they
are unequal, the lower or upper half of the array is eliminated depending on the result and the
process repeats in the remaining array until it is successful
...
The algorithm passes through the list until no swaps
are needed
...
The algorithm proceeds by finding the smallest element in the unsorted list and
swapping it with the leftmost unsorted element and moving the sublist boundaries one element to
the right
...
2
...


Collections
List
Order is important
Duplicate elements are allowed
Order matters in programming (e
...

compared to shopping list)
...

NB: Not required to return anything

4
...
3 Discuss an algorithm to
solve a specific problem
...


Types of collections:
Type of collection Duplicate Elements? Order Important?
List

Yes

Yes

Queue

Yes

Yes

Stack

Yes

Yes

Set

No

No

Multi-set

Yes

No

Operations of collections:
addItem()
Adds an item to the collection
...
Iterates through one every time
...

hasNext()
Returns a boolean based on if the collection has an element next
...


A binary search is faster, but can only be performed in a SORTED list
...
But it makes lots of swaps
...
But it makes fewer swaps maximum of N swaps
Both bubble and selection sort are equally complex
...
2
...


Start or end

Input or output

Process

Decision

Topic 4 Page 18

Decision

4
...
5 Analyse an algorithm
presented as pseudocode
...
2
...


Success Criteria (4
...
6 + 4
...
7): You will be
You should be able to:
- Propose suitable algorithms to attack a specific problem
able to:
- Propose suitable algorithms to attack a
- Explain the suitability of algorithms in terms of efficiency, correctness, reliability, and
specificc problem
flexibility
- Explain the suitability of algorithms in
terms of efficiency, correctness,
reliability, and flexibility

4
...
7 Suggest suitable algorithms
to solve a specific problem
...
2
...

• (n2-2n+1)
• Only pay attention to first term (other
terms get ignored)
• n = 1000
• 1000000-2000+1
• Worst case running time is proportional to
n2
• Algorithm Efficiency (Running time)
• Fastest
1 - hash table lookup
log(n) - Binary Search
n - Sequential Search
n log n - Merge sort, quick sort
n2 - Search for repetitions, Selection
sort, bubble sort
n3
n4
n10000
2n - Travelling Salesman
• If it's below line, then it's a hard problem
• Exam: Find n, n2
• What's the efficiency of this algorithm…

4
...
9 Determine the number of
times a step in an algorithm will
be performed for given input
data
...
As Computer Scientists, we only care about the worst case
running time
...

A nested loop that repeats times takes
(or
) times to run
...

O(n)
Big O notation summary
Notation

Type

Examples

Description

O(1)

Constant

Hash table access

Remains constant regardless of the
size of the data

O(log n)

Logarithmic Binary search of a sorted table Increases by a constant
...


O(< n)

Sublinear

Search using parallel procesing Performs at less than linear and more
than logarithmic levels
...
If n
list
doubles, time to perform doubles
...
g
...


Topic 4 Page 19

4
...
3 introduction to programming (13 hours)
Nature of programming languages
Use of programming languages

Topic 4 Page 20

Nature of programming languages
Topic

Class Notes

Organised Notes

4
...
1 State the fundamental
operations of a computer

• The Central Processing Unit of a computer can perform a
certain small set of operations
• These operations include:
• Retrieve data from memory
• Store data to memory
• Add, Subtract, Multiply or Divide two binary numbers
• Compare two binary numbers
• In addition, most CPU can perform some bitwise Boolean
operations on two binary numbers

All CPUs have sets of instructions, also called the fundamental operations, that
enable commands to be processed
...
g
...


4
...
2 Distinguish between
fundamental and compound
operations of a computer
...
3
...


• For example: Find the maximum of four numbers: a, b, c and
d
...
It might almost seem like a fundamental
operation
...

Count the fundamental operations used
...
It
might almost seem like a fundamental operation
...

(IMPORTANT)
What happens if a programer accidentally uses a keyword to
name a variable

The syntax refers to the structure of the words used in a particular language and the
rules for constructing statements in said language
...

A compound operation is an operation that involves a number of stages and other
operations
...


The semantics refers to the meaning of the statements constructed
...

The essential features of a computer language is that it has:
- Fixed vocabulary
- Is unambiguous in meaning
- Consistent grammar & syntax

4
...
4 Explain the need for higher Machine code
level languages
...

Higher-level languages make abstraction easier because the
code is easier to understand, meaning that the coder can find
easier abstractions in the code
...
The code is very difficult
to read, debug and maintain
...
However it is still very
difficult to debug, and abstraction is not easy
...
They are much more
readable, maintainable, and abstraction is much easier
...

The code is very difficult to read, debug and maintain
...
3
...


An interpreter goes through the process of translation every time the high-level
program is run
...

This can be slower to run than compiled languages, however debugging logical and
run-time errors can be easier
...

Assembler
An assembler is a program that takes basic computer
instructions and converts them into a pattern of bits that the
computer's processor can use to perform its basic operations
...
e
...

JVM
A Java virtual machine (JVM), an implementation of the Java
Virtual Machine Specification, interprets compiled Java binary
code (called bytecode) for a computer's processor (or
"hardware platform") so that it can perform a Java program's
instructions
...
However it is still very difficult to debug, and abstraction is not
easy
...
They are much more readable, maintainable, and abstraction is much easier
...

Higher-level languages make abstraction easier because they hide things that the
programmer does not need to know about, making the code easier to understand for
the programmer which allows the programmer to find easier abstractions
...

The resulting file then runs comparatively quickly because it doesn’t need to go
through the translation process again
...
Text files written with a
...
class files (written in Java Virtual Machine bytecode)
...
It can now be
run on any machine which has the JVM interpreter installed
...
There is no programming language specified in the
SL/HL core
...

Topic

Class Notes

Organised Notes

4
...
6 Define the terms: variable, Variable
constant, operator, object
...

- The value can be changed during normal execution
of the program
- the value is variable
...

Operator
- A character/set of characters
- Represents an action
...
The value can
be changed during normal execution of the program and the value is variable
...


4
...
7 Define the operators =, ≠,
<, <=, >, >=, mod, div
...
The value is constant
...

An operator is a character/set of characters that represents an action
...

Arithmetic operators (+, -, div, mod) for doing simple mathematical calculations
...

Equality & Relational operators (<, >, >=, <=, ==, !=,
...


Arithmetic operator
+ is used for adding two numbers (also used for String concatenation)
- is used for subtractions
* is used for multiplication
mod: returns the remainder of a division calculation
div: returns the numbers of times X divides into Y without a remainder
/ is used for division in OOP (but cannot be used in Pseudocode)
% is used for mod in OOP (but cannot be used in Pseudocode)
Unary operators
++ : Increment operator; increments a value by 1
I++ : is the same as I = I + 1
-- : Decrement operator; decrements a value by 1
I-- : is the same as I = I -1
Equality and Relational Operators
== : Equal to (only for non-Strings!)
!= or ≠ : Not equal to
> : Greater than
>= : Greater than or equal to
< : Less than
<= : Less than or equal to

4
...
8 Analyse the use of
variables, constants and
operators in algorithms
...
25 and why is an operator required?
When should a variable be used?
Variables should be used when the value of something
needs to be changed
...

When should operators be used?
Operators should be used when the value of a variable
needs to be changed
...
3
...

Construct algorithms using looping and branching
NUM = 5
if num < 3
then output "under 3"
else i
4
...
10 Describe the
characteristics and applications
of a collection
...

of the same type
size is variable
Applications of lists:
The order of elements in a collection is typically not
- Useful for group of items when you don’t know how many items you’ll be
known
needing/using (contrast to arrays where the size is set in stone at creation)
If you don't know the order of elements then you need to
- Because the collection is only as big as you need it to be, it is an efficient use of RAM
store them in a variable size data structure
...

- Can be of any data type (primitive or even your own object)
List is a type of collection
Topic 4 Page 22

List is a type of collection
4
...
11 Construct algorithms
using the access methods of a
collection
...
3
...


A sub-program is a set of computer instructions that perform a specific and predefined
task
...
This is an advantage because it improves the efficiency of the
programmers
...
This improves the maintanability of the code, making
the purpose of each sub-program clear
...
This allows for easy iteration through a collection
...
This ensures that no memory is wasted, which can increase computer
performance
...
3
...


Topic 4 Page 23

IB Questions
The following list of numbers need to be put into ascending order
...
[1 mark]

Consider the following algorithm that inputs

and , and outputs
...
[1 mark]
b) State the purpose of the algorithm
Question:
a) Express the logical xor operation using a truth table [2 marks]
b) Construct the simplified Boolean expression for output in terms of input ,
A

B

C

X

0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

0

and

for the following truth table
...
For
example all_even(246) outputs true and all_even(256) outputs false
...

EVEN = true
loop while (N > 0) and (EVEN = true)
if (N mod 10)mod 2 = 2 1 then
EVEN = false
end if
end loop
output EVEN

a) Explain why the algorithm is not correct
...
[3 marks]

Topic 4 Page 24



---