Introduction to Algorithms
Massachutts Institute of Technology 6.046J/18.410J Singapore-MIT Alliance SMA5503 Professors Erik Demaine,Lee Wee Sun,and Charles E.Leirson Handout6
Grade Grade
18
29
310
411
512
613
飞机退票手续费714
Subtotal Subtotal
Total
为了这一片净土Name:
Problem1
Consider the following pudocode:
R OUTINE
1if
2then return
3el return R OUTINE
(a)Give a one-ntence description of what R OUTINE does.(Remember,don’t guess.)
(b)Give a precondition for the routine to work correctly.
清炖鱼头(c)Give a one-ntence description of a faster implementation of the same routine.
金刚经读诵完整版
Problem2
小甲虫Give a short(1–2-ntence)description of each of the following data structures:
(a)FIFO queue
(b)Priority queue
(c)Hash table
Problem3
Using-notation,describe the worst-ca running time of the best algorithm that you know for each of the following:
(a)Finding an element in a sorted array.
(b)Finding an element in a sorted linked-list.
(c)Inrting an element in a sorted array,once the position is found.
(d)Inrting an element in a sorted linked-list,once the position is found.
Problem4
Describe an algorithm that locates thefirst occurrence of the largest element in afinite list of integers,where the integers are not necessarily distinct.What is the worst-ca running time of your algorithm?
Problem5
How does the height of a balanced binary arch tree relate to the number of nodes in the tree?
Problem6
Does an undirected graph with vertices,each of degree,exist?If so,draw such a graph.If not, explain why no such graph exists.
Problem7
简爱英文读后感It is known that if a solution to Problem A exists,then a solution to Problem B exists also.
(a)Professor Goldbach has just produced a1,000-page proof that Problem A is unsolvable.If his proof
turns out to be valid,can we conclude that Problem B is also unsolvable?Answer yes or no(or don’t know).
(b)Professor Wiles has just produced a10,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 no(or don’t know).
Problem8
Consider the following statement:
If points are placed anywhere on or inside a unit square,then there must exist two
that are no more than
秋季运动会开幕词units of one of the other points,since the furthest from the corners it can be is the center,which is exactly
units.Since there are points and only squares,at least two points must fall on or inside one of the smaller squares,giving a t of points that are no more than
Problem9
Give an inductive proof of the following statement:
For every natural number,we have.
Problem10
We want to line up out of children.Which of the following express the number of possible line-ups?(Circle the right answer.)
(a)
(b)
(c)
(d)
(e)None of the above
(f)Don’t know
Problem11
A deck of cards is shuffled thoroughly.What is the probability that the aces are all next to each other?(Circle the right answer.)
古代宫廷糕点(a)
(b)
(c)
(d)
(e)None of the above
(f)Don’t know
