Transcript No Slide Title

CS 315 Data Structures
B. Ravikumar
Office: 116 I Darwin Hall
Phone: 664 3335
E-mail: [email protected]
Course Web site:
http://ravi.cs.sonoma.edu/cs315sp09
Textbook for the course:
Data Structures and Algorithm
Analysis in C++
by Mark Allen Weiss
Class time
Lecture:
T Th 10:45 to 12 noon, Darwin Hall 102
Lab:
F 9 to 11:50 AM, Darwin Hall # 25
Data Structures – informal definition
How to store data sets in memory so that the
computation(s) can be solved easily, efficiently
etc.
Some typical issues:
• preprocessing vs. updating
• trade-offs between operations
• interaction between algorithm and data
structure
Course Goals
• Learn to use fundamental data structures:
• arrays, linked lists, stacks and queues
• hash table
• priority queue – binary heap and others
• binary trees, binary search trees, AVL trees
• quad-trees, skip-lists
• Improve your skill in programming in c++
• recursion, classes, algorithm implementation
• design solutions using different data
structures
Course Goals
• Analytical and experimental analysis
• quantitative reasoning about the
performance of algorithms (time, storage,
network, bandwidth etc.)
• comparing different data structures
• Applications
• image storage and manipulation
• image and data compression
• sorting and searching
• spelling checking, backtracking
• packet routing in a network
• geometric problems
Goals for today’s lecture
• Course outline
• Course work
• lab assignments
• projects
• tests, final exam
• quiz and class participation (new)
• If any time left, start discussing recursion.
Data Structures – key to software design
• Data structures play a key role in every type of
software.
• Data structure deals with how to organize the
data in the memory while solving a problem in
order to reduce
•overall running time of a program
•response time (for queries)
•memory requirements
• Cost model for data access - array access,
pointers
Abstract Data Structure (ADT), supported
operations
•Dictionary
•search
•insert
•Delete
•deleteMin
•Range search
•Successor
•Merge
•Priority queue
primary operations
secondary operations
•Insert
primary operations
•deleteMin
•Merge, split etc. Secondary operations
Linear data structures
• key properties of the (1-d) array:
• a sequence of items are stored in
consecutive memory locations.
• array provides a constant time access to
k-th element for any k.
(access the element by: Element[k].)
Linear data structures
•inserting at the end is easy.
if the current size is s, then we can add x
at the end using the single instruction:
Element[s++] = x;
• deleting at the end is also easy.
• inserting or deleting at any other position is
expensive.
• searching for a key is expensive (unless
sorted).
• Expensive means the number of operations ~
size of the array.
Images stored in 2-dim arrays

We will work on 2-d arrays by manipulating images:
• Each pixel is represented by a blue value, a red value
and a green value (any color is a combination of these
colors).
(255, 255, 255) represents white,
(255, 0,
0) represents red etc.
• pic(i , j)-> Blue represents the blue component of the i-th
row, j-th column pixel of pic and so on.
• Some basic operations on images:
• open, read, write
• rotate, copy a sub-image
• filter (remove blemishes)
• extract features (identify where buildings are in an
aerial photograph)