Lecture 1: Introduction
FAST- National University of
Computer and Emerging Sciences
Data Structures
Introduction
Lecture No. 1
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Miscellaneous Details
Course Instructor: Ms. Saba Rasheed Malik for Sec-C, D and F
Office: New Building, C-205G
Contact: [Link]@[Link]
Course Lab Instructor: Umair (Sec-C &F) and Touqeer (Sec-D)
Course Pre-Requisite: OOP
Course portal: Google classroom(already created),NU id has been
added, if you haven't got an invite at your NU Id yet, drop an email to
your instructor
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Course Policy
ü Instead of hunting for teachers, drop an email to your teacher and wait!
ü Subject must be DS_Fall20_Section:<Concern>
ü Follow office Hours(09:00-17:00)(Monday-Friday) for email communication
ü Expect reply from the instructor within 24 hours of working day.
ü Incase of delay you can share a reminder politely.
ü For every assignment, there will be an associated quiz to evaluate your performance.
ü Labs are compulsory and that content can be asked during class quizzes. Lab
performance will be included in your class grade however mechanics will be shared
along the way.
ü Lab grade is part of the class and that will only be considered if you attend the labs
as per schedules.
ü No extension in tasks so don’t expect ever
ü Deadlines will be based on semester’s practical constraints, already
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Course Policy
ü Warning! Be regular in class for not pleading later
ü Your attendance requirement is 100% however you are given compensation of
20% considering routine life circumstances.
ü For online classes, attendance will be accommodated as per guidelines
instructed by the university administration.
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Classroom etiquette
• Online meeting link for the class will be available.
• Classroom recordings will be shared.
• Arrive/join class on time and prepared. Have your note book and pen in every
class.
• You are not allowed to take your class in other section. If necessary, you need to
take permission otherwise your attendance won’t be considered and neither any
assessment being conducted in that class.
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Submission Guidelines
• There is no retake for assignments and quizzes.
– For quizzes the number of quizzes would be high that will
accommodate the missing quizzes in best-of-x policy
• No late submission is allowed
• To accommodate inconvenience of load shedding or
internet issues, you will be provided a 12 hours buffer
with every assignment submission time.
• Timeline of assignments will be released, so
accommodate your semester schedule accordingly.
• For group tasks, you are only allowed to make
groups within your section.
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Dishonesty, Plagiarism
• Plagiarism in project or midterm/ final exam
may result in F grade in the course.
• Plagiarism in an assignment will result in zero
marks in the whole assignments category.
• 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
Marks distribution( Subject to change)
Assessment Item Number Weight (%)
Assignments >2 15
Quizzes >5 05
Midterm Exam 1 20
Lab Work 12 10
Project 1 10
Final Exam 1 40
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
About you?
• You are here because?
– There is no other option J
– 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
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
Importance of Data Structures
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Importance of Data Structures
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Importance of Data Structures
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Importance of Data Structures
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Importance of Data Structures
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Importance of Data Structures
FAST, National University of Computer and Emerging Sciences, Islamabad
Lecture 1: Introduction
Course Contents
• Introduction
• Simple Data Types and Abstract Data
Types
• Array
• Searching techniques Mid Exam
• Sorting techniques
• List
• Stack
• Queue
• Tree
• Heap Final Exam
• Graph
• Hashing
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
21
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
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
NIC# Name Address
6584495-9 Muhammad Faheem House No 3 Gulshan Bahar Sec 16
1748425-5 Naeem Alam A-11 Shams Plaza Block-B [Link]
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 [Link]. 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 [Link]
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 [Link]. 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 all those records together that start with similar
NIC (first digit) numbers, and 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 [Link]
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 [Link]. 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 Data Structure
• Maintain pointers with records
• Non NULL pointer indicates presence of next
record
NIC# Name Address
0 6584495-9
1748425-5
Muhammad Faheem
Naeem Alam
House No 3 Gulshan Bahar Sec 16
A-11 Shams Plaza Block-B [Link]
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 [Link]. 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 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)
• Data Structures Using C++ (By D.S. Malik)
Some topics will be covered from other books. Material will
be provided for these topics.
FAST, National University of Computer and Emerging Sciences, Islamabad