Algorithm 重點筆記

An algorithm is an ordered set of unambiguous,executable stepsthat defines a terminating process.

A collection of primitives constitutes a programming language.

Polyas Problem Solving Steps                                                                      1.Understand the problem.                                                                           2.Devise a plan for solving the problem.                                                      3.Carry out the plan.                                                                                      4.Evaluate the solution for accuracy and its potential as a tool for solving other problems.  

Getting a Foot in the  Door                                                                                                             Try working the problem backwards
Solve an easier related problem
– Relax some of the problem constraints
– Solve pieces of the problem first (bottom up methodology)
Stepwise refinement: Divide the problem into
smaller problems (top-down methodology)   

Sorting, a process to order data, is a basic algorithm.

Selection sort, bubble sort, and insertion sort are
commonly used sorting algorithms.

Searching, a process to locate a target in a list of data,
is a basic algorithm.

Sequential search is used for unordered lists.

Binary search is used for ordered lists.

Recursion                                                                                                       The execution of a procedure leads to another
execution of the procedure.                                                                                 Multiple activations of the procedure are
formed, all but one of which are waiting for
other activations to complete.

Algorithm  Efficiency                                                                                                              Measured as number of instructions executed
Big theta notation: Used to represent efficiency
classes
– Example: Insertion sort is in Θ(n2)
Best, worst, and average case analysis

Dynamic Programming vs. Divide-and-Conquer                                               Similarity
• The instance of a problem is divided into smaller instances.
– Differences
• Divide-and-Conquer
– Top-Down
– Blindly solves the divided instances by using recursion.
– Inefficient when the divided instances are related.
– Inefficient when the divided instances are almost as large as the
original instance.
• Dynamic Programming
– Bottom-Up (solve small instances first, store the results, and later,
whenever we need a result, look it up instead of recomputing it.)
– Programming (the use of an array in which a solution is constructed.)

The Greedy Approach                                                                                                                                                             Philosophy
– A greedy algorithm arrives at a solution by making a
sequence of choices, each of which simply looks the best at
the moment (locally optimal).
• Like Dynamic Programming, Greedy Algorithms are
often used to solve Optimization Problems.
– However, Greedy Algorithms do not guarantee an optimal
solution.
• No Division is required.