Transcript Introduction to Algorithm and Data Sturcture

CIT231: Algorithms
and Data Structures
Bajuna Salehe
[email protected]
The aim of this Module

The main aim of this course is to learn a large
number of the most important algorithms
used on computers today in a such a way
that we will be able to apply and appreciate
them in the any further computer
applications.
Learning Outcome




Ability to develop and analyse efficiency of
various algorithm.
Ability to describe various data structure
and their use in respective application
domain.
Ability to develop application by integrating
various data structures.
Ability employ several sort procedure in
program development.
Recommended Reading



Ellis Horowitz, Sartaj Sahni and Dinesh Mehta
(2002); Fundamentals of Data Structures in C++;
Galgotia Publishing pvt. Ltd., New Delhi.
Robert L. Kruse, Clovis L. Tondo and Bruce P.
Leung (2002), Data Structures and Program Design
in C, Prentice-Hall of India Private Limited, New
Delhi.
Jean-Paul Trembley and Paul G. Sorenson (2003),
An Introduction to Data Structures with Applications,
Tata McGraw-Hill Publishing Company Limited, New
Delhi.
Additional Readings




Alfred V. Aho, John E. Hopcroft and Jeffrey D.
Ullman (2000), Data Structures and Algorithms,
Addison-Wesley, London.
Mark Allen Weiss (2003), Data Structures and
Problem Solving Using C++, 2nd Edition, Pearson
Education International Inc., Upper Saddle River,
N.J.
Alfred V. Aho, John E. Hopcroft and Jeffrey D.
Ullman (2003), The Design and Analysis of
Computer Algorithms, Pearson Education, Inc., New
Delhi.
Thomas H. Cormen, Charles E. Leiserson and
Ronald Leiserson (2000), Introduction To
Algorithms, McGraw-Hill Book Company, New York.
Useful Web Sources for this
Course

The useful Web resources for the course are:




http://cgm.cs.mcgill.ca/~godfried/teaching/algorith
ms-web.html
http://www.cs.fiu.edu/~weiss/dsaa_c++/Code/
http://www.maths.abdn.ac.uk/~igc/tch/mx4002/not
es/node11.html
http://www.cs.pitt.edu/~kirk/algorithmcourses/inde
x.html
Examination


Written Examination
Continuous Assessment

There will be two assignments



60%
40%
The first assignment will have 20 marks each.
The last assignment will carry 20 marks
The first assignment will be out in week 5 and the
second assignment will be out in week 10
Course Outlook




In this course we will be looking at various
concepts related to data structure and
important algorithms that can be applied to
solve nowadays computer applications
In data structure we will discuss some
important topics such as arrays, linked lists,
stacks and queues, and trees.
In algorithms analysis we will have a look at
sorting and searching algorithms
Other topics that will be discussed include
Hashing, Heap Structure, algorithms for
graph problems, geometric algorithms, and
randomised algorithms
Learning Methods, Strategies
and Techniques




The best way to learn this course is through
group work in the form of discussion.
Students must work together in some
assessment works to gain more
understanding on the course.
You have to think first in tackling any problem
whether it is a code oriented problem or an
analytic problem.
Ask your friend and neighbour if you see
some difficulties before rushing to the
lecturer.
Learning Methods, Strategies
and Techniques




The major strategy that might be used also to
well understand the course is to implement
and test some algorithms, experiment with
their variants, discuss their operation on
small examples, and to try them out on larger
examples.
We shall use the C++ programming language
to describe the algorithms, thus providing
useful implementations at the same time.
In this course we will look at many different
areas of application, focusing on the
fundamental algorithms that are important to
know and interesting to study.
Lab works for some implementations during
Tutorials
Introduction to Algorithms



By definition algorithm is a sequence of an
instructions that act on some input data to
produce some output in a finite number of
steps.
Simply stated it is a method of solving a
problem that are suited for computer
implementations.
Others describe it as a problem-solving
method suitable for implementation as a
computer program.
Introduction to Algorithms



When we write a computer program, we are
generally implementing a method that has
been devised previously to solve some
problem.
This method is independent on particular
computer to be used – it might be appropriate
for many computers and many programs.
Algorithm is the method that we use to learn
how to solve computer related problems
(programs).
How Data Structure is Involved




Most algorithms of interests involve methods
of organising the data involved in
computation.
Objects created in this way are called Data
Structures and they are the core objects to
study in computer science.
Therefore algorithms and data structures go
hand in hand.
Data structures exist as the end products of
algorithms, thus that we must study them in
order to understand the algorithms.
Properties of Algorithm





Input – must receive data supplied externally.
Output – Produce at least one output as the
results.
Finiteness – Must terminate after finite
number of the steps.
Definiteness – The steps to be performed
must be clear.
Effectiveness – Ability to perform the steps in
the algorithm without applying any
intelligence.
Categories of Algorithm



Fundamentally algorithms can be divided into
two categories.
 Iterative (repetitive) algorithm
 Recursive algorithms.
Iterative algorithms typically use loops and
conditional statements.
Recursive algorithms use ‘divide and
conquer’ strategy to break down a large
problem into small chunks and separately
apply algorithm to each chunk.
Principles of Problem Solving


No hard and fast rules that will ensure success in
the problem solving process.
The general steps and principles that may be useful
in the solution of the problems are:Understand the Problem
- Read the problem and make sure you understand it
clearly. Ask yourself the following questions:What is the unknown?
What are the given quantities?
What are the given conditions?
For some problems it is useful to draw a diagram and identify
the given and required quantities on the diagram.
Usually it is necessary to introduce suitable notation.

Principles of Problem Solving



Think of a Plan
Find the connection between the given
information and the unknown that will enable
you to find the unknown.
Carry Out the Plan
Check each stage of the plan and write the
details that prove that each stage is correct.
Look Back
Look back over your solution to see if you
have made errors in the solution.
Analysis of Algorithm


The choice of the best algorithm for a
particular task can be a complicated process,
perhaps involving sophisticated mathematical
analysis.
Analysis of algorithm involve the study of
sophisticated mathematical analysis of the
problem for a particular task.
Analysis of Algorithm



The primary goal of analysis of algorithm is to
learn reasonable algorithms for important
tasks as well as paying careful attention to
comparative performance of the methods.
Consider necessary resources that might be
needed by the entire algorithm before using
it.
Be aware of the performance of algorithm.
Analysis of Algorithm



There might be different ways (algorithms) in
which we can solve given problem.
Each algorithm has its own characteristics
when it operates which determine its
efficiency.
Understanding which algorithm is more
efficient than the other involve the analysis of
algorithm.
Analysis of Algorithm




In analysing algorithm the important thing to
consider is the time needed to execute it.
The time is not the number of seconds or any
such time unit, but the number of operations
to complete the execution of whole algorithm.
An algorithm cannot be considered better due
to its less time unit in execution or worse
because it takes more time units to execute.
In comparison between two algorithms it is
assumed that all other things like speed of
the computer and the language used are the
same for both the algorithms
Analysis of Algorithm



When analysing algorithms don’t consider the
actual number of operations done for some
specific size of input data.
Instead try to build an equation that relates
the number of operations that a particular
algorithm does to the size of input data.
Once the equations formed compare two
algorithms by comparing that rate at which
their equation grow.
Analysis of Algorithm


This growth rate is critical since there are
situations where one algorithm needs fewer
operations than the other when the input size
is small, but many more when the input size
gets large.
In analysing iterative algorithms it is important
to determine the number of times the loop is
executed.
Analysis of Algorithm

In analysing the recursive algorithms you
need to determine amount of work done for
three things.




Breaking down the large problem to smaller
pieces.
Getting solution for each piece
Combining the individual solutions to get the
solution to the whole problem
Create a recurrence relation for algorithm by
combining all this information and the number
of the smaller pieces and their sizes.
What is Analysis of Algorithm


The analysis of algorithm enable us to
understand how long an algorithm will take
for solving a problem.
For comparing the performance of two
algorithms we have to estimate the time
taken to solve a problem using each
algorithm for set of N input values.

E.g Number of comparisons a searching algorithm
does to search a value in a list of N values.
What is Analysis of Algorithm


As previously said the number of algorithms
can be used to solve a particular problem
successfully.
Analysis of algorithms enable us to have
scientific reason to determine which algorithm
should be chosen to solve the problem.

E.g Two algorithms to find the biggest of four
values.
What is Analysis of Algorithm




Each algorithm above does exactly three
comparisons to find the biggest number.
The first is easier to read and understand
however both have the same level of
complexity for computer to execute.
In terms of time these two algorithms are the
same, but in terms of space, the first need
more because of the temp variable ‘big’
The purpose of determining the number of
comparisons is to use them to figure out
which of algorithms can solve the problem
more efficiently
What Analysis Doesn’t Do


The analysis of algorithms doesn’t give a
formula that helps to determine how many
seconds or cycles a particular algorithm will
take to solve a problem.
This is not useful because



Type of computer
Instruction set used by the Microprocessor
What optimisation compiler performs on the
executable code, etc.
Cases to Consider During
Analysis
Choosing the input to consider when
analysing algorithm can have a significant
impact on the performance of the algorithms.
e.g. if the input list is already sorted, some
sorting algorithm will perform very well.
 The multiple input sets that normally are
considered when analyising algorithm are:

Best case input – Allows an algorithm to perform
most quickly. It makes an algorithm to take
shortest time to execute.
Cases to Consider During
Analysis


Worst Cases Input – This represents the input set
that allows an algorithm to perform most slowly. It
is an important analysis because it gives us an
idea of the most time algorithm will ever take.
Average Case Input – Represents the input set
that allows an algorithm to deliver an average
performance. It has a four-steps process:


Determine the number of different groups into which all input
sets can be divided.
Determine the probability that the input will come from each of
these groups
Determine how long the algorithm will run for each these
groups.
Data Structure



Organising the data for processing is an
essential step in the development of a
computer program.
Any algorithm necessary to solve a particular
problem will depend on the proper data
structure for implementing it to computer
application.
For the same data, some data structure
require more or less space than others; some
data structure lead to more or less efficient
Data Structure



The choices of algorithms and data structure
are closely intertwined, and beware of saving
time and space by making the choice
properly.
Consider operations needed to be performed
on the data structure as well as algorithms
used for these operations.
This concept is formalised in the notion of a
data type.
Data Structure




In C++ we will use low level construct to store
and process information.
All the data that we process in a computer
ultimately decompose into individual bits.
Types allow us to specify how we will use
particular sets of bits.
Functions allow us to specify the operations
to be performed on the data.
Data Structure



The data structure that will be considered are
important building blocks that can be used in
C++ and many other programming
languages. These are the tree, arrays,
strings, and linked lists.
Structures are going to be used to group
pieces of information together
Pointers will be used to refer to information
indirectly.
Data Structure

In C++, the programs are built from just a few
basic types of data:





Integers (int)
Floating-point numbers (floats)
Characters (chars)
Characters are most often used in higher
level abstraction for instances to make word
and sentences.
Integers (int) fall within specific range that
depends on the of bits that we to represent
them.
Data Structure




Floating-point numbers approximate real
numbers.
The number of bits that are used to represent
them affect the precision to approximate a
real number.
By definition A data type is a set of values
and collection of operations on those values.
When operations are performed its operands
and results must be of the correct type.
Data Structure



It is a common programming error to neglect
this responsibility.
In some cases C++ performs implicit type
conversion.
In other cases casts or explicit type
conversion can be used. For example if x and
N are integers, the expression ((float) x) / N
includes both types of conversion.
ARRAYS