Conjunction with similar quiz planned for the end the semester

Introduction to Algorithms Massachusetts Institute of Technology Singapore-MIT Alliance Professors Erik Demaine, Lee Wee Sun, and Charles E. Leiserson	September 5, 2001 6.046J/18.410J SMA5503 Handout 6

Diagnostic Quiz 0

Please do not spend more than ONE HOUR completing this diagnostic. It is not intended to measure your intelligence or ability, and it will lose its value as a diagnostic if you spend too much time on it. Just do the best you can in an hour.

Consider the following pseudocode:

1 if

Problem 3

Using -notation, describe the worst-case running time of the best algorithm that you know for

(d) Inserting an element in a sorted linked-list, once the position is found.

4 Handout 6: Diagnostic Quiz 0

Problem 5	of a balanced binary search tree relate to the number of nodes	�
		�

Handout 6: Diagnostic Quiz 0 5

Problem 7

(b) Professor Wiles has just produced a 10,000-page proof that Problem B is unsolvable. If the

proof turns out to be valid, can we conclude that problem A is unsolvable as well? Answer yes or

that are no more than units apart.

Here are two attempts to prove this statement.

Proof (b): Partition the square into squares, each with a side of unit. If any two points are

on or inside one of these smaller squares, the distance between these two points will be at

Problem 9
Give an inductive proof of the following statement:

For every natural number�

Let be an indicator random variable. Which of the following statements are true? (Circle all

that apply.)