Chapter 1 - Overview of Data Structure.pdf

SLIDE 1

Module Code & Module Title

Slide Title

FUNDAMENTAL CONCEPTS

CT077-3-2-DSTR & DATA STRUCTURES

SLIDE 2

Module Code & Module Title

Slide Title

TOPIC LEARNING OUTCOMES

At the end of this topic, you should be able to:
1. Understand the meaning of data structure.
2. Understand the fundamental aspects of an algorithm and its characteristics.
3. Understand the relationship between data , data structures, and algorithms.

SLIDE 3

Module Code & Module Title

Slide Title

• Introduction to Programming
• Introduction to Data Structures
• Types of Data Structures
• Introduction to Algorithms
• Relationship among data , data structures, and algorithms
• Measure of Efficiency

Contents & Structure

SLIDE 4

Module Code & Module Title

Slide Title

INTRODUCTION TO PROGRAMMING

Understand the program development life cycle

SLIDE 5

Module Code & Module Title

Slide Title

INTRODUCTION TO PROGRAMMING

A computer is a programmable data processor that
accepts input and instructions to process the input
(program) and generates the required output.

Sequence of instructions is known as a program.

A program that satisfies user needs as per his/her
specifications is called software.

The

physical

machinery

that

executes

these

instructions is known as hardware.

SLIDE 6

Module Code & Module Title

Slide Title

PROGRAM DEVELOPMENT LIFE CYCLE

1. Define the problem statement precisely.
2. Select the best suitable algorithm to

solve the problem.

3. Later the code is tested, debugged,

and revised, if required

SLIDE 7

Module Code & Module Title

Slide Title

INTRODUCTION TO DATA STRUCTURES

Understand the meaning of data structures

SLIDE 8

Module Code & Module Title

Slide Title

•Programming

requires

different

kinds

of

information to be stored in the computer and the
input data to be processed.

•The information can be stored in a generalized
format using variables.

•In principle, one variable allows the storage of a
single data entity.

•However, a set of single variables may not solve
complex problems efficiently.

•A data structure uses a collection of related
variables that can be accessed individually or as a
whole.

•In other words, a data structure represents a set of
data items with a specific relationship between
them.

INTRODUCTION TO DATA STRUCTUES

SLIDE 9

Module Code & Module Title

Slide Title

WHAT IS DATA STRUCTURES?

• “An organization of information, usually in memory, for

better algorithm efficiency” - NIST, 2004

• “Way in which data are stored for efficient search and

retrieval” – Encyclopedia Brittanica, 2014

• “A particular way of organizing data in a computer so

that it can be used effectively” - Geeks for Geeks, n.d.

SLIDE 10

Module Code & Module Title

Slide Title

Data Structure

Algorithm

a set of instruction to solve a class of problems or perform a computation

Data

Program

SLIDE 10

Module Code & Module Title

Slide Title

ATOMIC DATA VS COMPOSITE DATA

Atomic Data
• Data that we choose to consider as a single, non-decomposable entity.
• Example: integer number 1234 (a single integer value)
• Known as scalar data because of its numeric properties

Composite Data
• Can be broken down into subfields that have meaning.
• For example, a student’s record consists of Roll_Number, Name, Branch, Year, and so

on.

• Referred to as structured data and can be implemented using a structure or a class

in C++.

SLIDE 11

Module Code & Module Title

Slide Title

DATA TYPES

Data Type

Simple

Integral

char

short

int

long

bool

Floating

float

double

long double

Structured

Array

Struct

Union

Class

A data type is called simple if variables of that type can store only one value at a
time.
Simple types are also called: Primitive or Built-in Types.

SLIDE 12

Module Code & Module Title

Slide Title

DATA TYPES

Bool type is not supported by all C++ compilers
Can add “unsigned” modifier before char, short, int, and long, so that variables of
that type are positive always (maximum storable number gets doubled)

Simple Data Types

Integral

unsigned char

unsigned short

unsigned int

unsigned long

bool

Floating

float

double

long

double

SLIDE 13

Module Code & Module Title

Slide Title

DATA TYPES

Data Type

Simple

Integral

char

short

int

long

bool

Floating

float

double

long double

Structured

Array

Struct

Union

Class

A structured data type is one in which each data item is a collection of other data
items
Very similar to classes, but should be thought of as not having methods (just data
grouping)

SLIDE 14

Module Code & Module Title

Slide Title

A data structure is a collection of atomic and composite data
types into a set with defined relationships.

In brief, a data structure is…

•

A combination of elements, each of which is either as a
data type or another data structure and

•

A set of associations or relationships (structures) involving
the combined elements.

SLIDE 15

Module Code & Module Title

Slide Title

ABSTRACT DATA TYPES (ADT)

An ADT is the one in which the set of operations is
defined at a formal, logical
level, without being restricted by the operational details.

In other words, an ADT is a data declaration packaged
together with the operations that are meaningful for the
data type.

We encapsulate the data and the operations on this
data and hide them from the user.

In

brief,

an

ADT

includes

declaration

of

data,

implementation of operations, and encapsulation of data
and operations.

SLIDE 16

Module Code & Module Title

Slide Title

Consider the concept of a queue. At least
three data structures will support a queue.
We can use an array, a linked list, or a file.

If we place our queue in an ADT, users
should not be aware of the structure we
use.

As long as they can enqueue (insert) and
dequeue (retrieve) data, how we store the
data should make no difference.

UNDERSTAND THE MEANING OF ADT

SLIDE 21

Module Code & Module Title

Slide Title

• Data structure are normally divided into two broad categories:

– Primitive Data Structure

• The data structures, that are directly operated upon by machine level

instructions

– Non-Primitive Data Structure

• These are more complex data structures.
• These data structures are derived from the primitive data structures.
• The non-primitive data structures emphasize on structuring of a group of

homogeneous (same type) or heterogeneous (different type) data items.

Classifications of Data Structures

SLIDE 17

Module Code & Module Title

Slide Title

CLASSIFICATION OF DATA STRUCTURES

SLIDE 23

Module Code & Module Title

Slide Title

Classifications of Data Structures

Data Structure

Primitive Data

Structure

int

Char

Float

Double

Pointers

Non- Primitive
Data Structure

Arrays

Single

Dimension

Two Dimensions

Multi-

Dimensions

Lists

Linear

Stack

Queue

Linked-List

Non-Linear

Trees

Graphs

not defined by the

programming language, but
created by the programmer

(user defined)

predefined types of data (built in)

SLIDE 18

Module Code & Module Title

Slide Title

• Two type of data structures

–Linear data structure
–Non-linear data structure Linear data structures

Type of Data Structure

SLIDE 19

Module Code & Module Title

Slide Title

• In linear data structures, the elements are arranged in sequence one after the

other.

• Since elements are arranged order, they are easy to implement.
• However, when the complexity of the program increases, the linear data

structures might not be the best choice because of operational complexities
– Array
– Linked list
– Stack
– Queue

Linear Data Structure

SLIDE 20

Module Code & Module Title

Slide Title

Non-linear Data Structure

Non-linear data structures are not in any sequence.

Instead, they are arranged in a hierarchical manner where one element will be
connected to one or more elements.

Non-linear data structures are further
divided into graph and tree-based data
structures.

Graph

Tree

SLIDE 24

Module Code & Module Title

Slide Title

Characteristics of Data Structures

Correctness

• Data structure

implementation
should
implement its
interface
correctly.

Time Complexity

• Running time or

the execution
time of
operations of
data structure
must be as small
as possible.

Space Complexity

• Memory usage of

a data structure
operation should
be as little as
possible

SLIDE 18

Module Code & Module Title

Slide Title

INTRODUCTION TO ALGORITHMS

Understand the meaning of algorithms

SLIDE 19

Module Code & Module Title

Slide Title

WHAT IS ALGORITHMS?

• Clearly specified set of simple instructions to be

followed to solve a problem (Weiss, 2013).

• The steps to be carried out in order to accomplish

a particular task (Bhasin, 2015).

SLIDE 20

Module Code & Module Title

Slide Title

The real-world performance of any software depends
on:

1. the algorithm chosen and
2. the suitability and efficiency of various layers of implementation

SLIDE 21

Module Code & Module Title

Slide Title

Relationship Among Data , Data Structures, And
Algorithms

Analogy
Scenario :
In a movie theater, customers/patrons are given tickets with seat number.

Goal : Customers/patrons finding their seats in the movie hall.

​Imagine the seats in the movie hall are data.

Analysis :
1.Will they find their seat? - correctness
2.If yes, how long will it take? - efficiency

SLIDE 22

Module Code & Module Title

Slide Title

Case 1 : The seats in the movie hall are not numbered

Will the patrons find their seat? ​
No.

It is impossible to find.
How long will it take?

SLIDE 23

Module Code & Module Title

Slide Title

Case 2 : The seats are numbered. But the numbers are in random
order.

Will the patrons find their seat? ​
Yes.

Quite sometime as the patrons
need to check the seat one by
one.

How long will it take?

SLIDE 24

Module Code & Module Title

Slide Title

Case 3 : The seats are numbered. The numbers are in proper
sequence.

Will the patrons find their seat? ​
Yes.

Definite faster than case 2 since
the number are in order, there
patrons can expect the number
without checking the seat one-
by-one

How long will it take?

SLIDE 25

Module Code & Module Title

Slide Title

Case 4 : The seats are numbered based on row and seat.

Will the patrons find their seat? ​
Yes.

Faster than case 3 as patron
only need to check the seat of
specific row.

How long will it take?

SLIDE 26

Module Code & Module Title

Slide Title

HOW TO MEASURE EFFICIENCY?

•

Any process in computing requires 2 main resources, time and space.

•

Time: How long will it take to complete a process?

•

Space: How much memory space will this process use?

•

An optimum algorithm will should balance both time and space at
lowest possible value.

•

This is reflected by Big O complexity, O(n).

Home

Open in new tab

Copy link

SLIDE 27

Module Code & Module Title

Slide Title

EXAMPLE OF O(n)

SLIDE 28

Module Code & Module Title

Slide Title

Poll

So now, do you understand the importance of data structures and algorithms in the IT world?

• Yes, absolutely understand

• Should be understand

• Maybe

SLIDE 29

Module Code & Module Title

Slide Title

Best, Worst, and Average Cases

The best-case complexity of an algorithm is the function defined by the
minimum number of steps taken on any instance of size n.

The worst-case complexity of an algorithm is the function defined by the
maximum number of steps taken on any instance of size n.

The average case complexity of an algorithm is the function defined by an
average number of steps taken on any instance of size n.

Each of these complexities defines a numerical function — time versus size.

SLIDE 30

Module Code & Module Title

Slide Title

Review Questions

1. Define the terms data, data type, data structure, and abstract data type.

2. Explain the relationship between data structure and algorithm in the process of

problem solving with an example.

3. What is the formal definition of an algorithm?

SLIDE 31

Module Code & Module Title

Slide Title

We learnt brief information about:

• What is a data and data structure?

• What is an algorithm?

• The relationship between data, data structures and algorithms

• How to calculate the time complexity using Big-O-Notation?

Summary / Recap of Main Points

SLIDE 32

Module Code & Module Title

Slide Title

In Class
• Functions
• Arrays

Preparation for Class
• Understand the fundamental concept

of Functions

• Understand the fundamental concept

of Arrays

What To Expect Next Week