Transcript ppt

Come on down!
• Take and fill out a survey
• Get a copy of lecture slides
• Please sit in the first 5 rows!
CSE 326: Data Structures
Lecture #1
Introduction
Alon Halevy
Spring Quarter 2001
Today’s Outline
•
•
•
•
Administrative Stuff
Overview of 326
Survey
Introduction to Complexity
Course Information
• Instructor: Alon Halevy <alon@cs>
Office hours: Wed. 4:30-5:30, 310 Sieg Hall
• TA: Maya Rodrig <rodrig@cs>
Office hours: Monday 1:30-2:30.
Meet in Sieg 226B
• TA (1/2) (and C++ expert): Nicholas Bone (bone@cs)
• Sections are held in: BLD 392, EE1 031.
• Text: Data Structures & Algorithm Analysis in C++,
2nd edition, by Mark Allen Weiss
Course Policies
• Several written homeworks
– Due at the start of class on due date
• Several programming projects
– Projects turned in electronically before 11pm on due date
• 10% penalty for 1 weekday late; afterward, NOT accepted
• Work in teams only on explicit team projects
• Grading
–
–
–
–
homework:
projects:
midterm:
final:
25%
25%
20%
30%
Course Mechanics
• 326 Web page: www/education/courses/326/01sp
• 326 course directory: /cse/courses/cse326
• 326 mailing list: [email protected]
– subscribe to the mailing list using majordomo, see
homepage
• Course labs are 232 and 329 Sieg Hall
– lab has NT machines w/X servers to access UNIX
• All programming projects graded on UNIX/g++
What is this Course About?
Clever ways to organize information in order to
enable efficient computation
– What do we mean by clever?
– What do we mean by efficient?
Clever? Efficient?
Lists, Stacks, Queues
Heaps
Binary Search Trees
AVL Trees
Hash Tables
Graphs
Disjoint Sets
Data Structures
Insert
Delete
Find
Merge
Shortest Paths
Union
Algorithms
Graphics
Theory
AI
Applications
Systems
Used Everywhere!
Mastery of this
material separates
you from:
• Perhaps the most important course in your CS curriculum!
• Guaranteed non-obsolescence!
Anecdote #1
• N2 “pretty print” routine nearly dooms major
expert system project at AT&T
– 10 MB data = 10 days (100 MIPS)
– programmer was brilliant, but he skipped 326…
Asymptotic Complexity
Our notion of efficiency:
How the running time of an algorithm scales with the
size of its input
– several ways to further refine:
• worst case
• average case
• amortized over a series of runs
The Apocalyptic Laptop
Seth Lloyd, SCIENCE, 31 Aug 2000
Big Bang
Ultimate Laptop,
1 year
1 second
1E+60
1E+55
1E+50
2^N
1.2^N
N^5
N^3
5N
1E+45
1E+40
1000 MIPS,
since Big Bang
1E+35
1E+30
1E+25
1E+20
1000 MIPS,
1 day
1E+15
1E+10
100000
1
1
10
100
1000
Specific 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 (you’ll need this in upcoming courses)
One Preliminary Hurdle
1. Recall what you learned in CSE 321 …
–
–
–
–
proofs by mathematical induction
proofs by contradiction
formulas for calculating sums and products of series
recursion
Know Sec 1.1 – 1.4 of text by heart!
A Second Hurdle
• Unix
Experience 1975 all over again!
– Try to login, edit, create a Makefile, and compile your
favorite “hello world” program right away
– Programming Project #1 distributed Wednesday
– Bring your questions and frustrations to Section on
Thursday!
A Third Hurdle: Templates
class Set_of_ints {
public:
insert( int x );
boolean is_member( int x ); … }
template <class Obj> class Set {
public:
insert( Obj x );
boolean is_member( Obj x ); … }
Set <int> SomeNumbers;
Set <char *> SomeWords;
In Every Silver Lining, There’s a Big
Dark Cloud – George Carlin
• Templates were invented 12 years ago, and still no
compiler correctly implements them!
• Using templates with multiple source files tricky
– See Course Web pages and TAs for best way
• MAINTAINING SANITY RULE
– Write/debug first without templates
– Templatize as need
– Keep it simple!
Handy Libraries
• From Weiss:
vector < int > MySafeIntArray;
vector < double > MySafeFloatArray;
string MySafeString;
• Like arrays and char*, but provide
– bounds checking
– memory management
• STL (Standard Template Library)
– most of CSE 326 in a box
– don’t use (unless told); we’ll be rolling our own
C++  Data Structures
One of the all time great books in computer science:
The Art of Computer Programming (1968-1973)
by Donald Knuth
Examples in assembly language (and English)!
American Scientist
says: in top 12 books
of the CENTURY!
Very little about C++ in class.
Abstract Data Types
Abstract Data Type (ADT)
Mathematical description of an
object and the set of operations
on the object
tradeoffs!
Data Types
integer, array,
pointers, …
Algorithms
binary search,
quicksort, …
ADT Presentation Algorithm
• Present an ADT
• Motivate with some applications
• Repeat until it’s time to move on:
– develop a data structure and algorithms for the ADT
– analyze its properties
•
•
•
•
efficiency
correctness
limitations
ease of programming
• Contrast strengths and weaknesses
First Example: Queue ADT
• Queue operations
–
–
–
–
–
create
destroy
enqueue G enqueue
dequeue
is_empty
FEDCB
dequeue
A
• Queue property: if x is enQed before y is enQed,
then x will be deQed before y is deQed
FIFO: First In First Out
Applications of the Q
•
•
•
•
Hold jobs for a printer
Store packets on network routers
Make waitlists fair
Breadth first search
Circular Array Q Data Structure
Q
0
size - 1
b c d e f
front
back
enqueue(Object x) {
Q[back] = x ;
back = (back + 1) % size }
How test for empty list?
dequeue() {
x = Q[front] ;
front = (front + 1) % size;
return x ; }
What is complexity of
these operations?
How to find K-th
element in the queue?
Limitations of this
structure?
Linked List Q Data Structure
b
c
d
front
enqueue(Object x) {
back->next = new Node(x);
back = back->next; }
dequeue() {
saved = front->data;
temp = front;
front = front->next;
delete temp ;
return saved;}
e
f
back
What are tradeoffs?
• simplicity
• speed
• robustness
• memory usage
To Do
•
•
•
•
Return your survey before leaving!
Sign up on the cse326 mailing list
Check out the web page
Log on to the PCs in course labs and access an
instructional UNIX server
• Read Chapters 1 and 2 in the book