Design and Analysis of Algorithms Chapter 1

CSCE 310J: Data Structures & Algorithms CSCE 310J: Data Structures & Algorithms

I Giving credit where credit is due:

• Most of the lecture notes are based on the slides from
Introduction the Textbook’s companion website
– http://www.aw.com/cssuport/
• I have modified them and added new slides
Dr. Steve Goddard
goddard@cse.unl.edu

http://www.cse.unl.edu/~goddard/Courses/CSCE310J

Design and Analysis of Algorithms - Chapter 1 1 Design and Analysis of Algorithms - Chapter 1 2

What is a Computer Algorithm? Features of Algorithm

I “Besides merely being a finite set of rules that gives a
I An algorithm is a sequence of unambiguous sequence of operations for solving a specific type of
instructions for solving a problem, i.e., for problem, an algorithm has the five important features”
obtaining a required output for any legitimate [Knuth1]
input in a finite amount of time. – finiteness (otherwise: computational method)
» termination
– definiteness
» precise definition of each step
– input (zero or more)
– output (one or more)
– effectiveness
» “Its operations must all be sufficiently basic that they can in
principle be done exactly and in a finite length of time by
someone using pencil and paper” [Knuth1]

Design and Analysis of Algorithms - Chapter 1 3 Design and Analysis of Algorithms - Chapter 1 4

Computer Algorithm or Program? Notion of algorithm

I A computer algorithm is problem

• a detailed step-by-step method for solving a problem
using a computer.
algorithm
I A program is
• an implementation of one or more algorithms.
input “computer” output

Algorithmic solution
Design and Analysis of Algorithms - Chapter 1 5 Design and Analysis of Algorithms - Chapter 1 6

1
Design and Analysis of Algorithms Chapter 1

Example of computational problem: sorting Selection Sort

I Statement of problem: I Input: array a[1],…,a[n]
• Input: A sequence of n numbers <a1, a2, …, an>

• Output: A reordering of the input sequence <a´1, a´2, …, a´n> I Output: array a sorted in non-decreasing order
so that a´i ≤ a´j whenever i < j

I Algorithm:
I Instance: The sequence <5, 3, 2, 8, 3>

I Algorithms:
• Selection sort for i=1 to n
• Insertion sort swap a[i] with smallest of a[i],…a[n]
• Merge sort
• (many others)
• see also pseudocode, section 3.1
Design and Analysis of Algorithms - Chapter 1 7 Design and Analysis of Algorithms - Chapter 1 8

Some Well-known Computational Problems Basic Issues Related to Algorithms

I Sorting I How to design algorithms
I Searching
I Shortest paths in a graph I How to express algorithms
I Minimum spanning tree
I Proving correctness
I Primality testing
I Traveling salesman problem
I Efficiency
I Knapsack problem • Theoretical analysis
I Chess
I Towers of Hanoi • Empirical analysis

I Program termination
I Optimality

Design and Analysis of Algorithms - Chapter 1 9 Design and Analysis of Algorithms - Chapter 1 10

Algorithm design strategies Analysis of Algorithms

I How good is the algorithm?
• Correctness
• Time efficiency
I Brute force I Greedy approach
• Space efficiency

I Divide and conquer I Dynamic programming

I Does there exist a better algorithm?
I Decrease and conquer I Backtracking and Branch and bound • Lower bounds
• Optimality
I Transform and conquer I Space and time tradeoffs

Design and Analysis of Algorithms - Chapter 1 11 Design and Analysis of Algorithms - Chapter 1 12

2
Design and Analysis of Algorithms Chapter 1

Correctness Complexity
I Termination I Space complexity
– Well-founded sets: find a quantity that is never negative and I Time complexity
that always decreases as the algorithm is executed – For iterative algorithms: sums
I Partial Correctness – For recursive algorithms: recurrence relations
– For recursive algorithms: induction
– For iterative algorithms: axiomatic semantics, loop invariants

Design and Analysis of Algorithms - Chapter 1 13 Design and Analysis of Algorithms - Chapter 1 14

What is an algorithm? Why study algorithms?

I Recipe, process, method, technique, procedure, routine,… I Theoretical importance
with following requirements:
1. Finiteness • the core of computer science
I terminates after a finite number of steps
2. Definiteness I Practical importance
I rigorously and unambiguously specified
3. Input • A practitioner’s toolkit of known algorithms
I valid inputs are clearly specified
4. Output • Framework for designing and analyzing algorithms for new
I can be proved to produce the correct output given a valid input problems
5. Effectiveness
I steps are sufficiently simple and basic

Design and Analysis of Algorithms - Chapter 1 15 Design and Analysis of Algorithms - Chapter 1 16