Transcript ppt

Stuff
• Deadline for assn 3 extended to Monday, the 13th.
• Please note that the testing class for assn 3 has
changed (last Sunday). You will need to
download a new copy, if you have not done so
this week already.
• Solution to midterm posted shortly.
Winter 2006
CISC121 - Prof. McLeod
1
Dept. Math. & Stats. Colloquium
• Today!! Friday, March 10, 2:30 p.m., Jeffery Hall
234 (bad vibes?)
• Speaker: Olgica Milenkovic
University of Colorado
• Title: Two problems in analysis of algorithms
• (see next slide for abstract…)
Winter 2006
CISC121 - Prof. McLeod
2
• Abstract: We address the problem of analyzing the complexity of two
algorithms from the field of computer algebra and bioinformatics. The
first algorithm, known as Gosper's method for indefinite summation of
hypergeometric terms, is investigated in the asymptotic, average-case
complexity regime. We show that for several classes of input functions
represented in terms of urn models, the complexity of Gosper's
algorithm is related to the extremal behavior of a class of generalized
random-walks.
• The second algorithm we discuss is concerned with the problem of
sorting signed permutations by reversals. Algorithms for sorting by
reversals represent one of the most important tools in analyzing
rearrangements in the mouse vs. human genome. We point out some
shortcomings of the current approach to modeling reversals and
propose two new extensions for the notion of reversal distance. We
investigate the complexity of a Viterbi and M-type algorithm for
computing cost-constrained reversal distances. The first part of the
talk is a joint work with Kevin J. Compton from the University of
Michigan.
Winter 2006
CISC121 - Prof. McLeod
3
Last Time
• (Tutorial!)
• Before that:
– Doubly linked lists.
– Circular lists.
– Skip lists.
– Self – organizing lists.
Winter 2006
CISC121 - Prof. McLeod
4
Today
• Replacing sparse tables with linked lists.
• LinkList<E> in java.util
• Stacks (if we have time)
• Next time: Queues
Winter 2006
CISC121 - Prof. McLeod
5
Sparse Tables
• A sparse table is defined as a table where the
available cells are only partly populated.
• For example, consider a table where the columns
are student ID’s and the rows are courses taken,
for the entire University:
– A cell can contain a grade for a course taken by the
student.
– Of course, not all students take all courses, so only a
small portion of each column is taken up with data.
– Such a “sparse table” is probably not an efficient use
of memory.
Winter 2006
CISC121 - Prof. McLeod
6
Sparse Tables – Cont.
• Replace the table by a system of linked lists.
Here is one possible design:
– Have an ArrayList of course Objects. Each course
Object contains all the necessary info about each
course and a link to the first student enrolled in the
course.
– Have an ArrayList of student Objects. Each student
Object contains the necessary student information and
has a link to the first course taken by that student.
– However, make the node design in such a way that
the nodes are shared by both lists!
Winter 2006
CISC121 - Prof. McLeod
7
Sparse Tables – Cont.
– Each node contains:
• student number
• class number
Data
• grade code (0 is “A”, 9 is “F”)
• link to next student
Links
• link to next course
– One node for each course the student has taken. No
empty nodes.
• See the structure on the next slide:
Winter 2006
CISC121 - Prof. McLeod
8
1
Winter 2006
CISC121 - Prof. McLeod
9
Sparse Tables – Cont.
• (I don’t know why SN and course# have to be in each
node in the diagram…)
• How to navigate through this structure?
– Start with a student or start with a course.
– But from any given node you can flip the direction of
your navigation.
• At the moment, you have to follow links from oldest to
newest in one direction – this would be a painful way of
finding recent students in a course that has been around
for a while! How would you fix this?
Winter 2006
CISC121 - Prof. McLeod
10
Sparse Tables – Cont.
• More efficient use of memory because there are
no empty table elements.
• Uses 17% of the memory used by the sparse
table for a typical University setting.
• Can easily grow as required.
Winter 2006
CISC121 - Prof. McLeod
11
Linked Lists in java.util
• java.util contains a class called
“LinkedList<E>”.
• (E is the element type to be stored in the list.)
• As does the ArrayList class, LinkedList
contains many useful pre-defined methods.
• LinkedList implements a linked list as a
“generic doubly-linked list with references to the
head and tail”.
• Many of the LinkedList methods throw
Exceptions for illegal parameters.
• LinkedList only stores “Objects” of type E.
Winter 2006
CISC121 - Prof. McLeod
12
Linked Lists in java.util – Cont.
• Methods include (“ob” is an object of type E):
• void add(ob) // adds ob to end of list.
• void add(pos, ob) // adds ob at pos.
• void addFirst(ob) // adds ob at beginning
of list.
• void addLast(ob) // same as add(ob).
• void clear() // removes all objects from
the list.
• boolean contains(ob) // returns true if
the list contains ob.
Winter 2006
CISC121 - Prof. McLeod
13
Linked Lists in java.util – Cont.
• Object get(pos) // returns the
object at pos.
• Object getFirst() // returns first
object in list.
• Object getLast() // returns last
object in list.
• int indexOf(ob) // returns position
of first occurrence of ob, or –1 if
ob is not found.
• boolean isEmpty() // returns true
if list is empty, false otherwise.
Winter 2006
CISC121 - Prof. McLeod
14
Linked Lists in java.util – Cont.
• Iterator iterator() // generates and
returns an iterator for the list.
• LinkedList() // creates an empty
linked list.
• boolean remove(ob) // removes first
occurrence of ob and returns true.
• Object removeFirst() // removes and
returns first element in list.
Winter 2006
CISC121 - Prof. McLeod
15
Linked Lists in java.util – Cont.
• Object removeLast() // removes and
returns last element in list.
• int size() // returns number of
elements in list.
Winter 2006
CISC121 - Prof. McLeod
16
Stacks
• What is a stack?
• For example a “PEZ”
candy container:
Winter 2006
CISC121 - Prof. McLeod
17
Stacks – Cont.
• Another example are those plate dispensers in
cafeterias.
• A stack follows the “Last In, First Out” or “LIFO”
principle.
• A stack would have the following operations:
–
–
–
–
–
–
clear() – clear the stack.
isEmpty() – check to see if the stack is empty.
isFull() – check to see if the stack is full.
push(element) - put the element on top of the stack.
pop() – take the topmost element from the stack.
peek() – return the topmost element in the stack
without removing it.
Winter 2006
CISC121 - Prof. McLeod
18
Stacks – Cont.
• Any other methods would not be “legal” – you
would no longer be modeling a stack.
• This is a restrictive data structure! Why bother?
Winter 2006
CISC121 - Prof. McLeod
19
Stacks – Cont.
• A stack is modeled with another data structure
“under the hood”.
• If you used a linked list:
– What kind of a linked list would you use?
– What linked list methods would be used to
carry out the following stack methods:?
•
•
•
•
Winter 2006
push
pop
clear
peek
CISC121 - Prof. McLeod
20
Stacks – Cont.
• See IntStack.java for a linked list implementation.
• Some features of IntStack:
– An inner, inner class for the node.
– An inner class for the linked list.
– Only public methods are:
• clear ()
• boolean isEmpty ()
• push (int)
• int pop ()
• int peek ()
Winter 2006
CISC121 - Prof. McLeod
21
Stacks – Cont.
• A stack can also be implemented with an ArrayList
or even an array (But not as well, IMHO).
• Note that none of the stack operations require
iteration through the linked list.
Winter 2006
CISC121 - Prof. McLeod
22
ArrayList Stack Implementation
• See ALStack.java
• (Note that we are assuming the user will check to
see if the stack is empty before calling a “pop()”
operation. What else could we do?)
• “Features”:
– We need to keep track of position in the ArrayList.
– We could use (but did not) the automatic “un-boxing”
and boxing feature in Java 5.0 (huh?).
Winter 2006
CISC121 - Prof. McLeod
23
Array Stack Implementation
• See ArrayStack.java
• A bit clumsy?
• Of the three implementations, which is the best?
Winter 2006
CISC121 - Prof. McLeod
24
A Stack in Use
• How to add numbers that are too large to be
stored in a long type variable?
• See LongAddition.java
Winter 2006
CISC121 - Prof. McLeod
25
The Stack<E> Class in java.util
• java.util has a “Stack” class that implements the
above methods using a Vector as the storage
object.
• (A Vector is like an ArrayList…)
• Stack is a sub-class of Vector, and as such,
inherits all the Vector methods.
Winter 2006
CISC121 - Prof. McLeod
26
The Stack<E> Class – Cont.
• Unique Stack methods:
boolean empty() // same as isEmpty
Object peek()
Object pop()
Object push(element)
int search(target) // returns position of
target in stack, if not found –1 is
returned.
Stack() // constructor
Winter 2006
CISC121 - Prof. McLeod
27
The Stack<E> Class – Cont.
• In Stack, “push” also returns a reference to the
Object added to the stack, so both peek and
push can change that topmost object on the
stack.
• Since Stack “is a” Vector, methods like
“setElementAt” and “removeElementAt” can
be used on stack elements – but these methods
would be illegal by our definition of what a stack
is!
• Also, when Vector’s are used to implement the
stack, re-sizing of the Vector can greatly slow
down the push method.
Winter 2006
CISC121 - Prof. McLeod
28
The Stack<E> Class – Cont.
• For these reasons it is better to implement a stack
as we have done above, using a private linked list
(best) or a private array(next best) as a data
object within the definition of the class.
• Implementing a stack using a linked list defined
using an inner class for the list and an “inner,
inner” class for the node provides better
information hiding than the Stack class.
Winter 2006
CISC121 - Prof. McLeod
29