# 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.