U1+2 Fundamentals of Algorithms

define algorithm

a sequence of steps or stages that can be followed to complete a task

decomposition

breaking a problem into a number of sub-problems,

so that each sub-problem accomplishes an identifiable task,

which might itself be further subdivided.

abstraction

the process of removing unnecessary detail from a problem

flowchart symbol input/output

parallelogram

flowchart symbol process

rectangle

flowchart symbol subroutine

box with lines

flowchart symbol start/stop

oval kinda thing

flowchart symbol decision

diamond decision!

dry running an algorithm

inputting things into the variables and doing any processing, to determine the purpose of the simple algorithm

methods of searching

linear and binary search

methods of sorting

bubble and merge sorts

how does a linear search algorithm work

1. Identify a search term. eg 2

2. Look at the first item in the list. 129348

3. Compare the item with the search term. 2 compared to 1 - not found

4. Is the current item the same as the search term? If so, the item has been found. If not, move to the next item. 2 compared to 2 - found

5. Repeat from step two until the last item in the list has been reached. yes

6. If the end of the list has been reached and the search term has not been found, then the search term is not in the list and the algorithm can stop. 0 compared to 8 - not found

look at this pseudocode for linear search

how does a binary search algorithm work

1. Start by setting the counter to the middle position in the list.

2. If the value held there is a match, the search ends.

3. If the value at the midpoint is less than the value to be found, the list is divided in half, the lower half of the list is ignored and the search keeps to the upper half of the list.

4. Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.

5. The search moves to the midpoint of the remaining items. Steps 2-4 continue until a match is made or there are no more items to be found.

look at this pseudocode for binary search

PP2019 Perform a binary search on 1 6 14 21 27 31 35 and write what comparisons you would make to find 30 [3]

compare 21 with 30 [1]

compare 31 with 30 [1]

compare 27 with 30 [1]

which search or sort has a condition that must be met, and what is it

binary search the list must be already ordered

benefits of linear search

• for binary, items must already be in order

• simplicity

• quicker to add new items as items can be added at the end rather than in order

• efficient for smaller lists

benefits of binary search AND WHY

• efficient for large lists

• necause GENERALLY FEWER COMPARISONS on avg

if you have 2ⁿ items in a list, what’s the maximum number of items you need to compare for a binary search

n+1

e.g find 9 in 123456789

comp 5 with 9

comp 7 with 9

comp 8 with 9

comp 9 with 9

9 items, 16 = 2 ^4, 4+1 =5 oh.

how does a merge sort algorithm work (ideal answer from a picture from Mrs A)

1. first the algorithm splits the list in half

   9284 1376

2. it continues to split each new list in half until every sublist has just one element

   9 2 8 4 1 3 7 6

3. working in pairs of lists, the algorithm compares the first item of each sublist and the next, and creates a new list, with the lowest values first

   29 48 13 67

4. it continues checking each item in the list and adding the lowest value into the new list until the list is empty

   2489 1367

5. it continues this process from comparing pairs until all the items are in a newly ordered list

   12346789

how does a bubble sort algorithm work

1. Look at the first number in the list. 9 1 4 2 3

2. Compare the current number with the next number. 9>1

3. Is the next number smaller than the current number? If so, swap the two numbers around. If not, do not swap. 1 9 4 2 3

4. Move to the next number along in the list and make this the current number.

   1 9 4 2 3

5. Repeat from step 2 until the last number in the list has been reached. 1 4 2 3 9

6. If any numbers were swapped, repeat again from step 1. 1 2 3 4 9

7. If the end of the list is reached without any swaps being made, then the list is ordered and the algorithm can stop. 12349

look at this bubble sort pseudocode

if there are n items in a bubble sort, how many maximum passes will we make

n-1

advantages of bubble sort

• simple algorithm so easy to implement on a computer

• efficient way to check if the list is in order already

• does not use much memory as sort is done using original list

advantages of merge sort

• faster for very large lists

VB NET for a decimal

decimal, single, double

VB NET for whole number

integer. short, long

convert string to decimal VB

CDec

convert string to decimal PSEUDOCODE

string to decimal

convert integer to string PSEU

number_to_string()

define data type

what kind of value the variable holds

make gravity a constant holding 9.8 VB

Const Gravity as single = 9.8

make gravity a constant as 9.8 PSEU

Constant GRAVITY = 9.8

Output hello and a string called name PSEU

OUTPUT “hello”, name

output hello and a string called name VB

Console.WriteLine(“Hello” & name)

assign input to name PSEU

name ← USERINPUT

assign input to name VB

Name = Console.ReadLine()

concatenation of string1 and string2 to make string3 PSEU

string3 ← string1 & string2

concatenation of string1 and string2 to make string3 VB

string3 ← string1 7 string2 (same)

check if input number is a number P

if number.isnumeric = true

check if input number is a number VB

If isnumeric(number) then

definite iteration a counter to do something 5 times P

for counter = 1 to 5 do

…

end for

definite iteration a counter to do something 5 times VB

for counter = 1 to 5

…

next

indefinite iteration condition check first, general, P

While …

…

EndWhile

indefinite iteration condition check first, general, VB

do while …

…

loop

indefinite iteration condition check last, general, P

repeat

…

until …

indefinite iteration condition check last, general, VB

do

…

loop until …

simple selection

is the same in al of them so dwww

is there a gap between “else if” for VB, P, both or neither

neitherr

bubble sort algorithm though you dont need to know it !

difference between the two types of subroutine

• procedures do not send any data back to the main program

• functions must return a value to the program

declaring a new procedure PSU

Procedure nameofprocedure(variable)

declaring a new procedure VB

Sub nameofprocedure(variable)

…

end sub

declaring a function PSU

Function nameoffunction(variable)

Return

End function

declaring functions VB

Sub nameoffunction(variable)

return …

end sub

what is div

integer division, how many full times x goes into y

what is mod

remainder (MODremainDer)

not equal to in PSU

<> it is the same in VB

less that or equal to in PSU (or VB its the same)

<=

more that or equal To in VB or PSU its the same

>=

how to remember where the equal sign is

it is alwaus on the right rifht right

generating a random number PSU

Random.randint(start, stop)

generating a random number VB

Imports System.math

randomize()

dim randomnum as integer

randomnum = CINT(*6rnd()+1)

length of string PSU

Len(string)

Length of string VB

Len(string)

OR

string.length()

position of first character in string for VB (or PSU is the same)

String(0)

substring PSU

String(start,end)

substirng VB

String.substring(start, length)

convert character into ASCII code PSU

Char_to_code(variable)

convert character into ASCII code VB

ASC(variable)

convert ASCII code into character PSU

code_to_char(variable)

convert ASCII code into character VB

CHR(variable)

convert to uppercase PSU

Convert_to_upper(variable)

convert to uppercase VB

Variable.ToUpper

convert to lowercase PSU

Convert_to_lower(variable)

convert to lowercase VB

Variable.ToLower

get last character PSU

Variable[last]

i rllly dont believe this

get last character VB

Variable(variable.length-1)

1D array with 3 strings PSU

New 1D array Words[1] of string

OR

names ← [“abc”, “def”]

1D array with 3 strings VB

Dim words(2) as string

OR

dim words as new string() {“abc”, “def”}

2D array 3 people with their surname and first name PSU

dim words(3,2) as string

OR

words ← [ [“Red”,”Cap”], [“Yellow”,”Hoodie”], [“Blue”,”Mask”] ]

2D array for 3 people with their surname and first name VB

Dim words(3,2) as string

OR

Dim words = new string(,) { {“Red”,”Cap”}, {“Yellow”,”Hoodie”}, {“Blue”,”Mask”} }

what is a decimal in other words

real, float

three combining principles

selection, sequence, iteration

what type of loop is definite iteration (CC), and what loop can be used for it

counter controlled

for loop

what type of loop is indefinite iteration (CC), and what loop can be used for it

condition-controlled

PSU: while-endwhile, repeat-until

VB: while-end while, do-loop, do-loop until

input and output in PSU

USERINPUT and OUTPUT

input and output in VB

Console.ReadLine()

Console.WriteLine

generate a random number between 1 and 10 in PSU

RANDOM_INT(1,10)

generating a random number between 1 and 10 in VB is much easier…

Dim random As New Random()

Dim randomNumber As Integer = random.Next(1, 11)

define subroutine

a named ‘out of line’ block of code that may be executed (called) by simply writing its name in a program statement.

advantages of subroutines

• When a problem is decomposed, each problem to be solved can be written within its own subroutine, 

  • which makes it easier to solve

• Each subroutine can be tested separately, 

  • which can save time when debugging

• They can be used repeatedly within the same program without needing to be written more than once

  • This saves on memory space.

  • It saves on maintenance time. If there is a change to be made, it only needs to be changed within one subroutine.

• A team of programmers can work on different subroutines at the same time

  • which speeds up the finish time

  • Subroutines can be stored in a separate file called a “library” and then be used by other programs.

what is a local variable and what can it do

Know that subroutines may declare their own variables, called local variables, and that local variables usually:

• only exist while the subroutine is executing

• are only accessible within the subroutine.

what is a global variable

a variable that can be directly used by any subroutine in the program. is used anywhere in the program and is declared outside the subroutine

difference between local and global variables

global- If we change the value inside the variable from within a subroutine, the original value in the main program also changes.

local - use a copy of the value inside the variable so that we don't affect the original value. (like screenshotting a pic before editing the screenshot so you always have the original)

advantages of local variables

any variables created inside the subroutine will be deleted once the subroutine ends

disadvantages of local variables

we use one more memory location each time we pass a variable into a parameter,

what is a structured approach to programming

a way of writing a program that includes moduralised the code, created interfaces, decomposition and subroutines (including parameters, return values and local variables if a function)

advantages of a structured approach to programming

• Application programs are easier to read and understand.

• Application programs are less likely to contain logic errors.

• Errors are more easily found.

• Higher productivity during application program development.

• Improved application program design.