Transcript CISC220-final

CISC220
Fall 2009
James Atlas
Dec 07: Final Exam Review
Announcements
• Final Exam (comprehensive)
• Friday Dec 11 7:00PM-9:00PM WHL007
• Course Evaluations
• http://www.udel.edu/course-evals
Topics
• Pointers/Memory
Management
• Arrays
• Linked Lists
• Analysis/
Big O notation
• Stacks
• Queues
•
•
•
•
•
•
Trees
Sorting
Heaps
Graphs
Hashing
NP-completeness
NP-Completeness
A class of problems having two properties:
• Any given solution to the problem can be
verified quickly (in polynomial time)
– the set of problems with this property is called
NP (nondeterministic polynomial time).
• If the problem can be solved quickly (in
polynomial time), then so can every
problem in NP.
Pointers
• An address refers to a particular memory location.
In other words, it points to a memory location.
• Pointer: A variable that contains the address of a
variable.
Location (address)
...
name
101 102 103 104 105 ...
23
42
104
x
y
z
...
Pointers
• How to initialize a pointer:
–
can initialize to NULL (i.e. not currently pointing to anything)
– & operator: get address of a variable
int *x;
x
?
y
?
int y = 3; x
?
y
3
y
3
x = &y;
x
Pointers
• How to get the value that is pointed to?
– * “dereference operator”: get value pointed to
x returns 3
• How to change the variable pointed to?
• *
– Use dereference * operator to left of =
x
y
3
*x = 5;
x
y
5
Memory Allocation
• Two ways:
– On the stack
– On the heap
Memory Allocation (Stack)
int main(void) {
int x(5);
if (x > 3) {
int y(6);
cout << (x + y) << endl;
}
}
Memory Allocation (Heap)
int main(void) {
int *x = new int(5);
if (*x > 3) {
int *y = new int(6);
cout << (*x + *y) << endl;
}
}
Memory De-allocation (Heap)
int main(void) {
int *x = new int(5);
if (*x > 3) {
int *y = new int(6);
cout << (*x + *y) << endl;
delete y;
}
delete x;
}
Array Allocation (Heap)
int main(void) {
int *x = new int[5];
*x = 5;
if (*x > 3) {
int *y = new int(6);
cout << (*x + *y) << endl;
delete y;
}
delete [] x;
}
Arrays
void ArrayTest() {
int scores[100];
// operate on the elements of the
// scores array...
scores[0] = 1;
scores[1] = 2;
scores[2] = 3;
}
Abstract Data Types (ADTs)
• Combination of data and operations
• Encapsulates implementation details
• Provides an interface for usage
Collection
•
•
•
•
•
add(x)
remove(index)
member(x)
size()
first()
Single Linked List
Creating a Link
Efficiency of Algorithms
• An operation for an Absract Data Type can be
thought of as a “problem”
• An algorithm solves the “problem”
– A series of steps
– Each step has a cost
• Time
• Space
– Efficiency is a measurement of this cost
Example 2.14/2.16
Big-O notation
• Describes the relationship between input
size and execution time
• If we double the number of inputs, n, and
the execution time is approximately doubled
– Linear growth rate
– Growth rate has an order of n
– O(n)
Let’s count individual instructions
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Simple Statement
}
}
for (int k = 0; k < n; k++) {
Simple Statement 1
Simple Statement 2
Simple Statement 3
Simple Statement 4
Simple Statement 5
}
Simple Statement 1
Simple Statement 2
...
Simple Statement 25
Let’s count individual instructions
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Simple Statement
}
}
n2 executions
Let’s count individual instructions
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Simple Statement
}
}
for (int k = 0; k < n; k++) {
Simple Statement 1
Simple Statement 2
Simple Statement 3
Simple Statement 4
Simple Statement 5
}
n executions,
5 statements per
= 5n
Let’s count individual instructions
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Simple Statement
}
}
for (int k = 0; k < n; k++) {
Simple Statement 1
Simple Statement 2
Simple Statement 3
Simple Statement 4
Simple Statement 5
}
Simple Statement 1
Simple Statement 2
...
Simple Statement 25
1 execution,
25 statements
= 25
Let’s count individual instructions
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Simple Statement
}
}
for (int k = 0; k < n; k++) {
Simple Statement 1
Simple Statement 2
T(n)
Simple Statement 3
Simple Statement 4
Simple Statement 5
}
Simple Statement 1
T(n)
Simple Statement 2
...
Simple Statement 25
= total execution time
as a function of n
= n2 + 5n + 25
Formal Big-O Definition
T(n) = n2 + 5n + 25
T(n) = O(f(n)) means that there exists a
function, f(n), that for sufficiently large n
and some constant c:
cf(n)  T(n)
2
n
+ 25n + 25 vs.
2
3n
Common Big-O Runtimes
•
•
•
•
•
•
•
•
•
Constant -- O(1)
Logarithmic -- O(log n)
Fractional -- O(sqrt n)
Linear -- O(n)
Log-Linear-- O(n log n)
Quadratic -- O(n2)
Cubic -- O(n3)
Exponential -- O(2n)
Factorial -- O(n!)
Various Runtimes
Calculating Big-O
1. T(n) = 6n4 − 2n3 + 5
2. T(n) = 9 log n + 5 (log n)3 + 3n2 + 2n3
3. T(n) = 3n2 + O(log n) + O(n) + O(n log n)
Calculating Big-O
4. Binary Search on an array:
T(n) = T(n/2) + O(1)
5. T(1) = 2
T(n) = 2T(n - 1) + O(1) for n>1
6. T(1) = 1
T(n) = 2T(n/2) + O(1) for n>1
Stacks
Stack ADT
• peek() - returns the top element of the stack
without removing it
• pop() - removes (and returns) the top
element of the stack
• push(x) - pushes x onto the top of the stack
LIFO structure - last in, first out
Queue
Queue ADT
• front() - returns the front element of the
queue without removing it
• dequeue() - removes (and returns) the front
element of the queue
• queue(x) - queues x at the end of the queue
FIFO structure - first in, first out
Priority Queue ADT
• front() - returns the highest priority element
of the queue without removing it
• dequeue() - removes (and returns) the
highest priority element of the queue
• queue(x, int) - queues x at the given priority
in the queue
FIFO structure??
Trees
• Nonlinear data structure
Tree Terminology
• root, leaf
• external, internal node
• parent, child, sibling • ancestor, descendant
• subtree
• depth, height
Binary Trees
• Each node has 0, 1, or 2 children
Traversal Exercise
Find the:
• preorder
• inorder
• postorder
• level-order
Ordered Binary Tree (Example)
Inserting to an Ordered Binary Tree
Removing from an Ordered Binary Tree
Worst Case Scenario?
AVL Balanced Tree (automatic)
Balancing a Binary Tree
Balancing a Binary Tree
Balancing a Binary Tree
Balancing a Binary Tree
Balancing a Binary Tree
Sorting
• Bubble Sort: K+W 577-580
• Selection Sort: K+W 572-576
• Insertion Sort: K+W 581-585
• (Self-Balancing) Binary Tree Sort:
http://en.wikipedia.org/wiki/Binary tree sort
• Quick Sort: K+W 604-613
• Merge Sort: K+W 592-598
• MSD Radix Sort: http://en.wikipedia.org/wiki/Radix sort
Sorting Analysis
Name
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort
Binary Tree Sort
Merge Sort
Radix Sort
Worst Case
O(n2)
O(n2)
O(n2)
O(n2)
O(n • log n)
O(n • log n)
O(n • k)
Notes
Counting Sort
O(n + r)
r is the range of possible
data values.
Used in radix sort.
O(n • log n) average
k is number of bits required to
represent data
Binary Max Heap
Heap Insert (example)
1
2
3
Heap Delete (example)
1
2
Binary Heap Operation Running Times
Operation
findMax
Binary
O(1)
deleteMax
O(log n)
insert
O(log n)
decreaseKey
O(log n)
merge
O(n)
Binary Heap Implementations
• Array
Graph Representations
• How do we represent a graph?
A
B
C
D
E
List Structures
A
B
C
D
E
V = {A, B, C, D, E}
E = {{A, B}, {A, D}, {C, E}, {D, E}}
• Incidence List
– E = {{A, B}, {A, D}, {C, E}, {D, E}}
• Adjacency List
– L = [A={B, D}, B={A}, C={E}, D={A, E}, E={C, D}]
Matrix Structures
A
B
C
D
E
V = {A, B, C, D, E}
E = {{A, B}, {A, D}, {C, E}, {D, E}}
A
B
C
• Adjacency Matrix
D
E
A
1
1
0
1
0
B
1
1
0
0
0
C
0
0
1
0
1
D
1
0
0
1
1
E
0
0
1
1
1
Minimum Spanning Tree Example
Hash Tables
• Goal: access item given its key (not its position)
– we wish to avoid much searching
• Hash tables provide this capability
– Constant time in the average case!
– Linear time in the worst case
O(1)
O(n)
• Searching an array: O(n) Searching BST: O(log n)
How could we resolve collisions?
• Goal is to still be able to insert, delete, and
search based on key
0
1
Hash
function
mod(10000)
302-831-2712
302-737-2712
101 Smith Hall
Newark, DE
?
n-1
Array table
Performance of Hash Tables (2)
L
0
0.25
0.5
0.75
0.83
0.9
0.95
Number of Probes
Linear Probing
Chaining
1.00
1.17
1.50
2.50
3.38
5.50
10.50
1.00
1.13
1.25
1.38
1.43
1.45
1.48
Performance of Hash Tables (3)
• Hash table:
– Insert: average O(1)
– Search: average O(1)
• Sorted array:
– Insert: average O(n)
– Search: average O(log n)
• Binary Search Tree:
– Insert: average O(log n)
– Search: average O(log n)
• But balanced trees can guarantee worst case O(log n)