Hand-written Part (20%)

Exercise

1. (5%) (Exercise R-4.24 of the textbook) Show that if d(n) is O(f(n)) and e(n) is O(g(n)), then d(n)-e(n) is not necessarily O(f(n)-g(n)).
2. (5%) (Exercise C-4.8 of the textbook. Note that you need to prove it!) Give an example of a positive function f(n) such that f(n) is neither O(n) nor W(n).
3. (5%) Prove or disapprove the following statement. “For non-negative functions f, g, h, if f(n) = O(g(n)), then f(n) + h(n) = O(g(n) + h(n)).”
4. (5%) (Exercise R-4.7 of the textbook) The number of operations executed by algorithms A and B is $8 n \log n$ and $2n^2$, respectively. Determine $n_0$ such that A is better than B for $n \geq n_0$.

Submission guidelines

1. Format: A4 blank paper(s). Please add your class information (Mon/Tue).
2. Deadline: 4/19 (Tue) 23:00
3. Location: 409: There will have two boxes outside the room. Please put your HW in the right box as indicated. And we will place the boxes on 4/18.

Programming Part: Nonograms (Maze traversal, 80%)

Problem definition

In this homework, you need to write a program to solve the game of nonogram. More info about the game can be found at Wikipedia (English, Chinese), or 漫談 nonogram (in Chinese). You can also google "nonogram" or "picross" to find interactive pages to play the game, such as here and there.

Write a program to output the map based on the input criteria. The input has the following format:

The output format is as shown in the following test cases.

Here are some examples of nonograms:

One way to solve the problem is shown here. You can find many different methods, from simple to complex ones, to solve the problem.

Requirements & suggestions

• To solve the problem, you can simply use the maze traversal technique covered in the class, which uses a stack for DFS (depth first search).
• Since there is a time limit, brutal use of DFS may takes too long. So you should try the following strategies:
  1. Try to create an good initial guess of the map. Sometimes the initial guess can lead you to the answer directly. Here are some youtube tutorials:
     • Nonogram Tutorial
     • How to Play Picture Cross (Picross / Nonograms / Griddlers)
     • How To Do Nonogram Puzzles With Pencil and Paper
     • Pic-a-Pix Tutorial: How to solve a Pic-a-Pix logic puzzle
     Apply the trick systematically, for instance, row by row and column by column, and repeat the same procedure until the map converges. Try it over simple examples to make sure you understand the process.
  2. Start DFS if the initial guess does not lead to an answer. But remember to cut down as many infeasible braches as you can during DFS.
  If you are clueless about these strategies, please consult TAs ASAP.
• You can safely assume that
  1. 0 < m, n < 31.
  2. There is at least one solution to each test case.
  3. Each row and each column should have at least a black tile.
• Your program should take the input from the standard input and send the output to the standard output.
• The output may not be unique. As long as the output fulfils the given input, it is counted as a correct answer.
• TAs will use 5 test cases (with 2 out of the 8 basic test cases shown below, and 3 of 30x30 problems with similar difficulty as those shown in the 38 random test cases shown below) to test the correctness of your program, with a time limit of 60 seconds for each case.
• You need to write the program from scratch. You cannot use any open-source or readily available nonogram solvers.

Test cases

1. Basic test cases
   1. Simplest (3x2): input, output
   2. Checker board (4x4):input, output
   3. Tree (5x5): input, output
   4. Pig face (14x13): input, output
   5. Scorpion (20x20): input, output
   6. Beckham (20x20): input, output
   7. Smoke (20x20): input, output
   8. Cat (25x25): input, output
2. Random test cases

Submission guidelines

1. hw3/*, your source code.
2. hw3/Makefile, where the TAs can use the command ”make” on CSIE R217 linux machines to compile your code, and ”make run” to run your program.