1. Algorithms

A well-defined procedure:

• Input: instance of the problem
• Output: solution to the instance

The procedure must work for all instances of the problem.

Defining Algorithms

• English
• Pseudo-code
• Program
• Formal mathematical notation The further down you go, the more precise but less readable it gets.

Properties

• Correctness (for a defined set of inputs)
  • Don’t write clever code! Write correct code
• Scalability/Efficiency
  • Time, RAM, disk, CPU, power etc.
• Clarity
• Generality
  • Is it sufficient for it to work on a subset of problems? Then redefine the problem space
  • Is an optimal solution required, or does it just have to be good-enough?

Determining Correctness

Testing can not prove an algorithm is correct (unless you can test all cases): you can only prove it is incorrect. Only formal proofs can prove it. Not covered in the course.

Start with a reasonably precise statement of the problem and algorithm.

Then:

• Find failing cases
• Try proof by induction
  • Can you test every single case when the size is small?

Example: Robot Arm (Skiena 1.1)

Robot needs to place solder into $n$ points on a PCB. What is the shortest cycle tour that visits each point in the set $S$? This is the TSP, so an optimal solution cannot be found. Thus, heuristics need to be used.

Heuristics: greedy algorithm?

Example: Selecting Jobs (Skiena, 1.2)

Multiple movies that need to be filmed, need to maximize number of movies. Set $I$ of $n$ intervals on the line.

Heuristics: start with the shortest movie? Start with the first available movie?

Look for counter examples that show that the heuristic is incorrect:

• Think small
• Think exhaustively
• Find weaknesses
  • Ties
  • Extremes

Proof by induction

def sum(n):
    s = 0
    for i in range(1, n + 1):
        s += i
    return s

Assume that the loop works up to $k$. Thus, the loop must work up to when calculating the sum for $k+1$.

Insertion sort

After $n$ iterations of the outer for loop, the sub array, $[0, n)$ is sorted. Now, you only need to prove that it is able to sort the $n$th element correctly.