(c^x)^x== xwas wrong. Should have been
Recall that in homework 4, you viewed an array of N elements as a balanced binary tree. Note that the balanced requirement was critical since arrays do not have holes in them.
Now, instead of counting heap-orders, you need to count BST-orders in the same context. Assume that N >2 and that all N elements are different.
Note that each of the two approaches has advantages and drawbacks. If you come up with a closed-form expression, you can save a lot of time since no code needs to be written. If there is no closed-form expression, all attempts to find it can be futile. Also note that if the number of BST orders is very small, then randomized sampling will require a very large number of samples. If you decide to solve this question empirically, you must solve for all array sizes up to and including 15.
You have been asked, by the secret head of the NSA (one Igor "white hat" Markov) to break the encryption algorithm used by the evil villain Mark "nogoodnik" Brehob. Thankfully Brehob isn't the swiftest villain the NSA has ever faced -- he uses a really bad encryption scheme. Three encrypted messages from Brehob will be mailed out to you.
It is known that what Brehob uses is the XOR operation (^ in C++) on single characters. He takes his secret message and XORs it with an unknown pass-code consisting of 3 ASCII characters.
For example, encoding the plaintext "SECRET MESSAGE" with pass-code "BLA"
SECRET MESSAGE BLABLABLABLABLAThe encrypted message will consist of characters 'S'^'B', 'E'^'L', 'C'^'A' and so on.
The same pass-code and algorithm are used for encryption and decryption.
This technique is based on the fact that for two chars c and x
(c^x)^x== c is always true.
You are to find the unknown pass-code and decrypt a given message,
using "the dictionary attack". It assumes that the secret message
only uses ASCII characters and consists of space-separated words,
each of which is found in a given dictionary. You can use isascii()
man isascii) and can use a supplied dictionary (see
Algorithm: go over all possible pass-codes and "decrypt" the message
using each proposed pass-code. Check the resulting string against the
dictionary. If it consists entirely of words from the dictionary, you
cracked the pass-code and decrypted the message. Otherwise, check the
next pass-code. In order to speed up the dictionary check, you need to
read the dictionary into memory and put all of it into an STL's
hash_set (make sure that your workstation has enough memory).
The characters in the passcode will consist of only: lower case letters, upper case letters and numbers (0-9). No other ASCII characters will be in the pass-code.
Your program should take the following arguments:
/usr/dict/(they are used by Unix spellchecker
hash_setsare useful in this project (instead of
Note: Encryption by XOR is very very weak, and can be broken much more efficiently by smarter attacks. When you graduate and go to work (or grad school), do not use encryption by XOR when encryption strength is important.
You must use the described dictionary attack (brute force) for this project.
Note: Since encrypted messages are not in ASCII, you need to read/write them as binary (see handout 1 and handout 2).
References: example 1, example 2, theory
Implement Kruskal's algorithm. The only restrictions are that: