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

---

General Notes
29/08/17
Data structures
ArrayList
Delete something in an array - left with an empty space
Q: What's wrong with arrays?
Nothing if you know how much data you will be storing
Arrays have a fixed length
Issues with arrays in memory
nodes
few little consecutive chunks of memory
memory cells that store data, integer, string or some other object
also stores a pointer
Pointer - memory address of some object
Pointer to an object - memory address of that object
Give it a name and the computer will know that it refers to that piece of memory
First node is called head last note is called tail

30/08/17
Logical representations of linked list
Insertion
Deletion
Doubly linked list
Performance of the linked list
Space: O(n)
Insertion: O(1)
Deletion: O(1)
Visit each node in the list: O(n) time
Nodes are objects
Doubly linked lit has a previous pointer and a next pointer
Insertion
Circularly linked list
Singularly circularly linked lists
and Doubly circularly linked lists

11/10/17
TOH(n):
TOH(n-1) // onto tower 2
move bottom one to tower 3
TOH (n-1) // onto tower 3
Sequential Search:
input ARRAY
input VALUE
sequentialSearch(0, VALUE, ARRAY)
function sequentialSearch(I, VALUE, ARRAY)
if I >= ARRAY
...
left)
output T
...
right)

*if T = nil
then return

PRETRAV(T)
*
output T
...
LEFT)
PRETRAV(T
...
left)
POSTTRAV(T
...
data)
TRIANGLES(N) // N is an integer >= 0
if N = 0
return 0
else
N + TRIANGLES(N-1)
Trace the algorithm with an input of N=6
...
Consider the following recursive algorithm FUN(X, N), where X and N are two integers
...

a) Determine how many times multiplication is performed when this algorithm is executed
...
insert
• takes one integer as a parameter
• adds the integer to the tree
BinarySearchTree
...

Stacks and queues can be implemented in a linked list by making methods that pertain to the
stack/queue
...
g
...

State one method exclusive to a stack
...
[1 mark]

State two applications of a stack/queue
...
Modelling real world queues
2
...


Explain what are disallowed operations in terms of stacks and queues
...

Outline why a queue can be used to store the data
...
If v is in the array,
the method should return the row and column at which v is located in the array
...

SEARCH(A, V)
input A
input v
loop row from 0 to 3
loop column from 0 to 4[0]
if v = A[column][row]
return column, row
break
end if
end loop
end loop
return -1, -1
SEARCH(A, v)
loop I from 0 to 2
loop J from 0 to 3
if v = A[I][J]
output {I, J}
return
end if
end loop
end loop
output {-1, -1}

31/10/17
Stacks as arrays
Topic 5 Page 3

Stacks as arrays
For a stack, we store only the array, and an integer which is the size of the stack (initilly 0_
Push(34) size of stack is 5, it would be in the 6th position of the array
...

Question: What do we have to do when we enqueue(e)
Increase the tail index by one, add 'e' to that position of the array
...
length)
Question: What do we have to do when we dequeue?
Increase the head index by one, clear hat position, and return the relevant element
What if we don't know the maximum size in advance?

2/11/17
a

b

return

b == 0

a <= 3 * b

5

5

10

false

true

7

4

8

false

true

9

3

6

false

true

11

2

4

false

false

6

1

2

false

false

1

0

1

true

BASE!!

insertAtHead(12);
insertAtTail(16);
12, 3, 5, 7, 42, 16

15/11/17
A head node, tail node,
Each node points to the next and previous one
Data; A pointer/reference to the pervious node; next node;
Recursive solutions can be memory intensive as they call the method again and again, meaning that they keep using
memory
...

A stack is a LIFO data structure:
In the game it allows the "undo function to work/ movement/steps can be retraced
loop while S
...
enqueue(S
...
isEmpty() and NOT Q
...
pop()
Q
...
Empty()
output "incomplete process"
end if
A dynamic queue would not have a predetermined/fixed size;
Memory is allocated as required/efficient use of memory/flexible size/ there is always sufficient memory to
accommodate the queue;
A linked list is a dynamic data structure meaning that it does not have a fixed size
...

award [1] for a feature of a linked list
award [1] for relating it to the given scenario
b) the elements in the stack may be reversed using a queue using the stack pop() method, which removes the most
recent value and returns it
...
1 Abstract data structures
5
...


Students should be able to describe the most common data structures (arrays, stacks, queues, linked
lists, binary trees) and the most common data processing operations on each of the basic data
structures (addition, deletion and retrieval of data, traversal, searching for a given data, sorting of
data into some order)
...

The basic ideas and their application should be illustrated with non-computer examples
...


Topic 5 Page 6

Thinking recursively
Topic

Class Notes

5
...
1 Identify a situation that
requires the use of recursive
thinking
...
It is simply a method that calls itself
...

• Define a sequence as follows:
a0 = 0, ak = k + ak-1
• A linked list could be a recursive object
• A binary Tree could be a recursive object
• Exam question - come up with an algorithm to
solve a problem - come up with a recursive
algorithm
• could be easy, change it into recursive
algorithm
• How can we make it into smaller versions of the
same problem

Organised Notes

5
...
2 Identify recursive thinking
in a specified problem solution
...
g
...

- Each move consists of taking the upper disk from one of the rods and sliding it onto another
rod, on top of the other disks that may already be present on that rod
...


5
...
3 Trace a recursive algorithm Use trace tables
to express a solution to a
problem
...
Write down the known values, going down the table as it changes
2
...
Fill in the rest of the output column

Topic 5 Page 7

Abstract data structures
Topic

Class Notes

Organised Notes

5
...
4 Describe the characteristics
of a twodimensional array
...
They are not stored as a continous block of memory,
they are stored as an array of pointers to the other arrays
...


• stack - data structure which stores a set of
elements and supports the following
operations
• push(e) - inserts a new element e into the
set
• pop() - removes element on stack which
was pushed on most recently and returns
it
• isEmpty() - returns true nothing in the
stack, and false otherwise
• stacks and queues on blackboard
• Disallowed operations - anything else
which modifies a stack
• push (e) adds e to 'top' of stack
• pop() removes/returns the 'top' of stack
• isEmpty()
• peek()
• LIFO (last in first out)
• Depth First Search!
• Any recursive algorithm uses a stack
implicity
• Implementing a Stack - use a linked list
• Create a linked list that only allows
insertions at the head and deletions at the
head
• Another way is as an array
• What information would you need to
store? Store how many spaces in array
• Performance Guarantees
• pop(): O(1)
• push(e): O(1)
• Space: O(n)

A stack is a last in first out (LIFO) abstract data structure that stores a set of elements
...

- The pop() method removes and returns the item that is on top of the stack
...


Queue - data structure which stores a set of
elements and supports the following
operations
• Enqueue(e) - This operation inserts a
new element e into the set
• Dequeue - This operation removes
the element on the queue which was
added earliest and returns it
• Deque - method that is not relevant
to IB
• isEmpty()
Disallowed operations - Any operation
which modifies the elements in the queue
FIFO queue property;
Applications - Breadth First Search,
Implementing a Queue
use a LinkedList
enqueue(e) would insert an element at the
tail
dequeue() would remove and return the
element at the head
is Empty() would return trure if the head
was null; false otherwise

A queue is a first in first out (FIFO) abstract data structure that stores a set of elements
...

- The dequeue() method removes the element on the queue that was added the earliest
...


5
...
5 Construct algorithms using
twodimensional arrays
...
1
...


Applications of a stack:
- Depth First Search
- Pairing Algorithms
How to implement a stack:
- If you create a linked list, but only allow insertions at the head and deletions at the head, then
you have created a stack!
- Use a simple array
Performance guarantees:
pop() - O(1)
push(e) - O(1)
isEmpty - O(n)

5
...
7 Construct algorithms using
the access methods of a stack
...
1
...


Topic 5 Page 8

Applications of a queue:
- Breadth first search
- Queues of print jobs
- Modelling real world queues

How to implement a queue:
- If you create a linked list, but only allow insertions at the tail and deletions at the head, then
you have created a queue!
- Use a simple array
Performance guarantees:
enqueue() - O(1)
dequeue(e) - O(1)
isEmpty() - O(n)

was null; false otherwise
Performance Guarantees
Another way to implement a queue is to
use a simple array
5
...
9 Construct algorithms using
the access methods of a queue
...
1
...


Arrays are static data structures that can't change size while stacks and queues are dynamic data
structures that can change size
...

Stack:
There must be a variable that is equal to the index number of the last item put into the array, in order
to input new data
...
Then increment and the object to the array at position
...
Return what is at position and decrement by one
...
Start both variables as -1
...
A check must be done to see if the tail is at
the end of the array and the head at the beginning
...
If head = -1, make it 0
...
If tail is not at the end of the array increment tail
by 1 and add the item to the tail position
...
Return what is at position head
...


Topic 5 Page 9

Linked Lists
Linked lists will be examined at the level of diagrams and descriptions
...


Topic

Class Notes

5
...
11 Describe the features and
characteristics of a dynamic data
structure
...
1
...


A linked list is a linear collection of self-referential structures, called nodes, connected by pointer links
...
This pointer to the first node of a list
is typically named head
...


Inserting Into A Linked List
Inserting a new node into a linked list has three special cases:
1
...
Insertion at the end of the list
3
...
The algorithm sets both head and tail to point
to the new node
...
The new node is inserted right before the current head node
2
...
Update head link to point to the new node
Inserting at the end:
1
...
Update the "next" link of the current tail node, to point to new node
3
...
New node is inserted between two existing nodes
...

2
...

3
...


5
...
13 Sketch linked lists (single,
double and circular)
...
Each pointer works in one direction only
...
One to
next, one to previous
...
The
last element's pointer points to head (creating a circle)
...
Students are not expected to construct
tree algorithms using pseudocode
...


Topic

Class Notes

Organised Notes

5
...
14 Describe how trees
operate logically (both binary
and non-binary)
...

• Leaves are at the bottom and don't have a
child
• A binary search tree is a binary tree where
each node stores a piece of data
...
data a
...
data in left subtree and
a
...
right
...

- print everything in left subtree of
node
- print that node
- print everything in the right subtree
of node
• This prints everything in order
• e
...
D, L, M, P, S, T, V, W, Z
• pre order traversal
- Print node's data
- print everything in the left subtree
of the node
- print everything in the right subtree
• post order traversal
- print everything in the left subtree
of the node
- print everything in the right subtree
of the node
- print node's data
...
Each node has two
child nodes, the "left" and the "right" nodes
...
The "root" node
points to the top-most node in the tree
...


A non-binary tree is a tree in which at least one node has more than two children
...
1
...


Parent: A node in a tree that has children (left, right or both)
Left-child: A node on the left hand side below a parent node
Right-child: A node on the right hand side below a parent node
Root: The top node in a tree
Subtree: A parent with children with-in another parent/child relationship
Leaf: A node with no children

5
...
16 State the result of
inorder, postorder and preorder
tree traversal
...
1
...


Start with the first value, then go to the left or right subtree depending on the subsequent values
...
1
...


Organised Notes
Dynamic data structures are data structures that can change size during the execution of a
program
...


5
...
19 Compare the use of static
and dynamic data structures
...
1
...


Static data structures

Dynamic data structures

Computer can allocate space during
compilation
Easy to program
Easy to check for overflow
An array allows random access

Only uses the space needed at any time
Makes efficient use of memory
Storage no longer required can be returned
to the system for other use

Programmer has to estimate maximum
amount of space needed
Can waste space

Difficult to program
Can be slow to implement searches
A linked list only allows serial search

Stacks:
The most important application of a stack is to implement function calls
...


Queues:
Computing applications: serving requests of a single shared
resource (printer, disk, CPU),
Buffers: MP3 players and portable CD players, iPod playlist
...

Handling interruptions, so the first interruption can be treated first
Linked list:
You need constant-time insertions/deletions from the list
...

You don't need random access to any elements
...

Arrays:
You need indexed/random access to elements
You know the number of elements in the array ahead of time
so that you can allocate the correct amount of memory for
the array
You need speed when iterating through all the elements in
sequence

---