Chapter 1. Introduction to Algorithm Design
- There are three desirable properties for a good algorithm. We seek algorithms that are correct and efficient, while being easy to implement.
1.1 Robot Tour Optimization
Problem: Robot Tour Optimization
Input: A set S of n points in the plane.
Output: What is the shortest cycle tour that visits each point in the set S?
1. No matter what you do to pick the first point, the nearest-neighbor rule is doomed to work incorrectly on certain point sets. See the figure below.
2. A different idea might be to repeatedly connect the closest pair of endpoints whose connection will not create a problem, such as premature termination of the cycle. https://stackoverflow.com/questions/7216755/what-is-the-meaning-of-from-distinct-vertex-chains-in-this-nearest-neighbor-al/7216814#comment15114654_7216814
3. Neither of the above two are solutions to the problem.

The quest for an efficient algorithm to solve this problem, called the traveling salesman problem (TSP).
1.2 Selecting the Right Jobs
Problem: Movie Scheduling Problem
Input: A set I of n intervals on the line.
Output: What is the largest subset of mutually non-overlapping intervals which can be selected from I?
- Eearlist job first (Not a correct solution)
EarliestJobFirst(I)
Accept the earlest starting job j from I which does not overlap any previously accepted job, and repeat until no more such jobs remain.2. Shortest job first (Not a correct solution)
ShortestJobFirst(I)
While (I != ∅) do
Accept the shortest possible job j from I.
Delete j, and any interval which intersects j from I.3. Exhaustive Scheduling (Correct but extremely slow)
ExhaustiveScheduling(I)
Test all 2^n subsets of intervals from I, and return the largest subset consisting of mutually non-overlapping intervals.If a set contains ’n’ elements, then the number of subsets of the set is 2^n.
4. Optimal Scheduling
OptimalScheduling(I)
While (I != ∅) do
Accept the job j from I with the earliest completion date.
Delete j, and any interval which intersects j from I.1.3 Reasoning about Correctness
The three most common forms of algorithmic notation are (1) English, (2) pseudocode, or (3) a real programming language.
1.4 Modeling the Problem
Combinatorial Objects
Properties of common structures and all of the below are recursive objects.
- Permutations — which are arrangements, or orderings, of items. For example, {1, 4, 3, 2} and {4, 3, 2, 1} are two distinct permutations of the same set of four integers. Permutations are likely the object in question whenever your problem seeks an “arrangement,” “tour,” “ordering,” or “sequence.”
- Subsets — which represent selections from a set of items. For example, {1, 3, 4} and {2} are two distinct subsets of the first four integers. Order does not matter in subsets the way it does with permutations, so the subsets {1, 3, 4} and {4, 3, 1} would be considered identical. Subsets are likely the object in question whenever your problem seeks a “cluster,” “collection,” “committee,” “group,” “packaging,” or “selection.”
- Trees — which represent hierarchical relationships between items. Trees are likely the object in question whenever your problem seeks a “hierarchy,” “dominance relationship,” “ancestor/descendant relationship,” or “taxonomy.”
- Graphs — which represent relationships between arbitrary pairs of objects. Graphs are likely the object in question whenever you seek a “network,” “circuit,” “web,” or “relationship.”
- Points — which represent locations in some geometric space. Points are likely the object in question whenever your problems work on “sites,” “positions,” “data records,” or “locations.”
- Polygons — which represent regions in some geometric spaces. Polygons and polyhedra are likely the object in question whenever you are working on “shapes,” “regions,” “configurations,” or “boundaries.”
- Strings — which represent sequences of characters or patterns. Strings are likely the object in question whenever you are dealing with “text,” “charac- ters,” “patterns,” or “labels.”
