Lab Book — Week 3

Lab

Download pic from Slack: take photo — upload to slack — open the picture — find “screenshot” — select area to grab — save to desktop as “mugshot” — drag “mugshot” to code1161 folder to replace the origin “mugshot” — add, commit and push

Q&A

  1. What’s the difference between “print” and “return”? — “Print” is for human use and “return” is for computer use. Things printed can only be seen by human but can’t be used by computer. Things returned can be called by computer in other functions. If there’s no “return” (or “yield”) it will return “None”.
  2. Can I have multiple returns in a function? You can, but better to minimize the number of returns in each routine. You can use a tuple/a dictionary/a list/a class to return multiple values. http://stackoverflow.com/questions/354883/how-do-you-return-multiple-values-in-python

Algorithms

1. Algorithm is a set of steps for a computer program to accomplish a tank. e.g. When do shopping, I write a shopping list first, then divide the items on the list by shops. If no extremely heavy stuff to buy, go to the furthest shop first to the closest, otherwise buy the heavy stuff at last.

2–1. Use binary search algorithm in the number guessing game instead of linear search. Pseudocode description: input; output; variables; initial values; intermediate steps; simplification.

2–2. index: the position of an element in an array

(Almost lost everything here by pressing a key that I don’t remember then it jumped to the home page…Luckily it’s auto saved and I can just go back to the previous page :D)

2–3. For an array of length 2n, the first guess cuts the reasonable portion of the array down to size n. Therefore for an array of length x, we just need base-2 logarithm of x (=i) guesses.

3–1. The running time of an algorithm depends on how long it takes a computer to run the lines of code of the algorithm, which include: a) the size of its input; b) the rate of growth of the running time, which means how fast a function grows with the input size.

3–2. Asymptotic Notation

Big-θ (Big-Theta) notation:

Θ(1)
Θ(lgn)
Θ(n)
Θ(nlgn)
Θ(n²)
Θ(n^​2​​ lgn)
Θ(n^​3​​ )
Θ(2^​n​​ )

Big-O notation: a boundary from only above

Big-Ω (Big-Omega) notation: without upper boundary

Show your support

Clapping shows how much you appreciated xueqing.lu’s story.