《算法分析与设计ALgoD&ALectureNotesW1章节》由会员分享，可在线阅读，更多相关《算法分析与设计ALgoD&ALectureNotesW1章节（110页珍藏版）》请在金锄头文库上搜索。
1、Syllabus,Chapter 1 Introduction Chapter 2 Complete Development of an Algorithm Chapter 3 Sorting，Searching and Matching Algo.s Chapter 4 Divide and Conquer Chapter 5 Dynamic Programming Chapter 6 Greedy Algorithms Chapter 7 Backtracking Chapter 8 Branch and Bound Chapter 9 NP Completeness (& Lower B
2、ound Argument) Chapter 10 Approximation Algorithms Chapter 11 Randomized Algorithm Chapter 12 Heuristics: GA, NS, SA, TS, ACO, PSO,Sorting,Bubble sort Linear insertion sort Quicksort Shellsort Heapsort Linear probing sort Merge sort Bucket sort Radix sort Hybrid methods Treesort,Balanced merge sort
3、Cascade merge sort Polyphase merge sort Oscillating merge sort External quicksort List merging Array merging Minimal-comparison merging,Searching,Sequential search Basic Sequential search Self-organizing Sequential search Optimal Sequential search Jump search Sorted array search Binary search Interp
4、olation search Interpolation-Sequential search Binary tree search B-trees Index and indexed sequential files Digital trees Multidimensional search Quad trees K-dimensional trees,Hashing Uniform probing hashing Random probing hashing Linear probing hashing Double hashing Quadratic hashing Ordered has
5、hing Reorganization for Uniform probing: Brents algorithm Reorganization for Uniform probing: Binary tree hashing Optimal hashing Direct chaining hashing Separate chaining hashing Coalesced hashing Extendible hashing Linear hashing External hashing using minimal internal storage,Design and Analysis
6、of Algorithms,Introduction,Algorithms,An algorithm is a set of instructions for performing a task. It must have the following features: Each instruction must be clear and executable. The next step must be determinate. The process must terminate. The goal must be achieved.,Examples of algorithms are:
7、 a recipe. a musical score. a knitting pattern.,Features of Algorithms,Each algorithm has an author and a static form. Upon execution by a processor, we have a dynamic process. The processor for a recipe is a cook, for a musical score is a performer.,Algorithms: Declarations,Objects are manipulated.
8、 Programs operate on data. Instructions may be preceded by a declaration of the objects involved. This is true of recipes, model aeroplane assembly It is also true of many modern programming languages.,Algorithms: Decisions,Instructions are executed sequentially. Decisions may be required depending
9、on the current situation (conditional instruction).,Algorithms: Repetition,Some parts of the algorithm may be executed many times (iteration). The number of repetitions may be specified directly (knit five rows) or by testing for a desired state (cook until the surface is light brown).,Algorithms: P
10、rocedures,A group of instructions may be replaced by a single instruction. The group is called a procedure or method It is actually a sub-algorithm (solves part of our problem). We shall see the great importance of being able to solve small parts of problems as sub-problems.,Program = Algorithm + Da
11、ta,A program is a collection of algorithms expressed in a language which a computer can use. Before constructing a program, we must be able to answer the following two questions: What processing is required? What data are to be processed?,The program often will input some required values, process th
12、ese in the correct manner and then output the results to the user.,Algorithm Classifications and Course Coverage,(Non-) Numerical Strategically Hardness, complexity Exactness (Non-) Deterministic Application Orientated ,Why analyzing an algorithm?,Why,We analyze algorithms with the intension of Impr
13、oving them And for Choosing among several available for a problem,How to analyze an algorithm?,Analyzing an algorithm,We will use the following criteria: Correctness Amount of work done Amount of space used Simplicity Optimality,Correctness,-An algorithm is correct if when given a valid input it com
14、putes for a finite amount of time and produces the right answer. This definition is helpful if we know what the valid inputs are and what “the right answer” is. Thus showing that an algorithm is correct means making a precise statement about what result it is to produce when given certain specified
15、inputs, and then proving the statement.,对于每一个合法输入，算法都会在有限的时间内输出一个满足要求的结果,Correctness,There are two aspects to an algorithm: the problem solution method and the sequence of instructions for carrying it out. Establishing the correctness of the method and/or formulas used may require a long sequence of
16、 lemmas and theorems about the objects on which the algorithm works (for example, graphs, permutations, matrices).,Correctness,If an algorithm is fairly short and straightforward, we generally use some very informal (and indescribable) means of convincing ourselves that the various parts do what we expect them to do. We may check some details carefully (e.g., initial and final values of loop counters), and hand-simulate the algorithm on a few small examples. None of this proves
