CS 232
Data Structures
Lecture-01
Department of Computer Science & IT
Sarhad University of Science and Information
Technology, Peshawar
Course
Course Contents
Contents
• Introduction
• Algorithm Complexity Analysis
• Simple Data Types and Abstract Data Types
• Arrays and Lists
• Elementary Data Structures
• Stack and Queues
• Recursion
• Trees and Graphs
• Searching techniques
• Hashing
• Sorting techniques
CS 232: Data Structures 2
Text
Text Books
Books
• Data Structures using C and C++ 2nd Edition
– Yedidyah Langsam, Moshen J. Augenstein and Aaron M. Tenenbaum
• Schaum's Outline Series: Theory and problem of Data
structures
– Seymour Lipschutz
CS 232: Data Structures 3
Labs
Labs &
& Tutorials
Tutorials
• Labs will be held weekly
• Attendance is Compulsory
• Tutorials can be arranged if needed
• Make Groups of 3 students for Labs and Class Presentations
CS 232: Data Structures 4
Course
Course Objectives
Objectives
Prepares the students for the more advanced material the
students will encounter in later courses.
Understand the concepts of Efficiency in terms of time
complexity and space complexity.
Cover well-known data structures such as arrays, linked lists,
stacks, queues, tree and graphs.
Implement data structures in C++.
CS 232: Data Structures 5
Today’s
Today’s Lecture
Lecture
• Computer Program
• What are Data Structures?
• Data Structures Operations
• Why Data Structures?
• Need for Data Structures
• Organizing Data
• Efficiency
• Selecting a Data Structure
• Data Structure Philosophy
CS 232: Data Structures 6
Computer
Computer Program
Program
• To exactly know, what is data structure? We must know:
– What is a computer program?
Computer Program
Solution
Problem
Input Process Output
(DS) (Algorithm) (DS)
Data Structures + Algorithms = Programs
CS 232: Data Structures 7
What
What are
are Data
Data Structures?
Structures?
• Data structures let the input and output be represented in a
way that can be handled efficiently and effectively.
Array
Linked List
Queue
Tree
Stack
CS 232: Data Structures 8
Data
Data Structures
Structures Operations
Operations
• Traversing
– Accessing each record exactly once so that certain items in the record may
be processed
• Searching
– Finding the location of the record with the given key value or finding the
location of all records which satisfy one or more conditions
• Insertion
– Adding a new record to the structure
• Deletion
– Removing a record from the structure
• Sorting
– Arrange the records in a logical order
• Merging
– Combining records from two or more files or data structures into one
CS 232: Data Structures 9
Why
Why Data
Data Structures?
Structures?
• Goal: to organize data
• Criteria: to facilitate efficient
– storage of data
– retrieval of data
– manipulation of data
CS 232: Data Structures 10
Need
Need for
for Data
Data Structures
Structures
• Data structures organize data more efficient programs.
• More powerful computers more complex applications.
• More complex applications demand more calculations.
CS 232: Data Structures 11
Organizing
Organizing Data
Data
• Any organization collect data that can easily 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.
CS 232: Data Structures 12
Efficiency
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.
CS 232: Data Structures 13
Selecting
Selecting aa Data
Data Structure
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.
CS 232: Data Structures 14
Data
Data Structure
Structure Philosophy
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.
CS 232: Data Structures 15
Summary
Summary
• Computer Program
• What are Data Structures?
• Data Structures Operations
• Why Data Structures?
• Need for Data Structures
• Organizing Data
• Efficiency
• Selecting a Data Structure
• Data Structure Philosophy
CS 232: Data Structures 16
THANK
THANK YOU
YOU
CS 232: Data Structures 17
