Transcript ppt - Canisius College Computer Science

CSC 212 –
Data Structures
Lecture 37:
Course Review
Final Exam
Friday, Dec. 15 from 3:15 – 5:15 in OM 205
 Plan for exam to take full 2 hours

 Talk

to me if this is a major problem
Exam covers material from entire semester
 Format
like 2 midterms
 Still open-book, open-note, closed-computer
Objectives Met in CSC212

Design computational solutions

Decompose a problem into logically grouped subprograms
 Develop and analyze algorithms

Program well


Code in a high-level language
Debug a program
 Write and use a test plan
 Document a program
 Work independently

Organize data for effective use



Use fundamental data structures
Implement data structures
Understand the role of computing and the computer professional


Present or explain ideas
Weigh different solutions and explain or argue why one was preferable
What Gets Inherited and How

All fields & methods (members) inherited
 Public
members accessed as if declared in subclass
(but they should not be!)
 Private members cannot be accessed
 Protected members used as if subclass declared
them as private (but, do not do this!)

Subclasses can override/overload method
 Call

method defined for instance’s type
Subclasses can hide field
 Use
the field defined for variable’s type
Exceptions in Java

Throw exception when problem detected
 Must

Handle by catching exception
 Only

instantiate instance before throwing
catch exceptions you want to handle
Method lists exceptions thrown via throws
 Include
any exception not caught
 Does not matter if method was originator
Abstract Methods

Abstract methods cannot have a body
 IOU

that subclasses will define the method
Class with abstract methods is abstract
 Cannot
be instantiated, but can be extended
 Can have fields & methods

Interface declares abstract methods
 All
methods are public abstract methods
Arrays vs. Linked Lists

Two alternate ways to hold data
 Not ADTs,
but specific implementations
Arrays generally offer quick access times,
but hard to maintain and resize
 Linked lists offer flexible sizing, but access
times can be slow

 Can
be singly, doubly, or circularly linked
Queues, Stacks, & Deques

Offer simple means of tracking elements
a line, Queues are first-in, first-out
 Stacks are last-in, first-out
 Deques can be accessed from either end
 Like

Cannot access interior elements
 No

way of searching for an element either
Implemented with either array or linked list
 Arrays
can violate unlimited space guarantee
Iterators & Iterables

Important interfaces defined by Java:
import java.util.Iterator;
import java.lang.Iterable;
public interface Iterator<E> {
E next();
boolean hasNext() throws
NoSuchElementException;
void remove() throws
UnsupportedOperationException;
}
public interface Iterable<E> {
More Iterator & Iterable

Use Iterator to abstract processing
Iterator<Integer> it;
...
for (it = myList.iterator();
it.hasNext(); ) {
Integer i = it.next();
...
}

Process Iterable objects in an even easier way
...
for (Integer i : myList) {
...
}
Lists

List is Iterable collection of elements
 Can
now access any element in collection
 Different lists provide other accessor methods

IndexList access using 0-based ranks
 Not

the same as array -- ranks can change
PositionList access via relative position
 Relies

on Position ADT to hold elements
Sequence combines two lists & Deque
How Computer Normally Works
That’ll
be $2 billion
No problem.
I’ll have a Manhattan
Working With Map & Dictionary
That’ll
be $2 billion
No problem.
I’ll have a Manhattan
key
value
Maps & Dictionaries
Rely on Entry ADT -- key & value pair
 Maps have at most 1 Entry with any key

 New
Entry replaces previous Entry with
key
 Remove Entry by specifying its key

Entrys in Dictionary can share key
 New
Entry does not affect others with that
key
 Remove Entry by specifying key AND value
Map & Dictionary Implementation

Many possible implementations possible
 Sequence
with elements kept in sorted order
 Sequence with elements kept in unsorted
order
 Hash Table (which is not an ADT)

Hash table stores all of the Entrys
 Hash
function uses key to compute integer
from 0 to size of table - 1
 Goal is storing entry (k, v) at index h(k)
Collisions

When implemented with hash table & two
Keys share hash code

Three commonly used handling schemes
chaining: table contains Lists of
entries hashed to that index
 Linear probing: loop through array looking for
first open array location
 Double hashing: plug key into another hash
function to find empty array location
 Separate
Sets & Partitions

Sets implement at least three operations
 intersect,
union, & subtract
 Constructor others depend on how Set used
Set’s operations rely on instances of
subclasses of Merge
 Partition is first use of Set

hold collection of disjoint Sets
 Set’s constructor must take single element
 Instances
Quick-Select & Pattern
Matching

Quick-Select finds nth element in
Sequence
 Uses
divide-and-conquer for speed
 Honestly, not a lot to ask about it

Know the pattern matching algorithms
 When
& why we may want to use one over
the others
 Also know how to perform their actions -mostly “trained monkey” work
Hints for Studying

The exam will NOT require:
 Memorizing ADT’s
methods
 Memorizing Node implementations
 Memorizing big-Oh time proofs
 (Recursion)

The exam WILL require:
 Knowing
what the methods do
 Be able to implement the methods
 Computing big-Oh time complexity
Studying For the Exam
1.
What does the ADT do?

2.
How is the ADT used?


3.
What applications use this ADT?
How do they use it and why?
Can you explain examples’ answers?

4.
What are real-world analogues for it?
Keep reviewing material until you can do this cold
How do we implement the ADT?


Why is it implemented in that way?
What are the performance tradeoffs?
Before Next Lecture…

CSC212 Final Exam:
Fri., Dec. 15 from 3:15–5:15 in OM 205
Bring 1 (or more) pencils to the exam
 Do well on all your finals
 Have a good Christmas break
 Get ready for new term of challenges & fun
