Data Structure
and
Algorithms
1
Lecture 1
Introduction
2
Goals of this Course
1. Reinforce the concept that costs and benefits
exist for every data structure.
2. Learn the commonly used data structures.
These form a programmer's basic data structure
“toolkit.”
3. Understand how to measure the cost of a data
structure or program.
These techniques also allow you to judge the merits
of new data structures that you or others might
invent.
3
Goals of this Course
1. Reinforce the concept that costs and benefits
exist for every data structure.
2. Learn the commonly used data structures.
These form a programmer's basic data structure
“toolkit”.
3. Understand how to measure the cost of a data
structure or program.
These techniques also allow you to judge the merits
of new data structures that you or others might
invent.
4
Goals of this Course
1. Reinforce the concept that costs and benefits
exist for every data structure.
2. Learn the commonly used data structures.
These form a programmer's basic data structure
“toolkit”.
3. Understand how to measure the cost of a data
structure or program.
These techniques also allow you to judge the merits
of new data structures that you or others might
invent.
5
Course Contents
Introduction
Complexity Analysis
Simple Data Types and Abstract Data Types
Arrays and Lists
Elementary Data Structures
Stack and Queues
Recursion and Time Complexity of Recursive Algorithms
Trees and Graphs
Set structure
Searching techniques
Hashing
Sorting techniques
Data Structures
Text Book
Data Structures and Algorithms
By A. V. Aho, J. E. Hopcroft, J. D. Ullman
Data Structures and Algorithm Analysis in C++
Mark Allen Weiss, Florida International University
Addison-Wesley
C++ Introduction to Data Structures by Larry Nayhoff
Reference Material
Data Structures A psuedocode Approach with C by
Richard [Link] & Behrouz [Link]
7
Need for Data Structures
Data structures organize data more
efficient programs.
More powerful computers more complex
applications.
More complex applications demand more
calculations.
8
Need for Data Structures
Data structures organize data more
efficient programs.
More powerful computers more complex
applications.
More complex applications demand more
calculations.
9
Need for Data Structures
Data structures organize data more
efficient programs.
More powerful computers more complex
applications.
More complex applications demand more
calculations.
10
Organizing Data
Any organization for a collection of records
that can be searched, processed in any
order, or modified.
The choice of data structure and algorithm
can make the difference between a
program running in a few seconds or many
days.
11
Organizing Data
Any organization for a collection of records
that can be searched, processed in any
order, or modified.
The choice of data structure and algorithm
can make the difference between a
program running in a few seconds or many
days.
12
Efficiency
A solution is said to be efficient if it solves
the problem within its resource constraints.
Space
Time
The cost of a solution is the amount of
resources that the solution consumes.
13
Efficiency
A solution is said to be efficient if it solves
the problem within its resource constraints.
Space
Time
The cost of a solution is the amount of
resources that the solution consumes.
14
Selecting a Data Structure
Select a data structure as follows:
1. Analyze the problem to determine the
resource constraints a solution must
meet.
2. Determine the basic operations that must
be supported. Quantify the resource
constraints for each operation.
3. Select the data structure that best meets
these requirements.
15
Selecting a Data Structure
Select a data structure as follows:
1. Analyze the problem to determine the
resource constraints a solution must
meet.
2. Determine the basic operations that must
be supported. Quantify the resource
constraints for each operation.
3. Select the data structure that best meets
these requirements.
16
Selecting a Data Structure
Select a data structure as follows:
1. Analyze the problem to determine the
resource constraints a solution must
meet.
2. Determine the basic operations that must
be supported. Quantify the resource
constraints for each operation.
3. Select the data structure that best meets
these requirements.
17
Data Structure Philosophy
Each data structure has costs and
benefits.
Rarely is one data structure better than
another in all situations.
A data structure requires:
space for each data item it stores,
time to perform each basic operation,
programming effort.
18
Data Structure Philosophy
Each data structure has costs and
benefits.
Rarely is one data structure better than
another in all situations.
A data structure requires:
space for each data item it stores,
time to perform each basic operation,
programming effort.
19
Data Structure Philosophy
Each data structure has costs and
benefits.
Rarely is one data structure better than
another in all situations.
A data structure requires:
space for each data item it stores,
time to perform each basic operation,
programming effort.
20
Abstract Data Types
a collection of related data items together
with an associated set of operations
e.g. whole numbers (integers) and arithmetic
operators for addition, subtraction, multiplication and
division.
e.g. Flight reservation
Basic operations: find empty seat, reserve a seat,
cancel a seat assignment
Why "abstract?"
Data, operations, and relations are studied
independent of implementation.
Data Structure
A data structure is the physical implementation of
an ADT.
Each operation associated with the ADT is
implemented by one or more subroutines in the
implementation.
Data structure usually refers to an organization of
data in main memory.
File structure is an organization for data on
peripheral storage, such as a disk drive.
The LIST Data Structure
The List is among the most generic of data
structures.
Real life:
a. shopping list,
b. groceries list,
c. list of people to invite to dinner
d. list of presents to get
23