Lec 4 Data Structures and Algorithm Analysis

•Overview.
•Algorithm Analysis.
Some slides are borrowed from Mr. Mohammad Alqahtani

 Be familiar with problem solving.
 Be able to develop (and implement) algorithms.
 Be able to trace algorithms.
 Be able to select appropriate data structures and
algorithms for given problems.

 Prerequisites:
◦ Variables and expressions.
◦ Methods (functions or procedures ).
◦ Decision structures( like if-statements and
switch-statements.
◦ Iteration structures (for-loops and while-loops).
◦ Classes and objects
 Data
◦ A collection of facts from which conclusion may be drawn.
◦ e.g. Data: Temperature 35°C; Conclusion: It is hot.
 Types of data
◦ Textual: For example, your name (Alya)
◦ Numeric: For example, your ID (090254)
◦ Audio: For example, your voice
◦ Video: For example, your voice and picture
◦ (...)
 Applications/programs read data, store data
temporarily, process it and finally output
results.
 What is data? Numbers, Characters, etc.
Application/ Data
Data
Program
5
 Data is classified into data types. e.g. char, float, int, etc.
 A data type is (i) a domain of allowed values and (ii) a set
of operations on these values.
 Compiler signals an error if wrong operation is performed
on data of a certain type. For example, char x,y,z; z =
x*y is not allowed.
6
 Examples
Data Type Domain Operations

boolean 0,1 and, or, =, etc.
char ASCII =, <>, <, etc.
integer -maxint to +, _, =, ==,
+maxint <>, <, etc.
7
 Simple Data types: also known as atomic data
types  have no component parts. E.g. int,
char, float, etc.
21 3.14 ‘a’
8
A particular way of storing and organizing data in a
computer so that it can be used efficiently and
effectively.
 Data structure is the logical or mathematical model of
a particular organization of data.

 A group of data elements grouped together under one
name.
◦ For example, an array of integers
 Structured Data types: can be broken into
component parts. E.g. an object, array, set,
file, etc. Example: a student object.
NameA H M A D
Age 20
C S C
Branch
A Component part
10
Types of Data Structures
Array
Linked List
Queue Stack
Tree
There are many, but we named a few. We’ll learn these

data structures in great detail!
 Goal: to organize data
 Criteria: to facilitate efficient

◦ storage of data
◦ retrieval of data
◦ manipulation of data
 Design Issue:
◦ select and design appropriate data types
(This is the main motivation to learn and understand
data structures)
(Demonstrate using class room
example!)
 Navigating
Accessing each data element exactly once so
that certain items in the data may be processed
 Searching
Finding the location of the data element (key)
in the structure
 Insertion
Adding a new data element to the structure
 Deletion
◦ Removing a data element from the structure
 Sorting
◦ Arrange the data elements in a logical order
(ascending/descending)
 Merging
◦ Combining data elements from two or more
data structures into one
 A finite set of instructions which accomplish a particular
task
 A method or process to solve a problem
 Transforms input of a problem to output
Algorithm = Input + Process + Output
Algorithm development is an art – it needs practice, practice

and only practice!
 It must be correct
 It must be finite (in terms of time and size)
 It must terminate
 It must be unambiguous
 Which step is next?
 It must be space and time efficient
A program is an instance of an algorithm, written in some

specific programming language
 Problem: Find maximum of a, b, c
 Algorithm
 Input = a, b, c
 Output = max
 Process
o Let max = a
o If b > max then
max = b
o If c > max then
max = c
o Display max
Order is very important!!!

 Clearly identify:
 what output is required?
 what is the input?
 What steps are required to transform input into
output
o The most crucial bit
o Needs problem solving skills
o A problem can be solved in many different ways
o Which solution, amongst the different possible
solutions is optimal?
 A sequence of steps to solve a problem
 We need a way to express this sequence of steps
1. Natural language (NL) is an obvious choice, but not
a good choice. Why?
o NLs are notoriously ambiguous (unclear)
2. Programming language (PL) is another choice, but
again not a good choice. Why?
o Algorithm should be PL independent
 We need some balance
o We need PL independence
o We need clarity
o Pseudo-code provides the right balance
 Pseudo-code is a short hand way of describing a
computer program
 Rather than using the specific syntax of a
computer language, more general wording is used
 It is a mixture of NL and PL expressions, in a
systematic way
 Using pseudo-code, it is easier for a non-
programmer to understand the general workings of
the program
 Use PLs construct that are consistent with
modern high level languages, e.g. C++,
Java, ...
 Use appropriate comments for clarity
 Be simple and precise
 Expressions
 Standard mathematical symbols are used
o Left arrow sign (←) as the assignment operator in assignment statements
(equivalent to the = operator in Java)
o Equal sign (=) as the equality relation in Boolean expressions (equivalent to the "=
=" relation in Java)
o For example
Sum ← 0
Sum ← Sum + 5
What is the final value of sum?

 Decision structures (if-then-else logic)
 if condition then
true-actions
[else
false-actions]
 We use indentation to indicate what actions should be included in the true-
actions and false-actions
 For example
if marks > 50 then

print “Congratulation, you are passed!”
else
print “Sorry, you are failed!”
end if
What will be the output if marks are equal to 75?

 Loops (Repetition)
◦ Pre-condition loops
o While loops
 while condition do actions
 We use indentation to indicate what actions should be included in
the loop actions
 For example
while counter < 5 do
print “Welcome to CS204!”
counter ← counter + 1
end while
What will be the output if counter is initialised to 0, 7?

◦ Pre-condition loops
o For loops
 for variable-increment-definition do actions
 For example
for counter ← 0; counter < 5; counter ←
counter + 2 do
end for
What will be the output?

 Post-condition loops
o Do loops
 do actions while condition
 For example
do
counter ← counter + 1
while counter < 5
What will be the output, if counter was initialised to 10?
The body of a post-condition loop must execute at least once

 Method declarations
◦ Return_type method_name (parameter_list)
method_body
◦ For example
 integer sum ( integer num1, integer
num2)
 start
 result ← num1 + num2
 end
 Method calls
 object.method (args)
 For example
mycalculator.sum(num1, num2)
 Method returns
 return value
 For example
integer sum ( integer num1, integer num2)
start
result ← num1 + num2
return result
end
 Comments
◦ /* Multiple line comments go here. */
◦ // Single line comments go here
◦ Some people prefer braces {}, for comments
 Arrays
 A[i] represents the ith cell in the array A.
 The cells of an n-celled array A are indexed from A[0] to A[n −
1] (consistent with Java).
 Example 1: Determining even/odd number
 A number divisible by 2 is considered an even number, while a
number which is not divisible by 2 is considered an odd number.
Write pseudo-code to display first N odd/even numbers.
 Example 2: Computing Weekly Wages

 Gross pay depends on the pay rate and the number of hours
worked per week. However, if you work more than 40 hours, you
get paid time-and-a-half for all hours worked over 40. Write the
pseudo-code to compute gross pay given pay rate and hours
worked
Input range
for num←0; num<=range; num←num+1 do
if num % 2 = 0 then
print num is even
else
print num is odd
endif
endfor
 Example 1: Determining even/odd number
◦ A number divisible by 2 is considered an even number, while
a number which is not divisible by 2 is considered an odd
number. Write pseudo-code to display first N odd/even
numbers.
 Example 2: Computing Weekly Wages

 Gross pay depends on the pay rate and the number of hours
worked per week. However, if you work more than 40 hours,
you get paid time-and-a-half for all hours worked over 40.
Write the pseudo-code to compute gross pay given pay rate
and hours worked
Input range
for num←0; num<=range; num←num+1 do
if num % 2 = 0 then
print num is even
else
print num is odd
endif
endfor
Input hours_worked, pay_rate
if hours_worked <= 40 then
gross_pay ← pay_rate x hours_worked
else
basic_pay ← pay_rate x 40
over_time ← hours_worked – 40
over_time_pay ← 1.5 x pay_rate x over_time
gross_pay ← basic_pay + over_time_pay
endfor
print gross_pay
1. Write an algorithm to find the largest
of a set of numbers. You do not know
the number of numbers.
2. Write an algorithm in pseudocode
that finds the average of (n)
numbers.
For example numbers are [4,5,14,20,3,6]s

Lec 4 Data Structures and Algorithm Analysis

Uploaded by

Copyright:

Available Formats

Lec 4 Data Structures and Algorithm Analysis

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec 4 Data Structures and Algorithm Analysis

Uploaded by

Copyright:

Available Formats

•Overview.

Some slides are borrowed from Mr. Mohammad Alqahtani

algorithms for given problems.

Data Type Domain Operations

a particular organization of data.

There are many, but we named a few. We’ll learn these

 Criteria: to facilitate efficient

Algorithm development is an art – it needs practice, practice

A program is an instance of an algorithm, written in some

Order is very important!!!

What is the final value of sum?

if marks > 50 then

What will be the output if marks are equal to 75?

What will be the output if counter is initialised to 0, 7?

What will be the output?

What will be the output, if counter was initialised to 10?

The body of a post-condition loop must execute at least once

 Example 2: Computing Weekly Wages

 Example 2: Computing Weekly Wages

You might also like