1.3 Algorithms and Programs Flashcards
Write the bubble sort pseudocode
Procedure BubbleSort(List)
n = len(List)
Repeat
swapped = false
for i = 1 to n-1
if List[i-1] > List[i] then
temp = List[i-1]
List[i-1] = List[i]
List[i] = temp
swapped = true
end if
end for
until not swapped
End procedure
Write insertion sort pseudocode
Procedure InsertionSort(List)
n = len(List)
For i = 1 to n-1
temp = List[i]
z = i
While z>0 And List[z-1] > temp
List[z] = List[z-1]
z = z – 1
End While
List[z] = Temp
Next i
End procedure
Write quicksort pseudocode
Procedure Quicksort(List, Lo by val, Hi by val)
TmpLo = Lo
TmpHi = Hi
Pivot = List((Lo+Hi)/2)
While TmpLo <= TmpHi
While List(TmpLo) < Pivot and TmpLo < Hi
TmpLo = TmpLo + 1
End While
While Pivot < List(TmpHi) and TmpHi > Lo
TmpHi = TmpHi - 1
End While
If TmpLo <= TmpHi Then
temp = List[TmpLo]
List[TmpLo] = List[TmpHi]
List[TmpHi] = temp
TmpLo=TmpLo+1
TmpHi=TmpHi-1
End If
End While
if Lo < TmpHi Then QuickSort(List, Lo, TmpHi)
if TmpLo < Hi Then QuickSort(List, TmpLo, Hi)
End Procedure
binary search algorithm
Function BinarySearch(List, SearchItem)
Lo = 0
Hi = Len(List) - 1
While Hi >= Lo
Mid = Lo + (Hi – Lo) Div 2
If SearchItem = List[Mid] Then
Return Mid
Else if SearchItem < List[Mid] Then
Hi = Mid – 1
Else
Lo = Mid + 1
End if
End While
Return -1
End Function
Linear Search algorithm
Function LinearSearch(List, SearchItem)
i = 0
found = false
While i <= Len(List)-1 and Not found
if Searchitem = List[i] then
found = true
else
i = i + 1
end if
End While
If found then
return i
else
return -1
end if
End Function
what are trace-tables used for
use a trace table with a column for each variable and if applicable, a column for output. As values change you should note those changes in the table
what is meant by the term algorithm and give three common methods of defining algorithms
an algorithm is a set of rules to solve a specific problem
flow-chart,
structured english,
pseudocode
what is variable scope and the difference between local and global variables
The scope of a variable describes the parts of the program in which the variable can be accessed.
A global variable - variable can be accessed anywhere in the program - has a global scope
A local variable - variable can only be accessed within its subroutine - has a local scope
Why is it good practise to use constants, meaningful names for identifiers and annotation in computer programs?
-easier to make sense of what certain parts of the program do
-easier to make sense what value the variables hold
-makes it easier for other programmers to make changes to the program if they understand
what is a rogue value
A special value in a data set that indicates the end of the data. For example a list of scores in a test could be entered with -1 indicating there are no more scores to enter
what are the features of a recursive algorithm and what problems might the programmer encounter
recursive algorithms usually require much less code
calls itself
has a terminating condition
when it calls itself it passes one or more parameters
problems:
when it runs it can use more memory as it has to keep track of the multiple calls to the procedures on the run-time stack
debugging recursive algorithms can be more difficult because when an error occurs its not easy to work out which level of the recursion the error has occurred
Explain the purpose of DIV and MOD
DIV - same as divide but only returns the whole part of the number
MOD - carries out the division but only returns the remainder
What is meant by sequence, selection and repetition in programming
sequence - executing lines of code one after the other in the order given
selection - where there is a choice as to whether a set of instructions are executed (e.g. if) selections can also be nested (can contain further e.g. if statements)
repetition - when the same instruction is repeated in a loop. The loops can be nested (loops can contain further loops etc.)
explain the purpose of procedures
procedures are blocks of code which can be called from anywhere in the program to carry out a task.
what is a parameter and explain the difference between value and reference, giving reasons to use each of them
parameters are values that can be sent to a procedure and/or received from a procedure
passing by value means that a copy of the parameter value is passed into the subroutine and doesn’t return a value back.
could be used for e.g. a procedure to draw a dot on a screen might take two parameters x and y. These would only need to be value parameters.
passing by reference means that the memory address of the parameter is passed into the procedure to be used and any changes made to the value is returned to the parameter.
could be used for E.g. a procedure which takes in a length in metres and returns two values for feet and inches
