Fall 2008

Homework

- The numbers refer to the textbook. Don't get confused between
Exercises, at the end of each section, and Problems, at the end of each
chapter.
- Write clearly and legibly. Grading will be based on correctness,
clarity, and whether your solution is of the appropriate length.
If your handwriting is deemed too illegible, you may be asked
to type your homeworks.
- Don't forget to acknowledge all sources of assistance.
Unless otherwise instructed, you must write up your homework
on your own. Turn in your homework together with this
cover sheet.
- Homework is always due at the
**beginning**of class.

- Explain in your own words what the Church-Turing thesis says
and why it is significant.
- Consider the language L that consists of encodings of
all programs P such that P accepts input 0.
Show using a reduction from H (the halting set) that L
is undecidable. (Do not use Rice's theorem.)
You will get generous partial credit for setting up the problem
correctly and explaining what you have to do.
- State Rice's theorem and explain its significance.
- Use Rice's theorem to prove that language L from problem 2 is undecidable.

- Ex. 34.1-4
- Ex. 34.2-1
- Ex. 34.5-1
- Prob. 34-1, parts (a) and (c)
- Read Prob 34-3 enough to realize that the graph coloring problem is NP-complete. (Nothing to turn in.)

- Consists solely of this programming assignment (click on the link)

- Ex. 24.3-6.
*Hint:*Change the priority queue implementation to exploit the fact that weights are always in the set {0,1,...,W}. - Prob. 24-1 parts (a) and (c)
- Prob. 25-1, part (a)
- Ex. C.2-3 (in Appendix C)
- Ex. C.3-2
- Ex. C.3-3
- Ex. 5.2-4
- Ex. 7.4-4
- Ex. 7.4-5

- Ex. 22.1-3
- Ex. 22.2-7
- Ex. 22.3-6
- Ex. 22.5-3
- Prob. 22-3

- Ex. 15.4-5
- Prob. 15-4
- Prob. 15-5
- Ex. 17.1-3
- Ex. 17.2-2
- Ex. 17.3-2
- Ex. 17.4-3
- Ex. 21.1-3
- Ex. 21.2-2
- Ex. 21.3-1
- Ex. 21.4-4
- Follow this link for the programming assignment

- You have choice: Either do Ex. 28.2-1 (boring but easy)
or Ex. 28.2-6 (more interesting).
- Ex. 16.3-2.
- Ex. 16.3-6.
- Ex. 23.2-8.
- Prob. 23-4 (b)
- PROGRAMMING ASSIGNMENT: You may use any programming language
you like. You are to submit a hard copy of the code as part of
your homework submission. You must demonstrate the correct compilation
and execution of your program to Yue at a mutually agreeable time.
Recall the game of Battleship: There is a 10 by 10 grid on which the first player hides three battleships. Each battleship takes up five consecutive grid squares in a line (horizontal or vertical), so 15 grid square are occupied. The second player guesses a series of grid positions and is informed whether each one hits or misses a battleship; once the second player has found all the occupied grid squares, the game is over. You are to write a program that plays the game Battleship. To simulate the first player, randomly choose locations for the battleships. To simulate the second player, devise a strategy for finding all the battleship locations as quickly as you can. Use a divide-and-conquer or binary search approach. (Source: Skiena,

*Algorithm Design Manual*.)Feel free to make a nice user interface.

- Ex. 3.1-2. In more detail, find c and n0 that satisfy the
definition of (n+a)^b = O(n^b). Then find (possibly different)
c and n0 that satisfy the definition of (n+a)^b = Omega(n^b).
- Problem 3-2, parts (b) and (d). Justify your answers.
- Exercise 8.1-3
- (A) Draw the decision tree for insertion sort on inputs of length 4.
Refer to the pseudocode on p. 24 of the textbook.
- (B) In a published paper, an author decribes a comparison-based
sorting algorithm that runs in O(n log sqrt(n)) time.
How is this possible, since there is an Omega(n log n) lower
bound on sorting? (from Skiena's book)
- (C) Suppose someone claims to have developed a way to insert and remove items from a binary heap in constant time, no matter how many elements are in the heap. Is this possible? Explain your answer. (Hint: Think about the sorting lower bound.)