Transcript Document

Data Structures and
Algorithms
Lists, Stacks, Queues, and Graphs
Sorting and searching algorithms
Lists
 A list is a sequence of zero or more data
items.
 The total number of items is said to be
the length of the list.
 The length of a given list can grow and
shrink on demand.
 The items can be accessed, inserted, or
deleted at any position in a list.
Two ways to implement lists
 Array
implementation
array
End of list
 Linked list
implementation
null
Stacks
 A stack is a special kind of list in which
all insertions and deletions take place at
one end, called the top. Therefore, it
has another name ``pushdown list''.
 Its items are added and deleted on a
last-in-first-out (LIFO) basis.
 In Java, “Stack s = new Stack()”
creates a stack object.
Java Examples – using stacks
Q. What is printed out by the following fragment of
Java?
Stack s = new Stack();
for(int i=0; i<10; i++)
s.push(i);
while(!s.empty())
System.out.printnl(s.pop);
Java examples – using stacks
Q. What is printed out by the following fragment of
Java?
Stack s = new Stack();
for(int i=0; i<5; i++)
s.push(i);
while(!s.size() > 1)
s.push(s.pop() + s.pop());
System.out.printnl(s.pop);
Queues
 A queue is another special kind of list,
where items are inserted at one end (the
rear) and deleted at the other end (the
front).
 A queue is also called a FIFO, since the
items are deleted in the same order as
they were added - on a first-in-first-out
basis.
 For a queue structure, we have two
special names for insertion and deletion:
ENQUEUE and DEQUEUE.
How to implement queues?
Tricky!
 How to make both
0
1
2
3
4
5
6
7
tail
head
Wrap around
3
4
2
5
1
6
0
7
enqueue & dequeue
operations efficient ?
(avoid shifting items)
 enqueue
tail=
(tail+1) mod size
 dequeue
head=
(head+1) mod size
An example of using queue
 One printer is connected to several
computers
 Printing a file takes much longer time
than transmitting the data; a queue of
printing jobs is needed
 When new job P arrives, do enqueue(P)
 When a job is finished, do dequeue(P)
Printing task queue
job1 job2 job3 job4 job5 job6
^
|
|
|
jobs removed here (dequeue)
^
|
|_________
|
new jobs
added here
(enqueue)
Algorithms
 An algorithm is a step-by-step method
of solving computational tasks.
 Algorithm = a precise sequence of
actions for performing a computational
task (independent from computer
languages, i.e. pseudo code).
Computational Task ?
 A computational task is not just a “single”
task such as
 “Is
3962431 prime ?”
 “What is 37487*2371 ?”
 A computational task is a whole family of
“similar” tasks with varying INPUT, such as
 “Given
a whole number A, is A prime?”
 “Given 2 numbers x and y, what is x times y?”
Sorting - one of the most frequently
used computational task
 Nature tends towards disorder
 Human prefer order
e.g.
address books
shopping lists
databases
Insertion sort
 Commonly used for hand-sorting
 Use two lists – unsorted and sorted
unsorted = input list (assume that size = n)
sorted = an empty list
loop from i =0 to n-1 do {
// n loops
insert unsorted[i] to the sorted list
// needs about n steps comparing or shifting
}
Can you write an ordered insertion algorithm?
Another sorting algorithm – quick sort
(An example of using stack)
 Goal: sort numbers from position 1 to 10 into
order (to simplify assume size=10)
 Sub-goal: sort numbers from position a to b into
order. Easy case a = b.
 How to split goal into sub-goals?
Use a partitioning method
4
8
2
5
10
9
1
3
7
6
partitioning
 Randomly pick a pivot.
 The rest of the numbers are shifted to either the left or
right side of the pivot depending on whether it is greater
or less than the pivot.
 Pivot is already in the sorted position.
4
8
2
10
9
1
3
7
6
8
5
10
9
7
6
Pivot’s
moved
to here
picked
pivot
2
5
1
3
4
Using a Stack
push (1,10) onto stack
while stack not empty do {
pop (a,b) from stack
partitioning (a,b) into (a,m-1) and
(m+1,b)
if(a < m-1) push (a,m) onto stack
if(m+1 < b) push(m+1,b) onto stack
}
Step by step
4
2
2
2
2
2
1
1
8
1
1
1
1
1
2
2
2
3
3
3
3
3
3
3
5
4
4
4
4
4
4
4
10 9 1 3 7 6
8 5 10 9 7 6
5 7 6 8 10 9
5 7 6 8 9 10
5 7 6 8 9 10
5 6 7 8 9 10
5 6 7 8 9 10
5 6 7 8 9 10
Memo for In-class test 9 [
questions
1
2
3
4
5
my
answers
correct
answers
/5]
comments
Back to data structures – something not a sequence …
Graphs – examples of graphs
 Road maps (directed, cyclic, weighted)
 Project network (directed, cyclic, weighted)
 Electrical circuits
 Molecules
 Relationships (directed, un-weighted?)
- family tree
- students on courses
An abstract view of graphs
A graph is a collection of nodes (vertices) which
maybe connected in pairs by line segments called
edges.
Trees – a special graph without cycles
 Hieratical graph
 Root – the only node at
the topmost
 All rest of nodes must
be linked to a parent
note, and may have
zero or more child
nodes
 Leaf - Node without
children
root
Child 1
Child 2
leaf
leaf
Child 3
leaf
A Searching Problem ……
‘My house is No. 42 and is 100 yards from
the roundabout’, said your friend.
Unfortunately you realise, as you reach the
roundabout, that he hasn’t told you which
exit to take.
What should you do?
Even worse case, ‘100 yards from the 3rd
roundabout’, said your friend
Searching Algorithms - 1
Depth first with backtracking
 Go far as you can in one direction, stop
if the problems solved.
 If reach ‘dead-end’, go back up to the
last point where a decision was made,
and make a different (untried) direction.
 If there are no new decision, back up a
further choice point.
Searching Algorithms - 2
Breadth first
 Explore all possible directions in one
step, and remember those intermediate
stages
 Carry on exploring all intermediate
stages, step by step, until a solution
found.
An Example of Breadth First Search
 Finding a shortest path in a graph (say, from A to D)
4
B
C
3
2
3
2
A
D
E
2
3
F
1
H
1
1
G
Breadth first and Depth first
Breadth first
 Uses a queue
 Visit all nearest nodes first
Depth first
 Uses a stack
 Go as far as possible
Think about this
You have to build a tower from a
collection of small boxes of different
sizes. The height of the tower must be
1m.
How do you solve this problem?
Memo for In-class test 10 [
questions
1
2
3
4
5
my
answers
correct
answers
comments
/5]