Dodgy Search

I was making a comment on my friends blog and was too lazy to walk to the other room and check the title of a book on my shelf (The Record of the Paper: How the New York Times Misreports US Foreign Policy). So I tried searching Amazon.com with a few different combinations, such as New York Times Book Foreign Policy, which yields 48 results. They are mostly about crossword puzzles and you have to go to #21 (second page) for the singular result revelant to "Foreign Policy". The book I was looking for did not show up.

Maybe I should be thankful I got all books in my search results! The search New York Times Book has as its #5 result Sudoku Pro - Wildly Popular and Addictive Numbers Game That Challengers a Players Math & Logic Skills - it's an electronic Su Duko game. It has nothing to do with "New York" or the "New York Times" or "York" or "New" or "Times". And it is certainly not "Book".

How did I find the book title? (Certainly not by getting off my lazy butt and walking to the other room!) Googling the same text - New York Times Book Foreign Policy site:amazon.com - gives my book as the #2 result. (Google is the best thing since sliced bread).

And it's not my lame search text that is tripping up Amazon. Try something like To Kill A Mockingbird and the first result has no image, and is a used listing for $29. Hardly, the canonical entry for a famous book. How about Red Storm Rising? The first result is the book by Tom Clancy, but it has no image associated with it and it is a (used) Chinese version. Searching Amazon doesn't even give me books that I'm capable of reading!

Gray Areas In Java

In case you ever wondered what weak and soft references are in Java, here are couple good articles explain what they are and when you might use them:

• Plugging memory leaks with weak references
• Plugging memory leaks with soft references

Linear Algebra And Google's PageRank

The American Mathematical Society has a good article, How Google Finds Your Needle in the Web's Haystack, which explains how Google ranks the importance of each web page. There's lots of linear algebra, but its fairly accesible.

[Via Slashdot].

Memories of 342

Building a better HashMap is a short, but interesting, article on IBM's website about how java.util.concurrent.ConcurrentHashMap is implemented to provide much efficient concurrency than java.util.Hashtable.

Good Agile, Bad Agile

I just finished reading Steve Y's Good Agile, Bad Agile. I think this anecdote was my favourite part:

Most engineers are not early risers. I know a team that has to come in for an 8:00am meeting at least once (maybe several times) a week. Then they sit like zombies in front of their email until lunch. Then they go home and take a nap. Then they come in at night and work, but they're bleary-eyed and look perpetually exhausted. When I talk to them, they're usually cheery enough, but they usually don't finish their sentences.

CRC

In case you ever wondered how CRC worked (or how to use what you learned in Polynomials, Rings and Finite Fields), Cyclic Redundancy Check gives a short description of the math behind CRC as well as how to implement it as an algorithm.

Building a Better Voting Machine

Building a Better Voting Machine is a short and interesting article about voting machines (via Slashdot).

I've been meaning to print a copy of Rivest's Third Ballot Voting System and read it while I take the bus to work, but I haven't gotten around to it yet.

Learn Ruby Or Python?

I've been reading a lot of short computer-programming articles online lately, such as Exception-Handling Antipatterns, which I bookmarked a couple weeks ago (as a possible reference for a talk about Defensive Programming that I gave two weeks ago), but didn't end up reading it until today.

I also learn about Duck Typing (via Joel on Software's Ruby Performance Revisited). The articles The Perils of Duck Typing and Java does Duck Typing were interesting follow-ups.

I think I need to get around to learning Ruby. I've been meaning to for a while, but have never gotten any farther than bookmarking Prgramming Ruby and Why's Poignant Guide To Ruby. Do you think I should teach myself Ruby or try learning Python first?

A Couple Interesting Articles

Bush Is Not Incompetent - it's worth reading and it won't be what you expect.

Inversion of Control Containers and the Dependency Injection Pattern - an older computer science/programming article, but I found it enlightening. (Perhaps the title doesn't make a whole lot of sense, but if something has a title that long and still isn't clear then I can't succinctly explain what it's about either! ;-)

Who Can Name The Bigger Number?

Who Can Name The Bigger Number? (via Metafilter).

...

Ackermann numbers are pretty big, but they’re not yet big enough. The quest for still bigger numbers takes us back to the formalists. After Ackermann demonstrated that ‘primitive recursive’ isn’t what we mean by ‘computable,’ the question still stood: what do we mean by ‘computable’? In 1936, Alonzo Church and Alan Turing independently answered this question. While Church answered using a logical formalism called the lambda calculus, Turing answered using an idealized computing machine—the Turing machine—that, in essence, is equivalent to every Compaq, Dell, Macintosh, and Cray in the modern world. Turing’s paper describing his machine, "On Computable Numbers," is rightly celebrated as the founding document of computer science.

...

"Very nice," you say (or perhaps you say, "not nice at all"). "But what does all this have to do with big numbers?" Aha! The connection wasn’t published until May of 1962. Then, in the Bell System Technical Journal, nestled between pragmatically-minded papers on "Multiport Structures" and "Waveguide Pressure Seals," appeared the modestly titled "On Non-Computable Functions" by Tibor Rado. In this paper, Rado introduced the biggest numbers anyone had ever imagined.

...

I miss 365.

The Pragmatic Programmer

I finished reading The Pragmatic Programmer a couple weeks ago. (And have been meaning to mention it, but kept forgetting). The book outlines an approach to software development summed up by its first "tip": Care About Your Craft - Why spend your life developing software unless you care about doing it well?

What you learn in school tends to be either aspects of Computer Science or the syntax and features of various programming languages. Both are useful, but developing software and working with complex systems have many other facets, many of which are best learned though experience. The book is a collection of short chapters that discuss what the authors' have learned about the later.

The engineering process - creating maintainable and testable software, design, documentation, and debugging - receives a lot of coverage. But other engineering topics and skills, including tools, architecture, communication, scoping and estimation, as well as career development, are discussed. The writing style is clear and full of examples, but concise (in a good way).

I highly recommend this book as it will (likely) introduce many new and helpful ideas as well as solidifying things that you may have learned along the way but aren't quite sure how to articulate or reason about.

Dancing Links

One of my co-workers forwarded me a copy of Dancing Links by Donald Knuth. In the paper, Knuth describes a backtracking algorithm, DLX, for solving exact cover problems using a doubly-linked-list type data structure. As the algorithm recursively searches for possible solutions, the links in the lists that represent the problem "dance" as they are updated from previous candidate solutions to reflect the candidate solution that is currently under consideration.

What is the exact cover problem? Given a set of elements U and a collection S of subsets of U, an exact cover C of U is a subset of S so that each element of U appears in exactly one of the subsets in C.

For example, suppose U = { 1, 2, 3, 4, 5 } and S = { S₁ = ( 1, 5 ), S₂ = ( 1, 2, 4 ), S₃ = ( 2, 3, 5 ), S₄ = ( 2, 4 ), S₅ = ( 1, 4 ), S₆ = ( 3 ), S₇ = ( 4 ) }. Then an exact cover of U is { S₁, S₄, S₆ } since together these three sets have all of the elements U = { 1, 2, 3, 4, 5 } and no elements appears in more than one of S₁, S₄, S₆. Similarly, { S₃, S₅ } is another exact cover. On the other hand, { S₁, S₃, S₇ } is not an exact cover because 3 appears in both S₁ and S₃. Likewise, { S₂, S₆ } is not an exact cover because neither S₂ nor S₆ contains 5.

Suppose you are given a chessboard (an 8 x 8 grid) and 32 dominos (2 x 1 rectangles), which have squares of the same size as the chessboard. Can you place the dominos on the chessboard so that each square of the chessboard is cover? Yes; and it should be straightforward to do! (e.g. Make a row of four dominos that are horizontal. That will cover one of the ranks of the chessboard. Simply repeat this seven more times). Now, what happens if I give you 31 dominos and cut away the top left (a8) and bottom right (h1) squares of the chessboard (so it has 30 white and 32 black squares). Can you cover this modified chessboard with your 31 dominos?

If the domino and chessboard example still sounds too contrived then consider how you would write a computer program that can solve Su Doku problems. [Hint: Dancing Links!]

Data Mining

Business Week has an article, Math Will Rock Your World, that discuess data mining and using mathematics to model and improve business processes (e.g. supply chain optimization).

... This mathematical modeling of humanity promises to be one of the great undertakings of the 21st century. It will grow in scope to include much of the physical world as mathematicians get their hands on new flows of data, from atmospheric sensors to the feeds from millions of security cameras. It's a parallel world that's taking shape, a laboratory for innovation and discovery composed of numbers, vectors, and algorithms. "We turn the world of content into math, and we turn you into math," says Howard Kaushansky, CEO of Boulder (Colo.)-based Umbria Inc., a company that uses math to analyze marketing trends online...

Assorted Math & Technology News

When I started studying at the University of Waterloo's Faculty of Mathematics, Comptuer Science was a (very large) department. About halfway through my studies, it became the School of Computer Science. I read a couple days ago that David Cheriton, an alumnus and professor at Stanford donated $25 million to the School so the University renamed it to become the David R. Cheriton School of Computer Science. (How does a university professor become a multimillioniare you ask? They finance Google in 1998 with $200 thousand in seed money, which is, of course, the definition of ROI).

I heard from my Mom that the Ontario Government is planning on dropping Calculus from it's high school curriculum. That's not very wise.

Lastly, The New Yorker has an interesting article, Blackberry Picking, about patents. In particular, it addressed the RIM v. NTP proceedings. It's concise and very well written. It's worth reading.

Inversions

Given a sequence x₁, x₂, ... x_n, we say that the pair 1 &le i < j &le n is an inversion if x_i > x_j.

Now, given a sequence sequence S = x₁, x₂, ... x_n, how efficently can you count the total number of inversions in S?

For example, if S = 1, 5, 4, 3 then S has 3 inversions - the pairs (5, 4), (5, 3), and (4, 3).

The straightforward algorithm is the compare all pairs of elements in S, which has a O(n²) runtime.

A better algorithm is to modify the merge sort algorithm to count the inversions that it undoes while sorting S. This yields an O(nlogn) algorithm.

Is O(nlogn) the best possible? That is, is counting inversions also &Omega(nlogn)? (This is true for (comparision-based) sorting, but one does not necessarily need to sort to S to count the total number of inversions).

Tired

I'm glad this week is (basically) over. It has seemed really long. Perhaps because I've been so busy. Four days of class, two days of night class, a BBQ at Daniel & Andrew's, going to Moose Winooski's with Arun and Martin, plus homework = a lot of stuff and a lot of driving around...Oh I forgot the Brian Kernighan lecture that was this afternoon (What Should an Educated Person Know about Computers?). I found it interesting and he is a pretty good speaker. Perhaps it wasn't totally educational though as it was just a summary of a class he teaches at Princeton to inform arts students about what computers are, how they work, how pervasive they are, what contemporary issues involve computers, etc. (Being a Computer Science major I know all that stuff). Nevertheless, it was entertaining. I think more people came today than for the Aho talk back in January too.

Just one more class tomorrow before the weekend. (I want to go see The Corporation at Princess Cinema...)

No More RPC

I just submitted the CS 454 assignment. 3788 lines of code plus a couple of documents about how wonderful it is. [Well hopefully the TA thinks its wonderful :-)]. That is the end of my computer programming assignments as an undergrad student...Wow...That is a very nice realization (as I'm tired of being sleep deprived while chasing down segmentation faults..). :-) Time to make plans for going out tonight.

The return of f0(int, int) is: 15

Just under 32 hours to go...the middleware layer actually works now! Well it works for a procedure that adds 5 to 10 and gets 15. My to do list is down to 4 things plus testing (and fixing bugs...well hopefully not) and writing all the documentation. Not too bad. I think I'll take a break...

Blood-Shot Eyes

Man, my distributed computing assignment is driving me crazy. It is due in about 46 hours and I still am not done coding (so I can't even test)...too many crazy errors and too many pieces...I'm almost done...have to write 3 more things before I can get the client and server talking, plus my to do list has 4 other things that I should...plus I need to write server-side skeletons and write a real client and server that I can use for testing...(and I haven't even thought about the write up that need to go with the RPC layer)...Procrastination is a bad thing.

Time Flies

I can't believe reading week(end) is over already. :-( I did too much homework to relax enough and too much slacking to get enough homework done.

Probably the most interesting thing I did was going Friday night with a bunch of my friends to an African-cuisine restaurant downtown. I don't think any of us were impressed. The service was really slow. I had a beef dish with beef chunks, sauce, and according to the menu, there were a few vegetables in there too, but there were so few, they were hard to find. It wasn't warm enough either. (Cold food isn't usually good food). The salad consisted exclusively of lettuce and tomatos - nothing else. And I don't like tomatos. The bread was interesting. The plates were pizza dishes and the bread covered the entire plate. It was kind of like a pancake, but cold and rubbery. For the portion-size and the quality of service, the prices were too high too. To be nice though, it was better than the last time we went to Jack Astors...

Other than that I've been working on Distributed Computing a lot. Aside from the midterm on Wednesday, there is a big programming assignment, where we have to implement a RPC middleware with a binder process and a bunch of other bells and whistles. It's not too terrible, except I couldn't find a partner, so I'm doing it all myself. (Hopefully the TAs will be cool with that). I figure I'm about 40% done. Most of the socket stuff is out of the way (I forgot how crazy some of socket stuff can be!). I have the server talking to the binder and vice versa, but I need to write the part where what they say is meaningful. (I think I'm into the outside-in programming methodology - kind of a blend of top-down and bottom-up!). For the client, I can rip-off (i.e. reuse) most of what I've already written as (I think) I've made it all nice and generic.