Introduction to Algorithms September 3, 2003Massachusetts Institute of Technology 6.046J/18.410JProfessors Shafi Goldwasser and Silvio Micali Handout 5Course Objectives and OutcomesCourse objectivesThis course introduces students to the analysis and design of computer algorithms. Upon comple-tion of this course, students will be able to do the following:Analyze the asymptotic performance of algorithms.Demonstrate a familiarity with major algorithms and data structures.Apply important algorithmic design paradigms and methods of analysis.Synthesize efficient algorithms in common engineering design situations.Course outcomesStudents who complete the course will have demonstrated the ability to do the following:1. Argue the correctness of algorithms using inductive proofs and loop invariants.2. Analyze worst-case running times of algorithms using asymptotic analysis. Compare theasymptotic behaviors of functions obtained by elementary composition of polynomials, ex-ponentials, and logarithmic functions. Describe the relative merits of worst-, average-, andbest-case analysis.3. Analyze average-case running times of algorithms whose running time is probabilistic. Em-ploy indicator random variables and linearity of expectation to perform the analyses. Reciteanalyses of algorithms that employ this method of analysis.4. Explain the basic properties of randomized algorithms and methods for analyzing them.Recite algorithms that employ randomization. Explain the difference between a randomizedalgorithm and an algorithm with probabilistic inputs.5. Analyze algorithms using amortized analysis, when appropriate. Recite analyses of simplealgorithms that employ this method of analysis. Describe different strategies for amortizedanalysis, including the accounting method and the potential method.6. Describe the divide-and-conquer paradigm and explain when an algorithmic design situationcalls for it. Recite algorithms that employ this paradigm. Synthesize divide-and-conqueralgorithms. Derive and solve recurrences describing the performance of divide-and-conqueralgorithms.2Handout 5: Course Objectives and Outcomes7. Describe the dynamic-programming paradigm and explain when an algorithmic design sit-uation calls for it. Recite algorithms that employ this paradigm. Synthesize dynamic-programming algorithms and analyze them.8. Describe the greedy paradigm and explain when an algorithmic design situation calls forit. Recite algorithms that employ this paradigm. Synthesize greedy algorithms and analyzethem.9. Explain the major algorithms for sorting. Recite the analyses of these algorithms and thedesign strategies that the algorithms embody. Synthesize algorithms that employ sorting as asubprocedure. Derive lower bounds on the running time of comparison-sorting algorithms,and explain how these bounds can be overcome.10. Explain the major elementary data structures for implementing dynamic sets and the analysesof operations performed on them. Recite algorithms that employ data structures and howtheir performance depends on the choice of data structure. Synthesize new data structuresby augmenting existing data structures. Synthesize algorithms that employ data structures askey components.11. Explain the major graph algorithms and their analyses. Employ graphs to model engineeringproblems, when appropriate. Synthesize new graph algorithms and algorithms that employgraph computations as key components, and analyze them.12. Demonstrate a familiarity with applied algorithmic settings — such as computational ge-ometry, operations research, security and cryptography, parallel and distributed computing,operating systems, and computer architecture — by reciting several algorithms of impor-tance to different