Introduction to Data Structures on C++ Language

Intro to Data Structure

1. Data Structures
CS-2001
Introduction

2. Guidelines
Be attentivein class and always expect a quiz
There will be no retake of any quiz/activity,
whatever circumstances are
Strictlyfollow your deadlines otherwise be
ready for penalties
Follow SLATE/Classrommand reportyour
query in time otherwise don’t complaint
2

3. Guidelines
There will be no re-evaluationfor any marks,
when report time is over
If you don’t want to study leavethe class, let
others study.
You will be given zero (negative marks)for
copy cases (Both parties)
3

4. Important
Classroom Conduct
All students are expected to behave as scholars at a
leading institute of technology. This includes arriving
on time, not talking during lecture (unless addressing
the instructor), and not leaving the classroom before
the end of the lecture.
Disruptive students will be warnedand potentially
dismissed from the classroom
Academic Dishonesty
Academic dishonesty in any portion of the academic
work for a course shall be grounds for awarding a
grade of F for the entire course
4

5. Some Rules
•Raise your hand before asking any question and then WAIT for
the permission
•Never ever Miss a class
•Never ever “sleep” in the class
•Never even think about using mobile during the class
5

6. Distribution (Tentative)
Assignments /
Home Work
5 % 3 to 5
Quizzes 5% 7 to 10
Sessional-I 15% 1
Sessional-II 15% 1
Project 10% 2 to 3 phases
Final 50% 1
Attendance 100%
Weight-ages
6

7. Assignment/Quizzes
•A number of assignments and quizzes will be taken
•Announced and/or unannounced quizzes may be
given to students any time during the lecture
7

8. Submissions
All submissions (Assignments, Home Works, Project)
would be on Slate/Classroom, unless otherwise
announced.
The file naming convention should be as:
Roll Number_Assignment_Number_Course
For example: 23_1234_Assignment_2_DS
8

9. Prerequisite
•Enforced
•CS1004ObjectOrientedProgramming
•CL1004ObjectOrientedProgramming
9

10. Why should we study this course?
•Well,becauseitisthecorecomputersciencescourse
•Anyotherreasontostudythiscourse?
•Wewanttomakeasuccessfulcareeraftergraduation
•Themostcommonprogramminginterviewsquestions
•Linkedlists
•Strings
•BinaryTrees
•Arrays
•Queues
Source: http://maxnoy.com/interviews.html
10

11. Course Objective
•Introducethebasicconceptsofdatastructures/ADTs,and
usethemefficientlyinalgorithmsforsolvingvarious
problemsusingC/C++
•Whatshouldyouexpectinthiscourse?
•Extensiveprogramming
•Alotofthinking
•Whatshouldyoulearnbytheendofthiscourse
•Abilitytounderstandcommonprogrammingproblemsanddesignand
implementefficientdatastructurestosolvethem
11

12. Books
•Data Structures
•Seymour Lipschutz
•Data Structures Using C and C++
•Y. Langsam, M. J. Augenstein, A. M.
Tenenbaum
12

13. Reference Books
•Introduction to Algorithms
•Thomas H. Cormenet al
•Data Structures and Algorithms
•A. V. Aho, J. E. Hopcroft, J. D. Ullman
13

14. Course Outline
•In this course you will learn
•Introduction
•Algorithm Analysis
•Abstract Data Types (ADTs)
•Lists
•Stacks
•Queues
•Trees
•Hashing
•Sorting
•Graph
14

15. What is a data structure exactly?
15

16. To answer that, we must first understand:
What is a computer program?
Input
Some mysterious
processing
Output
16

17. How to solve the following problems:
1. Input 3 numbers, print out the maximum.
2. Input 30000 numbers, print out the largest 10 numbers.
17

18. Data structures let the input and output be represented
in a way that can be handled efficientlyand effectively.
array
Linked list
tree
queue
stack
18

19. Input
Some mysterious
processing
Output
Data structures+Algorithms=Programs
19

20. Definition
•Data may be organized in different ways
•Data structure is the logical or mathematical
model of a particular organization of data
•Must be rich enough to mirror the actual
relationships of the data in the real world
sample
20

21. Thank you
21

22. Introduction-2

23. What is a Data Structure?
•Data structures are used in almost every program or
software system
•In computer sciences, a data structure is a particular way of storing and
organizing data in a computer so that it can be used efficiently
•Efficient data structures Efficient algorithms
•Focus:Efficiency and performance
•Time and space analysis of algorithms
Source: http://en.wikipedia.org/wiki/Data_structure
23

24. Performance vs Efficiency
•Performance is the measure of quality of the work done byany
machine.
•Efficiency is the ratio of desired outputto the required input for
anymachine.
24

25. Some Example Data Structures
Arrays Stack Tree
Data structure = representation and
operations associated with a data type
Linked List
25

26. Data Structure Applications
•Arrays
•Consecutive memory locations
•lists (one dimensional arrays)
•matrices (two dimensional arrays)
•database applications
•to implement other data structures, such as heaps, hash tables, queues,
stacks, strings
•Stacks
•expression evaluation and syntax parsing
•Queues
•scheduling
•transportation
•operations management
26

27. Data Structure Applications
•Trees
•efficient searching of data (Binary search tree)
•manipulate hierarchical data
•manipulate sorted data
•Linked lists
•can be used to implement several other common abstract data
structures, such as
•stacks
•queues
•symbolic expressions, and etc
27

28. Abstract data type
•Incomputerscience,anabstractdatatype(ADT)isamathematical
modelfordatatypes,whereadatatypeisdefinedbyitsbehavior
(semantics)fromthepointofviewofauserofthedata,specifically
intermsofpossiblevalues,possibleoperationsondataofthistype,
andthebehavioroftheseoperations
•ADTusersareNOTconcernedwithhowthetaskisdonebutrather
whatitcando.
•Anabstractdatatypeisadatadeclarationpackagedtogetherwith
theoperationsthataremeaningfulforthedatatype.
28

29. Arrays
1 Ali
2 Salam
3 Usman
4 Danial
5 Saeed
6 Zaka
Linear Arrays

30. Array
Ali
Salam A B C
Usman
Danial
Saeed Y
Zaka X
Ali Y
Salam X
Usman Y
Danial X
Saeed Y
X

31. Arrays
Sale
Item 1 2 8 85
Item 2 5 8 5
Item 3 5 8 5
Item 4 4 8 5
Item 5 5 5 5
Two Dimensional Arrays

32. Arrays
Customer Salesperson
1 Jamal Tony
2 Sana Tony
3 Saeed Nadia
4 Farooq Owais
5 Salman Owais
6 Danial Nadia

33. Link List
Jamal 1
Sana 1
Saeed 2
Farooq 3
Salman 3 Salman 3

34. Trees
Employee
Name
Age
First NLast N
Address Salary
Street Area
CityProvincePost Code
34

35. Trees
(2x+y)(a-7b)
3
*
+ ^
* y
2 x
- 3
a *
7 b
35

36. Stacks
2132
123
123
123
123
123
123
546
45
543
3
3
2544
IN
OUT

37. Queue
2132
123
123
123
123
123
3
3
2544
33
IN
OUT

38. The Need for Data Structures
•Goal: to organize data
•Criteria: to facilitate efficient
•storageof data
•retrievalof data
•manipulationof data
•Design Issue:
•select and designappropriate data types.
(This is the real essence of OOP.)
38

39. Data Structure Operations
•Update
•Searching
•Insertion
•Deletion
•Sorting
•Merging
Dictionary Operations
39

40. Thank you
40