Lecture 1: Introduction

FAST- National University of

Computer and Emerging Sciences

Data Structures
Introduction
Dr. Abdul Waheed Khan
&
Shehreyar Rashid
Shehreyar.rashid@nu.edu.pk

Lecture No. 1
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction

Some Rules
– Raise your hand before asking any question and then
WAIT for the permission
– Never ever miss a class
• No retakes (except for Final Exam*)
– Never ever “sleep” in the class
• You might miss a quiz 
– Never use mobile phone in the class

– Above all, whatever you do, please do not disturb

others

* Conditional: as per university policy

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Dishonesty, Plagiarism

• Any kind of cheating will be considered serious

offense
• All parties involved in any kind of cheating in any
exam (Quizzes, Assignments & Projects) will get
minus (-) 50% in that exam
• Habitual cases will be awarded F

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Dishonesty, Plagiarism
You can fool some of the people all of the time, and
all of the people some of the time, but you can not
fool all of the people all of the time.
Abraham Lincoln,
16th president of US (1809 - 1865)

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Attendance Policy
• Student arriving after the attendance will be
marked “late” . No excuse to students arriving
immediately after the attendance.
• Two late arrivals will be treated as absent.
• Students are not allowed to switch sections.

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

About you?
• You are here because?

– There is no other option ☺

– What if you had an option?

• This is the core course not without any good

reason!

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

General Overview
Introduction to
Computer Science

What is Hardware, Software, Programming, Operating System etc

Computer
Programming

How to write software with the help of procedural and object oriented
programming?

Data Structures

How to efficiently utilize resources with the help of different data structures?

Algorithm Analysis

How to efficiently solve complex problems?

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Course objectives
• In simple words, you will learn how to write
efficent programs.

• At a personal level, I would be more than happy

if I can make you think and teach you to be
honest.

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

What is a data structure?

• In a general sense, any representation that is
used for storing information is a data structure

• Example: An integer, structures, classes, linked

lists, etc

• More typically, a data structure provides a way

of organization for a collection of data items

9
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction

Where Data Structure is Helpful?

• The choice of efficient data structure makes
the difference between a program running in a
few seconds or many days

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

What is Data Structure 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.

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Costs and Benefits

• Each data structure has costs and benefits.

• It is very difficult to find a data structure that

is better than others in all situations.

• A data structure requires:

– space for each data item it stores,
– time to perform each basic operation,
– programming effort.

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Goals of this Course

1. Learn the commonly used data structures.
– These form a programmer's basic data structure
“toolkit”

2. Case Studies of Data Structures.

3. We will examine the costs and benefits of

every data structure or program.

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Course Contents
• Introduction
• Simple Data Types and Abstract Data Types
• Background: Templates and Algorithm Analysis
• Array
• Searching techniques
• Sorting techniques Mid term
• Linked Lists
• Queue
• Stack
• Trees: Definitions and terminology

• Tree:
• BST
• AVL Trees
• Heap SECOND SESSION
• Graphs
• B+ Trees
• Hashing

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Tentative Evaluation Breakdown

Evaluation Name Weightage
Quiz 5
Lab 10
Assignment 15
Project 10
Midterm 20
Final 40

1. Labs attendance is mandatory!

2. Hard to get good marks in assignments without
lab

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Motivational Example
• A cellular service company provides contracts to its 10
million users
• Due to new security enforcements, the company wants
to prevent issuing of multiple contracts to users

• Method of Detecting Multiple Contracts

– Before issuing a new contract to user
– First search the id of user in existing contracts database
– In case of failure, issue a new contract
– In case of success, do not issue a new contract to user

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Example: linear Array Data Structure

NIC# Name Address
6584495-9 Muhammad Faheem House No 3 Gulshan Bahar Sec 16
1748425-5 Naeem Alam A-11 Shams Plaza Block-B N.Nazimabad
0889679-1 Arslan Akhtar H No 152 Bostang Colony
3419668-1 Zain Ahmed Sharfabad Street Gulshan Karachi
3445864-3 Sumair Farooq Post Office Tayyar, Multan
6395653-4 Ali Affan H.No. 425, Sector F-11/4, Islamabad
8224641-1 Syed Faraz Sharfabad Street Gulshan, Faisalabad

• Linear Array (with 10 million entries)

• 3 arrays (NIC, name, address),
• structure array,
• class’s object array

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Example
New NIC# Name Address
Contract 6584495-9 Muhammad Faheem House No 3 Gulshan Bahar Sec 16
1748425-5 Naeem Alam A-11 Shams Plaza Block-B N.Nazimabad
0889679-1 Arslan Akhtar H No 152 Bostang Colony
3419668-1 Zain Ahmed Sharfabad Street Gulshan Karachi
Searching
3445864-3 Sumair Farooq Post Office Tayyar, Multan
6395653-4 Ali Affan H.No. 425, Sector F-11/4, Islamabad
8224641-1 Syed Faraz Sharfabad Street Gulshan, Faisalabad

Failure Success

Issue Not Issue

• Any disadvantage of Linear Array (Data Structure)?
• How to improve?
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction

Example :Improved Data Structure

• Create a dictionary data structure
– Group similar records together
– Similarity in terms of first digit of NIC number
– Add a dictionary entry for each distinct digit (0-9)

• Example: 3419668-1, 3445864-3, 1748425-5.

• 3 and 1 are dictionary entries

– In case of searching, first search the dictionary entry,

and then proceed to searching contracts

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Example
0 2
3 3 4
6 0 5

Dictionary Array Elements

NIC# Name Address
6584495-9 Muhammad Faheem House No 3 Gulshan Bahar Sec 16
1748425-5 Naeem Alam A-11 Shams Plaza Block-B N.Nazimabad
0889679-1 Arslan Akhtar H No 152 Bostang Colony
3419668-1 Zain Ahmed Sharfabad Street Gulshan Karachi
3445864-3 Sumair Farooq Post Office Tayyar, Multan
6395653-4 Ali Affan H.No. 425, Sector F-11/4, Islamabad
8224641-1 Syed Faraz Sharfabad Street Gulshan, Faisalabad

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Example
• Another possibility
• Maintain pointers with structures ( or records)
• Non NULL pointer indicates presence of next
record

NIC# Name Address

6584495-9 Muhammad Faheem House No 3 Gulshan Bahar Sec 16
0 1748425-5 Naeem Alam A-11 Shams Plaza Block-B N.Nazimabad

3 0889679-1
3419668-1
Arslan Akhtar
Zain Ahmed
H No 152 Bostang Colony
Sharfabad Street Gulshan Karachi

6 3445864-3 Sumair Farooq Post Office Tayyar, Multan

6395653-4 Ali Affan H.No. 425, Sector F-11/4, Islamabad
8224641-1 Syed Faraz Sharfabad Street Gulshan, Faisalabad

Dictionary
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction

Books
• Data Structures Using C++ (By D. S. Malik)

• Data Structures Using C and C++ (By Y. Langsam, M. J.

Augenstein, A. M. Tenenbaum)

• Data Structures and Algorithms (By A. V. Aho, J. E.

Hopcroft, J. D. Ullman)

• Schaum's Outline Series, Theory and problems of Data

Structures (By Seymour Lipschutz)

Some topics will be covered from other books. Material will

be provided for these topics.

FAST, National University of Computer and Emerging Sciences, Islamabad

Lecture 1: Introduction

Any Question So Far?

FAST, National University of Computer and Emerging Sciences, Islamabad