Topic 4 (+Searching and sorting pseudocode)

Identify inputs and outputs required in a solution

Cycle: Input, Processing, Output, Feedback

Sequential

Following in logical orders/sequences

Preconditions

Constrains the state of a system before the next sector of code starts

Post conditions

Conditions after code has been executed

What to do if there's an exception?

Inform developer, then crash

What to do if there's an error?

Inform user, but keep running

Concurrent

When two or more processes are using the same resources at the same time

Describe how concurrent processing can be used to solve a problem

Increases: Computation speed, Complexity of programming language and hardware. Reduces: Complexity of array operations within loops, matrix multiplication/ sorting/ merging files.

I(CS, CPL, H) R(CAOL, MM, S, MF)

How do you evaluate the decision to use concurrent processing in solving a problem?

Saved or wasted time?

Saved or spent money?

Physically possible?

Consequence of not doing it?

Advantages of concurrency

Time

Cost

Disadvantages of concurrency

May get in each others way

Harder to supervise

Abstraction

Removing characteristics from something in order to reduce it to a set of essential characteristics. It's a technique for managing complexity.

Why is abstraction required?

Reduces complexity, enables concentration on essential, ignores distracting details and essential to problem solving.

How to distinguish between real and abstract?

DETAILS

IB assumptions about collections are

Unordered lists

Unknown length

Operations (5 PseudoCode operations)

.addItem()

.resetNext()

.hasNext()

.getNext()

.isEmpty()

.addItem()

Adds an item to the collection

.resetNext()

Starts at the beginning of the collection

.hasNext()

To see if it has another item

.getNext()

retrieves next data point from collection

.isEmpty()

Checks whether its empty

Most efficient search algorithm?

Binary, Olog(N) notation, only works on sorted lists

Sequential search

Slower, O(N) notation

Bubble sort

Quits early if no swaps occur, but LOTS of swaps happen. O(N^2)

When bubble sorting on a list

Compares and swaps every two numbers

Selection sort

No quit early, always N passes. O(N^2)

Flow chart shapes (bubble, parallelogram, rectangle and diamond)

Bubble: Terminator

Parallelogram: Input/ Output

Rectangle: Process

Diamond: Decision

What effects run time?

Hardware

Abstract data types

Compiler Efficiency

Programmers skills

Complexity

Size of input

(H, ADT, CE, PS, C, IS)

Worse case scenario

Max run time

Number of times the principal activity of the algorithm is performed

Best case scenario

Specific instances of input size N

Average case scenario

Most useful

General case

Fundamental operations of a computer

Add, Compare, Retrieve, Store.

Complex operation example

Finding the biggest number in an array

Low level language

Closer to binary, Machine code or Assembly

High level language

Java, C++, HTML

Natural language

Varying vocab

Ambiguous

Grammar & Syntax inconsistent

Computer language

Fixed vocab

Unambiguous meaning

Grammar & Syntax consistent

Why grammar and syntax is important

Easy to learn and use

Less compilation and logical errors

Need for High Level languages

Similar to human language

Needs for computer systems have expanded

Time constraints - too long to write machine code

(HL, NCS, T)

Need for Low Level languages

Close to binary code that's used to process instructions

Compiler

Translates from a high level language to a low level (in batches)

Interpreter

High level to intermediate, then executed by CPU

Why you need compliers and interpreters?

High level to low level langauge

Translated into machine code for CPU to execute

Why do you need BOTH?

Interpreter is faster and warns about syntax errors, easier when debugging

Compiler needed when there's a need to produce executable version of program

Assembler

Assembly to machine code (mnemonics -> binary)

Variables

Storage locations, naming memory locations with a name and data type that can't be changed.

Constant

Identifier with associated value that doesn't change.

Operator

Set of characters that represents an action (CRA)

Object

Instance of a class

Advantages of modular design

Code reusability, Eases program organization and makes future maintenance easier (CR, EPO, ME)

Need for sub programmes

Breaks down tasks into more manageable sections

Distributes development

Code Reusability

Program readability

(BM, DD, CR, PR)

Bubble sort algorithm

int temp;

loop i from 0 to array.length-1

loop j from 0 to array.length-1

if array[i] > array[i+1] then

temp = array[i]

array[i] = array[i+1]

array[i+1] = temp

end if

end loop

end loop

Selection sort algorithm

int temp;

loop i from 0 to array.length-1

loop j from i+1 to array.length

if array[i] > array[j] then

temp = array[i]

array[i] = array[j]

array[j] = temp

end if

end loop

end loop

Sequential search algorithm

loop for i from 0 to array.length

if searchkey == array[i] then

ouput searchkey, "has been found!"

break;

end loop

Finding the minimum and maximum in an array

int min = array[0]

int max = array[0]

loop i from 0 to array.length

if min > array[i] then

min = array[i]

end if

else if max < array[i] then

max = array[i]

end else if

end loop

output "min =", min, "max =", max

Binary Search Algorithm

input key

low = 0

high = array.length-1

found = -1

loop i while found == -1 && low <= high

mid = (low + high) div 2

if array[mid] == key then

found = mid

else if key < array[mid] then

high = mid - 1

else

low = mid + 1

end if

end while

if found >= 0 then

output key, " was found!"

else

output key, " was not found!"

end if

Hours given minutes

Div 60

Minutes remaining

Mod 60 (This was a past paper question!)