From EECS492_W11
Jump to: navigation, search

Problem Set 2 (65 points)[edit]

EECS492 problem sets are a collaborative activity amongst your staff-assigned team. You may also discuss the problem sets and problem solving approach with other teams, but the work you submit must be wholly that of your team. In particular, you may not derive your solutions from previous years' solutions, nor may you derive your solutions from code snippets found elsewhere (including online). Examples: studying pseudo-code as found on Wikipedia is acceptable; adapting code from an open source project is not.

Your submission will include a written portion (which must be typeset, including any equations, figures, or graphs, and must be in PDF format), and a programming portion. Your writeup should include a terse restatement of each question (copy/paste is fine) in a font face that clearly separates the question from your answer, and should be formatted in an easy-to-navigate fashion (i.e., with large headings for task, and smaller headings for each problem). Make sure that the uniqnames of each member are listed at the top of every page as a running header. Deviations from this format will be penalized.

For the programming portions, you must include all of your code in a ready-to-compile state, along with a README that gives invocation instructions. Your PDF and programming files must then be zipped and submitted by email. Your email must have the following form, where the challenge score is computed based on the scoring rules described in the problem set.

SUBJECT: PS1: <uniqname1>, <uniqname2>, <uniqname3>. challenge=<challenge score> 
CC: <all of your team members>

You may receive a "moderation pending" message; this is harmless.

Task 1. Local Search [15 points][edit]

1.1 Simulated Annealing [6 points]

Many optimization problems can be described in terms of simulated annealing. Consider the following problem: We start with a box of lightly packed cereal. The goal is to pack the flakes tightly together by shaking this box in some way. How can this problem be represented in terms of simulated annealing?

A. What represents temperature in this process?
B. What represents the energy in this process?
C. Explain how the energy in the system can sometimes go up and why this can be a good thing.
D. What is the "shaking strategy" that should be used?

1.2 Genetic Algorithms [9 points]

In the traveling salesman problem, the goal is to find the shortest path connecting multiple points. Your path must visit each point, and each point must be visited exactly once. For example, in the problem below, the solution ABCD has a cost of 20 (9 + 6 + 5). This differs from the canonical TSP problem in that we are not looking for a cycle - the path does not return to the starting city.

Traveling Salesman Problem

Your task is to solve this example using a genetic algorithm.

A. Describe your problem formulation. What is your state representation? What reproduction strategy will you use? What is the fitness function?
B. Use this formulation to carry out 4 generations of a genetic algorithm, spawning two new individuals during each generation, and maintaining a population of 4 individuals. Show the fitness of each individual in each generation. You can either do this part by hand or by writing a program (we recommend the latter!).
C. How did the average and maximum fitness of the population change each generation? Explain the trend that you observe.

Task 2. Adversarial Search [10 points][edit]

2.1. Minimax [5 points]

  1. We talked about 6 environment properties in Chapter 2. In what kind of environments can we use minimax?
  2. Apply minimax algorithm to the tree below. Please annotate the tree by filling values for each node.
  3. If we are using alpha-beta pruning, which nodes can we omit?

2.2. Apply minimax algorithm to the tree below that contains chance nodes. Again, please annotate the tree by filling values for each node. [ 5 points]


Task 3. Propositional Logic [20 points][edit]

3.1. True/False [11 points]

  1. For any A, False entails A.
  2. A |= B iff ((NOT B) OR A) is valid.
  3. Practically, we can always use truth tables to determine if KB enatails some statement.
  4. We can use entailment and inference interchangeably.
  5. A AND B (the domains for A, B are true and true) is valid.
  6. A AND B and NOT(B OR A) are logically equivalent.
  7. A sentence can have more than one model.
  8. Propositional logic extends the capabilities of first order logic.
  9. Backward chaining is a form of goal-directed reasoning.
  10. Predicates are used in both propositional and first order logic.
  11. Backward chaining runs in linear time.

3.2. [4 points] Prove that A <=> B is logically equivalent to ((A=>B) AND (B=>A)) using truth tables.

3.3. [R&N 7.14] [5 points]

Task 4. Cryptogram Solver (Challenge problem), [20 points][edit]

Encryption is the process of converting ordinary information (plaintext) into unintelligible gibberish (i.e.,ciphertext). Decryption is the reverse: moving from the unintelligible ciphertext back to plaintext. One form of encryption is a "single substitution cipher", in which characters of plaintext are replaced with ciphertext using a fixed mapping. For example, occurences of the letter 'B' in the plaintext might be represented by some letter 'D' in the cipher text. These types of ciphers are often called "cryptograms" and are often solved for fun by hobbyists (often by hand!)

In this problem set, we will solve simple substitution ciphers by discovering the plaintext that corresponds to the ciphertext. For example, given the ciphertext:


We wish to recover the original plaintext (which we can do via the mapping K = O, I = B, L = E, Q = R, J = N, B = H, S = A, C = I. R = S, O = Q, L = E):


This is a constraint satisfaction problem: the variables in the problem are the ciphertext letters A through Z, and the domain for each are the plaintext letters A through Z. The constraints are:

  1. No two ciphertext letters can map to the same plaintext letter.
  2. The descrambled ciphertext should be a sensible English solution.

A dictionary of valid English words is typically employed to help ferret out good solutions.

Tricky aspect #1: too many solutions[edit]

Note that in some cases, it is possible to have multiple plaintexts for a single ciphertext. For example, the ciphertext "ksf ljudr eovzi qvt" could be decoded as "the quick brown fox" or as "him spect board law". But the former is a better solution because it makes more sense.

Automatically identifying the "best" solution is often done by considering the likelihood of the answer. This can be done using a n-gram likelihood model: based on the last 'n' characters of the decoded plaintext, how likely was the next character? Project Gutenberg is a good place to get data so that you can compute these probabilities in advance.

A little more detail: in a 1-gram predictor, you would build a 27x27 table in which you count the frequency with which one letter follows another one (including spaces). For example, the first row tabulates the number of occurrences of 'AA', 'AB', 'AC', 'AD', ..., 'AZ', 'A_'. (I'm using an underscore to represent space so you can see it). The second row considers 'BA', 'BB', 'BC', etc. You can convert each table cell into a probability by normalizing the counts over a row. This gives you the conditional probability of the next letter given the previous letter. To compute the likelihood of a plaintext solution, you multiply the probabilities for the digrams 'TH', 'HE', 'E_', '_Q', 'QU', etc. You would find it to be significantly more likely than "him spect board law". In practice, you may find it better to add the logs of the probabilities rather than multiply the probabilities directly since the numbers may get *really* small.

You could alternatively rank solutions based on the frequency with which whole words occur. While perhaps a bit easier to implement, note that it may require a large corpus. You can get really fancy and do a 1-gram *word* predictor, but that would take a really big corpus.

Tricky aspect #2: too few solutions[edit]

Suppose the ciphertext contains a word which does NOT appear in the dictionary. This is common with quotations in which the author's name is given since dictionaries may lack proper nouns. The CSP will generally fail to find a solution, as there won't be a consistent set of variables that yields English words.

One simple approach for dealing with this is to allow the CSP solver to skip over words when the domain of values for it is empty. However, this can slow down your solver since you'll continue to expand nodes after a conflict has been found. As a work-around, you could limit the number of times you allow the solver to skip a node.

A very crude approach is to re-solve the CSP many times, using only a subset of the ciphertext. If your subset of the ciphertext doesn't contain the non-dictionary words, you'll get a solution. The challenge with this approach is figuring out which part of the ciphertext to get rid of: get rid of too little and the problem still won't be solvable; get rid of too much and you may end up with too many solutions!

Rules and Evaluation[edit]

For full credit on this problem, you must implement:

  1. A CSP solver capable of finding solutions to a cryptogram in which all of the words appear in the dictionary. [10 points]
  2. Implement either an approach for dealing with too many solutions or too few solutions. (Extra credit will be awarded to teams that implement both.) Describe your approach. [10 points]

There are two reasonable ways of formulating the CSP: one in which the variables are 26 letters A-Z in the plaintext. Alternatively, you can make a variable a whole ciphertext word. Its domain would then be all of the words in the dictionary that "fit". Of course, now there are constraints between the words, since the mapping of ciphertext letters to plaintext letters must be the same for every word in the ciphertext. Both approaches have merit; in fact, the staff solution switches back and forth between them in order to minimize the branching factor at each level of the tree.

  1. You must use the dictionary provided by us, and you may not add or remove words. You may, however, add additional statistical data such as n-grams.
  2. Your results must correspond to a single "run" of your program--- no tuning your parameters on a puzzle-by-puzzle basis!
  3. You cannot manually fix any errors in the output of your program; you must submit the output of your program as-is. We will verify that the output of your programs matches your submitted results.

Your solver will be passed a number of cryptograms (each with a different mapping). Your score will be the number of characters that are wrong in your solutions, and the lowest score will win the challenge. For example, you would be charged a point if you submitted the solution "the quick brown mox" instead of "the quick brown fox". Because there are non-dictionary words in the puzzles, we expect that good solvers will still get a few letters wrong. In fact, we will be suspicious of any scores that are *too* low! In the event of a tie, the team that submitted their answer first will win.

Note that computation time is not part of this challenge.

The winner of the challenge will get an award of a delicious nature along with 10 bonus points! You'll also get a chance to briefly explain your approach to the class.

Template code[edit]

In the file below, we have provided a basic template to get you started. The template will load the dictionary, load the problem file, and call a function (to be written by you) that actually solves the CSP. A natural way to implement this CSP solver is as a depth-first search using recursion, though there are a number of reasonable choices!


Media: english.txt

Media: puzzles2011.txt

Task 5. Certification and Peer Evaluation [required for credit, 0 points][edit]

Print or write the following on a sheet of paper:

"I participated and contributed to team discussions on each problem, and I attest to the integrity of each solution. Our team met as a group on [DATE(S)]."

Each team member should sign the paper (physically, not digitally), and a photo of the paper should be included with your problem set. By doing so, you are asserting that you were materially involved in each answer, and that you certify that every solution complies with the collaboration policy of this course. In the event of a violation of the course's guidelines, your certification will be forwarded to the honor council.

If the statement requires qualification (i.e., it's not quite true), please describe the issue and the steps you took to mitigate it. If a team member did not materially contribute to a particular solution, then their score on that problem will generally be reduced. The staff will use their discretion based on the specific circumstances you identify, and we are happy to discuss potential problems prior to the problem set due date.

If your team works together, as required, this will be painless! :)

Each member of your team must also complete a peer evaluation, accessible from the apps page.

Your evaluations of your teammates will remain private. If problems develop with your team, it is up to your team to resolve them: we will not intercede except in the most extreme situations.