Algorithms and Data Structure
Lecture 1
Please turnoff your
cell phone.
Why are you taking
Algorithm and Data
Structure Course???
I believe your REAL motivation is ...
I take it because I
am interested
Concepts to be covered
The course is divided roughly into 4 parts
1st Review of basic programming
And a Quiz on the topic
2nd Searching and Sorting
Different techniques of searching and sorting
3rd Memory manipulation Stacks, Queues and Linked List
Pointers and memory address space
Dynamic memory allocation
Abstract data types
4th Trees, Graph and Heap
Uses of trees in Computer Science, Heap as priority queue and
shortest path finding algorithms using graph.
Course Outline
Detailed Course Outline is on the CSC-112
homepage
http://groups.yahoo.com/group/BTE-5A
Check your email often for announcements
related to the course
Resources
Recommended Book:
C++ Plus Data Structures by Nell Dale 5th Edition
Resources
Reference Books:
Data Structure & Problem Design in C++, Robert Kruse /
C.L.Tondo, Bruce Leung
Data structures through C in depth by S.K. Srivastava and
Deepali Srivastava
Data Structure through “C” Language by Sameeran
Chattopadhyay, Matangini Chottopadhyay, BPB Publications
Data Structure Using C and C++ by Yedidyah Langsam,
Aaron.Tanenbaum Moshe J.Augenstein
Mastering Algorithms with C by Kyle Loudon
Data Structure and Algorithm Analysis in C by Mark Allen
Weises
Data Structures Demystified by Jim Keogh and Ken
Davidson
Five Tips to Success
Work hard
Try more exercises and more
practice
Do the labs and assignments
yourself
Be patient with the machine
If you really need that, do it quietly
...
But not in Class. What
you have to do is just
inform me about your
situation and I will not
mark your absent.
Course Policy
The 5-minute rule
Assignments
Applicable rules and submission
deadlines will be indicated with the
assignments
No make-ups
Quizzes
10-15 minutes duration
Will cover reading assignments and
material covered in the class
Unannounced
No make-ups
Tutorials/Lab Sessions
Supervised Lab Sessions and Tutorials
will be organized as and when required.
Class Questions
I will ask questions very often
So be attentive
Marks Break up
Labs 15%
Assignments 2%
Quiz 8%
1st Sessional 10%
2nd Sessional 15%
Final 50%
Is the same situation is with you?
yes
No
Boss assigns task
To perform certain task?
How u will do?
Your Question:
Um? Tell me what to code.
So your answer:
I can develop a new algorithm for you.
Great thinkers
will always be needed.
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.
What did they lack?
Fundamental understanding of the
algorithmic design techniques.
Computer Programming?
1. 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.
2. 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.
3. Set of instructions that tell the computer what to do and
how to do?
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.
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.
An algorithm is correct if, for any input instance, it
provides the correct answer.
Some examples of algorithms in everyday life are food
preparation, directions for assembling equipment or
instructions for filling out income tax forms.
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
From Algorithms to Programs
Problem Algorithm:
Algorithm A sequence
of instructions describing
how to do a task
Computer Program
Algorithm Representations
There are two ways to
represent an Algorithm.
They are:
1-Pseudo Code
2-Flow Chart
Algorithm
Pseudocode Flow Chart
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.
Pseudocode is really structured English. It is English
which has been formalised and abbreviated to look like
very high level computer languages.
Example
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
Algorithm to multiply two numbers
Ever you Revisited to your primary
school after leaving it?
2X2=5
Example
procedure Do_Thursday procedure Do_Week
{ {
Wake_up ;
Take_A_Shower ; Do_Monday ;
Eat_Breakfast ; Do_Tuesday ;
Drive_To_university ; Do_Thursday ;
Attend_ALGO_Lecture ; ...etc...etc...etc...
...etc...etc...etc... }
Drive_From_university ;
...etc...etc...etc...
}
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.
PSEUDOCODE
Pseudo code basically consists of keywords and English-
like phrases that are intended to indicate flow of
control. The following conventions are usually used.
1. 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.
2. 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.
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) .
Transposing Two Values – Example
Example: Transposing Two Values.
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.
Transposing Two Values – Example
To obtain the desired results, we must save the
original value of x. This is done by assigning
the value of x to a new variable called Save.
1. Input x, y [Input the values]
2. Save := x [Storing the original x]
3. x := y [Part of the output]
4. y := Save [The original x value]
5. Output x, y [Values Transposed]
Comparison of an Assignment & an
Equality
Suppose x has been assigned the value 3, and y the value 4,
then the statement
x := x + y
will simply reassign to x the value of 7.
whereas x=x+y
is simply false in this case. By algebra, of course, it is only true
when y = 0.
Similarly, the command
x := x + 1
Increase the value of x by 1. The statement, however,
x=x+1
` is always false.
PSEUDOCODE
3. Ordinarily, algorithm statements are executed one
after another in the order in which they are written.
CONDITIONAL STATEMENTS allow this natural order to
be overridden by using the current value of program
variables to determine which algorithm statement will be
executed next. Condition statements are denoted either as
if (condition) if (condition)
then s1 OR then s1
else s2
where condition is predicate involving algorithm variables
and where s1 and s2 are algorithm statements or groups
of algorithm statements. When ambiguity is possible,
however, we may explicitly bind a group of statements
together into a unit by preceding the group with the
word do and following it with the words end do.
EXAMPLE
Execution of if-then-else and if-then Statements.
Consider the following statements:
a. IF x > 2 b. y := 0
then y: = x+1 IF x >2
else do x:= x-1 then y := 25
y := 3 * X end do End IF
End IF
What is the value of y after execution of these statements for the
following values of x?
i. x =5 ii. x =2
EXAMPLE
Execution of if-then-else and if-then Statements.
SOLUTION
a. (i) Because the value of x is 5 before execution, the guard
condition x > 2 is true at the time it is evaluated. Hence
the statement following then is executed, and so the value
of x + 1 = 5 + 1 is computed and placed in the storage
location corresponding to y. So after execution, y = 6.
(ii) Because the value of x is 2 before execution, the
condition x >2 is false at the time it is evaluated. Hence
the statement following else is executed. The value of x
– 1 = 2 -1 is computed and place in the storage location
corresponding to x, and the value of 3*x is computed and
place in the storage location corresponding to y.
EXAMPLE
Execution of if-then-else and if-then Statements.
b. (i) Since x = 5 initially, the condition x > 2 is true at
the time it evaluated. So the statement following then
is executed, and y obtains the value 25 = 32.
(ii) Since x = 2 initially, the condition x > 2 is false at
the time it is evaluated. Execution, therefore, moves to
next statement following the if-then statement, and
the value of y does not change from its initial value of
0.
How to represent using Flow Chart?
Generally uses only four constructs:
Start/End specified by a circle,
Commands in a rectangle,
Decisions in diamonds, with only a Yes or No
answer,
and flow arrows indicating the next step to
follow. Pointing backwards may indicate a loop.
Lets see a sight of Flow Chart
How to represent using Flow Chart?
(Contd.)
The Oval.
This sign represents a limitation.
It shows where the program starts, and where it ends.
Start END
How to represent using Flow Chart? (Contd.)
A PARALLELOGRAM
This sign represents an Input or an Output.
READ PRINT
How to represent using Flow Chart?
A RECTANGLE.
S=a+b
NOTE: You must never write for example "a + b = s"!
How to represent using Flow Chart?
A SQUARE / DIAMOND BOX
yes
condition
No
This represents a condition.
Inside we write the condition, and if that condition is true,
then the flow branches to “YES” else to “NO”.
NOTE: This sign must always have two exits: "YES", if the
condition is fulfilled and "NO", if the condition is not
fulfilled.
How to represent using Flow Chart?
Arrows
These are the connectors.
They connect various blocks in a Flow Chart.
Flow Chart
Algorithms are more easily understood if they mainly
use self-contained modules and
1-Sequence logic or Sequential flow
2-Selection logic or Conditional flow
3-Iterative logic or Repetitive flow
Sequence logic (Sequential flow)
Sequence logic are executed in the obvious
sequence. The sequence may be presented
explicitly, by means of numbered steps, or
implicitly , by the order in which the module are
written.
Module A
Module B
Module C
Selection Logic (Conditional Flow)
Selection logic employs a number of conditions which lead to a
selection of one out of several alternative modules. The
structures which implement this logic are called selection
structures.
These selection structures fall into three types.
Single selection ( If structure )
Double selection ( If/else structure)
Multiple selection ( Switch structure )
Selection Logic (Conditional Flow)
Single selection:
The logic of this structure is, If the condition holds, then
Module A , which may consist of one or more statements is
executed ; otherwise Module A is skipped and control
transfers to the next step of the algorithm.
Selection Logic (Conditional Flow)
Single Selection:
No
Condition ?
Yes
Module A
Selection Logic (Conditional Flow)
Double selection:
No
Condition ?
Yes
Module A Module B
PSEUDOCODE – Execution of if-
then-else
Multiple selection :
T
Break
F
T
Break
F
..
.
T
Break
F
Iterative Logic (Repetitive Flow)
The third kind of logic refers to either of two types of structures
involving loops. Each type begins with a repeat statement
and is followed by a module ,called the body of the loop.
1- While structure
2- For Structure
Iterative Logic (Repetitive Flow)
While Structure :
No
Condition ?
Yes
Module
(body of loop)
Iterative Logic (Repetitive Flow)
For Structure :
KR
NO
Is K > S ?
YES
Module
(body of loop)
KK+T
Example – Add two numbers, calculate &
print the sum.
A Flow Chart
Start
READ a, b
S := a + b
Print S
End
Example-Find location and Max value
of Data (Using If structure )
Step 1. [Initialize] Set K:=0,Loc:=0 and Max:=Data[0]
Step 2. [Increment counter] Set K:=K+1
Step 3. [Test counter] If K > N, then
Write : Loc , Max ,and Exit
Step 4.[Compare and Update] If Max < Data[K] then
Set Loc:=K and Max:=Data[K]
Step 5 . [Repeat loop] Go to step 2
Flow Chart
Start
K1,Loc 1
Max Data[1]
K K+1
Yes
Is K > N Write: LOC, MAX
No
Stop
No
Is Max < Data[K]
Yes
LOC K
MAX DATA [K]
Write an algorithm to find out the largest number
from a given set of three numbers
1 Start
2 Input Three Numbers A,B & c
3 If A > B then
If A > C then [ nested if structure]
Print “ A is greater “
Else
Print “C is greater “
End If
Else
If B > C
Print “ B is greater “
Else
Print “ C is greater “
End if
End if
4. Exit
of the digits of an integer entered by
the user.
Step 1.[Initialize] Sum:=0
Step 2.Input the number N
Step 3.While ( N!= 0)
Sum:=Sum + N mod 10
N:= N div 10
End While
Step 4. Write Sum
Flow Chart
Start
Read N
sum := 0
No
N != 0
Yes
sum := sum + N mod 10
N = N div 10
End
Comparing of two numbers (using If
Structure)
Step 1. Input two Numbers num1 , num2
Step 2. If ( num1 == num2 )
Write “ num1 is equal to num2”
Step 3. If ( num1 != num2 )
Write “ num1 is not equal to num2”
Step 4. If ( num1 < num2 )
Write “ num1 is less than num2”
Step 5. If ( num1 > num2 )
Write “ num1 is greater than num2”
Step 6. If ( num1 <= num2 )
Write “ num1 is greater than or equal to num2”
Step 7. If ( num1 >= num2 )
Write “ num1 is greater than or equal to num2”
Flow Diagram
Start
Read num1,num2
num1==num2 Write”num1 equal num2
Yes
No
Yes
Write”num1 equal num2
Num1!=num2
No
Yes Write”num1 is less num2
num1< num2
No
Yes
Num1>num2 Write”num1 is greater num2
No
Yes
Num1<=num2 Write”num1 less or equal num2
No
Yes
Num1>= num2 Write”num1 is greater or equal num2
No
End
Write an algorithm that display the
sum
Step 1.[Initialize] Sum:=0
Step 2.Repeat For number:=2 To 100 BY Increment 2
Step 3. Sum:= Sum + number
End For
Step 4.Write Sum
Flow Diagram
Start
Sum:=0
number:=2
No
number<=100
Yes
Sum:=Sum+number
number:=number+2
Write" Sum”
End
Tracing an algorithm
The current values of algorithm variables at various
points during execution can be known by tracing the
algorithm with a table called Trace Table
Trace Table
Problem: Determine the value of the variable x and y
after the following algorithm is executed
Pseudocode:
1. x := 5
2. Y := 7
3. If x = 5 then y:= 8
else y:= 0
endif
4. if y:= 7 then
1. x := 6
else
2. x := 3
3. if x = y then y := 0
endif
endif
… Continued
Step X y
No.
1 5 -
2 5 7
3 5 8
4.1 5 8
4.2 3 8
4.3 3 8
Trace table for algorithm
Data Structures and Algorithms
Algorithm
Outline, the essence of a computational procedure,
step-by-step instructions
Program
– an implementation of an algorithm in some
programming language
Data structure
An Organization of data needed to solve the problem
Overall Picture
Data Structure and
Algorithm Design Goals
Correctness
Efficiency
Read Ahead
You are expected to read the lecture notes
before the lecture.
This will facilitate more productive
discussion during class.
Explaining
The best way of
studying is to read the
material over and
over.
Be Creative
Ask questions.
Guess the algorithms for solving a
problem.
Assignment # 1
Note: Write algorithm, draw their trace tables and
flowchart for each of the followings:
Algorithm 1: An algorithm that takes a number as input,
then gives an output saying whether the number is odd or
even.
Algorithm 2: Similar to algorithm 1), but the process is
repeated for n times.
Algorithm 3: An algorithm that takes number between 1 and
20 as input. Up to three chances should be given, and
greatest of the three numbers as output.
Continued … Assignment # 1
Algorithm 4: An algorithm that outputs the sum
of the digits of an integer. For example, if the
input is123, the algorithm should give output as:
The sum of the digits of 123 is 6
Algorithm 5: To find the greatest common
divisor of two numbers
Algorithm 6: Input a series of positive numbers.
When a non-positive number is entered input
stops and the sum of the numbers is displayed
Submission date: First class of next week
Please feel free
to ask questions!
Reference
http://www.cs.unt.edu/~rada/CSCE3110
Jeff Edmonds, York University
