Pseudocode and Algorithms Flashcards
1
Q
queue
A
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
2
Q
array
A
a finite, ordered set of elements of the same type. grouped under one identifier, each element addressed using index
3
Q
index
A
used to reference EACH element of an array
4
Q
elementary data type
A
data type built into a programming language e.g. VB, pascal, python
5
Q
tuple
A
dynamic data structure: ordered set of elements not necessarily of the same type able to inc/dec in size
6
Q
structural data type
A
collection of data (made up of a number of elements) of a specified type e.g. array, string, record
7
Q
primitive data type
A
data type PROVIDED by a programming language
8
Q
n-dimensional array
A
a finite, ordered set of elements of a specified type indexed by n integers
9
Q
abstract data type
A
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
10
Q
encapsulation
A
ensuring a subroutine is completely self contained and independent of any global variables
11
Q
dynamic data structure
A
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
12
Q
heap
A
portion of memory which is AUTOMATICALLY allocated and deallocated space as required (dynamic data structures)
13
Q
adv of dynamic data structures and built in dynamic data structure
A
- 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
14
Q
disadv of dynamic data structures
A
- can cause OVERFLOW if exceeds max memory limit
- needs memory to store pointers
- harder to program
- often time consuming to search
15
Q
static data structure
A
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
16
Q
adv static data structure
A
- 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
17
Q
disadv static data structure
A
- 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
18
Q
algorithm
A
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
19
Q
a good algorithm
A
- 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
20
Q
pseudocode
A
- 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
21
Q
input and output pseudocode
A
print(“what is your name”)
myname= input()
OR
myname= input(“what is your name”)
22
Q
integer
A
whole number
23
Q
float/real
A
number with a fractional part
24
Q
boolean
A
only takes values of true or false
25
character
a letter, number or special character typically represented in ASCII
26
string
a number of characters, enclosed in single or double quote marks
27
how to round a number to 3 dp
round(mynum,3)
28
exponentials
y=x**5 or y= x^5
29
finding remainder
20 mod 3 = 2
30
dividing whole
20 div 2 = 10
31
find length of string
len(string) or stringx.length, returns index of first character, and -1 otherwise. assume 1 is first element of string
32
find 'me' in a string called firststring
firststring.find(me)
33
finds ASCII value of a character
ord("a")
34
chr(97) ?
finds the CHARACTER value represented by an INTEGER
35
"Johnny" + "Bates" - what does this do
concatentate strings
36
convert char to integer
int("1")
37
convert integer to string
str(123)
38
convert string to float
float("123.4")
39
date format
date(year, month, date)
| printed: year-month-day
40
variables
identifiers (names) for memory locations whose contents will change throughout the course of the program
41
constants
values that never change WHILST THE PROGRAM is being run
42
why have constants
in a LONG complex program: no chance of accidentally changing a value by using the identifier for something else
43
how to define constants
CONST companyPhone = "0124638393"
44
why have meaningful var names
easier to follow and update
45
why have standards e.g. camelCaps for var names
less errors and inconsistencies
46
standards for var names
camelCaps, short meaningful names, caps for constants
47
program constructs
selection, sequence, iteration
48
sequence
two or more statements following one after the other. all statements are executed once in the order they appear
49
assignment statement
a statement where a value is assigned to a variable
50
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.
51
not equal to pseudocode
!=
52
selection eg
if..then..else, switch/case statement
53
what is a nested loop
a loop is placed within another allowing you to have several alternatives
54
why have a switch/case
useful when have several alternatives
55
switch case pseudocode
```
switch choice:
case 1 : print....
case 2: ....
case 3 : ...
else
print ("...")
endswitch
```
56
which boolean operators take precedence
brackets then AND then OR
57
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
58
iteration eg
while. ..endwhile
repeat. ..until
for. ..next
59
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
60
repeat...until properties
boolean expression tested at end of program
| done at least once
61
for...next properties
useful when know how many iterations to be performed
62
for...next pseudocode
for count = 2 to 12
product = 2 * count
print ("....")
next count
63
how to generate a random number between 1 and 6
random(1, 6)
64
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
65
function aka inline
a subroutine which assigns a return value to a variable and can be used within expressions
66
procedure
called by just writing its name but does not assign a result to a variable
67
existing system function
len(x), int("12"), input
68
procedure call vs procedure declaration
displayMenu = procedure call in main program
procedure displayMenu = procedure declaration
69
how to call a function in main program
option = getChoice //getChoice is function
print (option)
```
function getChoice
...
choice = input()
return choice
endfunction
```
70
parameters
used to pass values or variables into a subroutine
71
byval
a copy of the actual value is passed and treated as a local variable so value outside the subroutine is not affected
72
byref
the address of the parameter is passed so if the value is change, it changes in the main program also
73
pseudocode byval vs byref
```
procedure abc(x, y: integer; var z: integer)
if var then byref, so z is byref
x, y is byval
```
74
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.
75
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
76
encapsulation
ensuring a subroutine is COMPLETELY self contained and independent of any global variables
77
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
78
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
79
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
80
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
81
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
82
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
83
how to interpret algorithms
look at comments
look at variable names
follow steps of program
dry run the program
84
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
85
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
86
why have object orientated approach
water of time to decide how to implement abstract data structures and write own subroutines
87
those using data structure only need to know
state and behaviour
88
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
89
when are searching algorithms used
when searching items in a file or array in memory
90
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
91
types of test data
normal, boundary, erroneous
92
normal test data
within the expected range and correct data type
93
boundary test data
data at the ends of the expected range
94
erroneous
outside the expected range or wrong data type
95
initialise queue pseudocode
```
procedure initialise
front = 0
rear = -1
size = 0
maxSize = len[array]
endprocedure
```
96
test empty queue pseudocode
```
function isEmpty
if size == 0 then
return TRUE
else
return FALSE
endif
endfunction
```
97
test full queue pseudocode
```
function isFull
if size == maxSize then
return TRUE
else
return FALSE
endif
endfunction
```
98
add 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
endprocedure
```
99
remove 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
endfunction
```
100
why use a good sorting algorithm
reduces time spent on the task and for inc efficiency
101
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
102
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
103
what is a flag for
to ensure no unnecessary passes are made through an already sorted list
104
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
105
record pseudocode
studentType= record
integer ID
string firstname
end record
variable studentA: studentType
studentA.surname=.....
106
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
107
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
108
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
109
problems of a circular queue
requires more effort from programmer and less flexible than dynamic if the maximum size isn't known in advance
110
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
111
list usefulness
useful for a variety of operations and can be used to implement other data structures eg queue
112
list operation: isEmpty()
test for empty list, returns a boolean value
113
list operation: append(item)
adds a new item to list at the end of the list
114
list operation: remove(item)
removes the first occurance of an item from a list eg list1.remove(12)
115
list operation: search(item)
search for an item in a list eg a.search(22) and returns a boolean value
116
list operation: length()
returns the number of items
117
list operation: index(item)
returns the position of an item
118
list operation: insert(pos, item)
inserts a new item at position pos
119
list operation: pop()
remove and return the last item in a list
120
pop(pos)
remove and return the item at pos
121
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
122
if an array is used to implement a list
programmer has to work out and code algorithms for each list operation
123
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
124
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
125
stack
a last in first out data structure
126
application of stacks
- hold return addresses when subroutines are called
- back button in web browsers
- undo button in a word processor
127
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
128
stack operation: push(Item)
adds a new item to the top of the stack
129
stack operation: pop()
removes and returns the top item from the stack
130
stack operation: peek()
returns the top item from the stack but does not remove it
131
stack operation: isEmpty()
tests to see whether stack is empty, returning a Boolean value
132
stack operation: isFull()
tests to whether stack is full, and returns a Boolean value
133
stack isEmpty pseudocode
```
function isEmpty
if top== -1 then
return TRUE
else
return FALSE
endif
endfunction
```
134
stack isFull pseudocode
```
function isFull
if top==maxSize then
return TRUE
else
return FALSE
endif
endfunction
```
135
stack push(item) pseudocode
```
procedure push(item)
if isFull then
print ("Stack full")
else
top = top + 1
s(top)= item
endif
endprocedure
```
136
stack pop pseudocode
```
function pop
if isEmpty then
print ("stack empty")
item = null
else
item = s(top)
top = top - 1
return item
endif
endfunction
```
137
insertion 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
138
how insertion sort works
on each pass, current data item checked against those already sorted
139
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)
140
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)
```
141
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
142
Why global variables
Needs to be accessible from various parts of the program
Irrespective of where it's accessed
E.g. Date
143
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
144
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)
145
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
146
syntax error
an error in the spelling and grammar of the code, identified by an interpreter, unable to execute a line of code
147
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
148
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
149
how can linked lists be stored
array of records
150
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
151
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)
152
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
153
names[p].name
holds name in node[p] ie node pointed to by p
154
names[p].pointer
holds the value of the pointer in node[p]
155
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.
156
implementing a priority queue
start at the rear and moving along one place until item with same or higher priority is found, then inserted.
157
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.
158
When is overflow/underflow likely
If a faulty piece ends up calling itself in an endless loop ie infinite recursion
159
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.
160
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.
161
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.
162
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.
163
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
164
how to make data quickly accessible
generate index of the physical address of the file with the data on it using a hashing algorithm
165
how is an index generated
hashing algorithm applied to value in the key field of each record to transform into address
166
common hashing technique
dividing key by number of available addresses, and using remainder as address ie MOD
167
define synonym
two keys which hash to the same address
168
collisions (hashing)
when two record keys hash to the same address
169
implementing a hash table
array/list of a given size with a number of empty spaces
170
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)
171
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
172
hashing a string
add up ascii values and MOD by number of cells in table
173
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
174
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
175
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)
176
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.
177
implementation of dictionaries
built in data structures in Python and VB, otherwise can be static or dynamic
178
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)
179
dictionaries and hash tables
hashing key gives address to store in a hash table for fast lookup
180
other things IDE does
compile/interpret
save/load
run programs
display syntax errors
181
when would you not binary search
when not in order
when list is too small
when list is skewed
182
statement
a single instruction which can be executed. some statements can contain others, eg IF and WHILE statements
183
recursive subroutine
a subroutine which is defined in terms of itself
184
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
185
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
