alexx's starred items

It’s Time to Redesign The Sales Page! Part 2 (Part 1)

So, last time on “It’s Time to Redesign The Sales Page!” we talked about why I decided the Freckle Time Tracking sales page had to be totally redone.

Namely:

1. We weren’t proud of the design, so we didn’t promote it
2. We didn’t believe it was effective at reaching our visitors, so we didn’t promote it

So these problems break down into two categories:

1. Visual appearance
2. Message/content

Because the message/content issue is much harder than the visual appearance, that’s where I started.

Tune in next time for the design.

Pre-work: Why, and Who?

To figure out what to say on a marketing site, you first have to figure out:

Why the hell should anyone care?

Once you have the Why, you also have the Who.

Why… and Who

Freckle is focused on freelancers and small teams. 

Freelancers and small teams who do what? you may ask. Well, to us, it doesn’t really matter. We designed it around our needs—and we’re designers and developers—but, across most industries, freelancing or consulting is pretty much the same. It’s different in the same ways, too. There’s as much variation among designers in their freelance habits, as there are among all freelancers, of all types.

This is why “freelancers and small teams” isn’t really our Who.

The real difference between our customers, and people who’d be better suited with our competitors?

Attitude. And outlook.

If you like this, you’ll like us

Nobody has ever accused me of being nuanced. It’s not that I’m incapable of nuance, but it’s not my highest priority. I like bold statements, bold moves, and bold designs. 

Freckle, too, is bold. It’s got nuance to it—to quote one happy customer, it’s got “a thousand little touches”—but, at heart, it’s a bold and decisive tool. We made it to be, in many cases, the opposite of what’s out there currently for time tracking. Because, well, we used those systems, and we hated them.

We’ve thrown out a lot of time-honored time tracking tropes (teehee) in order to make Freckle what it is. But this isn’t a case of cargo-culting “less is more,” it’s less with a purpose.

Two examples of “features” we cut out: required client/project hierarchy, and the need to define tasks before you could track time for them. Those things have their place in the enterprise. 

But they’re not features for small teams, or soloists, with a flat hierarchy, a high level of trust, and a culture of independence. They’re hobbles. Annoyances. 

And those people, the ones who trust their team members, who crave freedom, efficiency, flexibility, and a 10,000 ft view of their time, are our audience. 

To be even more specific, they like bright, happy software with bright, happy colors, and a little friendly snark now and again.

And we deliver.

That’s our Who and our Why, so intimately entangled.

Now, to write the site content itself

So, after an exercise just like this one, on paper, I was able to articulate why. And who.

Now the question becomes: How?

• How to reach people who believe in trust, freedom, efficiency, and flexibility? 
• How to speak to them? (As in, “that really speaks to me” as opposed to “talking with your mouth”)
• How to communicate that we help them with the 10,000 ft view? 
• And the bright cheery bit?

Freedom, efficiency, and flexibility

I made a list of the most important aspects of Freckle, and I worked my butt off to figure out how to describe them purely in the terms of benefits: 

How does this help you, the user, kick ass? (Thanks to Kathy Sierra for this mantra.)

Features are in bold, benefits are in italic:

• Quick entry? Enjoy entering your time, and get it done in as little as 3 key strokes, no mousing.
• No up-front configuration? Create new clients or projects when you need them—the first time you log time for ‘em.
• Flexible tags & description? Describe your time however you want, when you want. Use tags with reports to get as granular as you want.
• Inline indication of time budgets? Always know exactly where your project stands, on every page.
• The Pulse? Learn the days where you & your team work the most—and least—and on what. Get a feel for your rhythm.
• Bright & cheerful? Lift your spirits, even if time tracking’s not your idea of The World’s Funnest Thing To Do.

Are these a little bit overblown? Of course. But they’re an example of a draft. Gimme a break.

All positive

Did you notice that the benefits I listed here (and on the actual site) are all phrased in the positive? That was on purpose. I don’t want negativity to creep in.

Even though it’s so easy to frame Freckle in terms of what it’s not: Not painful. Not ugly. Not full of horrible, evil select lists. Not disrespectful. Not ignorant of the fact that time is a business (e.g. our competitors mostly don’t offer any kind of non-billable time tracking). 

Psychological research has shown that when people hear a negating phrase (”I am not a crook!”), they forget the negative and remember it as a true, positive statement (”I am a crook!”). 

Freckle’s not an asshole. (Freckle’s an asshole! With a bad toupee!)

That’s why responding to your competitor’s claims with denials is a weak position, whereas stating things about your product that are positive is a strong one.

Headline: Setting the tone

The headline is the first thing a person will see when they load the page. ( Well, in theory, anyway.)

So, I spent my time brainstorming potential headlines that would set the tone for the rest of the page. Tone, of course, being a bit playful and irreverent, but still smart and get-down-to-business, because that’s how we roll (as a company, and as a software product). 

I decided up front that “Freckle Time Tracking” wasn’t good enough. If you tell people “Oh, we do time tracking software,” their eyes immediately glaze over. 

More importantly, if I tell you “time tracking” you immediately think of all those other apps that do time tracking. Those apps are mostly the same. It sets (incorrect) expectations: Oh, a time tracking app. I know what that looks like. 

If your app takes a really different approach, like ours, you’ve just screwed the pooch, and you haven’t even closed your </h1> yet!  

So really, my number two goal was to set the tone—the number one goal was to provoke a bit of curiosity. 

One headline I toyed with was: Sorry, control freaks!

The one that won, for now? 

Goodbye, Administrivia.

Is it perfect? No. But it’s surely better than “Freckle Time Tracking.” Or something nauseatingly self-congratulatory, like “Time Tracking: Solved” or some such. 

The others aren’t worth mentioning; they were various shades of boring, predictable, and ho-hum. That’s how it always is when you want to do good shit. Gotta keep cranking through all the predictable stuff until something cool sneaks through by accident.

Set the stage: highlighting the problem

But you can’t just drop benefits into a potential customer’s lap, and expect to get anywhere. It’s like trying to walk through a door that isn’t open. You’re just going to walk away with a big embarassing bruise on your forehead.

So, before popping out benefits, I tried to open the door. I tried to get the visitor in the mood to hear about benefits. That means getting them to think about their current lack of benefits.

My goal with the first two paragraphs on the page was to set the stage:

Frustration—many people find time tracking to be a truly ornerous task, because of bad software, mostly. So, first, I bring up the image of how awful it usually is, followed by the premise: Freckle can make it better.

Raising the question—does the visitor’s current system support the visitor in these critical ways? Freckle does.

Deliver the solution: benefits

And then, with the benefits work I did above, I wrote the copy for the benefits section—below the call to action for the tour. In case people weren’t ready for the tour yet.

This section I edited, over and over. Every time I wrote anything that sounded like a feature, I ripped it out and started again. I kept bringing the focus back to you, you, you. Our potential customers don’t want to hear about us unless it’s how we can help them. (Fundamental human fact: Your customer is the most important person in the world. Everybody goes through life looking at everything relative to them. You, too.)

I tried to make headlines for these mini-sections that would be descriptive, but, like the big heading up top, create a tone that fits with our software and our audience, and create curiosity as well.

I selected screenshots, especially, that showcased the little touches in Freckle, and the brightness and cheerfulness.

Lay it all out: features

Finally, for those who are less interested in touchy-feely benefits, who want cold hard facts: a feature list. 

I grouped the features by broad category, situating them in context to show how they created the great user experience.

Everything we say about Freckle, I want to always bring it back to that user experience. Even though we’ve got a lot of features that the competition don’t, what really ties it all together is the experience of using it. 

Now, your turn

Do you have a product with a sales page? How’d you decide to create your content?

And…Would you like more articles like this?

As you all may know, I watched and posted my lecture notes of the whole MIT Introduction to Algorithms course. In this post I want to summarize all the topics that were covered in the lectures and point out some of the most interesting things in them.

Actually, before I wrote this article, I had started writing an article called “The coolest things that I learned from MIT’s Introduction to Algorithms” but quickly did I realize that what I was doing was listing the topics in each article and not really pointing out the coolest things. Therefore I decided to write a summary article first (I had promised to do so), and only then write an article on really the most exciting topics.

Talking about the summary, I watched a total of 23 lectures and it resulted in 14 blog posts. It took nearly a year to publish them here. The first blog post in this series was written in August 2008, and the last in July 2009. Here is a list of all the posts:

• Lectures 1 and 2: Analysis of Algorithms
• Lecture 3: Divide and Conquer
• Lectures 4 and 5: Sorting
• Lecture 6: Order Statistics
• Lectures 7 and 8: Hashing
• Lectures 9 and 10: Search Trees
• Lecture 11: Augmenting Data Structures
• Lecture 12: Skip Lists
• Lectures 13 and 14: Amortized Analysis and Self-Organizing Lists
• Lecture 15: Dynamic Programming
• Lecture 16: Greedy Algorithms
• Lectures 17, 18 and 19: Shortest Path Algorithms
• Lectures 20 and 21: Parallel Algorithms
• Lectures 22 and 23: Cache Oblivious Algorithms

I’ll now go through each of the lectures. They require quite a bit of math knowledge to understand. If you are uncertain about your math skills, I’d suggest reading Knuth’s Concrete Mathematics book. It contains absolutely all the necessary math to understand this course.

Lecture 1: Analysis of Algorithms

If you’re a student, or even if you’re not, you must never miss the first lecture of any course, ever! The first lecture tells you what to expect from the course, how it will be taught, what it will cover, who the professor is, what the prerequisites are, and a bunch of other important and interesting things.

In this lecture you also get to know professor Charles E. Leiserson (author of CLRS) and he explains the following topics:

• Why study algorithms and their performance?
• What is the analysis of algorithms?
• What can be more important than the performance of algorithms?
• The sorting problem.
• Insertion sort algorithm.
• Running time analysis of insertion sort.
• Asymptotic analysis.
• Worst-case, average-case, best-case running time analysis.
• Analysis of insertion sort’s worst-case running time.
• Asymptotic notation - theta notation - Θ.
• Merge sort algorithm.
• The recursive nature of merge sort algorithm.
• Running time recurrence for merge sort.
• Recursion trees.
• Running time analysis of merge sort by looking at the recursion tree.
• General recurrence for divide and conquer algorithms.

I personally found the list of things that can be more important than the performance of the program interesting. These things are modularity, correctness, maintainability, security, functionality, robustness, user-friendliness, programmer’s time, simplicity, extensibility, reliability, scalability.

Follow this link to the full review of lecture one.

Lecture 2: Analysis of Algorithms (continued)

The second lecture is presented by Eric Demaine. He’s the youngest professor in the history of MIT.

Here are the topics that he explains in the second lecture:

• Asymptotic notation.
• Big-o notation - O.
• Set definition of O-notation.
• Capital-omega notation - Ω.
• Theta notation - Θ.
• Small-o notation - o.
• Small-omega notation - ω.
• Solving recurrences by substitution method.
• Solving recurrences by recursion-tree method.
• Solving recurrences by the Master’s method.
• Intuitive sketch proof of the Master’s method.

An interesting thing in this lecture is the analogy of (O, Ω, Θ, o, ω) to (≤, ≥, =, <, >).

For example, if we say f(n) = O(n²) then by using the analogy we can think of it as f(n) ≤ c·n², that is, function f(n) is always smaller than or equal to c·n², or in other words, it’s bounded above by function c·n², which is exactly what f(n) = O(n²) means.

Follow this link to the full review of lecture two.

Lecture 3: Divide and Conquer

The third lecture is all about the divide-and-conquer algorithm design method and its applications. The divide and conquer method solves a problem by 1) breaking it into a number of subproblems (divide step), 2) solving each problem recursively (conquer step), 3) combining the solutions (combine step).

Here are the topics explained in the third lecture:

• The nature of divide and conquer algorithms.
• An example of divide and conquer - merge sort.
• Solving for running time of merge sort by Master’s method.
• Binary search.
• Powering a number.
• Fibonacci numbers.
• Algorithms for computing Fibonacci numbers.
• Fibonacci by naive recursive algorithm.
• Fibonacci by bottom-up algorithm.
• Fibonacci by naive recursive squaring.
• Fibonacci by matrix recursive squaring.
• Matrix multiplication
• Strassen’s algorithm.
• VLSI (very large scale integration) layout problem.

I was the most impressed by the four algorithms for computing Fibonacci numbers. I actually wrote about one of them in my publication “On the Linear Time Algorithm For Finding Fibonacci Numbers,” which explains how this algorithms is actually quadratic in practice (but linear in theory).

Follow this link to the full review of lecture three.

Lecture 4: Sorting

Lecture four is devoted entirely to the quicksort algorithm. It’s the industry standard algorithm that is used for sorting in most of the computer systems. You just have to know it.

Topics explained in lecture four:

• Divide and conquer approach to sorting.
• Quicksort algorithm.
• The partition routine in the quicksort algorithm.
• Running time analysis of quicksort.
• Worst-case analysis of quicksort.
• Intuitive, best-case analysis of quicksort.
• Randomized quicksort.
• Indicator random variables.
• Running time analysis of randomized quicksort in expectation.

I loved how the idea of randomizing the partition subroutine in quicksort algorithm led to a running time that is independent of element order. The deterministic quicksort could always be fed an input that triggers the worst-case running time O(n²), but the worst-case running time of randomized quicksort is determined only by the output of the random number generator.

I once wrote another post about quicksort called “Three Beautiful Quicksorts” where I summarized what Jon Bentley’s had to say about the experimental analysis of quicksort’s running time and how the current quicksort algorithm looks in the industry libraries (such as c standard library, which provides qsort function).

Follow this link to the full review of lecture four.

Lecture 5: Sorting (continued)

Lecture five continues on sorting and looks at what limits the running time of sorting to O(n·lg(n)). It then breaks out of this limitation and shows several linear time sorting algorithms.

Topics explained in lecture five:

• How fast can we sort?
• Comparsion sort model.
• Decision trees.
• Comparsion sort algorithms based on decision trees.
• Lower bound for decision-tree sorting.
• Sorting in linear time.
• Counting sort.
• The concept of stable sorting.
• Radix sort.
• Correctness of radix sort.
• Running time analysis of radix sort.

The most interesting topic here was how any comparison sort algorithm can be translated into a decision tree (and vice versa), which limits how fast we can sort.

Follow this link to the full review of lecture five.

Lecture 6: Order Statistics

Lecture six deals with the order statistics problem - how to find the k-th smallest element among n elements. The naive algorithm is to sort the list of n elements and return the k-th element in the sorted list, but this approach makes it run in O(n·lg(n)) time. This lecture shows how a randomized, linear-time algorithm (in expectation) for this problem can be constructed.

Topics explained in lecture six:

• Order statistics.
• Naive order statistics algorithm via sorting.
• Randomized divide and conquer order statistics algorithm.
• Expected running time analysis of randomized order statistics algorithm.
• Worst-case linear-time order-statistics.

An interesting point in this lecture is that the worst-case, deterministic, linear-time algorithm for order statistics isn’t being used in practice because it performs poorly compared to the randomized linear-time algorithm.

Follow this link to the full review of lecture six.

Lecture 7: Hashing

This is the first lecture of two on hashing. It introduces hashing and various collision resolution strategies.

All the topics explained in lecture seven:

• Symbol table problem.
• Direct-access table.
• The concept of hashing.
• Collisions in hashing.
• Resolving collisions by chaining.
• Analysis of worst-case and average-case search time of chaining.
• Hash functions.
• Division hash method.
• Multiplication hash method.
• Resolving collisions by open addressing.
• Probing strategies.
• Linear probing.
• Double hashing.
• Analysis of open addressing.

Follow this link to the full review of lecture seven.

Lecture 8: Hashing (continued)

The second lecture on hashing. It addresses the weakness of hashing - for any choice of hash function, there exists a bad set of keys that all hash to the same value. An adversary can take an advantage of this and attack our program. Universal hashing solves this problem. The other topic explained in this lecture is perfect hashing - given n keys, how to construct a hash table of size O(n) where search takes O(1) guaranteed.

All the topics in lecture eight:

• Weakness of hashing.
• Universal hashing.
• Construction of universal hash functions.
• Perfect hashing.
• Markov inequality.

Follow this link to the full review of lecture eight.

Lecture 9: Search Trees

This lecture primarily discusses randomly built binary search trees. (It assumes you know what binary trees are.) Similar to universal hashing (see previous lecture), they solve a problem when you need to build a tree from untrusted data. It turns out that the expected height of a randomly built binary search tree is still O(lg(n)), more precisely, it’s expected to be 3·lg(n) at most.

Topics explained in lecture nine:

• What are good and bad binary search trees?
• Binary search tree sort.
• Analysis of binary search tree sort.
• BST sort relation to quicksort.
• Randomized BST sort.
• Randomly built binary search trees.
• Convex functions, Jensen’s inequality.
• Expected height of a randomly built BST.

The most surprising idea in this lecture is that the binary search tree sort (introduced in this lecture) does the same element comparsions as quicksort, that is, they produce the same decision tree.

Follow this link to the full review of lecture nine.

Lecture 10: Search Trees (continued)

This is the second lecture on search trees. It discusses self-balancing trees, more specifically, red-black trees. They balance themselves in such a manner that no matter what the input is, their height is always O(lg(n)).

Topics explained in lecture ten:

• Balanced search trees.
• Red-black trees.
• Height of red-black trees.
• Rotations in binary trees.
• How to insert an element in a red-black tree?
• Insert-element algorithm for red-black trees.

Follow this link to the full review of lecture ten.

Lecture 11: Augmenting Data Structures

The eleventh lecture explains how to build new data structures out of existing ones. For example, how to build a data structure that you can update and query quickly for the i-th smallest element. This is the problem of dynamic order statistics and an easy solution is to augment a binary tree, such as a red-black tree. Another example is interval trees - how to quickly find an interval (such as 5-9) that overlaps some other intervals (such as 4-11 and 8-20).

Topics explained in lecture eleven:

• Dynamic order statistics.
• Data structure augmentation.
• Interval trees.
• Augmenting red-black trees to have them perform as interval trees.
• Correctness of augmented red-black tree data structure.

Augmenting data structures require a lot of creativity. First you need to find an underlying data structure (the easiest step) and then think of a way to augment it with data to make it do what you want (the hardest step).

Follow this link to the full review of lecture eleven.

Lecture 12: Skip Lists

This lecture explains skip lists, which is a simple, efficient, easily implementable, randomized search structure. It performs as well as a balanced binary search tree but is much easier to implement. Eric Demaine says he implemented it in 40 minutes before the class (10 minutes to implement and 30 to debug).

In this lecture Eric builds this data structure from scratch. He starts with a linked list and builds up to a pair of linked lists, to three linked lists, until it finds the optimal number of linked lists needed to achieve logarithmic search time.

Next he continues to explain how to algorithmically build such a structure and proves that the search in this data structure is indeed quick.

Follow this link to the full review of lecture twelve.

Lecture 13: Amortized Analysis

Amortized analysis is a technique to show that even if several operations in a sequence of operations are costly, the overall performance is still good. A good example is adding elements to a dynamic list (such as a list in Python). Every time the list is full, Python has to allocate more space and this is costly. Amortized analysis can be used to show that the average cost per insert is still O(1), even though Python occasionally has to allocate more space for the list.

Topics explained in lecture thirteen:

• How large should a hash table be?
• Dynamic tables.
• Amortized analysis.
• Accounting method of amortized analysis.
• Dynamic table analysis with accounting method.
• Potential method of amortized analysis.
• Dynamic table analysis with potential method.

This is one of the most mathematically complicated lectures.

Follow this link to the full review of lecture thirteen.

Lecture 14: Self-Organizing Lists and Competitive Analysis

This lecture concentrates on self-orginizing lists. A self-organizing list is a list that reorders itself to improve the average access time. The goal is to find a reordering that minimizes the total access time. For example, each time an element is accessed, it’s moved to the front of the list, hoping that it might be accessed soon again. This is called move-to-front heuristic.

Competitive analysis can be used to theoretically reason how well such a strategy as moving items to front performs.

Topics explained in lecture fourteen:

• Self-organizing lists.
• Online and offline algorithms
• Worst-case analysis of self-organizing lists.
• Competitive analysis.
• Move-to-front heuristic for self-organizing lists.
• Amortized cost of move-to-front heuristic.

Follow this link to the full review of lecture fourteen.

Lecture 15: Dynamic Programming

This lecture is about the dynamic programming algorithm design technique. It’s a tabular method (involving constructing a table or some part of a table) that leads to a much faster running time of the algorithm.

The lecture focuses on the longest common subsequence problem, first showing the brute force algorithm, then a recursive one, and finally a dynamic programming algorithm. The brute force algorithm is exponential in the length of strings, the recursive one is also exponential, but the dynamic programming solution is O(n·m) where n is the length of one string, and m is the length of the other.

Topics explained in lecture fifteen:

• The idea of dynamic programming.
• Longest common subsequence problem (LCS).
• Brute force algorithm for LCS.
• Analysis of brute-force algorithm.
• Simplified algorithm for LCS.
• Dynamic programming hallmark #1: optimal substructure.
• Dynamic programming hallmark #2: overlapping subproblems.
• Recursive algorithm for LCS.
• Memoization.
• Dynamic programming algorithm for LCS.

The most interesting thing in this lecture is the two hallmarks that indicate that the problem may be solved with dynamic programming. They are “optimal substructure” and “overlapping subproblems”.

The first one means that an optimal solution to a problem contains the optimal solution to subproblems. For example, if z = LCS(x,y) - z is the solution to the problem LCS(x,y) - then any prefix of z is a solution to LCS of a prefix of x and prefix of y (prefix of z is a solution to subproblems).

The second one means exactly what it says, that the problem contains many overlapping subproblems.

Follow this link to the full review of lecture fifteen.

Lecture 16: Greedy Algorithms

This lecture introduced greedy algorithms via the minimum spanning three problem. The minimum spanning tree problem asks to find a tree that connects all the vertices of a graph with minimum edge weight. It seems at first that dynamic programming solution could solve it effectively, but if analyzed more carefully, it can be noticed that the problem exhibits another powerful property — the best solution to each of the subproblems leads to globally optimal solution. Therefore it’s called greedy, it always chooses the best solution for subproblems without ever thinking about the whole problem in general.

Topics explained in lecture sixteen:

• Review of graphs.
• Graph representations.
• Adjacency matrices.
• Adjacency lists.
• Sparse and dense graphs.
• Hand shaking lemma.
• Minimum spanning trees (MSTs).
• Hallmark for greedy algorithms: greedy choice property.
• Prim’s algorithm for finding MST.
• Running time analysis of Prim’s algorithm.
• Idea of Kruskal’s algorithm for MSTs.

Follow this link to the full review of lecture sixteen.

Lecture 17: Shortest Path Algorithms

This lecture starts a trilogy on shortest path algorithm. In this first episode single-source shortest path algorithms are discussed. The problem can be described as following — how to get from one point on a graph to another by traveling the shortest distance (think of a road network). The Dijkstra’s algorithm solves this problem effectively.

Topics explained in lecture seventeen:

• Paths in graphs.
• Shortest paths.
• Path weights.
• Negative path weights.
• Single-source shortest path.
• Dijkstra’s algorithm.
• Example of Dijkstra’s algorithm.
• Correctness of Dijkstra’s algorithm.
• Unweighted graphs.
• Breadth First Search.

The most interesting thing here is that the Dijkstra’s algorithm for unweighted graphs reduces to breadth first search algorithm which uses a FIFO instead of a priority queue because there is no longer a need to keep track of the shortest distance (all the paths have the same weight).

Follow this link to the full review of lecture seventeen.

Lecture 18: Shortest Path Algorithms (continued)

The second lecture in trilogy on shortest paths deals with single-source shortest paths that may have negative edge weights. Bellman-Ford algorithm solves the shortest path problem for graphs with negative edges.

Topics explained in lecture eighteen:

• Bellman-Ford algorithm for shortest paths with negative edges.
• Negative weight cycles.
• Correctness of Bellman-Ford algorithm.
• Linear programming.
• Linear feasibility problem.
• Difference constraints.
• Constraint graph.
• Using Bellman-Ford algorithm to solve a system of difference constraints.
• Solving VLSI (very large scale integration) layout problem via Bellman-Ford.

Follow this link to the full review of lecture eighteen.

Lecture 19: Shortest Path Algorithms (continued)

The last lecture in trilogy deals with all-pairs shortest paths problem — determine of the shortest distances between every pair of vertices in a given graph.

Topics explained in lecture nineteen:

• Review of single source shortest path problem.
• All-pairs shortest paths.
• Dynamic programming.
• Idea from matrix multiplication.
• Floyd-Warshall algorithm for all-pairs shortest paths.
• Transitive closure of directed graph.
• Johnson’s algorithm for all-pairs shortest paths.

An interesting point here is how the Floyd-Warshall algorithm that runs in O((number of vertices)³) can be transformed into something similar to Strassen’s algorithm to compute the transitive closure of a graph (now it runs in O((number of vertices)^lg7).

Follow this link to the full review of lecture nineteen.

Lecture 20: Parallel Algorithms

This is an introductory lecture to multithreaded algorithm analysis. It explains the terminology used in multithreaded algorithms, such as, work, critical path length, speedup, parallelism, scheduling, and others.

Topics explained in lecture twenty:

• Dynamic multithreading.
• Subroutines: spawn and sync.
• Logical parallelism and actual parallelism.
• Multithreaded computation.
• An example of a multithreaded execution on a recursive Fibonacci algorithm.
• Measuring performance of a multithreaded computation.
• The concept of speedup.
• Maximum possible speedup.
• Linear speedup.
• Super-linear speedup.
• Parallelism.
• Scheduling.
• Greedy scheduler.
• Grand and Brent theorem of competitiveness of greedy schedules.
• *Socrates and Cilkchess chess programs.

Follow this link to the full review of lecture twenty.

Lecture 21: Parallel Algorithms (continued)

The second lecture on parallel algorithms shows how to design and analyze multithreaded matrix multiplication algorithm and multithreaded sorting.

Topics explained in lecture twenty-one:

• Multithreaded algorithms.
• Multithreaded matrix multiplication.
• Performance analysis of the multithreaded matrix multiplication algorithm.
• Multithreaded sorting.
• Multithreaded merge-sort algorithm.
• Parallel-merge subroutine.
• Analysis of merge-sort with parallel-merge subroutine.

Follow this link to the full review of lecture twenty-one.

Lecture 22: Cache Oblivious Algorithms

Cache-oblivious algorithms take into account something that has been ignored in all the algorithms so far, particularly, the cache. An algorithm that can be transformed into using cache effectively will perform much better than a one that doesn’t. This lecture is all about how to lay out data structures in memory in such a way that memory transfers are minimized.

Topics explained in lecture twenty-two:

• Modern memory hierarchy.
• The concept of spatial locality and temporal locality.
• Two-level memory model.
• Cache-oblivious algorithms.
• Blocking of memory.
• Memory transfers in a simple scanning algorithm.
• Memory transfers in string-reverse algorithm.
• Memory analysis of binary search.
• Cache oblivious order statistics.
• Cache oblivious matrix multiplication algorithm.

Follow this link to the full review of lecture twenty-two.

Lecture 23: Cache Oblivious Algorithms (continued)

This is the final lecture of the course. It continues on cache oblivious algorithms and shows how to store binary search trees in memory so that memory transfers are minimized when searching in them. It wraps up with cache oblivious sorting.

Topics explained in lecture twenty-three:

• Static search trees.
• Memory efficient layout of static binary search trees in memory.
• Analysis of static search trees.
• Cache aware sorting.
• Cache-oblivious sorting.
• Funnel sort.
• K-funnel data structure.

This is the most complicated lecture in the whole course. It takes a day to understand the k-funnel data structure.

Follow this link to the full review of lecture twenty-three.

That’s it. This was the final lecture. I hope you find this summary useful.

Upcoming on my blog — review of MIT’s Linear Algebra course.

At first I thought I’d post Linear Algebra to a separate blog section that does not appear in the RSS feed but then I gave it another thought and came to a conclusion that every competent programmer must know the linear algebra and therefore it’s worth putting them in the feed.

You can surely be a good programmer without knowing linear algebra, but if you want to work on great problems and make a difference, then you absolutely have to know it.

Stay tuned!

Good article. The comments are even better:

reading this article reminds me countless time I have looked at the clock and the second hand it not moving and then it starts, I am sure this takes longer than a second

That’s always freaked me out. I've mentioned it once or twice but people just think I'm crazy so I don’t bring it up anymore. This guy, Frank, explains the phenomenon:

In more ‘joe sixpack’-terms. After you move your eyes fast, they are unable to collect information for a fraction of a second. When the eyes comes back ‘online’ the brain collects motion-information for an equal fraction of a second, and extrapolates the information backwards to create what things should have looked like and fills this fabricated visual information into your memory. Since the needle (or digit) didn’t move while the brain was collecting info for the extrapolation, it won’t be able to predict that it moved in the past either.

Crazy. I knew something was going on.

# | Discuss

This one is just so simple, I can't believe I didn't know about it earlier.

First, setup the cdpath or CDPATH variable:

cdpath=(~ ~/Projects/apps ~/Projects/tools ~/Projects/plugins ~/Projects/sites)

Now, changing directory in the shell becomes a whole world easier:

tomw@fellini:~$ cd super-secret-app
~/Projects/apps/super-secret-app
tomw@fellini:~/Projects/apps/super-secret-app$ cd Documents
~/Documents
tomw@fellini:~/Documents$ cd tomafro.net
~/Projects/sites/tomafro.net
tomw@fellini:~/Projects/sites/tomafro.net $

I've already added this to my dotfiles.

acts_as_state_machine is a great plugin really useful when you want to add constraints and behavior to your model objects.

Note : Those who don’t know what this plugin is all about should stop reading right there or risk being completely lost.

One thing that seems impossible to do with the plugin is to have variable “initial states” for an object. Say for example that you have a User model that needs to act as a state machine. New users have to fill up a signup form to gain access to the application. These new users will be “pending” until an administrator approve them (enabled) or refuse them (disabled)

So far so good. But what if an administrator can also create a new user? In this case we would’nt want the user to be “pending”, we want him to be “enabled” right away.

I experimented a similar scenario, so I tried a few things to bypass the initial state :

Too bad, so I tried this :

Of course, the following worked :

Yuk… there had to be something better.

Finally, I learned that initial_state was an inheritable attribute. I didn’t know what those were all about so I did some googling. The only good explanation I found is this one.

Anyway, I was able to override the initial state of my user object by doing this :

It’s not pretty I know, but at least it gets the job done. I wonder if the fact that you cannot “easily” change the initial state programmatically is a missing feature that should be added in a future version… or if it’s only my understanding of a “state machine” that sucks. Any thoughts?

Rails 2.1 is now available for general consumption with all the features and fixes we’ve been putting in over the last six months since 2.0. This has been a huge effort by a very wide range of contributors helping to make it happen.

Over the past six months, we’ve had 1,400 contributors creating patches and vetting them. This has resulted in 1,600+ patches. A truly staggering number. And lots of that has made it into this release.

New features
The new major features are:

• Time zones (by Geoff Buesing): Tutorial | Introdction | Railscast
• Dirty tracking: Introduction (partial updates) | Railscast
• Gem Dependencies: Introduction | Railscast
• Named scope (by Nick Kallen): Introduction | Railscast
• UTC-based migrations: Introduction | Railscast
• Better caching: Introduction

Thanks to Ryan Daigle for the feature introductions and Ryan Bates for the Railscasts. It makes writing the release notes so much easier :).

As always, you can install with:

gem install rails

...or you can use the Git tag for 2.1.0.

Enjoy!

I get to see a lot of Ruby code while writing for Ruby Inside. Most is very good, but sometimes we forget some of Ruby's shortcuts and tricks and instead reinvent the wheel. In this post I present 21 different Ruby tricks, from those that most experienced developers already use every day to those that are more obscure. Before writing this piece, for example, I had no idea about trick number 2! Whatever your level, a refresh may help you the next time you encounter similar scenarios.

Note to beginners: If you are still learning Ruby, check out my Beginning Ruby book (18 5-star reviews so far). It’s only $26.39 on Amazon in print or Kindle format or available from the publisher in PDF format.

1 - Extract regular expression matches quickly

A typical way to extract data from text using a regular expression is to use the match method. There is a shortcut, however, that can take the pain out of the process:

email = "Fred Bloggs <fred@bloggs.com>"
email.match(/<(.*?)>/)[1]            # => “fred@bloggs.com”
email[/<(.*?)>/, 1]                  # => “fred@bloggs.com”
email.match(/(x)/)[1]                # => NoMethodError [:(]
email[/(x)/, 1]                      # => nil
email[/([bcd]).*?([fgh])/, 2]        # => “g”

2 - Shortcut for Array#join

It's reasonably common knowledge that Array#*, when supplied with a number, multiplies the size of the array by duplicate elements, but it's a lot lesser known that when supplied with a string Array#* instead does a join!

%w{this is a test} * ", "                 # => “this, is, a, test”
h = { :name => "Fred“, :age => 77 }
h.map { |i| i * "=" } * "\n"              # => “age=77\nname=Fred”

3 - Format decimal amounts quickly

Formatting floating point numbers into a form used for prices can be done with sprintf or, alternatively, with a formatting interpolation:

money = 9.5
"%.2f" % money                       # => “9.50″

4 - Surround text quickly

The formatting interpolation technique from #3 comes out again, this time to insert a string inside another:

"[%s]" % "same old drag"             # => “[same old drag]“

You can use an array of elements to substitute in too:

x = %w{p hello p}
"<%s>%s</%s>" % x                    # => “<p>hello</p>"

5 - Delete trees of files

Don't resort to using the shell. Ruby comes with a handy file utilities library that can do your bidding:

require 'fileutils'
FileUtils.rm_r 'somedir'

Be careful how you use this one!

6 - Exploding enumerables

* can be used to “explode” enumerables (arrays and hashes). We'll let the examples do the talking:

a = %w{a b}
b = %w{c d}
[a + b]                              # => [["a", "b", "c", "d"]]
[*a + b]                             # => ["a", "b", "c", "d"]

a = { :name => "Fred“, :age => 93 }
[a]                                  # => [{:name => "Fred", :age =>93}]
[*a]                                 # => [[:name, "Fred"], [:age, 93]]

a = %w{a b c d e f g h}
b = [0, 5, 6]
a.values_at(*b).inspect              # => ["a", "f", "g"]

7 - Cut down on local variable definitions

Instead of defining a local variable with some initial content (often just an empty hash or array), you can instead define it “on the go” so you can perform operations on it at the same time:

(z ||= []) << 'test'

8 - Using non-strings or symbols as hash keys

It's very rare you see anyone use non-strings or symbols as hash keys. It's totally possible though, and sometimes handy (and, no, this isn't necessarily a great example!):

does = is = { true => 'Yes', false => 'No' }
does[10 == 50]                       # => “No”
is[10 > 5]                           # => “Yes”

9 - Use 'and' and 'or' to group operations for single liners

This is a trick that more confident Ruby developers use to tighten up their code and remove short multi-line if and unless statements:

queue = []
%w{hello x world}.each do |word|
  queue << word and puts "Added to queue" unless word.length <  2
end
puts queue.inspect

# Output:
#   Added to queue
#   Added to queue
#   ["hello", "world"]

10 - Do something only if the code is being implicitly run, not required

This is a very common pattern amongst experienced Ruby developers. If you're writing a Ruby script that could be used either as a library OR directly from the command line, you can use this trick to determine whether you're running the script directly or not:

if __FILE__ == $0
  # Do something.. run tests, call a method, etc. We're direct.
end

11 - Quick mass assignments

Mass assignment is something most Ruby developers learn early on, but it's amazing how little it's used relative to its terseness:

a, b, c, d = 1, 2, 3, 4

It can come in particularly useful for slurping method arguments that have been bundled into an array with *:

def my_method(*args)
  a, b, c, d = args
end

If you want to get really smart (although this is more 'clever' than truly wise):

def initialize(args)
  args.keys.each { |name| instance_variable_set "@" + name.to_s, args[name] }
end

12 - Use ranges instead of complex comparisons for numbers

No more if x > 1000 && x < 2000 nonsense. Instead:

year = 1972
puts  case year
        when 1970..1979: "Seventies"
        when 1980..1989: "Eighties"
        when 1990..1999: "Nineties"
      end

13 - Use enumerations to cut down repetitive code

%w{rubygems daemons eventmachine}.each { |x| require x }

14 - The Ternary Operator

Another trick that's usually learned early on by Ruby developers, but again something I see quite rarely in less experienced developers' code. The ternary operator is not a fix-all, but it can sometimes make things tighter.

puts x == 10 ? "x is ten" : "x is not ten"

# Or.. an assignment based on the results of a ternary operation:
LOG.sev_threshold = ENVIRONMENT == :development ? Logger::DEBUG : Logger::INFO

15 - Nested Ternary Operators

It may be asking for trouble but ternary operators can be nested within each other (after all, they only return objects, like everything else):

qty = 1
qty == 0 ? 'none' : qty == 1 ? 'one' : 'many'
# Just to illustrate, in case of confusion:
(qty == 0 ? 'none' : (qty == 1 ? 'one' : 'many'))

16 - Fight redundancy with Ruby's logical provisions

I commonly see methods using this sort of pattern:

def is_odd(x)
  # Wayyyy too long..
  if x % 2 == 0
    return false
  else
    return true
  end
end

Perhaps we can use a ternary operator to improve things?

def is_odd(x)
  # Don't EVER put false and true in a ternary operator!!
  x % 2 == 0 ? false : true
end

It's shorter, and I see that pattern a lot but really you should go one step further and just rely on the true / false responses Ruby's comparison operators already give!

def is_odd(x)
  # Use the logical results provided to you by Ruby already..
  x % 2 != 0
end

17 - See the whole of an exception's backtrace

def do_division_by_zero; 5 / 0; end
begin
  do_division_by_zero
rescue => exception
  puts exception.backtrace
end

18 - Allow both single items AND arrays to be enumerated against

# [*items] converts a single object into an array with that single object
# of converts an array back into, well, an array again
[*items].each do |item|
  # …
end

19 - Rescue blocks don't need to be tied to a 'begin'

def x
  begin
    # …
  rescue
    # …
  end
end

def x
  # …
rescue
  # …
end

20 - Block comments

I tend to see this in more 'old-school' Ruby code. It's surprisingly under-used though, but looks a lot better than a giant row of pound signs in many cases:

puts "x"
=begin
  this is a block comment
  You can put anything you like here!

  puts “y”
=end
puts "z"

21 - Rescue to the rescue

You can use rescue in its single line form to return a value when other things on the line go awry:

h = { :age => 10 }
h[:name].downcase                         # ERROR
h[:name].downcase rescue "No name"        # => “No name”

If you want to post your own list of Ruby tricks to your blog, send trackback here or leave a comment, and I'll link to all of them in a future post. Alternatively, feel free to post your own Ruby tricks as comments here, or critique or improve on those above.

As an aside, Ruby Inside is exactly two years old today. Thanks for your support! Intriguingly, the first post was another Ruby trick that I forgot to include above, so check that out too.

So there’s been a bit of activity on the Paperclip front. I’ve added Amazon S3 support using the RightAWS gem. Some fellow githubbers have contributed some patches to fix up said S3 support, as well as to add more (and better) validations for content type, etc. We’ve brought it up to a nice, round v2.1.2 as of yesterday. Give yourselves a round of applause.

I highly encourage you to give it a whirl if you haven’t already. It’s very easy to both get and to use!

An interesting note!

Ken Robertson has gone to great lengths to port Paperclip to DataMapper, which should be great news for all you Merbers out there. He’s kept it quite up-to-date, and it’s right alongside the 2.1.2 current release. Hopefully we’ll be able to merge codebases in the future, though right now there’s enough of a difference between DM and AR to make that not terribly feasible.

Here’s a handy tip!

One of the most frequently asked questions is how to use data from your instances in the path and/or URL. The answer is the interpolations hash, which is quite user-extensible. Let’s say you had a song that played in the background of each User’s profile (making this exercise purely hypothetical, of course), and you wanted its name to be the same as the User’s username.

One really good way of allowing this functionality would be to add the following to your config/initializers/paperclip.rb file:

1
2
3

Paperclip::Attachment.interpolations[:username] = proc do |attachment, style|
  attachment.instance.login # or whatever you've named your User's login/username/etc. attribute
end

The #instance method is the instance of the model that this attachment is attached to. You can access any of the model’s attributes, methods, associations, and so on from that object just like normal. Also note that you don’t have to name your interpolation the same thing as the attribute you’re interpolating (though it helps clarity).

Now you can add this to your :path and :url parameters like so:

1
2
3
4
5

class User < ActiveRecord::Base
  has_attached_file :song,
                    :path => ":rails_root/public/system/:attachment/:username.:extension",
                    :url  => "/:attachment/:username.:extension"
end

When you call #url or #path on your attachment, Paperclip will run through the interpolations hash, find strings that match its keys, and replace them with the return values of the procs. In this case, you’d produce a lovely url of ”/songs/jyurek.mp3”

It’s a very easy way to add flexibility to your files’ names without having to modify any code yourself.

Another handy tip!

S3 support is now baked in! The updated has_attached_file call looks kinda like this one does:

1
2
3
4
5
6
7
8

class House < ActiveRecord::Base
  has_attached_file :blueprint,
                    :styles => { :thumbnail => "150x150" },
                    :path => ":attachment/:id/:style.:extension",
                    :storage => :s3,
                    :s3_credentials => "#{RAILS_ROOT}/config/s3.yml",
                    :bucket => "bucket-of-holding"
end

Please note the additional options, including:

• :storage: Specify :s3 here to use S3. Strictly speaking you could specify :filesystem here if you’re using the filesystem, but it’s the default so don’t bother.
• :s3_credentials: You should give this a Hash, a path to a file, or a File object. The File should contain a YAML-ized Hash, and the contents of the Hash should be the access_key_id and secret_access_key used to access your S3 account. You can also “environment-space” these inside the hash, just like your database.yml file.
• :bucket: The name of the S3 bucket that will be holding your data.

Note that there’s no :url option. That’s because the S3 URLs are generated from the bucket and the path name, so you don’t have to worry about them. You can also specify permissions for your files, in case you don’t want the default “public-read”, by using :s3_permissions.

You can find more about the S3 Storage options and the Filesystem Storage options at their RDocs.

Keep up to date!

Remember, there’s always the Paperclip Google Group and the Paperclip Lighthouse Account in case you have problems, questions, or feature requests.