# 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**

- 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”.
- 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**