DS 1

Data Structures & Algorithms
ahmad
Lecture 1
Books
• Recommended Text Book:
• Langsam, Tanenbaum, “Data Structures

Using C and C++”, Prentice Hall.
• Alfred V. Aho, Jaffery D. Ullman, John E.
Hopcroft, “Data Structures and
Algorithms”, Addison-Wesley
Course Objectives
• The objective of this course is to introduce the
analysis and designing of data structures using
various standard algorithms.
• Cover well-known data structures such as

arrays, linked lists, stacks, queues, trees and
graphs.
• Implement data structures in C++

Data Representation
• A computer is a machine that manipulates

data.
• The prime aim of data structure includes to
study:
– Data Organization
– Data Manipulation
– Data retrieval
– Data Utilization
Data Structure
• A data structure is a particular way of storing,
retrieving and organizing data in a computer so
that it can be used efficiently.
• Data may be organized in many different ways,

the logical or mathematical model of a particular
organization of data in memory or on disk is
called Data Structure.
Algorithms are used for manipulation of data.

Data Structure Operation
• The data appearing in different data structures is
processed by means of certain operations.
• The particular data structure that one chooses for a

given situation depends largely on the frequency with
which specific operations are performed.
• The following four operations play a major role:

– Traversing
– Searching
– Insertion
– Deletion
Data Organization
• Structure: how data is organized

– Place data contiguously
– Place data here and there with “links”
– Place data with “formula”
Types of Data Structures
• Linear Data Structure
– Linear data structures organize their data elements in a
linear fashion
– Data elements in linear data structures are attached one
after the other and traversed one after the other.
– Only one element can be directly reached while traversing.
• Non- Linear Data Structure
– Data elements are not organized in a sequential fashion.
– A data item in a nonlinear data structure could be attached
to several other data elements to reflect a special
relationship among them.
– All the data items cannot be traversed in a single run.
Types of Data Structures
• Linear Data Structure
– Array
– Stack
– Queue
– Linked List
• Non- Linear Data Structure
– Tree
– Graph
Characteristic of data structure
Data Structure Advantages Disadvantages
Arrays Quick insertion, very fast access if index is Slow search, Slow deletion, Fixed
known size
Ordered Array Quicker search than unsorted array. Slow insertion and deletion, Fixed
size
Stack Provides last-in first-out access Slow access to other items
Queue Provides first-in first-out access Slow access to other items
Linked List Quick insertion and quick deletion Slow search
Binary Trees Quick search, insertion and deletion if Deletion algorithm is complex.
tree remains balance
Hash Table Very fast access if key known, Fast Slow deletion, access slow if key
insertion. not known, inefficient memory
usage
Heap Fast insertion ,deletion. Access to largest Slow access to other items
item
Graph Models real world situation Some algorithms are slow and
access.
Algorithm
• An algorithm is a finite set of instructions

that takes some raw data as input and
transforms it into refined data.
• An algorithm is a well-defined list of steps

for solving computational problem.
Complexity of Algorithm
• Efficiency or complexity of an algorithm is

stated as a function relating the length to
the number of steps (time complexity) or
storage location (space complexity).
f(n)
• In simple words complexity of an algorithm
is the time and space it uses.
Time Complexity
• Running time of the program as a function

of size of input.
Space Complexity
• Amount of Computer memory required during
the program execution, as a function of input
size.
Types of Analysis
• Types of Analysis
– Worst case running time
– Average case running time
– Best case running time
Time-Space Tradeoff
• In computer science, a space-time or time-
memory tradeoff is a way of solving a problem or
calculation in less time by using more storage space
(or memory), or by solving a problem in very little
space by spending a long time.
• So if your problem is taking a long time but not

much memory, a space-time tradeoff would let you
use more memory and solve the problem more
quickly.
• Or, if it could be solved very quickly but requires

more memory than, you can try to spend more time
solving the problem in the limited memory.
Simplest Data Structures
• Basic data types a language supports:

– Integer, float, double, char, boolean
– string: usually an array of char supported with
library
Simplest Data Structures
• A single datum in one of the basic types

• A structure is a combination of the basic
types
– A Publication: code—string, description—
string, price– double
• A structure is a combination of basic types
and structures
– An Order item: publication—Publication,
quantity– integer, deleteFlag – boolean
C Structures
struct type_name {
member_type1 member_name1;
.
.
} object_names;

DS 1

Uploaded by

Copyright:

Available Formats

DS 1

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS 1

Uploaded by

Copyright:

Available Formats

Data Structures & Algorithms

• Recommended Text Book:

• Langsam, Tanenbaum, “Data Structures

• Cover well-known data structures such as

• Implement data structures in C++

• A computer is a machine that manipulates

• Data may be organized in many different ways,

Algorithms are used for manipulation of data.

• The particular data structure that one chooses for a

• The following four operations play a major role:

• Structure: how data is organized

• An algorithm is a finite set of instructions

• An algorithm is a well-defined list of steps

• Efficiency or complexity of an algorithm is

• Running time of the program as a function

• So if your problem is taking a long time but not

• Or, if it could be solved very quickly but requires

• Basic data types a language supports:

• A single datum in one of the basic types

You might also like