Kevin's Social Blog

Sunday, April 28, 2013

Radio songs

Heard on Sacramento 88.9 FM:

Anton Heberle: Concerto for recorder and orchestra in G major - Saint Paul Chamber Orchestra; Pinchas Zukerman, conductor; Michala Petri, recorder; Label: Philips; Number: 420243
I think this is the nicest recorder piece I have ever heard...though not the biggest recorder fan.

Fantastic Scherzo

Benjamin Britten: Matinees musicales (Suite after Rossini) Opus 24 - Helsingborg Symphony Orchestra; Okko Kamu, conductor; Label: Ondine; Number: 825

Malcolm Arnold: Four Scottish Dances Opus 59 - Boston Pops Orchestra; Keith Lockhart, conductor; Label: Rca; Number: 68901

Heard on 100.5 FM:

Of Monsters and Men - Little Talks

Sunday, April 21, 2013

Day one - Configuring Debian GNU/Linux 7 "wheezy"

2013-04-21

Reviewing previous customizations

I´m going through many of the previous customizations from the previous stable release:

Cosmos screensaver

Looks like XFCE ships without the cosmos screensaver...

Unfortunately, gnome-screensaver, which has the cosmos screensaver, requires gnome-session
Just for fun, I installed all the xscreensaver options:

sudo apt-get install xscreensaver-data xscreensaver-data-extra xscreensaver-gl xscreensaver-gl-extra rss-glx

To configure xscreensaver to display a slideshow of images:

Applications Menu > Settings > Screensaver
Mode = Only One Screen Saver
Screen Saver = GLSlideshow
Blank After = 30 minutes
Cycle After = 3 minutes
Select button ¨Settings¨

Select button "Advanced"
Command Line =
glslideshow -root -delay 84615 -duration 17 -zoom 100 -pan 17 -fade 3 -fps
Letterbox = Checked, everything else unchecked
Select button ¨OK¨ to return to the main window

Select tab ¨Advanced¨

Select checkbox ¨Choose Random Image¨ and set to
/usr/share/backgrounds/cosmos
Uncheck ¨Grab Desktop Images¨

It appears all my old cosmos images got deleted though...so I chose to get them back manually:

cd /usr/share/backgrounds/cosmos
sudo wget https://git.gnome.org/browse/gnome-screensaver/plain/data/images/cosmos/blue-marble-west.jpg?id=2.91.90 -O blue-marble-west.jpg
sudo wget https://git.gnome.org/browse/gnome-screensaver/plain/data/images/cosmos/cloud.jpg?id=2.91.90 -O cloud.jpg
sudo wget https://git.gnome.org/browse/gnome-screensaver/plain/data/images/cosmos/comet.jpg?id=2.91.90 -O comet.jpg
sudo wget https://git.gnome.org/browse/gnome-screensaver/plain/data/images/cosmos/earth-horizon.jpg?id=2.91.90 -O earth-horizon.jpg
sudo wget https://git.gnome.org/browse/gnome-screensaver/plain/data/images/cosmos/galaxy-ngc3370.jpg?id=2.91.90 -O galaxy-ngc3370.jpg
sudo wget https://git.gnome.org/browse/gnome-screensaver/plain/data/images/cosmos/helix-nebula.jpg?id=2.91.90 -O helix-nebula.jpg
sudo wget https://git.gnome.org/browse/gnome-screensaver/plain/data/images/cosmos/jupiter.jpg?id=2.91.90 -O jupiter.jpg
sudo wget https://git.gnome.org/browse/gnome-screensaver/plain/data/images/cosmos/sombrero.jpg?id=2.91.90 -O sombrero.jpg
sudo wget https://git.gnome.org/browse/gnome-screensaver/plain/data/images/cosmos/whirlpool.jpg?id=2.91.90 -O whirlpool.jpg

All that work, because, as I said before, ...Carl Sagan...Cosmos

Printing

It appears I lost all my UI printer configuration utilities, so, via:

sudo apt-get install system-config-printer

This opens up Applications Menu > System > Printing

Vim colors

sudo cp /usr/share/vim/vim73/colors/koehler.vim /usr/share/vim/vim73/colors/koehler.vim.bak

Configure vim .vimrc

Configure XFCE4 Terminal 0.4.8 colors

Via my 2008 post:

Font: Monospace Regular 10 pt.
Text Color="0,255,0"
Background Color="0,55,0"
Default Bold Background="85,85,85"
Lines of scrollback: 9999

To set the preferred geometry (via):

vim ~/.config/Terminal/terminalrc
MiscDefaultGeometry=100x100+150+0

Eclipse

Geany

Citrix Receiver

Filezilla

Amarok 2.5-GIT

Loads OK

Headphone jack sensing

Not tested

Java plugin
sudo apt-get install icedtea-plugin
Restart browser

VLC

Seems unable to play YouTube files

To-Do:

Ghostview

Install Adobe Reader 9.5.3

Volume control sound theme

Java

gnome-screensaver

Reading up on gnome-screensaver this evening, as I upgrade from Debian Squeeze to Wheezy:
http://en.wikipedia.org/wiki/Gnome-screensaver

Tag 2.91.91 removed the cosmos images on 2011-03-08:
https://git.gnome.org/browse/gnome-screensaver/commit/?id=2.91.91

The commit to remove the Cosmos screensaver images, from 2011-03-06:
https://git.gnome.org/browse/gnome-screensaver/commit/?id=897dc79ba04b3cfb49b93f6bd03fa2ce59a274b7

Squeeze: gnome-screensaver 2.30.0-2squeeze1
http://packages.debian.org/squeeze/i386/gnome-screensaver/filelist

Wheezy: gnome-screensaver 3.4.1-1
http://packages.debian.org/wheezy/i386/gnome-screensaver/filelist

I had an "ah ha" moment while reading the description of why the gnome-screensavers chose the route they did to remove the Cosmos screensaver. At first, I think I reacted as many did--with surprise and indignation. However, their argument seems reasonable and they seem very open to explaining their actions.

I must say, however--playing with all the xscreensaver options brought some nostalgic joy to my heart this evening. : o ) I'm going to go ahead and salvage the old Cosmos screen saver images for xscreensaver, instead:

Upgrading to Debian GNU/Linux 7 "wheezy" + XFCE

Last night I took the plunge and upgraded my Debian GNU/Linux 6 "squeeze" install to "wheezy"...here's my running log of updates.

2013-04-20

Referencing http://www.debian.org/releases/testing/i386/release-notes/ch-upgrading.en.html:

sudo dpkg --audit
grep -q '^flags.*\bpae\b' /proc/cpuinfo && echo yes || echo no
(returned "no"...old hw without pae : o ( )

sudo vim /etc/apt/sources.list
--changed all my sources from squeeze to wheezy. Note: commented out backports for wheezy
sudo apt-get update
--updated sources...this took a few minutes
sudo apt-get -o APT::Get::Trivial-Only=true dist-upgrade
-- this told me whether or not I had enough space for the upgrade (yes)
sudo apt-get upgrade
-- this upgraded a bunch of stuff...took about 45 minutes

sudo apt-get dist-upgrade -o APT::Immediate-Configure=0 APT::Force-LoopBreak=1

-- the main upgrade...I received errors when I just ran "sudo apt-get dist-upgrade": "E: Could not perform immediate configuration on 'package'. Please see man 5 apt.conf under APT::Immediate-Configure for details." I also got an conflict/pre-depend error for xml-core and docbook-xml...ugh. So, I started uninstalling things:

sudo apt-get autoremove

sudo apt-get remove default-jre

sudo apt-get remove xml-core

sudo apt-get remove gnome

sudo apt-get remove kde

sudo apt-get remove libreoffice

sudo apt-get remove openoffice.org

sudo apt-get remove gcc

sudo apt-get remove openjdk-6-jre

finally:

sudo apt-get dist-upgrade

This ran overnight.

2013-04-21

In the morning, I awoke to a screen warning about the 686 kernel. After the dist-upgrade completed, I installed the 486 kernel, as suggested:

sudo apt-get install linux-image-486

sudo apt-get remove linux-image-686

sudo apt-get remove linux-image-2.6-686

sudo apt-get install gnome

sudo apt-get install default-jre

sudo apt-get install xml-core

sudo apt-get install kde

sudo apt-get install libreoffice

sudo apt-get install openoffice.org

sudo apt-get install gcc

sudo apt-get install openjdk-7-jre

sudo apt-get autoremove

-- a sanity check

sudo apt-get check

sudo apt-get update

sudo apt-get upgrade

sudo apt-get dist-upgrade

sudo apt-get install google-chrome-unstable

sudo dpkg --audit

sudo apt-get remove adobereader-enu

sudo apt-get remove dhcp3-client dhcp3-common

sudo apt-get remove gcj-jre-headless

sudo apt-get install gcj-jre-headless

sudo apt-get remove bogofilter doc-debian

sudo apt-get install bogofilter doc-debian

Done. : o )

At this point I attempted to fix my sudoers file, as per instructions. I moved /etc/sudoers to /etc/sudoers.d/mychanges ... this was a mistake, because as soon as I did, I lost the ability to sudo things. x_x After a few reboots into recovery mode I successfully copied back /etc/sudoers.d/mychanges to /etc/sudoers and removed /etc/sudoers.d/mychanges.

Next, I ran the following to remove the unneeded grub menu entries:

sudo aptitude search linux-image

sudo aptitude remove linux-image-2.6.32-5-686 linux-image-3.2.0-4-686-pae linux-image-686-pae

I installed bootlogd to record the Radeon error messages I receive during boot:

sudo apt-get install bootlogd

sudo apt-get install firmware-linux-nonfree

This solved getting Gnome3 to load with all the bells and whistles.

However, this ended up being too slow, given my hardware. So I uninstalled it, per instructions:

sudo aptitude purge `dpkg --get-selections | grep gnome | cut -f 1`
sudo aptitude -f install
sudo aptitude purge `dpkg --get-selections | grep deinstall | cut -f 1`
sudo aptitude -f install

Unfortunately, this sequence of commands led to two undesirable side-effects:

Network no longer worked

sudo vim /etc/network/interfaces
sudo dhclient eth0
ifconfig eth1 up
sudo iwconfig eth1 up
sudo iwconfig eth1 essid {ESSID}
sudo dhclient eth1

GDM - gone...booted into tty prompt

Added to ~/.xinitrc: exec ck-launch-session startxfce4
sudo apt-get install gdm3

At this point, everything looks like it´s pretty stable...moving on to configuration.

Other things installed:

wicd
p7zip-full
p7zip
mtools

Monday, February 18, 2013

Links from Stephan Sokolow´s blog

So I do not forget:

GOG.com www.openpandora.org
https://www.humblebundle.com/
http://www.graphviz.org/
http://betterexplained.com/
http://japanadventuretimepartygo.blogspot.com/2006/11/taken-from-httppepperidgenetjapanese.html
NearlyFreeSpeech.NET
http://git.or.cz/course/index.html
http://www.liberatedgames.com/
http://www.ilovejackdaniels.com/cheat-sheets/mod_rewrite-cheat-sheet/
http://blog.ssokolow.com/archives/2006/03/01/a-little-gem-from-the-fortune-command/

I am nerdier than 97% of all people. Are you a nerd? Click here to take the Nerd Test, get nerdy images and jokes, and write on the nerd forum!

Movie – “My Sassy Girl”

http://blog.ssokolow.com

Sunday, February 17, 2013

Top 10 ambient albums

http://www.discogs.com/lists/Top-10-Ambient-Albums/25708

So I remember to look later. Found this while attempting to find an ambient album I used to listen to back in the day...turns out it was Atlanta, Georgia-based artist John Serrie's "And the Stars Go With You" (1987). It turns out he wrote it in memory of the astronauts lost in the Space Shuttle Challenger disaster in 1986.

Criterion Collection

Movies watched this weekend:

Breathless (Godard)

The Seventh Seal (Bergman)

The Red Balloon (Lamorisse)

Hulu offered free access to their Criterion Collection this weekend (albeit, with commercial breaks).

Quite offputting; try to imagine one of cinema's landmark B&W films interrupted by full-color orange juice and car insurance commercials.

Monday, February 11, 2013

Klaus Schulze

Klaus and I share the same initials...watching a video of him from 1977, I see his initials on his equipment. ; o )

Charles Mingus

Listening to Charles Mingus' discography at the moment.

Sunday, February 10, 2013

The Big Empty

Still trying to find the quote from this movie, provided by Gary Farmer's character "Indian Bob" after he drops off John in the desert.

UPDATE, 2013-12-22:

Finally transcribed it myself:

J: And then what?
B: Stand there and wait
J: Wait for what? What's happening here, Bob?
B: The same old same old.
J: Am I going to die?
B: We all die John Person. Just a matter of when. Just the way of the world. You finally ask yourself: Was my life worth living? Did I make the right decisions? Did I do the right thing? Will I be remembered? It's a tough old road we follow, isn't it? Myself, there's a lot of things I want to accomplish before I leave this earth.
J: Yeah. Me too, Bob.

Online LaTEX editor

http://www.codecogs.com/latex/eqneditor.php

Awesome! Now I can practice writing LaTeX : o )

For example, here's (modified) code to write a function, via John D. Cook:

T(n) =
\left\{
\begin{array}{ll}
2 & \mbox{if } n = 2\mbox{ }, \\
2T(n/2)+n & \mbox{if } n = 2^k \mbox{ , for } k > 1
\end{array}
\right.

Smart snuggles

Via the SN&R:

www.adafruit.com

Saturday, February 02, 2013

Radio songs

Whitehorse...we heard them perform their song "Wisconsin"

Via 88.9 KXPR FM out of Sacramento, California:

Samuel Barber: School for Scandal Overture - Royal Scottish National Orchestra; Marin Alsop, conductor; Label: Naxos; Number: 559024 Audio.

Via unknown station:

Las Vegas-based The Crystal Method's "That's the Name of the Game", from their 2001 album Tweekend, on the Geffen Records Label. Video.

Saturday, January 26, 2013

Ting

This seems like a great service:

https://ting.com

Refreshing pricing plans.

Thursday, January 24, 2013

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.

Thursday, January 17, 2013

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

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

Saturday, January 12, 2013

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

Wednesday, January 09, 2013

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.

Kevin's Social Blog

Sunday, April 28, 2013

Radio songs

Sunday, April 21, 2013

Day one - Configuring Debian GNU/Linux 7 "wheezy"

gnome-screensaver

Upgrading to Debian GNU/Linux 7 "wheezy" + XFCE

Monday, February 18, 2013

Links from Stephan Sokolow´s blog

Sunday, February 17, 2013

Top 10 ambient albums

Criterion Collection

Monday, February 11, 2013

Klaus Schulze

Charles Mingus

Sunday, February 10, 2013

The Big Empty

Online LaTEX editor

Smart snuggles

Saturday, February 02, 2013

Radio songs

Saturday, January 26, 2013

Ting

Thursday, January 24, 2013

Fender

Thursday, January 17, 2013

Introduction to Algorithms, 3rd edition - Chapter 2

Saturday, January 12, 2013

Free digital copy of movie after viewing at the theater

Radio songs

Dash camera

Wednesday, January 09, 2013

Installing Ubuntu to Dell Inspiron 15r

Blog Archive

About Me