Skip to content

Latest commit

 

History

History
205 lines (151 loc) · 5.37 KB

01.md

File metadata and controls

205 lines (151 loc) · 5.37 KB
title
Introduction

Overview

Our goal is to be able to:

  1. Analyze algorithms in terms of correctness and time/space complexity, and
  2. Design algorithms efficiently.

If time permits, we'll cover NP-theory and ways to address intractability.

  • In other words, we won't be covering NP-theory or intractability.

Algorithms

Algorithm: Sequence of unambiguous instructions for solving a problem in a finite amount of time.

Why Study Them?:

  1. Theoretical: They're the core of computer science.
  2. Practical: They'll help you design & analyze algorithms for new problems.

Design & Analysis

The Process

  1. Understand the problem
  2. Decide on computational means
    • e.g., exact or approximate?
  3. Design an algorithm
  4. Prove correctness
  5. Analyze the algorithm
  6. Code the algorithm

Techniques & Strategies

  • Brute Force
  • Divide and Conquer
  • Decrease and Conquer
  • Transform and Conquer
  • Space and Time Tradeoffs
  • Greedy Approach
  • Dynamic Programming
  • Iterative Improvement
  • Backtracking
  • Branch and Bound

We'll be going through these in this course.

Important Problem Types

  • Sorting
  • Searching
  • String Processing
  • Graph Problems
  • Combinatorial
  • Geometric
  • Numerical

We'll be doing lots of graph problems.

Analysis of Algorithms

  1. How good is it?
    • Time efficiency
    • Space efficiency
  2. Does a better one exist?
    • Lower bounds
    • Optimality
  3. Other characteristics
    • Simplicity
    • Generality

And now, some introductory problems.

While following along, note how:

  • Our definitions for algorithms must be unambiguous.
  • You can describe an algorithm in many ways.
  • You can solve a problem in many ways.
    • But some ways are faster than others.

Note on Unambiguity: Be thorough! Even the [range of input]{.underline} must be defined.

Problem: Greatest Common Divisor

Problem: Find gcd(m,n), the greatest common divisor of two nonnegative, nonzero integers $m$ and $n$.

Suppose gcd(60,24). We can figure out the GCD is 12 in our heads, but what about an algorithm to get there?

Approach 1: Consecutive Integer Checking

A naive brute-force approach where we let $t = min(m,n)$, and then:

  1. Divide $m$ by $t$, go to step 2 if remainder if 0.
  2. Divide $n$ by $t$, return t and stop if remainder is 0. Otherwise, go to step 3.
  3. Decrease $t$ by 1 and go to Step 2.

Approach 2: Euclid's Algorithm

Euclid's Algorithm is an efficient solution that is based on the repeated application of the equality:

$$ gcd(m,n) = gcd(n, m % n) $$

(Why this equality is true is irrelevant to us, just take it as a given)

Describing the Algorithm in English:

Apply the above equality repeatedly until the second parameter becomes zero. At this point the problem becomes trivial to solve (because $gcd(x,0) = x$).

Describing the Algorithm in Steps:

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

Describing the Algorithm in Pseudocode:

// GCD via Euclid's Algoritm
while n != 0 do
	r <- m % n
	m <- n
	n <- r
return m

Example: Application of Euclid's Algorithm

Q: Use Euclid's algorithm to solve gcd(60,24) in three steps.

A: $$ gcd(60,24) = gcd(24,12) = gcd(12,0) = 12 $$

Professor's Recommendation: It's better to write pseudocode last.

Problem: Finding Primes

For this problem, we're just going to skip ahead to the interesting solution.

Problem: How can you find all prime numbers (up to some given $n$) with an algorithm?

Key Property: It's easier to tell if a number isn't prime

  • Example: Half of all numbers are divisible by 2, a third of all numbers are divisible by 3, et cetera.
  • This property is exactly what the next algorithm uses.

Approach: Sieve of Eratosthenes

This algorithm finds all prime numbers less than or equal to a given interger $n$.

Describing the Algorithm in Steps:

  1. Create a list of consecutive integers from 2 through $n$.
  2. Initialize $p=2$ (the first prime number).
  3. Starting from $p$, enumerate its multiples by counting to $n$ in increments of $p$, and mark them in the list ($2p$, $3p$, $4p$, etc.);
  4. Find the first number greater than $p$ in the list that is not marked. If there's no such number, stop. Otherwise, let $p$ equal this new number (the next prime) and repeat from Step 3.

Describing the Algorithm in Pseudocode:

// Sieve of Eratosthenes

// Input: Integer n >= 2
// Output: List of primes that are <= n

// Generate list
for p <- 2 to n do A[p] <- p

// The sieve part
for p <- 2 to \lfloor\sqrt{n}\rfloor do
	// if p hasn't been eliminated...
	if A[p] != 0			
		// ... derive all non-primes ...
		j <- p * p		
		while j <= n do
			// ... and eliminate them 
			A[j] <- 0	
			j <- j + p

Example: Applying sieve on n=20

First, we generate this list:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

After the first cycle on $p=2$:

2 3   5   7   9    11    13    15    17    19

Next (and last) cycle on $p=3$:

2 3   5   7        11    13          17    19

After this, no more cycles are needed for our $n$.

  • For example, shaking the sieve on $p=4$ is useless because we already did $p=2$; and $p=5$ already goes past our $n$; so we stop here.