Algorithms Analysis and Design Lec1,2 PDF

Algorithm An algorithm is a set of rules for solving a problem or performing a task. An algorithm is a finite set of precise instructions for performing a computation or for solving a problem. Characteristics: Should have a clear starting and ending point. Clear, unambiguous, finite st...

Algorithm An algorithm is a set of rules for solving a problem or performing a task. An algorithm is a finite set of precise instructions for performing a computation or for solving a problem. Characteristics: Should have a clear starting and ending point. Clear, unambiguous, finite steps with a defined input and output Algorithms can be expressed in natural language, pseudocode, or programming languages. Example find the maximum number in a list: 1. Start 2. Initialize max to the first element of the list. 3. For each element num in the list: a. If num is greater than max, update max to num. 4. End Pseudocode Pseudocode is A simplified, high-level representation of an algorithm that uses a mix of natural language and programming syntax. Characteristics: It’s not bound by specific programming language syntax making it easier to read and write. Making it easy to understand １  Focuses on logic rather than syntax Example find the maximum number in a list: FUNCTION findMax(list): max ← list FOR each num IN list: IF num > max THEN max ← num RETURN max Flowchart A flowchart is a visual representation of an algorithm using shapes and arrows to depict the flow of control. Characteristics: It uses standardized symbols (like ovals for start/end, rectangles for processes, diamonds for decisions) to show the steps and the order in which they occur. Flowcharts are useful for visualizing complex processes. ２ Summary Algorithm: A clear set of steps to solve a problem. Pseudocode: A text-based version of an algorithm that is easier to read and understand. Flowchart: A visual representation that illustrates the steps and flow of the algorithm Suppose, for example, we have four algorithms to solve a problem P: A1, A2, A3, and A4, and each of them has an execution time of T1, T2, T3, and 4. Which one will you choose? Of course, we will choose the shortest execution time How do we Compare algorithms? 1. Compare execution times? Experimental Studies Write a program implementing the algorithm. Run the program with inputs of varying size and composition. Use a method like System. currentTimeMillis to get an accurate measure of the actual running time. Plot the results. ３  Not good: a) It is necessary to implement the algorithm, which may be difficult. b) Results may not be indicative of the running time on other inputs not included in the experiment. c) To compare two algorithms, the same hardware and software environments must be used and the same inputs. 2. Count the number of statements executed? Not good: number of statements vary with the programming language as well as the style of the individual programmer. Algorithm 1 Algorithm 2 arr = 0; for(i=0; i