Transcript CSE 326 Course Review

CSE 326
Course Review
David Kaplan
Dept of Computer Science & Engineering
Autumn 2001
Why (did we) study data structures?
Clever ways to organize information in order to
enable efficient computation
Theory
Databases
AI
Networking
Graphics
Games
Systems
Applications
Data
Structures
Course Review
CSE 326 Autumn 2001
2
Why (did we) take CSE 326?
 Guaranteed non-obsolescence
 May be most important CS course you ever take
 Gain concepts, plans and mechanisms for
creating better software
Course Review
CSE 326 Autumn 2001
3
Course Goals
 Learn some of the fundamental data
structures in computer science
 Learn to solve problems abstractly
 Data structures are the building blocks
 Learn to analyze and improve algorithms
 Prove correctness
 Gauge and improve time complexity
 Learn UNIX
 Required in upcoming courses
Course Review
CSE 326 Autumn 2001
4
Concepts, Plans, Mechanisms
Concepts
 A list that lets me store and retrieve things
 A tree that lets me store and retrieve things by
hierarchy
 A table that lets me store and retrieve things by
name
 A graph (network) that represents distances
between cities, relationships between people,
tasks within a project, etc.
 and so on …
Course Review
CSE 326 Autumn 2001
5
Concepts, Plans, Mechanisms
Plans
 Pseudocode
 Block Diagrams
 Flowcharts
Mechanisms
 Working code
Intuition is the bridge
concepts  plans  mechanisms
Course Review
CSE 326 Autumn 2001
6
Organizing Information
“Linear”
“Hierarchical”
Simple collection Collection with
Concepts
hierarchy
“Graphical”
Collection with
complex topology
Plans
(ADTs)
List, Stack,
Queue
Binary Search Tree,
B-Tree, AVL Tree,
Heaps, …
Directed Graph, DAG,
Flow Network, …
Mechanisms
Numerous
Numerous
Numerous
Course Review
CSE 326 Autumn 2001
7
Using Organized Information
Examples
 Dictionary ADT
 Store, retrieve, update, delete to-from large bodies of
information
 Priority queue ADT
 Handle “priority” on-the-fly
 Disjoint Sets ADT
 Handle dynamic equivalence on-the-fly
 Graph {ADT, data structure, ???}
 Answer hard questions (sometimes efficiently!)
 Shortest paths, spanning trees, …
Course Review
CSE 326 Autumn 2001
8
Asymptotic Complexity
How the running time of an algorithm scales
with the size of its input
Ways to measure complexity
 Worst case
 Average case
 Amortized over a series of (presumably
representative) runs
 Best case (occasionally useful)
Course Review
CSE 326 Autumn 2001
9
Apocalyptic Laptop
Seth Lloyd, a physicist at the Massachusetts
Institute of Technology, has calculated how
to make PCs almost unimaginably faster--if
you don't mind working on a black hole.
Lloyd has used the laws of thermodynamics,
information, relativity, and quantum
mechanics to figure out the ultimate physical
limits on the speed of a computer…
Lloyd's ultimate laptop would convert all of
its 1-kilogram mass into energy via Einstein's
famous equation E = mc2, thus turning itself
into a billion-degree blob of plasma. "This
would present a packaging problem," Lloyd
admits … The computer would be capable of
performing 1051 operations per second.
- Charles Seife, Science Magazine,
Vol 289, No 5484, Sep 1 2000,
pp. 1447-1448
Course Review
CSE 326 Autumn 2001
10
Big Bang
1E+60
ApocaLap, 1 year
ApocaLap, 1 sec
1E+55
1E+50
1E+45
2^N
1E+40
1.2^N
1E+35
N^5
1E+30
N^3
1E+25
5N
1E+20
1000 MIPS since Big Bang
1000 MIPS, 1 day
1E+15
1E+10
100000
1
1
Course Review
10
100
CSE 326 Autumn 2001
1000
11
Stuff we did








Lists
Stacks
Queues
Search trees, in many flavors
(BST, AVL, splay)
Heaps, in many flavors
(binary, d, leftist, skew)
Hashing
Graphs, spanning trees
Graph algorithms (Dijkstra’s,
Kruskal’s, Prim’s)
Course Review




CSE 326 Autumn 2001
Asymptotic complexity
Recursion analysis
Sorting, in many flavors
Randomization (treaps,
skip lists)
12
:-(
Stuff we didn’t get to
 Algorithm Design




Greedy
Divide and conquer
Backtracking
Dynamic programming
 Amortized Analysis (formal mechanisms)
 NP-Completeness
 At least enough to qualitatively distinguish P and
NP problems
Course Review
CSE 326 Autumn 2001
13
Are we convinced yet?
Mastery of this material separates you from …
Course Review
CSE 326 Autumn 2001
14
Coming Attractions
 Wed Dec 12: wrap-up and closing ceremony
 Wed Dec 12 3:30-4:30pm: Case Study
 Better Living through Graphs and Trees
 Sun Dec 16: Final Exam Review Session
 Time/place TBD
To do
study for …
Final Exam Mon, Dec 17 2:30pm, MGH 389
Course Review
CSE 326 Autumn 2001
15