CpE 300
Design and Analysis
of Algorithms
COURSE INTRODUCTION
1
Objective
• Introduce the basics, as well as some advanced topics, in
the area of designing effective algorithms.
• Give the ability to analyze worst-case running time of
algorithms and understand fundamental algorithmic
problems.
• Get familiar with ongoing research.
• To appreciate the beauty behind efficient algorithms.
2
Prerequisite
• You are expected to have knowledge of basic:
• Discrete Mathematics.
• Proof techniques (induction/contradiction/contrapositive)
• Series and summations
• Discrete probability
• Basic combinatorics (permutations & combinations)
• Data Structures.
• Stacks, queues, and linked lists
• Hash functions and Hash tables
• Trees, Heaps, and Graphs
3
Main Questions
• What are algorithms?
• Why study algorithms?
• How to design and analyze algorithms?
4
What are Algorithms?
• Informally, an algorithm is a 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 a procedure (steps) used for solving a
problem.
5
Example: Sorting
• Problem: Sort a sequence of numbers in non-decreasing order
• Input: A sequence of numbers 𝜋 = 𝑎 , … , 𝑎
• Output: A permutation 𝜋 = 𝑎 , … , 𝑎 of 𝜋 such that
𝑎 ≤𝑎 ≤⋯≤𝑎
• An algorithm for the sorting problem is a sequence of computational steps with the above
input/output specifications.
• Ex: 8, 10, 1, 6, 2, 7, 3 ⇒ (1, 2,3,6,7,8,10)
6
Example: Traveling
• Problem: Find the cheapest way to get from city A to city B
• Input: A map of n cities with the cost of traveling from one city to
another, starting city A, and destination city B.
• Output: A path between city A and city B such that the cost of
the path is the minimum.
7
Example: Majority
• Problem: Find the element in a list that occurs the most number of times
• Input: A multi-set of numbers 𝑆 = 𝑎 , … , 𝑎
• Output: A number 𝑥 such that number of #𝑥 ∈ 𝑆 > (#𝑦 ∈ 𝑆) for any 𝑦 ≠ 𝑥
• An algorithm for the majority problem is a sequence of computational steps
with the above input/output specifications.
• Ex: 1, 7, 7, 1, 7, 7, 4 ⇒ 7
8
Example: Majority
• We will always start with the naïve approach
• Naïve: The simplest (not necessarily most efficient) approach that you know for sure will give you the correct
answer.
• What is the naïve approach for the majority problem?
1. List the number of unique elements 𝑥 , 𝑥 , … , 𝑥 in 𝑆
2. For each 𝑥 iterate over the entire list:
Count the number of 𝑥 in 𝑆
3. Output 𝑥 with the highest count
• How fast is this algorithm – in terms of the number of items in the list?
9
Example: Majority
• Questions you need to answer:
• Can you do better than naïve?
• How fast can the algorithm be?
• Is there a theoretical lower bound? (e.g., you can prove that it cannot be done better than
𝑛 )
10
Internet: Web search, Biology: Human Computers: Circuit Computer graphics:
packet routing, genome project, layout, file system, Movies, video games,
Algorithms distributed file sharing,
...
protein folding, ... compilers, ... virtual reality, ...
in Real Life
Security: Cell phones, Multimedia: MP3, JPG, Social networks: Physics: N-body
e-commerce, voting DivX, HDTV, face Recommendations, simulation, particle
machines, ... recognition, ... news feeds, collision simulation, ...
advertisements, ...
12
Why Study Algorithms?
• Correctness
• Running-time
• Scalability
• Composability
• Space/Memory
• Elegance and Simplicity
• Reliability
13
Algorithms as Technology
• If computers have infinite power, infinite memory, and infinite speed, then
any algorithm would be fine as long as it solves a problem correctly.
• Speed and memory are limited
• It is important to have efficient algorithms (shorter time and less
memory)
• Example: Insertion sort takes 𝑐 𝑛 , while Merge sort takes 𝑐 𝑛𝑙𝑔𝑛
• Machine A: 1 billion instructions/sec, B: 10 million instructions/sec,
• A use Insertion sort: 2𝑛 , B use Merge sort: 50𝑛𝑙𝑔𝑛
n A B
Million (10 ) ) 2000 sec 100 sec
10 million 2.3 days 20 min
14
How to Design and Analyze Algorithms?
Analysis: We will focus on Design: We will look at
techniques to analyze the various techniques that will
correctness and running- help you in designing your
time of algorithms. own algorithms
15
Pseudocode Conventions
• Indentation indicates block structure.
• The looping constructs while, for, and repeat-until and the if-else conditional construct have interpretations similar
to those in C, C++, Java, Python, and Pascal.
• The symbol “//” indicates that the remainder of the line is a comment.
• A multiple assignment of the form 𝑖 = 𝑗 = 𝑒 assigns to both variables i and j the value of expression e.
• Array indices start at 1 not 0.
• Compound data are organized into objects, which are composed of attributes. We access a particular attribute using
the dot operator.
• Parameters are passed to a procedure by value. Arrays and Objects are passed by reference (pointer).
• A return statement immediately transfers control back to the point of call in the calling procedure. Multiple values
to be returned in a single return statement are allowed.
• The boolean operators “and” and “or” are short circuiting.
• Error handling is omitted.
16
