Sums and Approximations When you analyze the running time of an algorithm, the probability some procedure succeeds, or the behavior of a load-balancing or communications scheme, you'll rarely get a simple answer. The world is not so kind. More likely, you'll end up with a complicated sum:

Recursion-breaking an object down into smaller objects of the same typeis a ma- jor theme in mathematics and computer science. For example, in an induction proof we establish the truth of a statement()from the truth of the statement P(n-1). In pro- gramming, a recursive algorithm solves a problem by applying itself to smaller instances

1 Introduction normally, a graph is a bunch of dots connected by lines. Here is an example of a graph

1 Coloring Graphs Each term, the MIT Schedules Office must assign a time slot for each final exam. This is not easy, because some students are taking several classes with finals, and a student can take only one test during a particular time slot. The Schedules Office wants to avoid all conflicts, but to make the exam period as short as possible

Srini devadas and Eric Lehman Lecture notes Number theory ll Image of Alan Turing removed for copyright reasons s The man pictured above is Alan Turing, the most important figure in the history of mputer science. For decades, his

Number Theory I Number theory is the study of the integers. Number theory is right at the core of math ematics; even Ug the Caveman surely had some grasp of the integers- at least the posi tive ones. In fact, the integers are so elementary that one might ask, What's to study?

Srini Devadas and Eric Lehman Lecture Notes Induction III 1 Two Puzzles Here are two challenging puzzles. 1.1 The 9-Number Puzzle

1 Unstacking Here is another wildly fun 6.042 game that's surely about to sweep the nation! You begin with a stack of n boxes. Then you make a sequence of moves. In each move, you divide one stack of boxes into two nonempty stacks. The game ends when you have n stacks, each containing a single box You earn points for each move; in particular, if you divide one stack of height a b into two stacks with heights a and b, then you score

Why do you believe that 3+3=6? Is it because your second-grade teacher, Miss Dalrymple, told you so? She might have been lying, you know Or are you trusting life experience? If you have three coconuts and someone gives you three more coconuts, then you have--ahal--six coconuts. But if that is the true basis for your belief, then why do you also believe that

It's really sort of amazing that people manage to communicate in the English language Here are some typical sentences: 1. You may have cake or you may have ice cream 2. If pigs can fly, then you can understand the Chernoff bound 3. If you can solve any problem we come up with then you get an a for the course. 4. Every American has a dream What precisely do these sentences mean? Can you have both cake and ice cream or must you choose just one desert? If the second sentence is true, then is the Chernoff bound incomprehensible? If you can solve some problems we come up with but not all, then do you get an a for the course? And can you still get an a even if you cant solve any of the problems? Does the last sentence imply that all Americans have the same dream or might