Pseudocode and Algorithms Flashcards
queue
FIFO data structure: ordered collection of items added at the rear and removed from the front. sequence depends on order inserted, size depends on number inserted
array
a finite, ordered set of elements of the same type. grouped under one identifier, each element addressed using index
index
used to reference EACH element of an array
elementary data type
data type built into a programming language e.g. VB, pascal, python
tuple
dynamic data structure: ordered set of elements not necessarily of the same type able to inc/dec in size
structural data type
collection of data (made up of a number of elements) of a specified type e.g. array, string, record
primitive data type
data type PROVIDED by a programming language
n-dimensional array
a finite, ordered set of elements of a specified type indexed by n integers
abstract data type
a data type created by the programmer rather than defined by the programming language.
logical description of how data is viewed and operations that can be performed on it
programmer decides how to build and implement it and uses data types from programming language, user just needs to know state and behaviour
uses data abstraction: encapsulation, hiding details and implementation from user
encapsulation
ensuring a subroutine is completely self contained and independent of any global variables
dynamic data structure
data structure (a COLLECTION of data of a specified type in memory) with the ABILITY to grow and shrink in size in run time, with the aid of a heap
heap
portion of memory which is AUTOMATICALLY allocated and deallocated space as required (dynamic data structures)
adv of dynamic data structures and built in dynamic data structure
- good for implementing data structures when you don’t know max size in advance (can have arbitrary max to prevent overflow but not necessary to allocate memory beforehand)
- if built in dynamic data structure- many methods and functions e.g. pop already written and can be used in other data structures
- good use of memory: only takes up storage required
disadv of dynamic data structures
- can cause OVERFLOW if exceeds max memory limit
- needs memory to store pointers
- harder to program
- often time consuming to search
static data structure
data structure (collection of data of a specified type in memory) which is fixed in size at compile time so can’t inc in size or free up memory whilst the PROGRAM IS RUNNING
adv static data structure
- suitable for storing a fixed number of items e.g. months of year
- size is known so easier to program
- no need for memory wasted on pointers
disadv static data structure
- size decided in advance and no more items can be added if full, irrespective if free space in memory
- wastes storage if items stored is small relative to size of data structure
algorithm
a sequence of steps / set of rules SPECIFYING how to solve a problem, including inputs outputs and processing, written in a way it can easily be translated into high level code and then machine code for execution by the computer if in context of programming.
execute in finite time and produce an expected output for given inputs
a good algorithm
- DESIGNED in such a way that others can UNDERSTAND and MODIFY if necessary
- CLEAR, PRECISELY stated steps with correct OUTPUT for any valid input
- should allow for invalid inputs
- should execute efficiently with as few steps as possible
- should TERMINATE at some point
pseudocode
- halfway between a program, with its structural functions and english, with a solution expressed in a way that can be easily translated, and easily readable WITH NO CONCRETE SYNTAX
- helps develop and outline algorithms and understand the functioning
input and output pseudocode
print(“what is your name”)
myname= input()
OR
myname= input(“what is your name”)
integer
whole number
float/real
number with a fractional part
boolean
only takes values of true or false
character
a letter, number or special character typically represented in ASCII
string
a number of characters, enclosed in single or double quote marks
how to round a number to 3 dp
round(mynum,3)
exponentials
y=x**5 or y= x^5
finding remainder
20 mod 3 = 2
dividing whole
20 div 2 = 10
find length of string
len(string) or stringx.length, returns index of first character, and -1 otherwise. assume 1 is first element of string
find ‘me’ in a string called firststring
firststring.find(me)
finds ASCII value of a character
ord(“a”)
chr(97) ?
finds the CHARACTER value represented by an INTEGER
“Johnny” + “Bates” - what does this do
concatentate strings
convert char to integer
int(“1”)
convert integer to string
str(123)
convert string to float
float(“123.4”)
date format
date(year, month, date)
printed: year-month-day
variables
identifiers (names) for memory locations whose contents will change throughout the course of the program
constants
values that never change WHILST THE PROGRAM is being run
why have constants
in a LONG complex program: no chance of accidentally changing a value by using the identifier for something else
how to define constants
CONST companyPhone = “0124638393”
why have meaningful var names
easier to follow and update
why have standards e.g. camelCaps for var names
less errors and inconsistencies
standards for var names
camelCaps, short meaningful names, caps for constants
program constructs
selection, sequence, iteration
sequence
two or more statements following one after the other. all statements are executed once in the order they appear
assignment statement
a statement where a value is assigned to a variable
selection
used to select which statement will be executed next, depending on some condition, formulated using a relational operator. some statements may not be executed as a result.
not equal to pseudocode
!=
selection eg
if..then..else, switch/case statement
what is a nested loop
a loop is placed within another allowing you to have several alternatives
why have a switch/case
useful when have several alternatives
switch case pseudocode
switch choice:
case 1 : print....
case 2: ....
case 3 : ...
else
print ("...")
endswitchwhich boolean operators take precedence
brackets then AND then OR
iteration
repetition, involves involves a loop to repeat a number of statements. It is either controlled by a condition or repeats a set number of times
iteration eg
while. ..endwhile
repeat. ..until
for. ..next
while…endwhile properties
expression controlling loop = boolean
expression tested at start of every loop :
so input to be tested should be at end of loop
repeat…until properties
boolean expression tested at end of program
done at least once
for…next properties
useful when know how many iterations to be performed
for…next pseudocode
for count = 2 to 12
product = 2 * count
print (“….”)
next count
how to generate a random number between 1 and 6
random(1, 6)
subroutines
a named block of code/SECTION OF THE PROGRAM performing a specific task within the program, used in a long complex program to break it into subroutines: helpful for designing a satisfactory solution. Used in modular programming
function aka inline
a subroutine which assigns a return value to a variable and can be used within expressions
procedure
called by just writing its name but does not assign a result to a variable
existing system function
len(x), int(“12”), input
procedure call vs procedure declaration
displayMenu = procedure call in main program
procedure displayMenu = procedure declaration
how to call a function in main program
option = getChoice //getChoice is function
print (option)
function getChoice
...
choice = input()
return choice
endfunction
parameters
used to pass values or variables into a subroutine
byval
a copy of the actual value is passed and treated as a local variable so value outside the subroutine is not affected
byref
the address of the parameter is passed so if the value is change, it changes in the main program also
pseudocode byval vs byref
procedure abc(x, y: integer; var z: integer) if var then byref, so z is byref x, y is byval
global variable
declared at the top. its scope is the whole program, so it can be accessed throughout the program. it allows data to be shared between subroutines.
local variable
can be used within a subroutine: its scope is the subroutine itself and only exists during its execution, can’t be accessed outside the subroutine and changing it has no effect on variables outside even if same name
encapsulation
ensuring a subroutine is COMPLETELY self contained and independent of any global variables
modular programming
when a long, complex program divided into separate self contained, specific well defined, tasks which can be WRITTEN and tested individually and subdivided further into smaller modules
advantages of subroutines
- understandable as a unit of code so can easily be modified, debugged, maintained, understood especially if the purpose is clearly DEFINED and documented
- can be tested independently, so shortens time to get the whole program working
- can reuse in different parts of the program/different programs once thoroughly tested
- programmers can be given a set of subroutines to work on so program is finished sooner
- the large program is easier to maintain and control
IDE
integrated development environment: a single program helping you write and develop the program more easily made from a number of components. Provides you with many tools to help you enter, edit, compile, test and debug programs
what can an IDE do
- step through the code: allowing the programmer to see the effects of each line of code
- debugging tools allow inspection of variable values, allowing run time detection of errors
- set a watch on a variable so value is displayed every time it changes
- insertion of a breakpoint allows the program to be stopped at a predetermined point in order to inspect its state
- can display stack contents, to show the sequencing through modules/procedures
- code can be examined whilst running, helping logical errors to be pinpointed
- can produced a crash dump, showing the state of variables at the point an error occurs
testing solutions
its complex and time consuming but has to be done throughly and systematically to try and uncover undetected errors. program should work irrespective of data inputted
procedural programming
a program written with a series of step by step instructions on how to solve a problem, usually broken down into a number of smaller modules with calls in the main program to procedures and functions, calling other procedures and functions in turn
how to interpret algorithms
look at comments
look at variable names
follow steps of program
dry run the program
dry running
follow the logic program in the sequence of the computer and note whenever a variable value changes in a trace table and to what value
divide and conquer algorithm
breaking situation into component parts then solving each separately eg binary search: whenever a guess is made, the search area is halved
why have object orientated approach
water of time to decide how to implement abstract data structures and write own subroutines
those using data structure only need to know
state and behaviour
linear search
if items aren’t in a particular sequence, search one by one until required item is found or the end of the list is reached
when are searching algorithms used
when searching items in a file or array in memory
binary search
much more efficient but must be sorted. a divide and conquer algorithm: the portion of the data list to be searched repeatedly divides in half that could contain the desired item. Continued till only 1 item left
types of test data
normal, boundary, erroneous
normal test data
within the expected range and correct data type
boundary test data
data at the ends of the expected range
erroneous
outside the expected range or wrong data type
initialise queue pseudocode
procedure initialise front = 0 rear = -1 size = 0 maxSize = len[array] endprocedure
test empty queue pseudocode
function isEmpty
if size == 0 then
return TRUE
else
return FALSE
endif
endfunctiontest full queue pseudocode
function isFull
if size == maxSize then
return TRUE
else
return FALSE
endif
endfunctionadd element queue pseudocode
procedure enqueue(newitem)
if isFull then
print ("queue is full")
else
rear = rear + 1 MOD len[array]
queue[rear] = newitem
size = size + 1
endif
endprocedureremove element queue pseudocode
function dequeue
if isEmpty then
print ("queue is empty")
item = null
else
item = queue[front]
front = front + 1 MOD len[array]
size = size - 1
endif
return item
endfunctionwhy use a good sorting algorithm
reduces time spent on the task and for inc efficiency
bubble sort
one of the most basic sorting algorithms. bubble up the largest/smallest item to the end of the list, then the second then the third until no more swaps needed
how does a bubble sort work
bubble up the largest /smallest item to the end of the list etc until no more swaps needed. compare each item with the one next to it and swap if greater. repeat n-1 passes, reducing by one on each pass the number of elements to be examined. first n-1 comparisons then n-2 etc
what is a flag for
to ensure no unnecessary passes are made through an already sorted list
record
stores data permanently to read and up date in future in a file on disk. allows the creation and interrogation own files. files consist of a number of records. a record consists of a number of fields each holding one item of data
record pseudocode
studentType= record
integer ID
string firstname
end record
variable studentA: studentType
studentA.surname=…..
queue uses
- output waiting to be printed, stored as a queue on disk: printed first come first serve
- characters typed on a keyboard held in a keyboard buffer
- simulation problems- modelling real life situations to learn something from it: eg optimum number of cashier queues using random number of customers, spending a random amount of time
ways of implementing a queue
- as items leave, all elements move up 1 space: front of queue always first element BUT a lot of processing time if long queue
- implemented as an array with pointers to front and rear. Integer holds max size of array and no. items in queue BUT as space removed from front, free space can’t be filled, and can’t add anymore when rear pointer at the end of array
circular queue
overcomes limitation of a static data structure, When queue full, rear pointer points to first element q[0] where next item will fill assuming empty
problems of a circular queue
requires more effort from programmer and less flexible than dynamic if the maximum size isn’t known in advance
list
an abstract data type consisting of a number of sequenced items where the same item may occur more than once. Sequenced so can refer/index a certain element
list usefulness
useful for a variety of operations and can be used to implement other data structures eg queue
list operation: isEmpty()
test for empty list, returns a boolean value
list operation: append(item)
adds a new item to list at the end of the list
list operation: remove(item)
removes the first occurance of an item from a list eg list1.remove(12)
list operation: search(item)
search for an item in a list eg a.search(22) and returns a boolean value
list operation: length()
returns the number of items
list operation: index(item)
returns the position of an item
list operation: insert(pos, item)
inserts a new item at position pos
list operation: pop()
remove and return the last item in a list
pop(pos)
remove and return the item at pos
how else to implement a list
using an array(static data structure) if list data type isn’t supported and maximum number of data items is known in advance and small
if an array is used to implement a list
programmer has to work out and code algorithms for each list operation
inserting a new item into a list
test if full first, if held in sequential order, first determine where a new item to be added then start at end of list and move the rest of items along in order to make room
deleting an item from the list
after item deleted, the items after have to be moved up one to fill up gap, so are copied into the previous spot in array then last element (duplicated now) is replaced with a blank
stack
a last in first out data structure
application of stacks
- hold return addresses when subroutines are called
- back button in web browsers
- undo button in a word processor
implementing stacks
implemented as static (eg array) with 2 more variables- pointer to top of stack and size of array/max stack size or dynamic
stack operation: push(Item)
adds a new item to the top of the stack
stack operation: pop()
removes and returns the top item from the stack
stack operation: peek()
returns the top item from the stack but does not remove it
stack operation: isEmpty()
tests to see whether stack is empty, returning a Boolean value
stack operation: isFull()
tests to whether stack is full, and returns a Boolean value
stack isEmpty pseudocode
function isEmpty
if top== -1 then
return TRUE
else
return FALSE
endif
endfunctionstack isFull pseudocode
function isFull
if top==maxSize then
return TRUE
else
return FALSE
endif
endfunctionstack push(item) pseudocode
procedure push(item)
if isFull then
print ("Stack full")
else
top = top + 1
s(top)= item
endif
endprocedurestack pop pseudocode
function pop
if isEmpty then
print ("stack empty")
item = null
else
item = s(top)
top = top - 1
return item
endif
endfunctioninsertion sort
sorts one data item at a time, takes one data item from the list an dplaces it in the correct location in the list and repeated until no more unsorted data items in list. More efficient than bubble sort but less than quick/merge
how insertion sort works
on each pass, current data item checked against those already sorted
time complexity of bubble and insertion sorts
bubble sort close to n passes through list, with each pass requiring max n-1 swaps of order O(n^2)
Insertion sort has two nested loops so O(n^2) but if already almost sorted then reduced close to O(n)
types of algorithms
internet related (managing and manipulating huge amount of data on internet, finding pages with relevant info quickly) route finding ( shortest/best distance between two points e.g. transmit packets of data and GPS) compression algorithms (so can be transmitted faster or held in smaller storage space) encryption (so if personal/confidential details intercepted, can't be read)
Global v local variables
Global can be accessed in and outside subroutines and from more than one part of the program
Global is visible throughout program v visible in only one module/construct where declared
Why global variables
Needs to be accessible from various parts of the program
Irrespective of where it’s accessed
E.g. Date
Why prevent using global variables
Makes it difficult to integrate modules
Increases complexity of a program
Conflict with other names in other modules, changed inadvertently
Why parameters better than global variables
Parameters only pass a copy of data so no unforeseen effects in other modules. (Case only if by val)
logic error and when do they typically occur
an error in the logic of the code, although executing, causing it to produce unexpected results, resolved by performing a dry run with a trace table or setting breakpoints
they typically occur at points where decisions have to be made or in the conditions affecting the outcome of a decision
syntax error
an error in the spelling and grammar of the code, identified by an interpreter, unable to execute a line of code
execution error/runtime error
an error that becomes evident during run time, causing a crash because the program is being asked to do something it cannot e.g. retrieve an item from location 11 when only 10 locations
linked list
dynamic data structure used to hold a sequence:
- items in sequence not necessarily held in contiguous data locations or order which they occur in sequence
- each item in list is called a node: it contains a data field (may consist of several subfields) and a next address field aka LINK/POINTER FIELD
- Data field: holds actual data associated with the list item and pointer field holds address of the next item in the sequence
- link field in last item uses null pointer to indicate no further items
- associated with the list is a pointer variable, pointing to (containing the address of) the first node in the list
how can linked lists be stored
array of records
pseudocode: defining a node record
type nodeType
string name
integer pointer
endtype
(in delphi data type and identifier are the other way round and nodeType = record)
dim names[0..5] of nodeType
initialising a linked list
One array consisting of one linked list of free space. Nextfree pointer = address of first item eg 0
Start pointer = first data item in list = null
Last item in free space pointer = null (last available free space in list)
start, nextfree and array pointers when data items have been added
start: points to the first data item in list
nextfree: points to next free location in array (and first free space in free space linked list)
Last data item pointer = null
Last available free space = null
names[p].name
holds name in node[p] ie node pointed to by p
names[p].pointer
holds the value of the pointer in node[p]
priority queue
data structure: ordered collection of items removed from the front. Logical order is dependent on priority of jobs so not necessarily added to the rear.
implementing a priority queue
start at the rear and moving along one place until item with same or higher priority is found, then inserted.
Overflow and underflow
Occurs because not indefinite growth of memory. Occurs if reaches limit/is full and a POP operation is attempted or is empty and PUSH operation is attempted, causing it to crash.
When is overflow/underflow likely
If a faulty piece ends up calling itself in an endless loop ie infinite recursion
Call stack
Stores information about active subroutines whilst a computer program is running. Each call to subroutine is given separate space on the call stack for return addresses, parameters, local variables. Details are hidden from user in all high level languages.
Call stack and return addresses
Call stack keeps track of return address ie address of the instruction control should return to once a subroutine is completed .
Nested subroutines = stack contains several return addresses which are popped as completed.
Recursive subroutines = several calls to itself, so pushes itself to stack as return address. Then popped each time the subroutine ends.
Call stack and local variables
Local variables are only know within the subroutine. Storing on the call stack is more efficient than dynamic memory allocation which uses heap space.
Stack frame
A call stack is composed of stack frames, each corresponding to a call to a subroutine which has not yet terminated. Holds local variables, return address and parameters.
hash table
collection of items stored in such a way that they can be quickly located without looking through all the records eg customer records
how to make data quickly accessible
generate index of the physical address of the file with the data on it using a hashing algorithm
how is an index generated
hashing algorithm applied to value in the key field of each record to transform into address
common hashing technique
dividing key by number of available addresses, and using remainder as address ie MOD
define synonym
two keys which hash to the same address
collisions (hashing)
when two record keys hash to the same address
implementing a hash table
array/list of a given size with a number of empty spaces
searching for an item in a hash table
apply hashing algorithm to key field
examine resulting cell in the list
if the item is there- return it
if cell is empty- item isn’t in the table
if another item in the spot- keep moving forward until found or blank cell (ie not in table)
folding method hashing
divide record key into equal parts, and add them together. if > number of spaces in hash table, then MOD by number of cells
hashing a string
add up ascii values and MOD by number of cells in table
when are collisions more likely and when do you take this into account
when the hash table is more full. take this into account when designing a hashing algorithm and deciding on the table size- you want to MINIMISE COLLISIONS for efficiency eg make it that table is only 70% full when all the items are added
rehashing
process of finding an empty slot when a collision has occurred, can do this by adding one to the hashed address or the ‘plus three’ rehash or hash incremented by 1,3,5..etc
uses of hash table
efficient lookup eg organise indexes as hash table, looking up telephone numbers, user codes and encrypted passwords that need to be searched and verified quickly, implementing dictionary (data structure)
dictionaries
abstract data types consisting of associated pairs of item: a key and a value. eg Whenever the user supplies a key, the value is returned.
implementation of dictionaries
built in data structures in Python and VB, otherwise can be static or dynamic
operations on dictionaries
Create new empty dictionary
Delete a key:value pair eg DEL IDs[188]
Add a pair eg IDs[333]= ‘Maria’
Amend a pair eg IDs[333]= ‘Mandy’
Return a value associated with key k eg IDs[127]
Return True or False depending on whether key is in dictionary eg 634 in IDs
Returns length of dictionary eg len(IDs)
dictionaries and hash tables
hashing key gives address to store in a hash table for fast lookup
other things IDE does
compile/interpret
save/load
run programs
display syntax errors
when would you not binary search
when not in order
when list is too small
when list is skewed
statement
a single instruction which can be executed. some statements can contain others, eg IF and WHILE statements
recursive subroutine
a subroutine which is defined in terms of itself
conditions for recursive subroutines
- must have a base case/stopping condition, so when met it stops calling itself and starts to unwind
- for input values other than the base case, the subroutine should call itself
- the stopping condition should be reached after a finite number of calls
advantages of iterative over recursive
- there’s no limit to how many times you can call it (ie no stack overflow)
- its easier to trace through
