Fundamentals of

Data-Structures and
Algorithms
SESSION 1
OBJECTIVES
• Understand what algorithms are and the
important properties they must have
• Understand the role of algorithms in programming
• Understand what data structures are
• Understand the role of data structures and
Algorithms in computing
• Be familiar with problem solving
• Be able to select appropriate data structures and
algorithms for given problems
 Introduction
• What are algorithms?
• Why is the study of algorithms worthwhile?
• What is the role of algorithms relative to other
technologies used in computers?
• What are data structures?
• In this lesson we will answer these questions
Problems
• In our everyday lives we are faced with a
number of problem.
• By problem we mean a task to be performed.
• Examples of problems could include:
• Baking a cake
• Solving an equation (quadratic equation)
• Sorting out a number of books according the year of
publishing…etc.
Focus however will be on what we call
computational problems (to be solved by
a computer)
 Computational problems
• A computational problem specifies an input-output relationship
 that values to be processed (input)must be determined
 the expected outcome (output )of the
computation/processing should be known
• Examples of computational problems:
• Input: An integer number of a given value n
• Output: Response whether it is a prime
• Input: A list of names of students enrolled in the BIT250
course
• Output: The same list with the names sorted in alphabetic
order
• Input: A picture in digital format
• Output: An English description of what the picture shows
The Problem-solving Process
1. Problem analysis

Problem
specification 2. Design

Algorithm

3. Implementation

Program
Solution
(Executable) 4. Compilation
The problem-solving process
NB: In this course there is emphasis on good software
development practice:

Problem solving and solution presentation should

demonstrate application of the previous diagram

Focus on designing a solution before

implementation

Good documentation

Self-documenting code
 Algorithms
• Informally, an algorithm is any well-defined
computational procedure that takes some value, or
set of values, as input and produces some value, or
set of values, as output.
• An algorithm is thus a sequence of computational
steps that transform the input into the output.
• We can also view an algorithm as a tool for solving a
well-specified computational problem.
• The statement of the problem specifies in general
terms the desired input/output relationship.
• The algorithm describes a specific computational
procedure for achieving that input/output
relationship.
 Algorithms
 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!
 Algorithms
• Example:
Given three integers values a, b and c. Write a
flow chart diagram of the solution that
displays a value which is maximum of the
three values
Algorithms
• solution:
Algorithms
• Usually we use “pseudo-code” to describe
algorithms
• And Flow charts
• Algorithms can be implemented in any
programming language
• A given algorithm solves only one problem
• (i.e., computes a particular function).
Algorithms
• Properties of an algorithm:
1. It must be correct.

2. It is composed of a series of concrete steps.

3. There can be no ambiguity as to which step will be
performed next.
4. It must be composed of a finite number of steps.

5. It must terminate.

6. must be general (in terms of data structures used)

 Algorithm development:
Basics
 Clearly identify:
 what output is required?
 what is the input?
 What steps are required to transform input into
output
oNeeds problem solving skills
o A problem can be solved in many different ways
o Which solution, amongst the different possible
solutions is optimal?
 How to express an
algorithm?
 A sequence of steps to solve a problem
 We need a way to express this sequence of steps
 Natural language (NL) is an obvious choice, but not a
good choice. Why?
o NLs are notoriously ambiguous (unclear)
 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
 What is pseudo-code?
 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
 Pseudo-code: general
guidelines
 Use PLs construct that are consistent with modern high level
languages, e.g. C++, Java, ...
 Use appropriate comments for clarity
 Be simple and precise
 Components of
Pseudo-code
 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?

 Components of Pseudo-
code (cont.)
 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?

 Components of Pseudo-
code (cont.)
 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?

 Components of
Pseudo-code (cont.)
 Loops (Repetition)
 Pre-condition loops
o For loops
• for variable-increment-definition do actions
• For example
for counter ← 0; counter < 5; counter ← counter + 2 do
print “Welcome to CS204!”
end for

What will be the output?

 Components of
Pseudo-code (cont.)
 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)
 Components of
Pseudo-code (cont.)
 Method returns
 return value
 For example
integer sum ( integer num1, integer num2)
start
result ← num1 + num2
return result
end
 Components of
Pseudo-code (cont.)
 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]
Algorithms
• Why are algorithms important?
• At the foundation of most of the computing
problem are algorithms.

• As earlier indicated, an algorithm is a design so

they play a major role in implementations of
simple and complex problems.

• Algorithms are applied practically used in most of

the fields other than software development
 Algorithms
Applications of algorithms in the real world.
1. Compression of data (e.g. JPEG, MPEG,…etc)

2. Cryptography and information security (application in e-

commerce of technologies such RSA, AES, SSL,… etc)

3. Web and internet (searching of content over the internet)

4. Computational biology/string matching (DNA sequencing)

5. Linear and integer programming (generation of fixture in sports

leagues, timetable making …etc)

6. Mail delivery and trash collection ( determining shortest path,

efficient routes….etc)
 Data structures
• A data structure is a way to store and
organize data in order to facilitate access and
modifications.
• No single data structure works well for all
purposes, and so it is important to know the
strengths and limitations of several of them.
 What is data?
 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 (Mulenga)
 Numeric: For example, your ID (190254)
 Audio: For example, your voice
 Video: For example, your voice and picture
 (...)
 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!
Data Structures
Examples:

simple variables— primitive types (int, float)

arrays — collection of data items of the same type,

stored contiguously (one next to the
other)

linked lists — sequence of data items, each one

points to the next one
Data Structures
There are several kinds of data structures as
seen from the previous example. A
programmer is at liberty to use any data
structure in their programs.

HOWEVER!!

Need of developing efficient programs

 The Need for Data
Structures
 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)
 Data Structure Operations
(Demonstrate using class room example!)
 Traversing
 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
 Data Structure Operations
(cont.)
 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
Data Structures
• Efficient programs are as a result of the use of the
correct resources in terms of data structure.

• How often the program does operations such as

searching, inserting data records, and deleting
data records determines the efficiency of a
program.

• Therefore the need to choose the write data

structure.
Data Structures
• To choose a data structure, the following
steps must be followed:
1. Analyze the problem to determine the basic operations
needed (data and operations to be performed on them)

2. Identify the resource constraint for each operation (how

often do you carry out operations such as searching,
sorting…etc ).

3. Select the data structure that best meets the

requirements
 Tutorial

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 and
flowchart that finds the average of (n)
numbers.
For example numbers are [4,5,14,20,3,6]