Had a little time and got it done quicker than I expected. Problem 1.12 was to write a procedure to calculate elements of pascals triangle. I took that to mean calculate the value at position n of a given row. Take a look -
(define (pascal row n) (cond ((> n row) 0) ((or (= n 1) (= n row)) 1) (else (+ (pascal (- row 1) n) (pascal (- row 1) (- n 1))))))
As I said in a post earlier this week I’ve begun reading and working on the problems in SICP. I just read chapter 1 section 2.2 on tree recursion and completed problem 1.11 and plan to do 1.12 and 1.13. Problem 1.11 was creating recursive and iterative procedures to calculate the following function:
The recursive function was straight-forward:
(define (f n) (if (< n 3) n (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
Writing the procedure as an iterative process wasn’t as trivial. I initially expected it would be easy and sat down to write the code without really thinking about the problem, but wrapping my head around how to maintain the state needed for 3 function calls didn’t compute. So I resorted to pencil and paper – I wrote out the iterations of the function for n=0 through n=5 and the solution became clear:
(define (f-iter a b c count n) (cond ((< n 3) n) ((= count n) c) (else (f-iter b c (+ c (* 2 b) (* 3 a)) (+ count 1) n)))) (define (f2 n) (f-iter 0 1 2 2 n))
As a quick comparison of run-time for the 2 procedures I ran them with the same n value (n=30). For f(30) (recursive) the procedure took approximately 16 seconds to finish. For f2(30) (iterative) the procedure finished in less than a second. I tried higher numbers but the recursive process just takes to long – I killed the process at 3 minutes when running it for n=35. I’ve run the iterative process with n up to 150 and it completes in less than 1 second.
This one was relatively straight forward.
(define (fib-iter last-one last-two total max) (if (or (> (+ last-one last-two) max) (= (+ last-one last-two) max)) total (fib-iter (+ last-one last-two) last-one (if (= (modulo (+ last-one last-two) 2) 0) (+ total last-one last-two) total) max))) (fib-iter 1 0 0 4000000)
Working my way through SICP has a goal I’ve had for a while but never seemed to get to. However – this past week I started reading the book and working on the exercises and am looking forward to the challenge. I skipped a couple of exercises in the first section but came up with the following to exercise 1.8:
(define (cube x) (* x x x)) (define (abs-val x) (cond ((> x 0) x) ((= x 0) 0) ((< x 0) (- x)))) (define (improve guess x) (/ (+ (/ x (* guess guess)) (* 2 guess)) 3)) (define (good-enough? guess x) (< (abs-val (- (cube guess) x)) 0.001)) (define (cube-root-iter guess x) (if (good-enough? guess x) guess (cube-root-iter (improve guess x) x))) (define (cube-root x) (cube-root-iter 1.0 x))
Along with the exercises in SICP I plan to also apply my new found knowledge to some of the problems from Project Euler. The solution I came up with for exercise 1 was probably overkill but it worked and should work for larger sets of numbers:
(define (calc-iter total count limit) (if (= count limit) total (calc-iter (+ (if (or (= (modulo count 3) 0) (= (modulo count 5) 0)) count 0) total) (+ count 1) limit))) (define (calc x) (calc-iter 0 0 x)) (calc 1000)
I installed the latest MIT/GNU Scheme version and ran into an issue with a missing dependency. When attempting to start scheme I would get the following message -
This ended up being an easy fix -
I ran into an issue last night where I changed the boot options for XP using MSCONFIG (foolishly) to enter safemode. After doing this the computer would blue screen when booting and then attempt to boot back into safe mode. I didn’t have a XP disc to enter recovery mode so I ended at google trying to find some sort of boot/recovery disc and found – ERD Commander from Micrsoft (30 day eval) – which has some great tools on it. I ended up making an ERD boot disc and restored to a restore point to fix the BSOD issue. After the restore I rebooted and found the computer booted correctly but I couldn’t log into the Admin account. (This is a company laptop and the admins changed the admin password to something new – so I thought I was screwed.) I tried booting the different boot options - ‘Last known good configuration’, ‘Windows XP Normally’, etc. but no luck.
I tried resetting the admin password with the ‘locksmith’ utility in ERD but for whatever reason I couldn’t get it to work. Back to Google – I tried to find a way to reset the admin password – and found plenty of tools to reset the account but none seemed to work.
At this point the system was booting fine so I didn’t care about getting into safe mode but I since I set the options in MSCONFIG (won’t do that again) I couldn’t get around them. I tried running MSCONFIG when I booting using the ERD Commander boot disc but it didn’t work – I could get the app to run – but it wouldn’t save the changes. Next I try running bootcfg from the command line – using this I can remove all options from the boot config except for /SAFEBOOT:MINIMAL – WTF? So then I figure why not just edit the boot config by hand? I don’t know why it took me so long to get to that point – I could have done that initially and saved myself a lot of time . After booting using the ERD Commander CD – I went to the file explorer and navigated to the root (C:\) and changed the properties of boot.ini to writable (uncheck ‘Read-Only’). I then edited to remove the /SAFEBOOT:MINIMAL switch, saved the file, and rebooted – back to Windows as normal.
All in all this was a pain in the ass (and a little embarrassing but I’m sharing it here so it wasn’t that bad).
I’ve been playing with Chrome since I downloaded it yesterday and have a couple of observations -
Its fast – much faster to start than Firefox, Opera, or IE7 – and pages start loading quicker
As far as memory usage is concerned for 1 page (1 tab) Chrome uses less memory. As you add tabs Chrome utilizes more memory per tab than Firefox, Opera, or IE7. I assume this is a result of the tabs being contianed in their own process – for 7 tabs I had 10 Chrome processes running. The overhead to create each process certainly contributes to the greater memory usage. That said – as I use the other 3 browsers the memory usage creeps up significantly whereas Chrome’s memory usage creeps much more slowly.
Due to each tab running in its own independent process I was able to kill one of the processes without closing the other tabs. I assume the same works when a process crashes due to a problem with a plugin, or some other error. When the process does crash you’re tab will remain with the image below -
Chrome Error - Aw Snap!
I’m not sure how well flash is working – I’ve been to a couple of flash heavy sites that load with content missing but other sites have loaded flash content correctly. I’m not sure if its flash related or something unrelated.
There are very few plugins available for Chrome – even the Google toolbar isn’t available – but there are some and there does appear to be support for themes. So far though its a nice piece of software – I’m not sure what it brings for the average user who gets similar or more functionality in IE or Firefox (or Opera).
Google announced it intends to release its own open source web browser called Chrome on Tuesday (Sept. 2). The announcement came after Google accidently posted a comic book detailing the plans. You can view the comic book on Google Books. I wonder how the name came about since Google has been a big supporter of Firefox and Firefox already uses a technology called Chrome?
Theres a link in the comic book to – www.google.com/chrome – that doesn’t appear to work right now but I assume it will on Tuesday. Looks like the website might actually be – gears.google.com/chrome – although I don’t think it will be available until after a 2PM Eastern webcast from Google.
In searching for a place to download Chrome I stumbled on a post at zwadia.com – Assessing Google Chrome – that I found interesting.
Although the Android hasn’t been released yet Google is working on the details of a marketplace to support 3rd party applications for the platform. According to a post on the Android Developers Blog - devices will initially have a beta version of the market where users will be able to find free apps. A future update will allow for paid content/applications.
I guess I missed the big news yesterday but many didn’t – Comcast is implementing a 250GB cap on bandwidth per month – I assume for residential customers. My first response is WTF? I’m already paying $50/month for Internet access and they might charge me more? Although – realistically I probably come nowhere near 250GB usage per month. But for the money I would rather the availability be there if I needed it – I guess theres always Fios which is coming to my area soon. As far as I can tell Verizon doesn’t put any caps on bandwidth usage.
Plus Comcast supports enhanced P2P.