代写一个比较杂的作业，从开始的Vigénere cipher到Hash Table, 最后是AVL Tree.
Introduction
In this assignment, you will explore the applications of hash tables to encode
plaintext using simple substitution ciphers in cryptography. Work
individually. Follow the guidelines in the syllabus for any discussions with
others. You may work in pairs on extra credit contests, but then the extra
credit will be divided among the two of you. Extra credit entries must be bug-
free to be eligible and turned in on time (no late days).
Files
After downloading the assignment tarball from the course website, extract the
files by running:
tar -xvf lab3-handout.tgz
from a terminal window. Some of the files worth looking at are listed below.
Files you won’t necessarily modify:
Makefile
lib/.h
lib/.c
lib/words
Files you should modify (and the files denoted by * will be submitted for
grading):
*vc-ht.c
*encrypt.c
*decrypt.c
*vigenere_test.c
Additionally, you should create a file called: written.pdf which contains the
answers to the written parts of the assignment. For your convenience, we’ve
provided a LATEX template (written.tex).
Submission
To submit your programming assignment, first generate a handin archive
lab3-handin.tgz with the command
make clean && make package
then submit your lab3-handin.tgz file to your Subversion repository (svn) for
the class. Once you’ve completed all problems, you should also submit your
written.pdf to Gradescope.
Note that your code will not be graded until after the due date. It is your
responsibility to test your code on the CSIL machines and proofread your
writeup thoroughly before submitting. Code that does not compile will not
receive any points.
Word Substitution Cipher
Due to your excellent work in parsing hashtags in lab 2, you are reached out
by an agent from the Never Segfault Academy, also known as the NSA.1 To ensure
secure communication among their newly set up computer network and prevent any
data from being intercepted and copied, they intend to implement an encryption
protocol. Your job is to implement a simple word substitution cipher using
hash tables in C for their secure transmission network.
Vigénere cipher
After doing some research on different types of substitution cipher, you find
that the Vigénere cipher may be a good start. So in this part of the
assignment, you will implement a modified version of the Vigénere cipher.
First, a little cryptographic background. Let’s say you’re sitting in class
bored, and you want to pass a note to your friend sitting way on the other
side of the classroom. To get the note there, you’ll have to relay your note
through a lot of your classmates. However, perhaps the message contains some
secret information that you don’t want any classmate but your friend to know
(name of your crush, your Netflix password, etc). The purpose of a
cryptographic cipher is to encrypt the message in a way so that only you and
your friend can figure out, or decrypt, the original message.
In order to accomplish this, you and your friend need some shared, secret
piece of information, called a key. A cryptographic cipher is a function that
takes a key k and a message m, and outputs a ciphertext c which is the
encoding of m. There is also a matching decryption function that takes the key
k and a ciphertext c, and outputs the original message m.
One of the very first ciphers ever used was the Caesar cipher. We will
describe a slightly modified version of the Caesar cipher based on words (if
you want to read about the original version, you can find it on Wikipedia).
The key is a number, and encryption offsets the words in the message by the
key value. The easiest way to describe this is by example. Let’s say all words
in the message must come from some “language” L, for example
L = [“NSA”, “CIA”, “IRA”, “PPAP”, “PW”, “DJT”, “HRC”, “IS”, “WIFI”]
and we want to pass the message “WIFI PW IS CIA”. Notice that the “language” L
in this example is not sorted in any order, but you can safely assume that the
dictionary lib/words you will use later is sorted alphabetically. Furthermore,
words in this example L are all capitalized, however the language we will use
in later sections are all in lowercase. Using key 1, each word becomes the one
at the next index in the language (with the last looping back) e.g. “NSA”
becomes “CIA”, “CIA” becomes “IRA”, … , “IS” becomes “WIFI”, and “WIFI”
becomes “NSA”. On key 2, each word becomes the one that is two indices away
e.g. “NSA” becomes “IRA”, . . . , “HRC” becomes “WIFI”, “IS” becomes “NSA”,
and “WIFI” becomes “CIA”. Applying this to each word, on key 4 the message
“WIFI PW IS CIA” becomes “PPAP WIFI IRA DJT”. To decrypt, we would replace
each word with the one 4 words before it.
The Vigénere cipher you are implementing is an improvement on this. Instead of
using just a single number for a key, we use an entire phrase. Each word in
the phrase is associated with its index in the language, and we shift the
words in our message by that index as in the Caesar cipher.
Again, an example is the best description. Let’s use key “HRC DJT PPAP DJT” to
encipher “WIFI PW
IS CIA”. We start by aligning the words of the message with key:
HRCD DJT PPAP DJT
WIFI PWD ISDD CIA
“HRC” is the 6th word of the language (0 index!), so we shift “WIFI” by 6
(like the Caesar cipher) to “DJT”. “DJT” is the 5th word, so we shift “PW” by
5 to “NSA”, and so on. The entire ciphertext becomes
DJT NSA CIA HRC
To decrypt, we align the key words with the ciphertext words, and take each
words back by each index. Finally, we don’t want to require that the key and
message have the same length. To get around this, we just repeat the key as
many times as necessary to cover the message. For example, encrypting with key
“DJT IS HRC” would produce
DJTD IS HRC DJT IS HRC
WIFI PW ISD CIA → PW IRA PW HRC
Task 4.1
Using the above language, encrypt “NSA IS CIA IS IRA” using the key “PW PPAP
WIFI”.
Ok! For your next tasks, we work with a generic language, which we enumerate
as w1, w2, …, wn and the l-word key as wk1 … wkl.
Task 4.2
If the message is wm1 wm2 … wmd and the ciphertext is wc1 wc2 … wcd, write a
mathematical expression for encrypting i.e. computing the wci from the wmi .
Task 4.3
Write a mathematical expression for decrypting i.e. computing the wmi from the
wci.
Hash Tables
As you discovered in the previous tasks, the best way to implement the
Vigénere cipher is to associate each word in the language with a index. We
could create an array of words, sorted in alphabetical order, and therefore
find each word by its index. However, during the encipher/decipher process, we
also need to be able to compute the index of a word efficiently.
Therefore, we will be using both arrays and hash tables to implement the
Vigénere cipher protocol. In this part of the assignment, you are going to
implement a wrapper around the generic hash tables implementation that is
provided to you. So you do not have to implement the hash table from scratch.
The wrapper will serve as an interface specifically for inserting and looking
up the words used in Vigénere cipher.
The functions you will implement in vc-ht.c should respect the header
interface in lib/vc-ht.h.
Specifically, you will need to complete the functions, vc_ht_new,
vc_ht_insert, vc_ht_lookup, vc_ht_free, and other helper functions for the
underlying hash table. Note that this hash table stores each word as its
element struct vc_ht_elem_base which has two fields. The field idx is the
index of the word in the dictionary lib/words. The field word is of type
word_t, which is just a typedef of char *, and is the string value of the word
stored in the hash table element.
Task 4.4
In vc-ht.c, implement the helper functions, each of which should be less than
two lines (except for hash), as required by vc_ht_new. Notice that they will
be passed into (the generic) ht_new as function pointers, and their argument
and return types do not have the “vc_“ prefix, which means you will probably
need to think carefully about casting before writing your code.
For instance, elem_key takes an input e of type ht_elem, but in order to read
the value stored in e, you might need to cast to the proper type first.
More specifically, the helper functions are:
- elem_key: Read off the key stored in the element.
- key_equal: Key comparison function for the hash table.
- hash: Hash function that maps each key to its appropriate location in the hash table. A good hash function should be efficient and should minimize the number of collisions.
- elem_free: Tell the hash table how each element should be freed.
Task 4.5
In vc-ht.c, implement the function in less than two lines: vc_ht_elem
vc_ht_insert(ht H, vc_ht_elem e) that adds the element e to the hash table H,
and returns the old element with key of e that is replaced, if it exists, and
returns NULL otherwise.
Task 4.6
In vc-ht.c, implement the function in less than two lines: vc_ht_elem
vc_ht_lookup(ht H, vc_ht_key k) that returns NULL if no element with key k
exists and the element associated with the key otherwise.
Task 4.7
In vc-ht.c, implement the function in less than two lines: void vc_ht_free(ht
H) that frees the hash table and all of its data.
Encryption
Now we can finally put everything together and start implement the encryption
protocol.
Task 5.1
In encrypt.c, implement the function:
void decrypt_msg(word_t *A, ht HT, int wordcount,
word_t *key_sentence, int key_len,
word_t *cipher_text, word_t *plain_text, int txt_len)
—|—
Task 5.2
And conversely, in decrypt.c, implement the function:
void decrypt_msg(word_t *A, ht HT, int wordcount,
word_t *key_sentence, int key_len,
word_t *cipher_text, word_t *plain_text, int txt_len)
—|—
For your convenience, we have implemented some utility functions to test your
implementation.
You might want to check out the functions in lib/english.h and vigenere-
test.c.
In lib/english.h:
- word_cmp: Comparison function for type word_t.
- print_sentence: Print an array of words to stdout.
In vigenere-test.c: - init_word_array: Allocate and initialize an array of words from lib/words.
- free_word_array: Free the memory used by the array of words.
- init_word_ht: Allocate and initialize a hash table from the word array.
- free_word_ht: Free the memory used by the hash table of words.
Feel free to use/modify the functions implemented in vigenere-test.c, which is
also where all your tests should go. We have provided you with a sample test
in the main function, however it is strongly recommended that you add more of
your own tests and run:
make vigenere
Runtime Complexity
Consider the following function that sorts the integers in an array, assuming
swap and is_sorted were implemented, where swap(A, i, j) swaps the array
element A[i] and A[j], and is_sorted(A, i, j) checks if A[i,j) is sorted.
void sort(int[] A, int n)
// pre_condition: 0 <= n && n <= length(A);
// post_condition: is_sorted(A, 0, n);
{
for (int i = 0; i < n; i++)
// loop_invariant: 0 <= i && i <= n;
// loop_invariant: is_sorted(A, _____, _____);
{
int s = 0;
for (int j = 0; j < n-i-1; j++)
// loop_invariant: 0 <= j && j <= n−i−1;
// loop_invariant: s > 0 || (s == 0 && is_sorted(A, 0, j));
{
if (A[j] > A[j+1]) {
swap(A, j, j+1); // function that swaps A[j] and A[j+1]
s = s + 1;
}
}
if (s == 0) return;
}
}
—|—
Task 6.1
Complete the missing loop invariant (at line 7) after the first i iterations.
Task 6.2
The asymptotic complexity of this sort depends on the number of comparisons
made between pairs of array elements. Let T(n) be the worst-case number of
such comparisons made when sort(A, n) is called. Give a closed form expression
for T(n).
Task 6.3
Using Big-O notation, what is the asymptotic complexity of T(n)? This is the
worst-case runtime complexity of sort.
Task 6.4
Using your answer from the previous part, show that T(n) ∈ O(f(n)) using the
formal definition of Big-O. That is, find a c > 0 and n0 ≥ 0 such that for
every n ≥ n0, T(n) ≤ cf(n). Show your work.
Task 6.5
Using Big-O notation, what is the best case asymptotic complexity of this sort
as a function of n.
AVL Trees
Task 7.1
Draw the AVL trees that result after successively inserting the following keys
into an initially empty tree, in the order shown:
27, 16, 8, 9, 6, 12, 7
Show the tree after each insertion and subsequent re-balancing (if any) is
completed: the tree after the first element, 27, is inserted into an empty
tree, then the tree after 16 is inserted into the first tree, and so on for a
total of seven trees. Make it clear what order the trees are in.
Hashing
For the following two tasks, we use the hash function:
int hash(int x) {
return x + (x % 3) * 4;
}
—|—
As seen from lecture, we say that if the hash value of a key k is hash(k),
then the index that we insert this key to is hash(k)%m, where m is the size of
the hash table.
Task 8.1
Draw the resulting hash table of size 7 after inserting the following values,
using linear probing to resolve collisions:
84, 44, 66, 16, 105, 76
Task 8.2
Draw the resulting hash table of size 7 after inserting the following values,
using quadratic probing to resolve collisions:
84, 44, 66, 16, 105, 76
