Transcript dataStructx

Data Structures
and Algorithms
revision
Merge
sort
Analysis of Merge-Sort
• The “height” h of the merge-sort tree is O(log n)
– This is a consequence of the dividing the problem in 2 at each step,
• The overall amount of work done at each merge i is O(n)
• Thus, the total running time of merge-sort is O(n log n)
size
n
n
n
…
Divide and Conquer Sorting
3
Worst-case Running Time
• The worst case for quick-sort occurs when the pivot is the unique
minimum or maximum element
• One of L and G has size n - 1 and the other has size 0
• The running time is proportional to the sum
n + (n - 1) + … + 2 + 1
• Thus, the worst-case running time of quick-sort is O(n2)
depth time
0
n
1
n-1
…
…
n-1
1
Divide and Conquer Sorting
4
Insertion Sort
• GREEN– sorted, RED unsorted.
• while some elements unsorted:
– Using linear search, find the location in the sorted portion
where the 1st element of the unsorted portion should be
inserted
– Move all the elements after the insertion location up one
position to make space for the new element
45
38 60 66 45 79 47 13 74 36 21 94 22 57 16 29 81
the fourth iteration of this loop is shown here
38 45
60 60
66 45
66 79 47 13 74 36 21 94 22 57 16 29 81
Insert sort in action
Start of algorithm. Sorted portion of list will be marked in colour.
0
1
2
15
3
91 68 2 25 31 32 16 4 21 15 62
3
4
5
6
7
8
9
Assign i the value 1.
Set pivot to be equal to numbers[i] (next…)
10
11
12
Insert sort in action
pivot 3
0
1
15
2
3
4
5
6
7
8
9
10
11
12
91 68 2 25 31 32 16 4 21 15 62
i
Is the value before the gap greater than pivot? Yes!
Move this value into the gap (next…)
Insert sort in action
pivot 3
0
1
2
3
4
5
6
7
8
9
10
11
12
15 91 68 2 25 31 32 16 4 21 15 62
i
Is the value before the gap greater than pivot? No.
Move pivot into the gap.
Add 1 to i, then select the ith value as pivot (next…)
Insert sort in action
pivot 91
0
3
1
2
15
3
4
5
6
7
8
9
10
11
12
68 2 25 31 32 16 4 21 15 62
i
Is the value before the gap greater than pivot? No.
Move pivot into the gap.
Add 1 to i, then select the ith value as pivot (next…)
Insert sort in action
pivot 68
0
3
1
2
3
15 91
4
5
6
7
8
9
10
11
12
2 25 31 32 16 4 21 15 62
i
Is the value before the gap greater than pivot? Yes!
Move this value into the gap (next…)
Insert sort in action
pivot 68
0
3
1
15
2
3
4
5
6
7
8
9
10
11
12
91 2 25 31 32 16 4 21 15 62
i
Is the value before the gap greater than pivot? No.
Move pivot into the gap.
Add 1 to i, then select the ith value as pivot (next…)
Insert sort in action
pivot 2
0
3
1
2
3
4
15 68 91
5
6
7
8
9
10
11
12
25 31 32 16 4 21 15 62
i
Is the value before the gap greater than pivot? Yes!
Move this value into the gap (next…)
Insert sort in action
pivot 2
0
3
1
2
15 68
3
4
5
6
7
8
9
10
11
12
91 25 31 32 16 4 21 15 62
i
Is the value before the gap greater than pivot? Yes!
Move this value into the gap (next…)
Insert sort in action
pivot 2
0
3
1
15
2
3
4
5
6
7
8
9
10
11
12
68 91 25 31 32 16 4 21 15 62
i
Is the value before the gap greater than pivot? Yes!
Move this value into the gap (next…)
Insert sort in action
pivot 2
0
3
1
2
3
4
5
6
7
8
9
10
11
12
15 68 91 25 31 32 16 4 21 15 62
i
Is the value before the gap greater than pivot? Yes!
Move this value into the gap (next…)
Insert sort in action
pivot 2
0
1
2
3
15 68 91 25 31 32 16 4 21 15 62
3
4
5
6
7
8
9
10
11
i
Is the value before the gap greater than pivot? No.
Move pivot into the gap.
Add 1 to i, then select the ith value as pivot (next…)
12
Insert sort in action
pivot 25
0
1
2
2
3
15 68 91
3
4
5
6
7
8
9
10
11
12
31 32 16 4 21 15 62
i
And so on…until the list is finally in order:
pivot
0
1
2
2
3
4
3
4
5
6
7
8
9
10
11
12
15 15 16 21 25 31 32 62 68 91
i
An insertion sort partitions the array into two regions; variable i referred to as pivot.
Selection Sort
5
1
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
5
1
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
5
1
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
5
1
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
5
1
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
5
1
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
5
1
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
5
1

Smallest
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
1
5
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
1
5
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
1
5
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
1
5
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
1
5
Comparison
Data Movement
Sorted
3
4
6
2
Selection Sort
1
5
3
4
6
2

Smallest
Comparison
Data Movement
Sorted
Selection Sort
1
5
3
4
6
2

Smallest
Comparison
Data Movement
Sorted
Selection Sort
1
2
Comparison
Data Movement
Sorted
3
4
6
5
Selection Sort
1
2
Comparison
Data Movement
Sorted
3
4
6
5
Selection Sort Algorithm
SelectionSort(A)
Input: An array ‘A’ of n comparable items
Output: The array ‘A’ with elements in non-decreasing order
1. for i0 to n-2 do // note n-2 not n-1
2.
//Insert smallest item in 0th slot, 2nd smallest in 1st, etc.
3.
4.
5.
6.
min  i
for j  i+1 to j <= n-1 do
if (A[j] < A[min])
min  j
7.
swap A[i] and A[min]. // What is really happening here?
What is the complexity of Selection Sort, and does it vary with input?
Complexity
1. Time complexity is the amount of time (or
computational steps) to achieve a task.
2. Space complexity is the amount of memory
needed to complete that task.
3. Time complexity>Space complexity. WHY???
4. Time complexity is considered more important.
5. We do not use wall clock time – as this depends
on the hardware.
6. We use an abstract measure O(n), O(n log n)
How long does this take to open 1)
know 2) don’t know.
What is the smallest operation we can count
Analysis of Algorithms
39
n = number of
elements
Counting Operations
public static double avg(int[] a, int n){
double sum=0;
for(int j=0; j<n; j++)
sum+=a[j];
return (sum/n);
}
Loop
runsisnone
times
1 loop
There
operation
comparison
1 loop
in the for-loop
increment
1 operation
3n operations
Total Operations:
3n + 3
Analysis of Algorithms
40
1 Loop assignments.
3 operations for each of
the n-1 iterations.
2
O(n )
Method
Total = n(n-1)/2
iterations
public static void bubble(int[] a, int n){
for (i=0; i<n-1; i++) {//how many are sorted
for (j=0; j<n-1-i; j++)//unsorted part
if (a[j+1] < a[j]) //compare neighbors
Inner loop has
2 loop ops
6[n(n-1)/2]
swap(a, j, j+1);
n-1 iterations
1 comparison
=3n(n-1)
}
n-2 2iterations
=3n
+ 3 ops
-3n for swap
}
n-3 iterations
6 operationsfrom inner loop
Operations
…..
On Each iteration
1 iteration
Operation Count = 3n
1 +2–3(n-1)
–22+ 3n2 – 3n
Analysis of Algorithms
41
Functions
• If the following are runtimes expressed
as functions of the number of inputs
(x), we would label them as follows:
1.
2.
3.
4.
5.
6.
f(x)
f(x)
f(x)
f(x)
f(x)
f(x)
=
=
=
=
=
=
O(1)
7
log(x + 3)O(log n)
O(n)
3x + 5
2)
2
O(n
4x + 15x + 90
O(n3)
3
10x – 30
O(2n)
(3x
+
3)
2
Analysis of Algorithms
42
Singly Linked List
• A singly linked list is a
concrete data structure
consisting of a sequence of
nodes
• Each node stores:
next
– an element
– a link to the next node
node
elem

A
B
C
Linked Lists
D
43
The Node Class for List Nodes
public class StringNode
{
// Attributes
private String element;// The data to be stored in this node
private StringNode next;
// A link to the next node in the chain
/**
Constructor
Creates a node with the given element and next node. */
public StringNode(String e, StringNode n)
{
element = e;
next = n;
}
/**
Constructor
Creates a node with null references to its element and next node. */
public StringNode()
{
this(null, null);
}
Linked Lists
44
The Node Class for List Nodes
// Accessor methods
public String getElement()
{
return element;
}
public StringNode getNext()
{
return next;
}
// Modifier methods:
public void setElement(String newElem)
{
element = newElem;
}
public void setNext(StringNode newNext)
{
next = newNext;
}
}
Linked Lists
45
For any data structure/storage:
Operations
• How to add
Location of Operation
• Beginning
• How to retreive
• End
• How to remove/delete.
• Middle
Linked Lists
46
Inserting at the Head of a List
1.
The current list...
head

A
2.
3.
Create a new node
with content X
node
B
C

X
Insert the node
node
A.
X
Have new node point to old head
head
B.

Update head to point to new
node
A
B
C
node
head

X
Linked Lists
A
B
C
47
Linked List - addFirst
public class StringLinkedList {
StringNode head = null;
// The start of the list
StringNode tail = null;
// The last element in the list
public void addFirst(StringNode n)
{
// Check we have a node to add...
if (n == null) return;
// Set our new node to point to the head
// of the current list.
n.setNext(head);
// Our new node 'n' will now become the head of the list
head = n;
// If the list was empty, make the tail point to
// the new node as well
if (tail == null) tail = n;
}
Linked Lists
48
Removing from the Head
head

A
1.
2.
Update head to point to next
node in the list
Allow garbage collector to
reclaim the former first node
B
C
D
head

A
B
C
D
head

B
Linked Lists
C
D
49
Linked List - removeFirst
public void removeFirst()
{
// If list is empty, we can't remove anything so leave
if (head == null) return;
// Move head to the next item in the list
head = head.getNext();
// If the list is empty, set the tail reference to null
if (head == null) tail = null;
// The original item that was at the head of the list
// no longer has anything referencing it and will be
// garbage collected in Java. In other programming languages
// e.g. C++, you would have to delete it other wise you
// would get a memory leak.
}
Linked Lists
50
Inserting at the Tail
tail
1.
The current list...
head

A
2.
3.
Create a new node pointing to
null
node
B

X
node
Insert new element
A.
B.
C

tail
Have old last node point to new
node
X
head
A
B
C
node
Update tail to point to new
node
tail
head

A
Linked Lists
B
C
X
51
Linked List - addLast
public void addLast(StringNode node)
{
// If we were not given a node, leave
if (node == null) return;
// If list is empty, our new node will
// be the head and tail of list
if (head == null)
{
head = node;
tail = node;
return;
}
// Make the current last node point to our new node
tail.setNext(node);
}
// Now update the tail to be our new node
tail = node;
Linked Lists
52
Removing at the Tail
• Removing at the tail of a singly
linked list is not efficient!
• There is no constant-time way
to update the tail to point to
the previous node
tail
head
Linked Lists

A
B
C
D
53
Linked List - removeLast
public void removeLast() {
if (head == null) return; // If list is empty, leave
// If head is also the tail, the list
// will be empty
if (head == tail) {
head = null;
tail = null;
return;
}
// Start at the head of the list
StringNode n = head;
// Now look for the last item
while (n.getNext() != tail)
n = n.getNext();
// n should now be pointing to the last but one
// node in the list. This will be the new tail
// We are going to drop the last element in the list
// so make the current node's next pointer null
n.setNext(null);
}
// The old tail node is now replaced with 'n'. The
// old tail node has no reference and will be garbage
tail = n;
Linked Lists
54
HASH TABLES.
1. HASH TABLES. Try to take advantage of the fast
speed we can access arrays (a build in data
structure.)
2. We could use an id (e.g. passport number or
student number, mobile number), but the
array would be huge.
3. We “squash” or “compress” the possible
indexes into a smaller range with hashing
function.
4. However collisions can occur between entries.
Array as table
studid
0012345
0033333
0056789
...
9801010
9802020
...
9903030
9908080
name
score
andy
betty
david
81.5
90
56.8
peter
mary
20
100
tom
bill
73
49
Consider this problem. We want to store 1,000
student records and search them by student id.
56
Array as table
0
:
12345
:
33333
:
56789
:
:
9908080
:
9999999
name
score
:
andy
:
betty
:
david
:
:
bill
:
:
81.5
:
90
:
56.8
:
:
49
:
One way is to store the records in
a huge array (index 0..9999999).
The index is used as the student id,
i.e. the record of the student with
studid 0012345 is stored at
A[12345] -- Is this a good idea?
Most of the table would be empty
57
Array as table
•
It is also called Direct-address Hash Table.
• Each slot, or position, corresponds to a key in U.
• If there’s an element x with key k, then T [k] contains a pointer to x.
• Otherwise, T [k] is empty, represented by NIL.
58
Array as table
• Store the records in a huge array where the
index corresponds to the key
– add - very fast O(1)
– delete - very fast O(1)
– search - very fast O(1)
• But it wastes a lot of memory! Not feasible.
59
Hash function
function Hash(key: KeyType): integer;
Imagine that we have such a magic
function Hash. It maps the key
(studid) of the 1000 records into the
integers 0..999, one to one. No two
different keys maps to the same
number.
H(‘0012345’) = 134
H(‘0033333’) = 67
H(‘0056789’) = 764
…
H(‘9908080’) = 3
60
Hash Table
0
To store a record, we
compute Hash(stud_id)
for the record and store
it at the location
Hash(stud_id) of the
array. To search for a
student, we only need
to peek at the location
Hash(target stud_id).
:
3
9908080
:
67 0033333
:
134 0012345
:
764 0056789
:
999
:
name
:
bill
:
betty
:
andy
:
david
:
:
score
:
49
:
90
:
81.5
:
56.8
:
:
61
Chained Hash Table
0
1
2
3
4
5
nil
nil
One way to handle collision is to store the
collided records in a linked list. The array
now stores pointers to such lists. If no key
maps to a certain hash value, that array
entry points to nil.
nil
:
HASHMAX nil
Key: 9903030
name: tom
score: 73
62
Collections Framework Diagram
• Each collection class implements an interface from a
hierarchy
– Each class is designed for a
specific type of storage
Copyright © 2013 by John Wiley &
Sons. All rights reserved.
Page 63
Depth first
search
Breath
first
search
Greedy
MST
PRIM
kRUKLALK
DISTTAR.
Depth First Search (DFS)
• Depth First Search (DFS) algorithm traverses a
graph in a depthward motion and uses a stack
to remember to get the next vertex to start a
search, when a dead end occurs in any
iteration.
Depth First Search (DFS)
Depth First Search (DFS)
• Rule 1 − Visit the adjacent unvisited vertex.
Mark it as visited. Display it. Push it in a stack.
• Rule 2 − If no adjacent vertex is found, pop up
a vertex from the stack. (It will pop up all the
vertices from the stack, which do not have
adjacent vertices.)
• Rule 3 − Repeat Rule 1 and Rule 2 until the
stack is empty.
dfs1
• Initialize the stack.
dfs2
• Mark S as visited and put it onto the stack.
Explore any unvisited adjacent node from S.
We have three nodes and we can pick any of
them. For this example, we shall take the node
in an alphabetical order.
dfs3
• Mark A as visited and put it onto the stack.
Explore any unvisited adjacent node from A.
Both Sand D are adjacent to A but we are
concerned for unvisited nodes only.
dfs4
• Visit D and mark it as visited and put onto the
stack. Here, we have B and C nodes, which are
adjacent to D and both are unvisited.
However, we shall again choose in an
alphabetical order.
dfs5
• We choose B, mark it as visited and put onto
the stack. Here Bdoes not have any unvisited
adjacent node. So, we pop Bfrom the stack.
dfs6
• We choose B, mark it as visited and put onto
the stack. Here Bdoes not have any unvisited
adjacent node. So, we pop Bfrom the stack.
dfs7
• Only unvisited adjacent node is
from D is C now. So we visit C, mark it as
visited and put it onto the stack.
Breadth First Search (BFS)
• Breadth First Search (BFS) algorithm traverses
a graph in a breadthward motion and uses a
queue to remember to get the next vertex to
start a search, when a dead end occurs in any
iteration.
• Visit all nodes depth 1 first, then depth 2, …
Breadth First Traversal
• Rule 1 − Visit the adjacent unvisited vertex.
Mark it as visited. Display it. Insert it in a
queue.
• Rule 2 − If no adjacent vertex is found, remove
the first vertex from the queue.
• Rule 3 − Repeat Rule 1 and Rule 2 until the
queue is empty.
Bfs 1
• Initialize the queue.
Bfs 2
• We start from
visiting S(starting
node), and mark it as
visited.
Bfs 3
• We then see an
unvisited adjacent
node from S. In this
example, we have
three nodes but
alphabetically we
choose A, mark it as
visited and enqueue
it.
Bfs 4
• Next, the unvisited
adjacent node
from S is B. We mark
it as visited and
enqueue it.
Bfs 5
• Next, the unvisited
adjacent node
from S is C. We mark
it as visited and
enqueue it.
Bfs 6
• Now, S is left with no
unvisited adjacent
nodes. So, we
dequeue and find A.
Bfs 7
• From A we have D as
unvisited adjacent
node. We mark it as
visited and enqueue
it.
binary tree is traversed in-order,
• We start from A, and
following in-order
traversal, we move to
its left subtree B. B is
also traversed inorder. The process
goes on until all the
nodes are visited.
binary tree is traversed in-order,
• D→B→E→A→F→C→G
Algorithm inorder
•
•
•
•
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.
Pre order
• We start from A, and
following pre-order
traversal, we first
visit A itself and then
move to its left
subtree B. B is also
traversed pre-order.
The process goes on
until all the nodes
are visited.
Pre order
• A→B→D→E→C→F→G
Algorithm preorder
•
•
•
•
Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
traversed post-order
• We start from A, and
following pre-order
traversal, we first visit
the left subtree B. B is
also traversed postorder. The process
goes on until all the
nodes are visited. The
output of post-order
traversal of this tree
will be −
traversed post-order
• D→E→B→F→G→C→A
Algorithm post order
• Until all nodes are traversed −
• Step 1 − Recursively traverse left subtree.
• Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.
Binary Search Tree
• BST is a collection of nodes arranged in a way
where they maintain BST properties. Each
node has a key and an associated value. While
searching, the desired key is compared to the
keys in BST and if found, the associated value
is retrieved.
Is this a BST
Basic Operations
1. Search − Searches an element in a tree.
2. Insert − Inserts an element in a tree.
3. Pre-order Traversal − Traverses a tree in a
pre-order manner.
4. In-order Traversal − Traverses a tree in an inorder manner.
5. Post-order Traversal − Traverses a tree in a
post-order manner.