Free Intro to Algorithms video lectures from MIT

April 16, 2009 | Leave a Comment

Course Description

This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing.

http://academicearth.org/courses/introduction-to-algorithms

Posted by | Filed Under Programming, Lectures, Algorithms 

Free CS video lectures from Harvard

April 16, 2009 | Leave a Comment

Course description:
Introduction to Computer Science I is a first course in computer science at Harvard College for concentrators and non-concentrators alike. More than just teach you how to program, this course teaches you how to think more methodically and how to solve problems more effectively. As such, its lessons are applicable well beyond the boundaries of computer science itself. That the course does teach you how to program, though, is perhaps its most empowering return. With this skill comes the ability to solve real-world problems in ways and at speeds beyond the abilities of most humans.

http://academicearth.org/courses/introduction-to-computer-science-i

Posted by | Filed Under Programming, Lectures, Algorithms 

Mental Math shortcuts

December 28, 2007 | Leave a Comment

Here’s a collection of time-saving math shortcuts, great for back-of-the-envelope estimates.

Time and Distance

60 mph = 1 mile per minute

  • Going 60 mph and the exit is in 10 miles? That’s 10 minutes.
  • Been driving a half hour? That’s about 30 miles at highway speeds.

Feet Per Second = MPH * 1.5
MPH = Feet Per Second * 2/3 (derivation)

  • 60 mph is about 90 feet per second (88 exactly), so just multiply by 1.5. Or, just add half to itself (60 + 30 = 90).
  • Going 100 mph? That’s 150 fps.
  • Going 10 fps? That’s about 7 mph (10 * 2/3 is 6.666). Or, just take away 1/3 (10 - 3 = 7).

speed of light = 1 foot per nanosecond (derivation)

  • The US is about 3000 miles long. There’s about 5000 feet/mile, so that’s about 3000 × 5000 or 15 million feet. 15 million feet takes 15 million nanoseconds, or 15/1000, or 15 milliseconds. That’s the minimum time for a signal to go across the country.
  • Inside a microchip, if you have a clock cycle every nanosecond (1 GHz), your signal can only travel 1 foot at most (or less, depending on the material). Even light takes 30ns to cross a 30 foot room.

1 year = 250 work days = 2000 work hours (derivation)

  • Project takes 1000 man hours? That’s 6 months for 1 person.
  • Daily commute of 1/2 hour? That’s .5 * 250 = 125 hours in the car each year.

Money and Finance

$1/hour = $2000/year (derivation)

  • Earn $25/hour? That’s about 50k/year.
  • Make 200k/year? That’s about $100/hour. This assumes a 40-hour work week.

$20/week = $1000/year (derivation)

  • Spend $20/week at Starbucks? That’s a cool grand a year.

Rule of 72: Years To Double = 72/Interest Rate (derivation)

  • Have an investment growing at 10% interest? It will double in 7.2 years.
  • Want your investment to double in 5 years? You need 72/5 or about 15% interest.
  • Growing at 2% a week? You’ll double in 72/2 or 36 weeks. You can use this rule for any duration of time, not just years.
  • Inflation at 4%? It will halve your money in 72/4 or 18 years.

Mental Arithmetic

10,000 = hundred hundred
million = thousand thousand
billion = thousand million
trillion = million million

  • 1% of 10k is 100. The Dow is roughly 10k (it’s about 12k now). So if the dow drops 100, it’s about a 1% loss.
  • What’s 5k x 50k? That’s 250 * thousand * thousand or 250 million.

2^6 = 64 (the sixes match: six and sixty-four)
2^10 ~ thousand (1 kb)
2^20 ~ million (1 mb)
2^30 ~ billion (1 gb)

  • Sure, 2 to the tenth = 1024, but 1000 is good enough for government work. (Read on about KB vs KiB).
  • Have 32-bit color? That’s 2 + 30 bits, aka 2^2 billion, or 4 billion (4gb exactly).
  • Have a 16-bit number? That’s 6 + 10 bits, or 2^6 thousand, or 64 thousand (64 kb).

a% of b = b% of a

  • It’s not immediately clear, but it’s true: a% of b = .01 * a * b, which is the same as b% of a (.01 * b * a).
  • What’s 16% of 25? The same as 25% of 16: 4
  • What’s 43% of 200? Same as 200% of 43: 86.

Posted by | Filed Under Algorithms 

Analog clock. How many times does the hour and minute hands overlap?

October 20, 2007 | Leave a Comment

Imagine an analog clock set to 12 o’clock. Note that the hour and minute hands overlap. How many times each day do both the hour and minute hands overlap? How would you determine the exact times of the day that this occurs?

Posted by | Filed Under Algorithms 

Next Page »