Lecture 1

Introduction

1
 Lecture Contents

1. What is an algorithm?
2. Fundamentals of Algorithmic Problem Solving
3. Important Problem Types
4. Fundamental Data Structures

2
 1. What is an Algorithm?

• Algorithm is sequence of unambiguous

instructions for solving problem, i.e., for obtaining
required output for any legitimate input in finite
amount of time.

3
1. What is an Algorithm?

problem

algorithm

input “computer” output

4
 Why Do We 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

5
 Requirements of an Algorithm

1. Finiteness
terminates after finite number of steps
2. Definiteness
rigorously and unambiguously specified
3. Input
valid inputs are clearly specified

6
 Requirements of an Algorithm

4. Output
can be proved to produce the correct output
given a valid input
5. Effectiveness
steps are sufficiently simple and basic

7
 Finding the Greatest Common Divisor

• Euclid’s algorithm
• Consecutive integer checking algorithm
• Middle-school procedure

8
 Euclid’s Algorithm

• Problem: Find greatest common divisor

gcd(m,n) of two nonnegative, not both zero
integers m and n
• Examples: gcd(60, 24) = 12, gcd(60, 0) = 60,
gcd(0, 0) = ?

9
 Euclid’s Algorithm

• Euclid’s algorithm is based on repeated

application of equality gcd(m, n) = gcd(n, m mod
n) until the second number becomes 0, which
makes the problem trivial.

• Example: gcd(60, 24) = gcd(24, 12) = gcd(12, 0)

= 12

10
 Two Expressions of Euclid’s Algorithm

Description
Step 1 If n = 0, return m and stop;
otherwise go to Step 2
Step 2 Divide m by n and assign value of
remainder to r
Step 3 Assign value of n to m and value of r to n.
Go to Step 1.

11
 Two Expressions of Euclid’s Algorithm

Pseudocode
while n ≠ 0 do
r ← m mod n
m←n
n←r
return m

12
 Other Methods for Computing gcd(m, n)

Consecutive integer checking algorithm

Step 1 Assign value of min{m, n} to t
Step 2 Divide m by t.
If remainder is 0, go to Step 3;
Otherwise, go to Step 4
Step 3 Divide n by t.
If remainder is 0, return t and stop;
Otherwise, go to Step 4
Step 4 Decrease t by 1 and go to Step 2
13
 Other Methods for gcd(m, n) [cont.]

Middle-school procedure
Step 1 Find prime factorization of m
Step 2 Find prime factorization of n
Step 3 Find all common prime factors
Step 4 Compute product of all common prime
factors and return it as gcd(m, n)

Q: Is this an algorithm?

14
 Sieve of Eratosthenes

Input: Integer n ≥ 2
Output: List of primes less than or equal to n
for p ← 2 to n do A[p] ← p
for p ← 2 to ë n û do
if A[p] ¹ 0
//p hasn’t been previously eliminated from the list
j←p*p
while j ≤ n do
A[j] ← 0 //mark element as eliminated
j←j+p
15
 Sieve of Eratosthenes

//copy remaining elements of A to array L of the

primes
for p ← 2 to n do
if A[p] ¹ 0
L[i] ← A[p]
i←i+1
return L

16
 Lecture Contents

1. What is an algorithm?
2. Fundamentals of Algorithmic Problem
Solving
3. Important Problem Types
4. Fundamental Data Structures

17
18
 Basic Issues Related to Algorithms

• How to design algorithms

• How to express algorithms
- Description, pseudocode, flowchart
• Proving correctness
- Formal verification (mathematical proof)
- Test and debug a program
• Efficiency
- Theoretical analysis
- Experimental analysis
19
 Algorithm Design Strategies

• Brute force (i.e., exhaustive)

• Divide and conquer
• Greedy approach
• Dynamic programming
• Backtracking
• Branch and bound
• Space and time tradeoffs
…

20
 Analysis of Algorithms

• How good is the algorithm?

- Correctness
- Time efficiency
- Space efficiency
…
• Does there exist a better algorithm?
- Lower bounds, upper bounds
- Complexity

21
 Lecture Contents

1. What is an algorithm?
2. Fundamentals of Algorithmic Problem Solving
3. Important Problem Types
4. Fundamental Data Structures

22
 3. Important Problem Types

• Searching
• Sorting
• Geometric problems (Computational geometry)
• Combinatorial problems (Combinatorics)
• Graph problems (Graph theory)
• String processing
• Numerical problems

23
 3. Important Problem Types

• Searching
- Linear (or sequential) search
- Binary search
- Interpolation search

24
 3. Important Problem Types

• Sorting
- Selection sort, bubble sort, insertion sort
- Merge sort, quick sort, heap sort

25
 3. Important Problem Types

• Geometric problems (Computational geometry)

- Closest-pair problem
- Convex-hull problem
- Linear programming problem

26
 3. Important Problem Types

• Combinatorial problems (Combinatorics)

- Generating permutations (n!)
- Generating subsets (2n)
- Knapsack problem
- Assignment problem
- n-Queens problem
- Subset-Sum problem

27
 3. Important Problem Types

• Graph problems (Graph theory)

- Minimum spanning tree (MST) Problem
◦ Kruskal’s algorithm, Prim’s algorithm
- Shortest paths in a graph
◦ Single-Source Shortest-Paths Problem
▪ Dijkstra’s algorithm (nonnegative)
▪ Bellman-Ford’s algorithm (negative)
◦ All-Pairs Shortest-Paths Problem
▪ Floyd’s algorithm
28
 3. Important Problem Types

• Graph problems (Graph theory)

- Traveling Salesman Problem (TSP)
- Hamiltonian Circuit Problems

29
 3. Important Problem Types

• String processing
- String Matching Problem
• Numerical problems
- Solving equation f(x) = 0
- Solving system of equations
- Evaluating polynomial p(x) at x = x0

30
 Lecture Contents

1. What is an algorithm?
2. Fundamentals of Algorithmic Problem Solving
3. Important Problem Types
4. Fundamental Data Structures

31
 4. Fundamental Data Structures

• list: array, linked list, string

• stack (LIFO)

• queue (FIFO)

• priority queue

• graph

• tree

• set and dictionary

32
 A Big Question

How to Design a new Algorithm?

33
 Exercises

1. Prove that ëlog2 nû + 1 = élog2 (n + 1)ù, where n

is a positive integer.

2. Show that the maximum number of nodes in a

binary tree of height h is 2h+1 – 1. That is, a binary
tree of height h has at most 2h+1 – 1 nodes (i.e., n ≤
2h+1 – 1).

34
 Exercises

3. Show that the height h of any binary tree with n

nodes is at least ëlog2 nû and at most n – 1 (i.e.,
ëlog2 nû ≤ h ≤ n – 1).

4. Show that the maximum number of nodes at

level i (i = 0, 1, 2, ...) in a binary tree is 2i. That is,
in a binary tree, the number of nodes at level i is at
most 2i.

35
 References

1. Anany Levitin. 2011. Introduction to the Design

and Analysis of Algorithms. 3rd Ed. Pearson.
ISBN: 0132316811.

2. M. H. Alsuwaiyel. 2016. Algorithms: Designs

Techniques and Analysis. Revised Ed. World
Scientific Publishing. ISBN: 9814723649.

36
 References

3. Mark Allen Weiss. 2011. Data Structures and

Algorithm Analysis in Java, 3rd Ed. Pearson. ISBN:
0132576279.

4. Thomas H. Cormen, Charles E. Leiserson,

Ronald L. Rivest, Clifford Stein. 2009. Introduction
to Algorithms. 3rd Ed. The MIT Press. ISBN:
0262033844.

37