实验 Laboratory projects 共5次;迟交罚扣为10%/day;抄袭者0分 罔3人一组,各组自行分工(例如:按功能模块、按开 发过程等),各自工作量应相当,试验报告中必须写 明各自工作量 A通过e-mai提交,请在邮件标题写明班级学号及试验 I,并在文档末尾写明分工 @助教( Teaching assistant): e杜洪伟(dhw98426@126c0m) e潘东(pandong912agmail.com)
实验 (Laboratory Projects) 共 5 次；迟交罚扣为 10% /day；抄袭者0分； 3人一组，各组自行分工（例如：按功能模块、按开 发过程等），各自工作量应相当，试验报告中必须写 明各自工作量； 通过e-mail提交，请在邮件标题写明班级学号及试验 ID，并在文档末尾写明分工。 助教（Teaching Assistant）： ☺ 杜洪伟（dhw198426@126.com） ☺ 潘东 （pandong912@gmail.com）
CHAPTER 2 ALGORITHM ANALYSIS Definition) An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria (1)Input There are zero or more quantities that are externally supplied. (2)Output At least one quantity is produced. (3)Definiteness Each instruction is clear and unambiguous. (4)Finiteness If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after finite number of steps. (5) Effectiveness Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. It is not enough that each operation be definite as in (3); it also must be feasible
CHAPTER 2 ALGORITHM ANALYSIS 【Definition】An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria: (1) Input There are zero or more quantities that are externally supplied. (2) Output At least one quantity is produced. (3) Definiteness Each instruction is clear and unambiguous. (4) Finiteness If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after finite number of steps. (5) Effectiveness Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. It is not enough that each operation be definite as in(3); it also must be feasible
Note: A program is written in some programming language, and does not have to be finite(e.g. an operation system). An algorithm can be described by human languages, flow charts, some programming languages, or pseudo code I Example] Selection Sort: Sort a set of n> 1 integers in increasing order. From those integers that are currently unsorted, find the smallest and place it next in the sorted list. for (i=0; i<n; i++)t Examine list[i to list[n-1]and suppose that the smallest integer is at list[min]; Interchange list[ and list(min]; Sort= Find the smallest integer Interchange it with list[i
Note: A program is written in some programming language, and does not have to be finite (e.g. an operation system). An algorithm can be described by human languages, flow charts, some programming languages, or pseudocode. 〖Example〗 Selection Sort: Sort a set of n 1 integers in increasing order. From those integers that are currently unsorted, find the smallest and place it next in the sorted list. for ( i = 0; i < n; i++) { Examine list[i] to list[n−1] and suppose that the smallest integer is at list[min]; Interchange list[i] and list[min]; } Sort = Find the smallest integer + Interchange it with list[i]
81 What to Analyze Machine compiler-dependent run times Time space complexities machine compiler independent ° Assumptions: O instructions are executed sequentially 2 each instruction is simple, and takes exactly one time unit 3 integer size is fixed and we have infinite memory Typically the following two functions are analyzed: Tavo(n& TworstN--the average and worst case time complexities, respectively, as functions ofinput size N
§1 What to Analyze ➢ Machine & compiler-dependent run times. ➢ Time & space complexities : machine & compilerindependent. • Assumptions: instructions are executed sequentially each instruction is simple, and takes exactly one time unit integer size is fixed and we have infinite memory • Typically the following two functions are analyzed: Tavg(N) & Tworst(N) -- the average and worst case time complexities, respectively, as functions of input size N
[Example] Matrix addition void add (int all[ MAX SIze, int b][ MAX SIzE1, int CLI[ MAX SIZE, int rows, int cols for(i=0; i< rows; i++)/*rows+1*/ for(j=0; j< cols; j++)/*rows(cols+1)*/ c[i]j]=a[i[j]+bi]j]; /*rows. cols * T(rows, cols )=2 rows cols rows+ 1
〖Example〗 Matrix addition void add ( int a[ ][ MAX_SIZE ], int b[ ][ MAX_SIZE ], int c[ ][ MAX_SIZE ], int rows, int cols ) { int i, j ; for ( i = 0; i < rows; i++ ) for ( j = 0; j < cols; j++ ) c[ i ][ j ] = a[ i ][ j ] + b[ i ][ j ]; } /* rows + 1 */ /* rows(cols+1) */ /* rows cols */ T(rows, cols ) = 2 rows cols + 2rows + 1