Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Pseudo­code​
: while, for, if, then, else, assignments​
 Operations:​
 Access
...
 Delete
...
 Sort
...
 Combine
...
 
Arrays 
Advantages ­ Immediate access ­ Fixed length ­ No wasted space if used correctly 
Disadvantages ­ Pre determined length ­ May need to expand but unable ­ May only use part of array, creating waste 
Create, Destroy, Is Empty?, Length, Insert / Retrieve / Delete data at given position 
Linked­lists 
Insert after current 
newNode = new ListNode;      Create 
newNode
...
link;    Point to next 
current
...
link; 
current
...
link; 
toDelete = null; 

Inserting ­ Cases to consider 
Case 1: Insert as the first node (into an empty list ​ in front) 
or​
Case 2: new item is smaller than the smallest item in the list (Ordered) 
Case 3: Insert after another node (at back ​ in middle) 
or​

ToString ­ Traversing ­ Algorithm 
for (current = head; current != null; current = current
...
out
...
data); 
} 

Deleting ­ Cases to consider 
Case 1: the list is initially empty
...
 
Case 3: the item to be deleted is somewhere in the list
...
 

 
Type 

Explanation 

Example 

Ordinary 

Each node in a linked list has 2 components: data and link 

TODO lists 

Circular 

Last node points to first ­ if (cur
...
 
Can start traversal at any point ­ no start or end 

Naturally circular structures ­ 
days in week, conveyer belt 

Doubly 

Each node points to not only its successor but also its predecessor 
There are two null: at the first and last nodes 
Advantage: given a node, it is easy to visit its predecessor 

Back button in a browser etc
...
 
Last In First Out (LIFO) 
 
Done using arrays (possible 
with both) 

Push (insert): Adds to top of stack
...
 
Pop: Deletes most recently inserted 
element
...
 
Top: Returns the top element of the 
stack
...
 
Initialise ­ Create an empty stack 
IsFull ­ If there is max (e
...
 arrays) 
IsEmpty
...
 
Associated with each stack is 
TopOfStack
...
 
(2)   Set Stack[TopOfStack] = X 
Pop 
(1)   Set return value to 
Stack[TopOfStack] 
(2)   Decrement TopOfStack by 1 

Newspapers 
 
Plates 
 
Undo button 
 
Reverse Polish Notation 

Queue 

Insertion done at one end, 
while deletion performed at 
the other end 
First In First Out (FIFO) 
 
Done using linked lists 
(possible with both) 
 
Double­Ended Queue 
(Deque) (Pronounced ‘deck’) 
also possible 

Enqueue (insert): Add to rear of queue
...
 
Dequeue: Deletes front / oldest – Must 
exist and not empty
...
 Must exist and not empty
...
 IsFull
...
 

When item enqueued, rear index moves 
forward
...
 
 

Empty queue when back = front ­ 1 
Full queue? back = front ­ 1 
Problem! Solutions: 
• Boolean variable to say if empty or 
not
...
 
• Use a counter of the number of 
elements in the queue
...
 To solve, use a circular 
array 

When an element moves past the end 
of a circular array, it wraps around to 
the beginning
...

o“” 
Recursion 
1 A recursive function calls itself
...
 
3 A test for the base case enables the recursive calls to stop
...
 
 
Example ​
(m ≤ n) “going­up” 
int SumSquares(int m, int n) { 
 if (m < n) 
   return m*m + SumSquares(m+1, n); 
 else 
   return m*m; 
} 

Advantages​
 define things simply and concisely, help express algorithms in a 
form that makes their performance easy to analyse 
Disadvantages​
 not always efficient
...
 If 
both solutions exist, favour the iterative one 
 
Winding 
…
...
 

Sorting 
Name 

O(n) 

Description / Explanation 

Notes 

Real example with data 

Bubble sort 

n² 

Highest value rises to the top 
like a bubble each pass 

 

 

Selection sort 

n² 

Find smallest unsorted value 
and swap with front each 
pass 

 

 

Insertion sort 

n² 

Each pass, take next value, 
find position in sorted array, 
insert, shift others right 

 

 

Binary search 

log(n) 

Go down tree, comparing 
values on the way 

Important to make tree depth 
short as possible ­ Use AVL 

 

Merge sort 

n log (n) 

Recursively sort halves 

 

 

Quick sort 

n² 

Recursively sort around 
pivots 

No merging
...
 
Worst case when data is 
already sorted 

 

Time taken (further right is faster / better) (n = number of items being sorted): 
3​
n​
 > n² > n log n > log n > n > 1 
log​
8 = log​ 3​
(2​
2​
2​ ) = 3 
log​ X = Answer 
base​
Answer ​
base​ = X

 

TREES ­ preOrder(node, left, right);      inOrder(left, node, right)      postOrder(left, right, node) 

AVL Trees 



---