CPSC 411
Fall 2008
Homework

General Instructions:
1. 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.

2. 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.

3. 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.

4. Homework is always due at the beginning of class.

[Homework 1] [Homework 2] [Homework 3] [Homework 4] [Homework 5] [Homework 6] [Homework 7] [Homework 8]

Homework 8: Due Tuesday, Dec 2, 2:20 PM

1. Explain in your own words what the Church-Turing thesis says and why it is significant.

2. 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.

3. State Rice's theorem and explain its significance.

4. Use Rice's theorem to prove that language L from problem 2 is undecidable.

Homework 7: Due Tuesday, Nov 18, 2:20 PM

• 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.)

Homework 6: Due Tuesday, Nov 11, 2:20 PM

Homework 5: Due Tuesday, Nov 4, 2:20 PM

• 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

Homework 4: Due Thursday, Oct 23, 2:20 PM

• Ex. 22.1-3

• Ex. 22.2-7

• Ex. 22.3-6

• Ex. 22.5-3

• Prob. 22-3

Homework 3: Due Thursday, Oct 9, 2:20 PM

Homework 2: Due Tuesday, Sep 23, 2:20 PM

• 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.

Homework 1: Due Thursday, Sep 4, 2:20 PM

• 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).