Transcript CSE 326: Data Structures Lecture #7 Branching Out

CSE 326: Data Structures
Lecture #25
Class Wrap-up
Steve Wolfman
Winter Quarter 2000
Today’s Outline
• Finish algorithms
• Wrap-up of class
Game Search
•
•
•
•
Search space is composed of board positions
Transitions are moves
Levels alternate between us and them
We can evaluate any given board position
according to a scoring heuristic
How should we decide the next move?
Backtracking Game Search
(MiniMax)
44
us
44
them
us
27
36
44
78
44
68
40
78
40
36
27
36
36
42 27 86 44 68 73 78 79 73 40 27 87 68 36 55 36
42 25 27 7 72 86 9 44 50 68 73 31 78 17 79 37 73 23 30 40 19 27 64 87 57 68 29 36 5 55 12 36
- Pruned Game Search
us
them
us
7
44
44
42 27 86 44
42 25 27 7 72 86 9 44 50 68 73 31 78 17 79 37 73 23 30 40 19 27 64 87 57 68 29 36 5 55 12 36
Randomized Algorithms
• Define a property (or subroutine) in an algorithm
• Sample or randomly modify the property
• Use altered property as if it were the true property
Can transform average case runtimes into expected
runtimes (remove input dependency).
Sometimes allows substantial speedup in exchange
for probabilistic unsoundness.
Randomization in Action
•
•
•
•
Treaps
Quicksort
Randomized back-off
Primality testing
Properties of Primes
P is a prime 0 < A < P and 0 < X < P
Then:
AP-1 = 1 (mod P)
And, the only solutions to X2 = 1 (mod P) are:
X = 1 and X = P - 1
Calculating Powers
HugeInt pow(HugeInt x, HugeInt n, HugeInt modulo)
{
if (n == 0)
return 1;
if (n == 1)
return x;
HugeInt squared = x * x % modulo; // If 1 < x < modulo - 1
if (isEven(n))
// but squared == 1,
// then modulo isn’t prime!
return pow(squared, n / 2);
else
return (pow(squared, n/2) * x) % modulo;
}
Checking Primality
Systematic algorithm:
– For prime P, for all A such that 0 < A < P
– Calculate AP-1 mod P using pow
– Check at each step of pow and at end for primality
conditions
Randomized algorithm: use just one random A
If the randomized algorithm reports failure, then P really isn’t prime.
If the randomized algorithm reports success, then P might be prime.
– P is prime with probability > ¾
– Each new A has independent probability of false positive
Evaluating Randomized
Primality Testing
Your probability of being struck by lightning this
year: 0.00004%
Your probability that a number that tests prime 11
times in a row is actually not prime: 0.00003%
Your probability of winning a lottery of 1 million
people five times in a row: 1 in 2100
Your probability that a number that tests prime 50
times in a row is actually not prime: 1 in 2100
Randomized Greedy Algorithms:
Simulated Annealing
25
20
15
10
5
0
-5
-10
Randomized Backtracking for
Heavy-Tailed Distributions
Some backtracking algorithms have a few (fruitless)
branches that are very large, both deep and broad.
Algorithms which choose randomly at a split point will
have a small probability of getting caught in one of
these branches.
Therefore, some runs finish very quickly, most runs
take some time, and a few runs take orders of
magnitude more time than the median.
Solution: cut off long runs and reseed the randomizer.
Course Overview
Data Structures and ADTs
List, Stack,
Queue, Multilist
Dictionary
Priority Queue
Linked lists
Arrays
BSTs
AVL trees
Splay trees
B-Trees
Hash tables
Treaps
Skip lists
Binary heaps
d-Heaps
Leftist heaps
Skew heaps
Binomial queues
Course Overview
Data Structures and ADTs
Disjoint Set
Union/Find ADT
Multidimensional
Dictionary
Graph
Up-tree forest
k-D trees
Quad trees
BSP trees
Adjacency list
Adjacency matrix
Course Overview
Algorithms and
Algorithm Analysis
• Analysis of algorithms
–
–
–
–
proofs of correctness
asymptotic analysis (relative runtimes in the limit)
strict analysis (actual number of operations)
greedy vs. divide&conquer vs. backtracking etc.
• Actual algorithms
– searching (linear search, binary search, tree search,
hashing)
– sorting (heapsort, mergesort, quicksort, radixsort)
– graph algorithms (Dijkstra’s, Kruskal’s)
Course Overview
Evaluating Algorithms
Use of space and time:
– asymptotic analysis for high-level comparison
•
•
•
•
worst case
best case
average case
expected case
– stricter analysis, experiments for practical performance
How fast is fast enough?
Course Overview
Criteria for Good Running Time
Your resources
– how much time/memory can you afford?
Nature of the problem
– some problems are just harder than others
(e.g., sorting is harder than finding)
Characteristics of your application
– what problem sizes/types of inputs will you be running on?
– how might they change in the future?
Ease of Coding/Maintainability
– sometimes coding and maintenance time and costs dominate
Sour Cove Review
Games Theoreticians Play
Prove that an algorithm is (f(n)) by nature
– e.g., sorting using only comparisons cannot be done in
less than n log n
What’s wrong with this claim?
“I wrote a FindMin() operation that runs in
in O(log n) time on an unsorted list of integers!”
Receives Our Vow
More Games Theoreticians Play
Take an operation and
– see how fast you can do it
(e.g., decreaseKey in amortized O(1))
– see how simple you can make it
(e.g., Treaps)
– see how you can put it together with other operations
Or Cues Overview
Observation
• All programs manipulate data
– programs process, store, display, gather
– data can be information, numbers, images, sound
• Each program must decide how to store data
• Choice influences program at every level
– execution speed
– memory requirements
– maintenance (debugging, extending, etc.)
Course Overview
Goals of the Course
• Become familiar with some of the fundamental data
structures in computer science
• Improve ability to solve problems abstractly
– data structures are the building blocks
• Improve ability to analyze your algorithms
– prove correctness
– gauge (and improve) time complexity
• Become modestly skilled with the UNIX operating
system and X-windows (you’ll need this in upcoming courses)
To Do
• Study for the final
Coming Up
• Fun stuff on Friday
• Final Exam (March 13th)