This is an old revision of the document!
Table of Contents
Chapter 2
This chapter introduces us the basic mathematical tools needed for algorithm analysis.
Section 1: Computational Tractability
This section introduces several ways of defining “efficiency”. The first way is the literal meaning of “efficiency”-it runs quickly. The second way is defined through comparison: if an algorithm can be designed to run faster than the most basic “brute-force search” way, then it is efficiency. The third way is that if an algorithm can be run in linear time, then it is efficient. Then the author explains why the third way is the most realistic way of defining efficiency. This section gives an evolutionary view of the concept of efficiency. It helps me understand and remember the actual definition of efficiency. Though there are many overlaps with the lecture. So the readable score is 6.
Section 2: Asymptotic Order of Growth
This section introduces the concept of asymptotic order of growth. First, it defines the big O, little O, and tight O. Then it shows several basic properties of the O notations as well as gives out detailed proofs. Last, it lists several common functions as examples to describe their asymptotic bounds. In class, we especially emphasized the concept of asymptotic order of growth. Thus the key points are not unfamiliar. However, due to time constrain, we skipped much of the detailed proof, which I think is not very hard to pursue, but good to go over anyway. So the readable score is also 6.
Section 3: Implementing the Stable Matching Algorithm Using Lists and Arrays
This section introduces the advantages and disadvantages of lists and arrays in implementations. First, it introduces implementations by arrays: advantage lies in to access a certain element; disadvantage is the fixed size. Second, the section talks about implementation of lists, particularly linked list: it has constant time in deleting and inserting (provided that the element's position is known); but. The third way is that if an algorithm can be run in linear time, then it is efficient. Then the author explains why the third way is the most realistic way of defining efficiency. This section gives an evolutionary view of the concept of efficiency. It helps me understand and remember the actual definition of efficiency. Though there are many overlaps with the lecture. So the readability score is 6.
