Data Structures and Algorithm

CS 232

Lecture-01

Dr. Muhammad sohail

November 11, 2024
Course Contents
• Introduction
• Algorithm Complexity Analysis
• Simple Data Types and Abstract Data Types
• Linear data structures (Stacks, Queues, Linked list)
• Non-linear data structures (Trees, Graphs)
• Recursion and recursive algorithms
• Sorting Algorithms (Bubble, Insertion, Selection, Quick,
Merge, Shell, Heap)
• Searching (Linear, Binary, Depth First, Breadth First,
Shortest Path, Minimum Spanning Trees)
• Hashing
• Data Compression (Huffman’s Code), Complexity
Analysis of Algorithms (Big-O notation)

2
Text 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

3
Course learning outcomes

CLO-01 Explain and compare different data structures and their

applications
CLO-02 Apply appropriate data structures according to the given
scenarios and application domain
CLO-03 Analyze time complexity of different algorithms
CLO-04 Design efficient algorithm(s) to solve real world problems

4
Labs & 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

5
Today’s Lecture
• Computer Program
• What are Data Structures?
• Data structure classification
• Data Structures Operations
• Why Data Structures?
• Need for Data Structures
• Organizing Data
• Efficiency
• Selecting a Data Structure
• Data Structure Philosophy

6
Computer Program
• To exactly know, what is data structure? We must know:
• What is a computer program?

Solution
Problem Computer Program

Input Process Output

(DS) (Algorithm) (DS)

Data Structures + Algorithms = Programs

7
What are Data 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
8
Data Structures & Algorithm Definition
A data structure is a format for organizing, processing, retrieving and
storing data so it can be easily accessed and effectively used.
While an algorithm is : step by step solution of a problem.

9
Data Structures Classification

10
Data Structures Operations
• Traversing
Visiting each element in
the Data Structure
Accessing each record
exactly once so that
certain items in the record
may be processed

• Searching
Finding the location or
presence of the record
with the given key value
or finding the location of
all records which satisfy
one or more conditions

11
Data Structures Operations..
• Insertion
• Adding a new record to
the structure

• Deletion
• Removing a record
from the structure

12
Data Structures Operations..
• Sorting
• Arrange the records in
a logical order

13
Data Structures Operations..
• Merging
• Combining records from two or more
files or data structures into one

14
Why Data Structures?
• Goal: to organize data

• Criteria: to facilitate efficient

• storage of data
• retrieval of data
• manipulation of data

15
16
Need for Data Structures
• Data structures organize data  more efficient programs.

• More powerful computers  more complex applications.

• More complex applications demand more calculations.

17
Organizing 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.

18
Efficiency
• A solution is said to be efficient
• If it solves the problem within its resource constraints
• Both in terms of Time and Space

• Time complexity is:

• The amount of time an algorithm takes to run as a function of the size of its
input.
• An algorithm with lower time complexity is more efficient, as it completes
its task in fewer steps.
• For example,
• an algorithm with a time complexity of O(n) (linear time) will take
approximately n steps to process an input of size n.

• An algorithm with a time complexity of O(n^2) (quadratic time) will take

roughly n^2 steps, which can become inefficient for large input sizes.

19
20
Efficiency
• Space complexity
• The amount of memory space used by an algorithm to complete its task as a
function of the input size
• It includes the memory used for variables, data structures, function calls,
and so on
• An algorithm with lower space complexity uses less memory and is more
efficient in terms of space usage.
• For example,
• An algorithm with a space complexity of O(1) (constant space) uses a
fixed amount of memory regardless of the input size.

• On the other hand, an algorithm with a space complexity of O(n) (linear

space) uses an amount of memory proportional to the input size.

• The cost of a solution is the amount of resources that the solution

consumes.

21
22
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.

23
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.

24
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

25
THANK YOU

26