Algorithms

Overview

An effective method (or algorithm) is a finite-time, deterministic procedure for solving a problem of a specific class. This is a term of art; it has no agreed upon definition.

Computable Functions

A function $f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$ is computable if some Turing machine $M$, on every input $w$, halts with just $f(w)$ on its tape. Such a function is polynomial time computable if the given Turing machine runs in polynomial time.

Incremental

An incremental approach to algorithm design involves acting on a single element at a time.

Divide-and-Conquer

The divide-and-conquer approach breaks problems into subproblems that are easier to solve. They generally involve three distinct steps:

1. Divide the problem into one or more subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively.
3. Combine the subproblem solutions to form a solution to the original problem.

Dynamic Programming

Dynamic programming refers to the general technique of simplifying a problem by breaking it down into simpler subproblems in a recursive manner. Unlike in divide-and-conquer, its expected subproblems overlap. That is, subproblems have shared subsubproblems.

Dynamic programming is typically applied to optimization problems, hence its name. We say a problem exhibits optimal subtructure if optional solutions to the problem incorporate optimal solutions to related subproblems, solved independently.

Top-Down

In top-down dynamic programming, a procedure is written recursively in a natural manner, but modified so the result of each subproblem is memoized.

Bottom-Up

In bottom-up dynamic programming, a procedure is written by first solving subproblems of smaller "size" first and then solving slightly larger problems using the saved results of the smaller subproblems.

Greedy Algorithm

A greedy algorithm is an algorithm that makes locally optimal choices in a given moment. This may or may not end up with a globally optimal solution, unlike in the case of dynamic programming.

The greedy-choice property refers to the ability to assemble a globally optimal solution by making locally optimal choices.