THE DESIGN AND

ANALYSIS OF
ALGORITHMS
by Anany Levitin
CHAPTER 1:
INTRODUCTION
■ What is an Algorithm
■ Steps in Designing and Implementing an Algorithm
■ Important Problem Types
■ Fundamental Data Structures

Text reading: 1.1 – 1.4.

2
3
 ALGORITHM
[Link]
■ A sequence of unambiguous
instructions for solving a
problem, i.e. for obtaining the
required output for any
legitimate input in
a finite amount of time

4
 Important points

■ Non-ambiguity: a requirement for each step of an algorithm.

■ Range of inputs: the range of inputs for which an algorithm
works has to be specified carefully.
■ The same algorithm can be represented in
different ways

■ Several algorithms for solving the same problem

■ Algorithms for the same problem can be based
on very different ideas and can solve the
problem with dramatically different speeds.

5
 ALGORITHM

■ A finite, definitive, and effective procedure that

takes some input and produces some output.
– Finite: terminate for every input.
– Definitive: Each instruction is precisely stated.
– Effective: well-defined and controlled procedure to
give the required output.

6
 Why study algorithms?

■ Theoretical importance

– the core of computer science

■ Practical importance

– A practitioner’s toolkit of known algorithms

– Framework for designing and analyzing algorithms for

new problems

Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 1 ©2012
7
Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.
Two main issues related
to algorithms
■ How to design algorithms

■ How to analyze algorithm efficiency

Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 1 ©2012
8
Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.
 Is an algorithm…

■ Programming language-dependent?
■ Platform-dependent?
■ Compiler-dependent?

9
Example: Sorting Problem
■ The sorting problem is to rearrange the items of a given list in an
increasing / decreasing order.
■ the nature of the list items must allow such an ordering.
– lists of numbers,
– characters from an alphabet,
– character strings,
– records: choose a piece of information (a key) to guide sorting.

10
 Sorting Algorithms

■ computer scientists have discovered dozens of different

sorting algorithms.
– Selection sort,
– Insertion sort,
– Bubble sort,
– Quicksort
– Merge sort
:
:

11
 Why so many sorting
algorithms?
■ There is no algorithm that would be the best solution in all
situations.
– Some are simple but slow, others are faster but more complex;
– Some work better on randomly ordered inputs, while others do
better on almost-sorted lists;
– some work only for lists residing in memory, while others can work
for sorting large files stored on a disk;
– and so on.
Amount of swapping

Larger space requirements

12
Steps in Algorithmic Problem Solving
Understand the problem

Decide on computational means

Exact vs approximate solution?
Data structures?
Algorithm design technique?

Design an algorithm

Prove correctness

Analyze the algorithm

Code the algorithm

13
 Understanding the
Problem
■ the first thing you need to do before designing an algorithm is
to understand completely the problem given.
– Read the problem’s description carefully
– ask questions if you have any doubts about the problem,
– do a few small examples by hand,
– think about special cases, and ask questions again if needed.

14
 Understanding the
Problem, cont.
■ An input to an algorithm specifies an instance of the problem
the algorithm solves.
– It is very important to specify exactly the set of instances the
algorithm needs to handle.
■ If you fail to do this, your algorithm may work correctly for a
majority of inputs but crash on some “boundary” value.

15
Steps in Algorithmic Problem Solving
Understand the problem

Decide on computational means

Exact vs approximate solution?
Data structures?
Algorithm design technique?

Design an algorithm

Prove correctness

Analyze the algorithm

Code the algorithm

16
 Exact vs Approximate
Problem Solving
■ A principal decision is to choose between solving the problem
exactly or solving it approximately.
 There are important problems that simply cannot be
solved exactly;
– Examples: extracting square roots, solving nonlinear
equations, and evaluating definite integrals.

17
 Exact vs Approximate
Problem Solving, cont.
– Available algorithms for solving a problem exactly can
be unacceptably slow because of the problem’s
intrinsic complexity.
■ This happens, in particular, for many problems
involving a very large number of choices;
■ Example: Traveling Salesman Problem.

18
Steps in Algorithmic Problem Solving
Understand the problem

Decide on computational means

Exact vs approximate solution?
Data structures?
Algorithm design technique?

Design an algorithm

Prove correctness

Analyze the algorithm

Code the algorithm

19
 Algorithm Design
Techniques
■ An algorithm design technique (or “strategy” or “paradigm”) is
a general approach to solving problems algorithmically that is
applicable to a variety of problems from different areas of
computing.

20
 Algorithm Design
Techniques, cont.
■ Algorithm design techniques make it possible to classify
algorithms according to an underlying design idea;
– Brute Force
– Divide and Conquer
– Dynamic Programming
– Greedy Approach

21
Steps in Algorithmic Problem Solving
Understand the problem

Decide on computational means

Exact vs approximate solution?
Data structures?
Algorithm design technique?

Design an algorithm

Prove correctness

Analyze the algorithm

Code the algorithm

22
 Methods of Specifying
an Algorithm
■ Once you have designed an algorithm, you need to specify it in some
fashion.
– Pseudocode: a mixture of a natural language and programming language
like constructs.
– Flowchart: In the earlier days of computing, a collection of connected
geometric shapes containing descriptions of the algorithm’s steps.
– Source Code: a program written in a particular computer language,
although it is preferable to consider it as the algorithm’s implementation.

23
Steps in Algorithmic Problem Solving
Understand the problem

Decide on computational means

Exact vs approximate solution?
Data structures?
Algorithm design technique?

Design an algorithm

Prove correctness

Analyze the algorithm

Code the algorithm

24
 Proving an Algorithm’s
Correctness
■ Once an algorithm has been specified, you have to
prove its correctness.
– Proof of correctness: to prove that the
algorithm yields a required result for every
legitimate input in a finite amount of time.
■ For some algorithms, a proof of correctness is quite
easy; for others, it can be quite complex.

25
 Proving an Algorithm’s
Correctness, cont.
■ techniques for proving correctness:
– Mathematical induction: an algorithm’s
iterations provide a natural sequence of steps
needed for such proofs.
– computing a loop’s invariant (an expression
that does not change its value) outside the
loop,

26
Steps in Algorithmic Problem Solving
Understand the problem

Decide on computational means

Exact vs approximate solution?
Data structures?
Algorithm design technique?

Design an algorithm

Prove correctness

Analyze the algorithm

Code the algorithm

27
 Analyzing an
Algorithm
■ After correctness, by far the most important quality an
algorithm needs to possess is efficiency.
■ Two kinds of algorithm efficiency:
– time efficiency, indicating how fast the algorithm runs, and
– space efficiency, indicating how much extra memory it uses.

28
IMPORTANT
PROBLEM
TYPES
Section 1.3

29
 Important problem
types
■ Sorting
■ Searching
■ String processing
■ Graph problems
■ Combinatorial problems
■ Geometric problems
■ Numerical problems

30
Sorting

■ Rearrange the items of a given list in ascending order.

– Input: A sequence of n numbers <a1, a2, …, an>
– Output: A reordering <a’1, a’2, …, a’n> of the input sequence such
that
a’1≤ a’2 ≤ … ≤ a’n.
■ Why sort?
– Help searching
– Algorithms often use sorting as a key subroutine.
■ Sorting key
– A specially chosen piece of information used to guide sorting.
– Example: sort student records by names.

31
Sorting, cont.

■ Examples of sorting algorithms

– Selection sort
– Bubble sort
– Insertion sort
– Mergesort
– Heap sort

32
Sorting, cont.

■ To evaluate a sorting algorithm’s complexity we look at the

number of key comparisons.
■ Two properties
– Stability: A sorting algorithm is called stable if it preserves the
relative order of any two equal elements in its input.
■ Some sorting algorithms are stable by nature like Insertion Sort, Mergesort,
Bubble Sort, etc., while some sorting algorithms are not, like Heap Sort,
Quicksort, etc.
– In place: A sorting algorithm is in place if it does not require
extra memory, except, possibly for a few memory units.

33
 Selection Sort
Algorithm SelectionSort(A[0..n-1])
//The algorithm sorts a given array by selection sort
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in ascending order

for i←0 to n–2 do

min ← i
for j ← i+1 to n–1 do
if A[j] < A[min] then
min ← j
swap A[i] and A[min]

34
Selection Sort

■ The selection sort algorithm picks the minimum item and

swaps it with the element at the current position.
■ Selection sort is not stable but it is in place:
– In an array implementation of this algorithm, it swaps the first
element of the unsorted part with the minimal element (then
it is included in the sorted part). This implementation of
selection sort in not stable.
– In case of linked list if, instead of swapping, the minimal
element is linked to the unsorted part, then selection sort is
stable.

35
Searching

■ Find a given value, called a search key, in a given set.

■ Examples of searching algorithms
– Sequential search
– Binary search
Input: sorted array a[i] < … < a[j] and key x;
m←(i+j)/2;
while i<j and x!=a[m] do
if x<a[m] then j ←m-1
else i  m+1;
if x = a[m] then output a[m];

Time: O(log n), Log2(100)≈6, Log2(1000)≈10

36
String Processing

■ A string is a sequence of characters from an alphabet.

■ Text strings: letters, numbers, and special characters.
■ String matching: searching for a given word/pattern in a text.
■ Examples:
– Searching for a word or phrase on WWW or in a Word
document
– Searching for a short read in the reference genomic
sequence

37
Graph Problems

■ graph can be thought of as a collection of points called vertices, some of

which are connected by line segments called edges.
■ Graphs can be used for modeling a wide variety of applications, including
transportation, communication, social and economic networks, project
scheduling, and games.
■ Basic graph algorithms include :
– graph-traversal algorithms
– shortest-path algorithms
– topological sorting for graphs with directed edges
■ Examples
– Traveling salesman problem
– Graph coloring problem

38
 Combinatorial Problems
■ The traveling salesman problem and the graph coloring problem are
examples of combinatorial problems.
■ Concept: Find a combinatorial object— a permutation, a combination,
or a subset—
– that satisfies certain constraints.
– may also be required to have some additional property such as a max
value or min cost.
■ Among most difficult problems in computation.
– number of combinatorial objects typically grows extremely fast with a
problem’s size
– No known algorithms for solving most such problems exactly in an
acceptable amount of time.

39
 FUNDAMENTAL
DATA STRUCTURES
Section 1.4

40
 Fundamental data
structures
■ A data structure : a particular scheme of organizing related
data items.
– Data items can range from elementary data types (e.g.,
integers or characters) to data structures (e.g., a one-
dimensional array).
■ There are a few data structures that have proved to be
particularly important for computer algorithms.
– a quick review is provided next.

41
 Fundamental data structures

 List : a collection of data items arranged in a

certain linear order
- Array, linked list, string
 Stack
 Queue
 Priority queue/heap
 Graph
 Tree and binary tree
 Set and dictionary

1-42
 Fundamental data structures
Linear data structures
■ Array
■ Linked list
■ Stack
■ Queue

Operations: search, delete, insert

Implementation: static, dynamic

43
 Linear Data Structures
■ Arrays  Arrays
– A sequence of n items of the same data  fixed length (need preliminary
type that are stored contiguously in reservation of memory)
computer memory and made accessible  contiguous memory locations
by specifying a value of the array’s index.
 direct access
■ Linked List  Insert/delete
– A sequence of zero or more nodes each  Linked Lists
containing two kinds of information:
some data and one or more links called  dynamic length
pointers to other nodes of the linked list.  arbitrary memory locations
– Singly linked list (next pointer)  access by following links
– Doubly linked list (next + previous  Insert/delete
pointers)
… .
a1 a2 an

1-44
 Stacks and Queues
■ Stacks
– A stack of plates
■ insertion/deletion can be done only at the top.
■ LIFO
– Two operations (push and pop)
■ Queues
– A queue of customers waiting for services
■ Insertion/enqueue from the rear and deletion/dequeue from the front.
■ FIFO
– Two operations (enqueue and dequeue)

1-45
 Priority Queue and Heap

 Priority queues (implemented using heaps)

 A data structure for maintaining a set of elements,
each associated with a key/priority, with the
following operations
 Finding the element with the highest priority
 Deleting the element with the highest priority
 Inserting a new element 9
6 8
 Scheduling jobs on a shared computer
5 2 3

9 6 8 5 2 3
1-46
 Fundamental data structures

Non-linear data structures

■ Graphs
■ Trees : connected graph without cycles
– Rooted trees
■ Ordered trees
– Binary trees

Graph representation: adjacency lists,

adjacency matrix
Tree representation: as graphs; binary
nodes 47
 Graphs
■ Formal definition
– A graph G = <V, E> is defined by a pair of two sets: a finite set
V of items called vertices and a set E of vertex pairs called
edges.
■ Undirected and directed graphs (digraphs).

■ Complete, dense, and sparse graphs

– A graph with every pair of its vertices connected by an edge is
called complete, K|V|

1 2

3 4
1-48
 Graph Representation

■ Adjacency matrix
– n x n Boolean matrix if |V| is n.
– The element on the ith row and jth column is 1 if there’s an edge
from ith vertex to the jth vertex; otherwise 0.
– The adjacency matrix of an undirected graph is symmetric.

■ Adjacency linked lists

– A collection of linked lists, one for each vertex, that contain all the
vertices adjacent to the list’s vertex.

0111 2 3 4
0001 4
0001
0000 4
1-49
 Trees
■ Trees
– A tree is a connected acyclic graph.
– Forest: a graph that has no cycles but is not necessarily
connected.
■ Properties of trees
– For every two vertices in a tree there always exists exactly one
simple path from one of these vertices to the other. Why?
■ Rooted trees: The above property makes it possible to select an arbitrary
vertex in a free tree and consider it as the root of the so called rooted tree.
■ Levels in a rooted tree.

rooted
3
 |E| = |V| - 1 1 3 5
4 1 5
2 4
1-50 2
 Ordered Trees
■ Binary trees
– A binary tree is an ordered tree in which every vertex has no
more than two children and each children is designated s
either a left child or a right child of its parent.
■ Binary search trees
– Each vertex is assigned a number.
– A number assigned to each parental vertex is larger than all
the numbers in its left subtree and smaller than all the
numbers in its right subtree.
■ 𝒍𝒐𝒈𝟐 n  h  n – 1 , ==> where h is the height of a binary tree and
n the size.

9 6
6 8 3 9
5 2 3 2 5 8
1-51
 Conclusion

■ Algorithm classification
■ By types of problems
■ By design technique

■ Design techniques
■ a general approach to solving problems

52