RAM model of Computation

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

• Describe what is meant by efficiency of algorithms.
• Explain the purpose of using the RAM model of computation for the analysis of algorithms.
• Identify what counts as a "step" in an algorithm.
• Explain how algorithm runtime is calculated under the RAM model of computation.
• Describe runtime by counting up the number of RAM instructions for a given code snippet.
• Recognize the importance of input size on evaluating algorithm efficiency.
• Know that what we choose to call the size of input can vary from problem to problem.
• Differentiate between the best-case vs the worst-case analysis.
• Explain why we focus on the worst-case analysis.
• Express the number of steps for a given code segment as a function of the input size in the worst-case scenario.
• Appreciate that it can be very difficult to work out precisely the exact number of steps (RAM instructions) in an algorithm.

This chapter does not have a starter/solution code.