Ting

This seems like a great service:

https://ting.com

Refreshing pricing plans.

Fender

A big animal (dog?), sadly, leaped over the median this evening on our way home and collided with our car. I think it struck a glancing blow, so I hope everything turns out all right...it was not a place to stop, unfortunately, and in the dark of night I did not get a good sense of what fully happened. I only remember something leaping over a median as we drove uphill...thinking, ah, I hope that represents a garbage bag...seeing the leaping outstretched legs, and a glancing thud.

Unfortunately for our car, the animal shattered the driver-side turn-signal cover and dented and bent the driver-side fender. The driver-side door will not open, so I will likely need to get a sense of how to repair it in the near future. The headlamp I can manage easily enough on my own.

UPDATE: visited Pick 'n Pull today and purchased a replacement driver-side turn signal assembly. Some other car repairs today: replaced the driver-side main bulb; swapped out wiper blades; re-installed cabin kick panels; replaced worn clutch pedal cover; sprayed lithium grease on the door hinges and automatic seat belt tracks; cleaned the oxidized plastic of the headlamp assemblies; added door ajar switch cover to the passenger side door. I also straightened out the driver-side fender near the door so I could open the door again. Still have a salad-plate sized dent in the driver-side fender, but I can wait on that for a moment until I have some time to take it in to a body shop. I briefly considered visiting all four local Pick 'n Pull locations today, but decided I did not want to spend the several hours it would take to do so.

Also: the car passed 225,000 miles today  : o )

Reminder: double-check the last time I changed the timing belt : o |

UPDATE: the nice thing about keeping an AUTO binder of all repair work: I last changed the timing belt in July 2010, at mileage 188,000. So, will have to change when it gets to about 250,000 miles.

Introduction to Algorithms, 3rd edition - Chapter 2

Switching to the third edition, just because.

Exercises

2.1-1  Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array  = < 31, 41, 59, 26, 41, 58 >

Note: solution produced via free tool LucidChart

2.1-2  Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.

INSERTION-SORT(A)
1. for j = 2 to A.length
2.   key = A[j]
3.   // Insert A[j] into the sorted sequence A[1..j - 1].
4.   i = j - 1
5.   while i > 0 and A[i] < key
6.     A[i + 1] = A[i]
7.     i = i - 1
8.   A[i + 1] = key

2.1-3 Consider the searching problem:

Input: A sequence of n numbers A = < a1, a2, ..., an > and a value v.
Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove your algorithm is correct.

LINEAR-SEARCH(A, v)
1. i = 1
2. while i <= A.length
3.   if v == A[i]
4.     return i
5.   i = i + 1
6. return NIL 


Loop invariant: At the start of each iteration of the while loop of lines 2-5, the algorithm has yet to find value v in subarray A[1..i - 1], which represents the searched elements of array A.

Initialization: We start by showing the loop invariant holds before the first loop iteration, when index i = 1. Since the algorithm has yet to begin searching for value v, subarray A[1..i - 1] correctly consists of zero elements and therefore cannot contain value v. Therefore, the loop invariant holds prior to the first iteration of the loop.

Maintenance: Next, we tackle the second property: showing each iteration maintains the loop invariant. The body of the while loop tests whether value v equals array element A[i] (line 3). If so, it exits with an output of index i. Otherwise, incrementing i for the next iteration of the while loop preserves the loop invariant, as the algorithm will now have fruitlessly searched subarray A[1..i - 1] for value v.

Termination: Finally, we examine what happens when the loop terminates. Condition i > A.length = n causes the while loop to terminate. Since each loop iteration increases i by 1, we must have i = n + 1 at that time. Substituting n + 1 for i in the wording of the loop invariant, we have the subarray A[1..n] consisting of the searched elements of array A. Observing subarray A[1..n] represents the entire array, we conclude v does not exist in A. At this point, the algorithm returns the special value NIL. Hence, the algorithm is correct.

2.1-4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n + 1)-element array C. State the problem formally and write pseudocode for adding the two integers.

Input: A sequence of n binary numbers A = < a1, a2, ..., an > and B = < b1, b2, ..., bn >, representing binary integers A and B, with binary numbers a1 and b1 representing the least-significant bits of each sequence, respectively

Output: A sequence of n + 1 binary numbers C = < c1, c2, ..., cn+1 > representing the sum of binary integers A + B, with binary number c1 representing the least-significant bit

BINARY-SUM(A, B, C)
1.  carry = 0
2.  for i = 1 to A.length
3.    if (A[i] + B[i] + carry) == 3
4.      carry = 1
5.      C[i] = 1
6.    elseif (A[i] + B[i] + carry) == 2
7.      carry = 1
8.      C[i] = 0
9.    elseif (A[i] + B[i] + carry) == 1
10.     carry = 0
11.     C[i] = 1
12.   else
13.     carry = 0
14.     C[i] = 0
15. C[i] = carry

2.2-1 Express the function n^3 / 1000 - 100n^2 - 100n + 3 in terms of Θ-notation

Θ(n^3)

2.2-2 Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n - 1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n - 1 elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ-notation.

SELECTION-SORT(A)
1.  for i = 1 to A.length - 1
2.    min_index = i
3.    // Find the smallest number in unsorted subarray A[i + 1..n]
4.    for j = i + 1 to A.length
5.      if A[j] < A[min_index]
6.        min_index = j
7.    // Exchange current and smallest unsorted element
8.    key = A[i]
9.    A[i] = A[min_index]
10.   A[min_index] = key


Loop invariant: At the start of each iteration of the for loop of lines 1-10, the subarray A[1..i - 1] consists of the i - 1 smallest elements of A, in sorted ascending order.

It only needs to run for the first n - 1 elements of A because upon termination, index i will equal (A.length - 1) + 1 = n. The loop invariant guarantees subarray A[1..n - 1] will consist of the n - 1 smallest elements of A in sorted ascending order, which implies the remaining original element not only resides in A[n], but it also represents the nth smallest element of A.

Best and worst case: SELECTION-SORT(A) performs the same, in terms of Θ-notation, regardless of input. For example, the algorithm executes the same number of steps with a sorted or reverse-sorted array as input.

The algorithm runs in Θ(n^2): The outer loop takes n - 1 iterations. The inner loop takes

iterations. Together, both outer and inner take

where c equals the number of incidental, non-comment lines of code in SELECTIOTN-SORT. This simplifies to

which equals a running time of Θ(n^2).

2.2-3 Consider linear search again (see 2.1-3). How many elements of the input sequence need to be checked on the average, assuming the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Θ-notation? Justify your answers.

On the average, assuming the element being searched for is equally likely to be any element in the array, LINEAR-SEARCH(A, v) will check the i-th element of input sequence

A.length - (i - 1) 

times. For example, if A.length == 100 and we call LINEAR-SEARCH(A, v) 100 times with the same inputs, it will, on the average, check element #1 100 times, element #2 99 times, element #3 98 times, and so forth, checking element #100 only 1 time. So, on average, we will check

(A.length + A.length-1 + A.length-2 + ... + 1) / A.length

or

So, on the average, assuming the element being searched for is equally likely to be any element in the array, LINEAR-SEARCH(A, v) will check

elements of the input sequence, or a little over one-half of all elements.

In the worst case, when value v matches the last element in A (or matches no elements in A), LINEAR-SEARCH(A, v) will check all elements in A.

Therefore, both on the average and in the worst case, LINEAR-SEARCH(A, v) runs in Θ(n) time. As n represents the leading term in each case, given large enough array sizes, it dominates the order of growth calculation.

2.2-4 How can we modify almost any algorithm to have a good best-case running time?

We can modify almost any algorithm to have a good best-case running time by ensuring it runs in constant time for at least one input.

2.3-1

Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A = <3, 41, 52, 26, 38, 57, 9, 49>

Note: solution produced via free tool LucidChart

2.3-2

Rewrite the MERGE procedure so it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.

MERGE(A, p, q, r)
1.   nsub1 = q - p + 1
2.   nsub2 = r - q
3.   let L[1..nsub1] and R[1..nsub2] be new arrays
4.   for i = 1 to nsub1
5.     L[i] = A[p + i - 1]
6.   for j = 1 to nsub2
7.     R[j] = A[q + j]
8.   i = 1
9.   j = 1
10.  k = 1
11.  while nsub1 > 0 and nsub2 > 0
12.    if L[i] <= R[i]
13.      A[k] = L[i]
14.      i = i + 1
15.      k = k + 1
16.      nsub1 = nsub1 - 1
17.    else A[k] = R[j]
18.      j = j + 1
19.      k = k + 1

20.      nsub2 = nsub2 - 1

21.  if nsub1 > 0

22.    do

23.      A[k] = L[i]

24.      k = k + 1

25.      i = i + 1

26.      nsub1 = nsub1 - 1

27.    while nsub1 > 0

28.  else

29.    do\
30.      A[k] = R[j]
31.      k = k + 1
32.      j = j + 1
33.      nsub2 = nsub2 - 1
34.    while nsub2 > 0

2.3-3

Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

is T(n) = n lg n (where lg = log base 2).

Base case: Let n = 2. Then T(n) = 2, which equals T(n) = n lg n, as 2*log2(2) = 2*1 = 2.

Inductive step: Assuming T(n) holds, for some unspecified value of n where n =  and k > 1, we must show T(2n) holds, as 2n represents the next valid input. In this case, .

We want to show

This simplifies to 

Since we assume T(n) holds, we substitute in n lg(n) for T(n), which results in 

Via associative and distributive properties, this simplifies to

Our proof only concerns cases in which n represents a multiple of 2. Specifically, the case in which . Substituting  for 2n and  for n allows us to rewrite the formula as

Simplifying via logarithmic identify  reduces this to:

thereby showing inductive step T(2n) holds.

Since both the basis and the inductive step have been proved, we have therefore proved T(n) holds for all n where n =  and k >= 1. Q.E.D.

2.3-4

We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n], we recursively sort A[1..n - 1] and then insert A[n] into the sorted array A[1..n - 1]. Write a recurrence for the running time of this recursive version of insertion sort.


INSERTION-SORT(A, n)
1.  if n > 2
2.    INSERTION-SORT(A, n - 1)
3.  INSERT(A, n - 1, A[n])

INSERT(A, sorted_end, el)
1.   // Insert el into the sorted sequence A[1..sorted_end].
2.   // Assume total buffer equals A[1..sorted_end + 1], with
3.   // el initially at A[sorted_end + 1]
4.   i = sorted_end 
5.   while i > 0 and A[i] > el
6.     A[i + 1] = A[i]
7.     i = i - 1
8.   A[i + 1] = el

As with the non-recursive insertion sort, a reverse-sorted array represents the worst-case scenario, while a sorted array represents the best-case scenario.

2.3-5

Referring back to the searching problem (see 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue  represents the worst-case running time of binary search.

The iterative case:


BINARY-SEARCH(A, v)
1.  l = 1
2.  r = A.length
3.  while l != r
4.    mid = l + CEILING((r - l) / 2)

5.    if v == A[mid]
6.      return mid7.    elseif v > A[mid]
8.      l = mid
9.    else
10.     r = mid
11. return NIL  




The recursive case:




BINARY-SEARCH(A, v)

1.  return SEARCH(A, v, 1, A.length)


SEARCH(A, v, l, r)

1.  if l == r

2.    return NIL

3.  else

4.    mid = l + CEILING((r - l) / 2)

5.    if v == A[mid]
6.      return mid7.    elseif v > A[mid]
8.      return SEARCH(A, v, mid, r)
9.    else
10.     return SEARCH(A, v, l, mid)

We can express the recursive case with recurrence:

where the constant c represents the time required to solve problems of size 1.

Note: solution produced via free tool LucidChart

We can construct a recursion tree to see why BINARY-SEARCH runs in worst-case lg n time. In (a) and (b), above, we see T(n) progressively expanding. In (c), we see the fully expanded tree, which has lg n + 1 levels and each level contributes a total cost of c. The total cost, therefore, is c lg n, which is .

2.3-6

Observe that the while loop of lines 5-7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[1..j - 1]. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to ?

INSERTION-SORT(A)
1. for j = 2 to A.length
2.   key = A[j]
3.   // Insert A[j] into the sorted sequence A[1..j - 1].
4.   i = j - 1
5.   while i > 0 and A[i] < key
6.     A[i + 1] = A[i]
7.     i = i - 1
8.   A[i + 1] = key  ,'''''''''''''''''''

Previous - Chapter one
Next - Chapter three

Free digital copy of movie after viewing at the theater

Why not offer people a free digital copy of the movie they just watched at the theater?

Radio songs

Heard on KPFA 94.1 FM out of Berkeley, CA on Saturday, Jan 5:

ORQUESTA LA MODERNA TRADICION's "Juarez" from their album Goza Con Migo on the Outman Records label.

Heard on KDVS 90.3 FM out of Davis, CA on Wednesday, Jan 9:

Julia Holter - Marienbad
http://www.youtube.com/watch?v=QukVgY8I_nA

Dash camera

Thinking about getting one, if for nothing else than the beautiful sights of driving in California.

http://www.amazon.com/Hdvr-150-Accident-Camera-Video-Recorder/dp/B005GTKY24/ref=cm_cr_pr_product_top

Installing Ubuntu to Dell Inspiron 15r

Lots of fun (ha ha, joking) this evening installing a copy of Ubuntu to a Dell Inspiron 15r via USB:

• USB partition must be FAT16 to avoid boot failure
• Use 1GB (of 8GB) partition to avoid weird "out of disk space" error when writing the ISO to the USB
• Have to reinstall GRUB after the install

Oy.

Introduction to Algorithms, 2nd edition - Chapter 1

Notes

1.1 Algorithms 

Algorithm = Inputs -> Outputs (Specific procedure)

Computational problem = desired I/O relationship (general)...an algorithm defines a specific relationship

Nondecreasing = same or greater

Define computational problem by specifiying I/O

Instance = One input

Correct algorithm = halts on all inputs with correct output

Correct algorithm solves a problem

Specification = Precise description of guts

"Incorrect algorithms can sometimes be useful"

Problems solved by algorithms:

• Determining sequences (Human Genome Project)
• Finding good routes; quickly find Internet pages
• Negotiate and exchange electronic commerce
• Allocate scarce resources

2-D -> 3-D mapping?

Given = inputs

Wish to find = outputs

Two common characteristics of algorithms:

1. Many candidate solutions
2. Practical applications

Data structure = store and organize data to facilitate access and modifications

Problems without published algorithms

Efficiency

Interesting NP-complete properties:

1. it is unknown whether or not efficient algorithms exist
2. If an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them
3. Several NP-complete problems are similar, but not identical, to problems for which we do not know of efficient algorithms

Real world NP-complete problems arise in real world

Traveling salesman

1.2 Algorithms as a technology

Terminates with correct answer

What if infinite speed and free memory?

Good software engineering practice = well designed and documented

Bounded resources (like computing time) should be used wisely

Algorithms are greater than hardware and software considerations

Insertion sort

Merge sort

Constant factors versus input sizes

Running time

Crossover point

Algorithms are important

Algorithms = core of contemporary technology

Algorithm knowledge technique = truly skilled programmer

Definitions

• Concave polygon (one of the angles surpasses 180-degrees)
• Permutation (a rearranging of terms)
• Linear programming (Linear programming (optimization)  is a specific case of mathematical programming (mathematical optimization).
• Graph
• Product
• Vertex
• Associative
• Dynamic programming (a method for solving complex problems by breaking them down into simpler subproblems...The word dynamic was chosen by Bellman to capture the time-varying aspect of the problems, and because it sounded impressive.[3] The word programming referred to the use of the method to find an optimal program, in the sense of a military schedule for training or logistics. This usage is the same as that in the phrases linear programming and mathematical programming, a synonym for mathematical optimization.)
• Constant not dependent on n
• Pipelining (a set of data processing elements connected in series, so that the output of one element is the input of the next one)
• Superscalar (a form of parallelism called instruction level parallelism within a single processor. It therefore allows faster CPU throughput than would otherwise be possible at a given clock rate. A superscalar processor executes more than one instruction during a clock cycle by simultaneously dispatching multiple instructions to redundant functional units on the processor.)

Exercises 1.1

1.1-1 Give a real world example in which one of the following computational problems appears: sorting, determining the best order for multiplying matrices, or finding the convex hull.

• Sorting
• Sorting files in a directory by creation date
• Sorting various paper denominations of money
• Sorting tax return forms by form ID number
• Determining the best order for multiplying matrices
• ???
• Finding the convex hull
• Identifying area of forest burned by fire

1.1-2 Other than speed, what other measures of efficiency might one use in a real-world setting?

• Storage requirements during runtime
• Power consumption
• Size of hardware
• Size of software at rest

1.1-3 Select a data structure you have seen previously and discuss its strengths and limitations.
Stack

• Strengths
• Simple to implement: two operations, push and pop
• Push and pop operate in constant time
• Limitations
• Not elegant way to traverse elements, since have to pop and store elsewhere in order to inspect and preserve order

1.1-4 How are the shortest-path and traveling-salesman problems given above similar? How are they different?

• Same
• Both want shortest path, per constraints
• Both seem like NP-complete problems
• Differences
• Traveling-salesman requires begin and end at same node
• Shortest-path goes point-to-point

1.1-5 Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is "approximately" the best is good enough.

• Only the best solution
• Note: best means no cutting corners, not necessarily "perfection"
• Everything comes down to acceptable tolerances, in the real world
• Typically, anything involving human safety in life and death situations
• Space station airlocks (opening and closing)
• Airplane auto-pilot systems
• Traffic control systems (for example, traffic lights)
• Financial transactions
• ATM
• Approximately the best is good enough
• Pretty much everything else ; o )
• Point-to-point driving when time not of the essence...probably OK to get reasonably close to a location and then figure out parking, eating, and so forth
• Pouring a beer...OK to have a bit of foam at the top

Exercises 1.2

1.2-1 Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.

Section 1.1 of this book defines an algorithm as "any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output." Given this broad definition, I suggest the example of a web-based SQL formatter. As input, it takes a sequence of characters representing a SQL query. As output, it produces formatted SQL code, per constraints specified by the user. The algorithm functions as a set of rules which transform the input into the output based on the constraints specified by the user. For example, if the user selects "DB2" SQL as the input and C# as the output, the algorithm logic would transform the inputs into outputs conforming to C# rules.

1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in 64nlgn steps. For which values of n does insertion sort beat merge sort?

We wish to find the greatest value of n for which 8n^2 < 64nlgn. Since this seems to represent a transcendental function, I have elected to plug and chug to arrive at the answer. I used OpenOffice.org Calc to calculate the results below:

• When n = 2, we have 8(4) < 64(2)(1) => 32 < 128, which is true.

• When n = 4, we have 8(16) < 64(4)(2) => 128 < 512, which is true.

• and so forth, until n = 44, when we have 15,488 < 15373.8, which is false

Therefore, in this particular implementation, insertion sort beats merge sort for values of 2 <= n <= 43.

1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n^2 runs faster than an algorithm whose running time is 2^n on the same machine?

We wish to find the smallest value of n for which 100n^2 < 2^n. Since this seems to represent a transcendental function, I have elected to plug and chug to arrive at the answer. I used OpenOffice.org Calc to calculate the results below:

• When n = 1, we have 100(1) < 2^1 => 100 < 2, which is false.

• When n = 2, we have 100(4) < 2^2=> 400 < 4, which is false.

• and so forth, until n = 15, when we have 22,500 < 32,768, which is true

Therefore, in this particular implementation, the algorithm with running time 100(n^2) runs faster than the algorithm with running time 2^n for values of n >= 15.

Problems

1-1 Comparison of running times
For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

Note: I found this problem statement confusing, initially. The authors treat the computational problem and algorithm as a black box. The black box can solve an input of n items in f(n) microseconds. The authors ask the reader to calculate the largest size n the black box can solve on or before various times (t). For example, for f(n) = n, the black box can solve an input of 1 item in f(1) = 1 microsecond and 2 items in f(2) = 2 microseconds.

We first convert the times in the header row into microseconds (one microsecond = 1/1,000,000 of a second):

• 1 second = 1 * 10^6 or 1,000,000 microseconds
• 1 minute = 6 * 10^7 or 60,000,000 microseconds
• 1 hour = 3.6 * 10^9 or 3,600,000,000 microseconds
• 1 day = 8.64 * 10^10 or 86,400,000,000 microseconds
• 1 month = 2.592 * 10^12 or 2,592,000,000,000 microseconds (assuming 30 days per month, on average)
• 1 year = 3.15576 * 10^13 or 31,557,600,000,000 microseconds (assuming 365.25 days per year)
• 1 century = 3.15576 * 10^15 or 3,155,760,000,000,000 microseconds

Second, for each cell, we need to calculate the largest size n the black box can solve on or before the specified number of microseconds:

	Notes	1 second	1 minute	1 hour	1 day	1 month (assume 30 days, on average)	1 year (assume 365.25 days)	1 century
lg(n)	Put both sides on base 2; this converts 2^lg(n) to n.	2^(1 * 10^6)	2^(6 * 10^7)	2^(3.6 * 10^9)	2^(8.64 * 10^10)	2^(2.592 * 10^12)	2^(3.15576 * 10^13)	2^(3.15576 * 10^15)
sqrt(n)	Squaring both sides solves for n.	(1 * 10^6)^2 = 1 * 10^12	(6 * 10^7)^2 = 3.6 * 10^15	(3.6 * 10^9)^2 = 1.296 * 10^19	(8.64 * 10^10)^2 = 7.46496 * 10^21	(2.592 * 10^12)^2 = 6.718464 * 10^24	(3.15576 * 10^13)^2 = 9.9588211776×10^26	(3.15576 * 10^15)^2 = 9.9588211776×10^30
n		1 * 10^6	6 * 10^7	3.6 * 10^9	8.64 * 10^10	2.592 * 10^12	3.15576 * 10^13	3.15576 * 10^15
nlg(n)	Put both sides as an exponent on base 2; since nlg(n) = lg(n^n), this converts 2^(lg(n^n)) to n^n. Transcendental...so we have to do things the hard way.	6.2746 * 10^4 (link)	2.801417 * 10^6 (link to get approximation, then manual refinement)	1.33378058 * 10^8 (link to get approximation, then manual refinement)	2.755147513 * 10^9 (link to get approximation, then manual refinement)	7.1870856404 * 10^10 (link to get approximation, then manual refinement)	7.98161 * 10^11 (link to get approximation, then manual refinement)	6.86565x10^13 (link to get approximation, then manual refinement)
n^2	Taking the square root of both sides solves for n.	sqrt(1 * 10^6) = 1 * 10^3 or 1,000	sqrt(6 * 10^7) = 7.745966692 * 10^3 or 7,745	sqrt(3.6 * 10^9) = 6 * 10^4 or 60,000	sqrt(8.64 * 10^10) = 2.939387691 * 10^5 or 293,938	sqrt(2.592 * 10^12) = 1.609968944 * 10^6 or 1,609,968	sqrt(3.15576 * 10^13) = 5.617615152357805 * 10^6 or 5,617,615	sqrt(3.15576 * 10^15) = 5.617615152357 × 10^7 or 56,176,151
n^3	Taking the cube root of both sides solves for n.	cuberoot(1 * 10^6) = 1 * 10^2 or 100	cuberoot(6 * 10^7) = 3.914867641×10^2 or 391	cuberoot(3.6 * 10^9) = 1.532618865×10^3 or 1,532	cuberoot(8.64 * 10^10) = 4.420837798×10^3 or 4,420	cuberoot(2.592 * 10^12) = 1.373657091×10^4 or 13,736	cuberoot(3.15576 * 10^13) = 3.1601×10^4 or 31,601	cuberoot(3.15576 * 10^15) = 1.46679335×10^5 or 146,679
2^n	Taking lg of both sides solves for n.	log(1 * 10^6) / log(2) = 1.993156857×10^1 or 19	log(6 * 10^7) / log(2) = 2.583845916×10^1 or 25	log(3.6 * 10^9) / log(2) = 3.174534976×10^1 or 31	log(8.64 * 10^10) / log(2) = 3.633031226×10^1 or 36	log(2.592 * 10^12) / log(2) = 4.123720286×10^1 or 41	log(3.15576 * 10^13) / log(2) = 4.484305×10^1 or 44.84305	log(3.15576 * 10^15) / log(2) = 5.1486909×10^1 or 51
n!	Plug and chug...Wolfram Alpha helps	9	11	12	13	15	16	17

Speeding up playback rate for online videos under Linux

Seems like every link I have found to-date shows how to increase playback rate for online videos under Windows/Mac using Enounce MySpeed plugin or recommends downloading the video to local storage and using a client-side app like mplayer/VLC/and so forth.

Will keep looking.

Scarf pattern

http://www.morehousefarm.com/KnittingKits/Scarves/Beaudelaire/

Time to get classy

From Reddit:

Good evening gentleman/ladies.

1. Get out your drink of choice.
2. open 3 tabs on your favorite browser.
3. On the first tab
4. On another tab
5. On the last

All on one page.

Wool navy trench coat - purchased

Found one after years of looking...for $70 on eBay! : o )

UPDATE: it's a very nice coat. It turned out a bit darker than expected, so more formal than something I would want to wear every day. So, still looking for a grayed navy trench coat. This one looks very nice, though--no complaints.

Clothing measurements

Circa 2012:

Chest: 38"
Neck: 16"
Sleeve: 26"
Shoulders: 19.5"
Waist: 34"
Inseam: 32"
Thigh: 23"
Belly: 38.5"
Torso: 29"
Arm: 12"
Hip: 43"

Reyn Spooner (c. 2024)

Tailored Fit XL Aloha Shirt fits shoulders the best...but this leaves the length too long and the chest a bit baggy

• Shoulder: 20.3"
• Chest: 50.6" (slightly baggy)
  
• Bottom opening: 48.6" (slightly baggy)
  
• Length: 31.8" (slightly long)
  

Blue Ginger (c. 2024)

Men's medium aloha shirt: fits OK. Shirt measurements of the men's aloha shirt (Taro / Navy-Blue-Multi)(taken while not worn):

• Shoulder: 21"
• Chest: 21.5" x 2
• Length: 26"
• Bottom opening: ~23"
  

Christopher Hayes

Heard Christopher Hayes speaking on NPR a few months ago and he seems like a clued-in progressive.

Proud to be Sanatan

Saw this on a bumper sticker (or something like it) a month or two ago.

This refers to Hinduism. From Wikipedia: "Sanātana Dharma, a Sanskrit phrase meaning "the eternal law", or the "eternal way"."

Cafe Yesterday photos - Berkeley, CA

Some striking photos installed earlier this summer at Cafe Yesterday in Berkeley, CA:

celsa.dockstauer@berkeley.edu

In addition, they have a sandwich named "The Schultz". Nice.

Shower curtains

Looking for a purple and/or gold shower curtain in a traditional Japanese style.

http://www.cafepress.com/+japanese+shower-curtains

Google images search

http://www.ebay.com/itm/Japanese-Seascape-Vintage-Shower-Curtain-630045129-/360516011449?pt=Shower_Curtains&hash=item53f06dc5b9

Revenue streams

Earlier this year, I wrote down this pledge:

"I will create a new stream of passive income by Dec 31, 2012, that generates at least $50 per month on average and endures for a minimum of five years."

Midikat

http://www.midikat.com/

I saw the MidiKat car on the way home a week or two ago.

Radio songs

Heard on 88.9 FM KXPR out of Sacramento, CA:

Alan Hovhaness: Symphony No. 2 "Mysterious Mountain" Opus 132 - Royal Liverpool Philharmonic; Gerard Schwarz, conductor; Label: Telarc; Number: 80604 (audio). The intermittent xylophone sounds like the Legend of Zelda secret passage music. : o D

Audio:
http://www.youtube.com/watch?v=vlXBmIjjzAc (part 1 of 3)