CSC 211

Data Structures
Lecture 1
Dr. Iftikhar Azim Niaz
[email protected]

Dr. Iftikhar Azim Niaz

B.Sc (Maritime Studies) 1988

M.Sc (Computer Science) 1994

Allama Iqbal Open University

Ph.D (Software Engineering) 2005

Quaid-i-Azam University

MBA (Marketing) 1999

Pakistan Marine Academy,

Presidents Gold Medalist
Karachi University

University of Tsukuba, Japan

PGD (Professional Ethics and Teaching

Methodology) 2010

Riphah International University

2

Dr. Iftikhar Azim Niaz

Deck Officer

Sep 1995 Jan 2007

Quaid-i-Azam University

Head of Department

National Institute of Electronics

Lecturer

Deutsche Telepost Consultants, Islamabad

Deputy Manager Apr 1995 Aug 1995

Atlas Shipmanagement Limited, Hong Kong

System Analyst Mar 1994 Mar 1995

Feb 1989 Feb 1991

Jan 2007 Feb 2012

Riphah International University

Assistant Professor Feb 2012 to Date

COMSATS Institute of Information Technology

Islamabad Campus
3

Why?
Why are you
studying Data
Structure and
Computer
Science ?

Are these your Motivations?

Motivations is a feeling of enthusiasm,

interest, or commitment that makes
somebody want to do something, or
something that causes such a feeling

Encarta Dictionary

Because many people take it

Just a random choice, no particular reasons
A required course
I failed CSC211 before;
Want to be taught by a tough instructor
More
5

I believe your REAL motivation

is ...
I take it because I
am interested

Course Details

Course Code:

CSC 211

Course Title:

Data Structures

Credit Hours:
3+1
Course Prerequisites CSC141
Course Objectives:
The course is designed to teach students
structures and schemes, which allow them
to write programs to efficiently manipulate,
store, and retrieve data.

Course Description

In recent years the subject of computer programming

has been recognized as a discipline whose mastery is
fundamental and crucial to the success of many
engineering projects and which is amenable to
scientific treatment and presentation.
It has advanced from a craft to an academic discipline
it is abundantly clear that a systematic and scientific
approach to program construction primarily has a
bearing in the case of large, complex programs which
involve complicated sets of data.
Hence, a methodology of programming is also bound
to include all aspects of data structuring.
8

Course Objectives

To extend and deepen the student's knowledge

and understanding of algorithms and data
structures and the associated design and
analysis techniques
To examine previously studied algorithms and
data structures more rigorously and introduce the
student to "new" algorithms and data structures.
It focuses the student's attention on the design of
program structures that are correct, efficient in
both time and space utilization, and defined in
terms of appropriate abstractions.
9

Course Goals

Upon completion of this course, a successful student

will be able to:

Describe the strengths and limitations of linear data

structures, trees, graphs, and hash tables
Select appropriate data structures for a specied problem
Compare and contrast the basic data structures used in
Computer Science: lists, stacks, queues, trees and graphs
Describe classic sorting techniques
Recognize when and how to use the following data
structures: arrays, linked lists, stacks, queues and binary
trees.
Identify and implement the basic operations for
manipulating each type of data structure
10

Course Goals

Upon completion of this course, a successful

student will be able to:

Perform sequential searching, binary searching and hashing

algorithms.
Apply various sorting algorithms including bubble, insertion,
selection and quick sort.
Understand recursion and be able to give examples of its
use
Use dynamic data structures
Know the standard Abstract Data Types, and their
implementations
Students will be introduced to (and will have a basic
understanding of) issues and techniques for the assessment
of the correctness and efficiency of programs.
11

Course Outline - I

Introduction to data structures

Linear and non-linear data structures
Arrays and pointers
List data structure
Singly linked list
Doubly linked list
Analysis of List data structures
Circular linked list
Stack; Implementation of stack using arrays and
linked list
Applications of a stack
12

Course Outline - II

Infix to postfix conversion

Evaluation of postfix expressions
Queues; Implementation of queues using arrays
and linked list
Circular Queues; Priority Queues;
Trees; Tree traversals; Binary search trees and
implementation
Heaps and Heap sort;
Graphs; Minimum spanning trees;
Hashing
Files
13

Recommended Books
Textbooks:

R. Kruse, C.L. Tondo, B. Leung Data Structures & Program

Design in C, 2nd Edition, Pearson Education Inc. India , 2007

Mark A. Weiss, Data Structures and Algorithm Analysis in C,

2nd Edition, Pearson Education Inc. India, 1997 .

Reference Books:

Debasis Samanta, Classic Data Structures, 2nd Edition,

Prentice Hall India, 2009

ISRD Group, Data Structures Using C, Tata McGraw-Hill

Publishing Company, New Delhi, India, 2006.
14

Recommended Text Books

15

Recommended Text Book

16

Marks Distribution of Course

Assignments .

15%

Quizzes

10%

Sessionals
25%

Final

....

....

. 50%

17

A Nice Quote
Want to get something in life
Always think positive
You will definitely get the thing you want

18

A nice saying
I keep 6 honest serving men.
They taught me all I knew.
Their names are:
WHAT and WHY and WHEN and HOW and WHERE
and WHO.
(R. Kipling)

And believe me,

on the road of learning,
these are your best companions.

19

Five Tips to Success

Work Hard

Try More
exercises and
more practice

Do the Labs and

assignments by
yourself

20

Five Tips

Be patient with the

Machine

If you really need

that, do it quietly

21

Is the same situation is with

you?
yes
No

22

Boss assigns task

To perform certain task?

How u will do?

23

Your Question:

Um? Tell me what to code.

24

So your answer:

I can develop a new algorithm for you.

Great thinkers
will always be needed.

25

Study:

Many experienced programmers were asked to

code up binary search.

80% got it wrong

Good thing is was not for a
nuclear power plant.

26

What did they lack?

Fundamental understanding of the

algorithmic design techniques.

27

Programming is Problem
Solving
Programming is a process of problem solving

Problem solving techniques

Analyze the problem

Outline the problem requirements
Specify what the solution should do
Design steps, called an algorithm, to solve the
problem (the general solution)
Verify that your solution really solves the problem

Algorithm a step-by-step problem-solving

process in which a solution is arrived at in a
finite amount of time
28

Computer Programming

Nicklaus Wirth

Program = Algorithm + Data Structure

Computer programming involves writing software

that allows a machine to perform various tasks
which, by hand, would be tedious or so time
consuming as to be essentially impossible to do.
Machines work incredibly quickly, never get tired,
and are excellent at following orders; however, they
will only perform as well as the instructions
presented to them.
Set of instructions that tell the computer what to do
and how to do?
29

Introduction to Problem
Solving
Programming is a problem solving activity.

When you write a program, you are actually

writing an instruction for the computer to solve
something for you.
Problem solving is the process of transforming
the description of a problem into a solution by
using our knowledge of the problem domain
and by relying on our ability to select and use
appropriate problem-solving strategies,
techniques and tools.
30

Case Study: Yummy Cupcake

Problem: You are required to calculate the

amount to be paid by a customer buying
cupcakes.

31

Software Development Method (SDM)

For programmer, we solve problems

using Software Development Method
(SDM), which is as follows:
1.
2.
3.
4.
5.
6.

Specify the problem requirements.

Analyze the problem.
Design the algorithm to solve the problem.
Implement the algorithm.
Test and verify the completed program.
Documentation

32

1. Requirement Specification

Specifying the problem requirements

requires you to state the problem clearly
and to gain the understanding of what to
be solved and what would be the solution.
When specifying problem requirement, we
ask ourselves the following questions:

What the problem is.

What the solution should provide.
What is needed to solve it.
If there are constraints and special conditions.
33

Yummy Cupcake
Problem: You are required to calculate the amount to be
paid by a customer buying cupcakes.

What the problem is.

What the solution should provide.

What is needed to solve it.

If there are constraints and special conditions.

34

Problem Analysis

Analyzing the problem require us to

identify the following:

Input(s) to the problem, their form and the input

media to be used
Output(s) expected from the problem, their
form and the output media to be used
Special constraints or conditions (if any)
Any formulas or equations to be used

35

Yummy Cupcake

Input?
Quantity of the cupcake purchased (integer)
Price per cupcake (RM, float)

Output?
Total amount to be paid by the customer (RM, float)

Constraint/condition?
Quantity purchased must be more than zero
Price per cupcake must be more than zero (it is not free)
We assume that the price given is the standard price to all
cupcakes

Formula/equation?

Amount to pay = quantity of cupcake x price per cupcake

36

Designing algorithm

Designing algorithm to solve the problem

requires you to develop a list of steps,
arranged in a specific logical order which,
when executed, produces the solution for a
problem.
Using top-down design (also called divide and
conquer):

You first list down the major tasks

For each major task, you further divide it into subtasks (refinement step)

When you write algorithm, write it from the

computers point of view.

37

Designing Algorithm cont..

An algorithm must satisfy these requirements:

It may have an input(s)

It must have an output(s)
It should not be ambiguous (there should not be
different interpretations to it. Every step in algorithm
must be clear as what it is supposed to do)
It must be general (it can be used for different
inputs)
It must be correct and it must solve the problem for
which it is designed
It must execute and terminate in a finite amount of
time
It must be efficient enough so that it can solve the
intended problem using the resource currently
available on the computer
38

Yummy Cupcake
Major Task:
1.
Read the quantity of cupcake purchased
2.
Read the price per cupcake
3.
Calculate total amount to pay
4.
Display the total amount to pay
However, looking at the above algorithm, we can still further refine
step 3, by introducing the formula to calculate the amount to pay.
After refinement:
5.
Read the quantity of cupcake purchased
6.
Read the price per cupcake
7.
Total amount to pay = quantity of cupcake x price per cupcake
8.
Display the total amount to pay

39

Remember, the order of the steps in

algorithm is very important. Consider the
following, will the result be the same?
1.

2.

3.

Display the total amount to

pay
Get the quantity of cupcake
purchased
Total amount to pay = quantity
of cupcake x price per cupcake
40

Control Structure

An algorithm can be represented using

Pseudocode or Flowchart.
In 1966, two researchers, C. Bohn and G.
Jacopini, demonstrated that any algorithm
can be described using only 3 control
structures: sequence, selection and
repetition.

41

Control Structure

Sequence: A series of steps or

statements that are executed in the
order they are written in an algorithm.
Selection: Defines two courses of action
depending on the outcome of a condition.
A condition is an expression that is, when
computed, evaluated to either true or
false.
Repetition: Specifies a block of one or
more statements that are repeatedly
executed until a condition is satisfied.
42

What is an Algorithm?
There are two parts to a computer
program.
There is the process or sequence of
steps which are necessary to
complete the given task and
the translation of this process into a
language which the computer can
understand.

43

Algorithm (Definition)

An algorithm refers to a step-by-step method

for performing some action.
A precisely defined sequence of (computational
steps) that transform a given input into a
desired output.
An algorithm tells us how to perform a task.
The logical steps to solve a problem.
Some examples of algorithms in everyday life
are food preparation, directions for assembling
equipment or instructions for filling out income
tax forms.
44

Criteria for Algorithm

Input: Zero or more quantities are externally

supplied
Output: At least one desired result is produced
Definiteness: Each instruction must be clear
and unambiguous
Finiteness: Algorithm terminates after a finite
number of steps
Effectiveness: Each instruction must be
feasible and very basic

45

From Algorithms to
Programs
Problem

Algorithm: A sequence
of instructions describing
how to do a task

Computer Program
46

Algorithm Representation

Pseudocode

Algorithm

Flow Chart

47

What is Pseudocode?

Traditionally, flowcharts were used to represent the

steps in an algorithm diagrammatically. These were
bulky, difficult to draw and often led to poor
program structure.
Pseudocode is the method of writing down an
algorithm.
Pseudocode is easy to read and write. It represents
the statements of an algorithm in English like
language.
Pseudocode is really structured English. It is
English which has been formalised and abbreviated
to look like very high level computer languages.
48

Pseudocodes

A pseudocode is a semiformal, Englishlike language with limited vocabulary

that can be used to design and describe
algorithms.

Criteria of a good pseudocode:

Easy to understand, precise and clear

Gives the correct solution in all cases
Eventually ends
49

Example of Pseudocode
1. Open freezer door
2. Take out Meal
3. Close freezer door
4. Open microwave door
5. Put Meal on carousel
6. Shut microwave door
7. Set microwave on high for 5 minutes
8. Start microwave
9. Wait 5 minutes
10. Open microwave door
11. Remove Meal
12. Close microwave door
50

Example of Algorithm
procedure Do_Thursday
{
Wake_up ;
Take_A_Shower ;
Eat_Breakfast ;
Drive_To_university ;
Attend_ALGO_Lecture ;
...etc...etc...etc...
Drive_From_university ;
...etc...etc...etc...
}

procedure Do_Week
{
Do_Monday ;
Do_Tuesday ;
Do_Thursday ;
...etc...etc...etc...
}

51

Pseudocode

Pseudocode = English + Code

relaxed syntax that
extended version of the
is easy to read
basic control structures
(sequential, conditional,
iterative)

52

Pseudocode Rules

There is currently no standard pseudocode.

There are however certain conventions:
Statements are written in simple English;
Each instruction is written on a separate line;
Logic-showing Keywords are written in UPPER
CASE
(e.g. IF , THEN, FOR, WHILE )
Each set of instructions is written from top to
bottom with only one entry and one exit;
Groups of statements may be formed into
modules, and that group given a name.
53

Pseudocode

The following conventions are usually used.

The symbol is used to indicate that the
reminder of a line should be treated as a
comment. If more than one statement appears on
a single line, a semicolon will be used to separate
them.
ASSIGNMENT STATEMENTS have the form x
e, which assigns the value of expression e to
variable x. Multiple assignments can be
performed in one statement; for example,
x
y e assigns the value of e to variables x
and y.
54

Pseudocode

Another way do this as follows:

x := e
where x is a variable and e is an expression.
When an assignment statement is executed,

the expression e is evaluated (using the current

values of all variables in the expression), and
then its value is placed in the memory location
corresponding to x (replacing any previous contents
of this location) .

55

Transposing Two Values Example

Find an algorithm that takes two values x and y

as inputs. The input values are, then,

interchanged to obtain the output.
Method: If we try
x := y
y :=x
We would not obtain the desired output. Step 1
correctly changed x but the original value of x
was lost. Step 2 has no effect on the value of y.
To obtain the desired results, we must save the
original value of x.
56

Transposing Two Values To

obtain the desired results, we must save
Example

1.
2.
3.
4.
5.

the original value of x. This is done by

assigning the value of x to a new variable
called Save.
Input x, y
[Input the values]
Save := x [Storing the original x]
x := y
[Part of the output]
y := Save [The original x value]
Output x, y
[Values Transposed]
57

Flowcharts

Flowcharts is a graph used to depict or

show a step by step solution using symbols
which represent a task.

The symbols used consist of geometrical

shapes that are connected by flow lines.

It is an alternative to pseudocoding;
whereas a pseudocode description is
verbal, a flowchart is graphical in nature.
58

Flowchart Symbols
Terminal symbol - indicates the beginning and
end points of an algorithm.
Process symbol - shows an instruction other than
input, output or selection.
Input-output symbol - shows an input or an
output operation.
Disk storage I/O symbol - indicates input
from or output to disk storage.
Printer output symbol - shows hardcopy printer
output.
59

Flowchart Symbols cont

Selection symbol - shows a selection
process for two-way selection.
Off-page connector provides continuation of
a logical path on another page.
On-page connector - provides continuation
of logical path at another point in the same
page.
Flow lines - indicate the logical sequence of
execution steps in the algorithm.

60

The Sequence control

A series of steps or statements that are executed in the
structure
order they are written in an algorithm.

The beginning and end of a block of statements can be

optionally marked with the keywords begin and end.
begin
statement 1.
statement 2.

statement n.
end

begi
n

statement 1
statement 2

statement n
end

61

The Sequence control

structure
Problem:
calculate a persons age
Begin
read birth year
age = current year birth year
display age
End

begi
n

read birth year

Age = current
year birth year
Display age
end

62

The Selection control

Defines two courses of action depending on the
structure
outcome of a condition. A condition is an expression

that is, when computed, evaluated to either true or

false.
The keyword used are if and else.
Format:
if (condition)
then-part
else
else-part
end_if

No

elsestatement(s)

Condition?

Yes

thenstatement(s)

63

The Selection control

Beginstructure
read age
if (age is greater than 55)
print Pencen
else
print Kerja lagi
end_if
End
Begin
read age
if (age > 55)
print Pencen
else
print Kerja lagi
end_if
End

Begin

Read age

YES

age > 55?

NO

print Kerja lagi

print Pencen

End

64

Pseudocodes: The Selection

Sometimes
in certain situation, we may omit the else-part.
control
structure

if (number is odd number)

print This is an odd number
end_if

Example 1

Nested selection structure: basic selection structure that

contains other if/else structure in its then-part or else-part.
if (number is equal to 1)
print One
else if (number is equal to 2)
print Two
else if (number is equal to 3)
print Three
else
print Other
end_if

Example 2

65

Exercise
Draw the flowchart diagram for
Example 1 and Example 2

66

The Repetition control

Specifies a block of one or more
structure

statements that are repeatedly executed

until a condition is satisfied.
The keyword used is while.
Format:
while (condition)
loop-body
end_while

Condition?

yes

Loop
Statement(s)

no

67

Problem: Write a program that reads and displays

the age of 10 people (one after another).
For this problem, we need a way to count how many people
whose age have been processed (read and displayed).
Therefore, we introduce a concept of counter, a variable
used to count the number of people whose age have been
processed by the program.

68

Counter initialisation

Begin
number of users giving his age = 1
while (number of users giving his age <= 10)
read the age from the user.
Loop condition
print the user age.
number of user giving his age + 1
Updating counter
end_while
End
Begin
users = 1
while (users <= 10)
read age
print age.
users = users + 1
end_while
End
69

Begin

users = 1

NO
End

users <= 10?

YES
read age

print age

users =users + 1

70

Subsequently..
You can start the
counter with ZERO

Begin
number of users giving his age = 0
while (number of users giving his age < 10)
read the age from the user.
print the user age.
The loop condition
must less than the
number of user giving his age + 1
value it requires to
end_while
stop
End
Begin
users = 0
while (users < 10)
read age
print age.
users = users + 1
end_while
End

Be
consiste
nt

71

Little extra

Now let us put together everything that you

have learnt so far.
Problem:
Write a program that will calculate and print the
age of 10 persons, given their birth year. If the
age of the person is above 55, then the
program will print Pencen, otherwise, the
program will print Kerja lagi.

72

Begin
Example 3
users = 1
while (users <= 10)
begin
Read birth year
age = current year birth year
Note that in this
print age
example, we are
if age > 55
using all the
print Pencen
three control
else
structures:
print Kerja lagi
sequence,
end_if
selection and
users = users + 1
repetition
end
end_while
End

73

Exercise
Draw the flowchart diagram for
Example 3

74

Implementation

The process of implementing an algorithm by

writing a computer program using a programming
language (for example, using C language)

The output of the program must be the solution

of the intended problem

The program must not do anything that it is not

supposed to do
(Think of those many viruses, buffer overflows, trojan
horses, etc. that we experience almost daily. All these
result from programs doing more than they were
intended to do)

75

Testing and Verification

Program testing is the process of

executing a program to demonstrate its
correctness

Program verification is the process of

ensuring that a program meets userrequirement

After the program is compiled, we must

execute the program and test/verify it with
different inputs before the program can be
released to the public or other users (or to
the instructor of this class)

76

Documentation

Writing description that explain what the

program does.

Can be done in 2 ways:

Writing comments between the line of codes
Creating a separate text file to explain the
program

Important not only for other people to use or

modify your program, but also for you to
understand your own program after a long time
(believe me, you will forget the details of your
own program after some time ...)
77

Documentation cont

Documentation is so important because:

You may return to this program in future to use the

whole of or a part of it again
Other programmer or end user will need some
information about your program for reference or
maintenance
You may someday have to modify the program, or may
discover some errors or weaknesses in your program

Although documentation is listed as the last

stage of software development method, it is
actually an ongoing process which should be
done from the very beginning of the software
development process.
78

Exercise time!!!

79

Volume calculation
Write a pseudocode and a flowchart for a
C program that reads the value of height,
width and length of a box from the user
and prints its volume.

80

Calculating Electricity Bills

The unit for electricity usage is kWh. For
domestic usage, the monthly rate is 21.8
cents/unit for the first 200 unit, 25.8 cents/unit
for the next 800 units and 27.8 cents/unit for
each additional units. Given the amount of
electricity units (in kWh) used by a customer,
calculate the amount of money needs to be
paid by the customer to TNB. A bill statement
needs to be printed out.
Write a pseudocode or a flow chart to solve
the above problem.
81

Sum of 1 to 10
Write a pseudocode or flowchart for a
program that would compute and print the
sum of all integers between 1 and 10.

82

Summary

Course Description, Goals and Contents

Introduced the concept of problem
solving : a process of transforming the
description of a problem into a solution.

A commonly used method SDM which

consists of 6 steps

3 basic control structures : sequence,

selection and repetition structures

Pseudocode and Flow chart

83