95-771 Data Structures and Algorithms Homework 1

95-771 Data Structures and Algorithms Carnegie Mellon University

95-771 Data Structures and Algorithms Project 1

Due: Wednesday, September 13, 2017, 11:59:59 PM

This is a four part programming assignment. The first part provides the student with practice in constructing a simple doubly linked list. The second partalso uses doubly linked lists and is a bit more challenging. The second part also serves as an introduction to NP-Complete problems.The third part is exactly the same as the second part but with arrays replacing lists. If good software engineering practices are used, the third part should be trivial. Much of the code from the second part should be reused in the third part.In the fourth part, you will work with a singly linked list of characters.

Part 1. Doubly Linked Lists 40%

Attached are abbreviated Javadoc specifications for two classes, DoubleNode.java and DoublyLinkedList.java.

You have seen how singly linked lists work in class. A singly linked list consists of a series of nodes linked together via pointers. Each node has a next pointer which points to the next node in the list. The next pointer of the last node in the list is set to null.

A doubly linked list is similar to a singly linked list, however in a doubly linked list each node also contains a previous pointer, which points to the previous node in the list. The previous pointer of the node at the head of the list is set to null. The next pointer of the last node is set to null.

Following the Javadoc specifications given, you are to write implementations of DoubleNode and DoublyLinkedList. You need to use the exact same names as those provided so that your classes may be included in our test driver. You should begin by writing only the method signatures and Javadoc comments for each class. You should then generate Javadoc specifications for your classes similar to those attached. You are required to include pre- and post-conditions in your Javadoc for each method. After that, you should write your own implementation for each of the methods.

A simple test driver that you are required to use is provided below.

You need to submit:

DoubleNode.java and DoublyLinkedList.java, containing your Java source for these classes.

Javadoc for each class and method. This Javadoc must contain each method’s best and worst case run time complexity. This must be expressed using big theta notation. If you are not able to determine the best and worst case run time complexity, explain why. Again, the Javadoc will contain pre- and post-conditions for each method.Use good judgment with respect to pre- and post-conditions. Only use them if you feel it makes good sense to do so.

A screen scrape showing the output of the main program. The main program is provided below.

Part 1 Grading:

Working code passing the test driver: 70%

Javadoc describing worst and best case big theta values and

pre- and post-conditions: 20%

Overall presentation: 10%

Test Driver

publicstaticvoid main(String a[]) {

DoublyLinkedList list = new DoublyLinkedList();

list.addCharAtEnd('H');

list.addCharAtEnd('e');

list.addCharAtEnd('l');

list.addCharAtEnd('o');

System.out.println(list);

System.out.println("Deleting l");

list.deleteChar('l');

System.out.println(list);

System.out.println("Deleting H");

list.deleteChar('H');

System.out.println(list);

System.out.println("Deleting o");

list.deleteChar('o');

System.out.println(list);

System.out.println("Deleting e");

list.deleteChar('e');

System.out.println(list);

System.out.println("Deleting l");

list.deleteChar('l');

System.out.println(list);

list.addCharAtFront('o');

list.addCharAtFront('l');

list.addCharAtFront('e');

list.addCharAtFront('H');

System.out.println(list);

System.out.println(list.countNodes());

System.out.println("Popping everything");

while(!list.isEmpty()){

System.out.println(list.removeCharFromFront());

}

list.addCharAtFront('o');

list.addCharAtFront('l');

list.addCharAtFront('e');

list.addCharAtFront('H');

System.out.println("Popping everything from the end");

while(!list.isEmpty()){

System.out.println(list.removeCharAtEnd());

}

System.out.println(list.countNodes());

list.addCharAtEnd('o');

list.addCharAtEnd('l');

list.addCharAtEnd('e');

list.addCharAtEnd('H');

list.reverse();

System.out.println(list);

list.reverse();

System.out.println(list);

DoublyLinkedList list2 = new DoublyLinkedList();

list2.addCharAtEnd('O');

list2.addCharAtEnd('K');

list2.reverse();

System.out.println(list2);

System.out.println(list2.countNodes());

}

Part 2 Merkle-Hellman Knapsack Cryptosystem 30%

In this assignment you will implement key generation, encryption and decryption using the Merkle-Hellman Knapsack Cryptosystem. A very clear and well-written description of this algorithm can be found at the following link. This is a required reading for the course and should be understood prior to writing code:

Note that the example provided on the wiki is an example using small integers with w = {2, 7, 11, 21, 42, 89, 180, 354}. In this project, w will consist of 640 huge integers.

You will write two doublylinked lists of objects to hold two lists of Java BigIntegers. One list, w, will be used to hold the superincreasing sequence of integers that make up part of the private key and used for decryption. The second list, b, will be used to hold the public key material used for encryption. Your list class should encapsulate all of the work associated with lists and should not know anything about Merkle-Hellman. You will include pre- and post-conditions with each of your methods and will describe each method’s run-time complexity using Big Theta.

Using a doubly linked list for this problem is appropriate but not ideal. It is very appropriate for a first course in data structures. Hence, use it for this project but you should be aware that there are alternatives (see Part 3).

Use the built in methods of the BigInteger class provided by Java. These methods make it fairly easy to implement some of the tedious but essential parts of Merkle-Hellman.

To do a practice example, you might like to use Wolfram Alpha at It accepts operations such as

(3 * 5) mod 2, gcd(32,5) and PowerMod(15,-1,64) to find the multiplicative inverseof 15 modulo 64.

Your program will be interactive and will behave in a similar manner as mine. An example run of my program appears below. You will need to submit several screenshots showing example executions of your code. Note that you may assume that the user will enter a string of less than 80 characters in length. If the user enters a longer string, inform them that the string entered is too long and ask the user to try again.

Hint: Since your program must handle 80 characters of input and since each character can be represented in 8 bits, your lists will have (80 * 8) 640 nodes. Note that key generation is typically done once. Then, the key is used. It is not typical that the key size would depend on the size of the input (which may vary).

Example execution:

Enter a string and I will encrypt it as single large integer.

Welcome to Data Structures and Algorithms

Clear text:

Welcome to Data Structures and Algorithms

Number of clear text bytes = 41

Welcome to Data Structures and Algorithms is encrypted as 317817076350145785260656997739621373931469119807217110529280649332942724728174120224095587842484635884305367159163265896397856056390477056525611299805189287161133817602808317806202994211855425964737022224210974561644533817599450919039345942975178915818105632933959978787221138943336909734004773052722627400695

Result of decryption: Welcome to Data Structures and Algorithms

Part 2 Grading:

You need to submit:

Working code performing key generation, encryption and decryption and using doublylinked lists to hold BigIntegers: 70%

Javadoc describing worst and best case big theta values and pre-and post-conditions in your linked list class. : 20%

Overall presentation including several screenshots: 10%

Part 3. Merkle-Hellman Knapsack Cryptosystem with arrays 20%

Reuse code from Part 2 and solve the exact same problem as Part 2. Use arrays rather than lists. You may not use a Java ArrayList ot the Java collection classes.

Part 3 Grading:

You need to submit:

Working code performing key generation, encryption and decryption and using arrays to hold BigIntegers: 50%

Javadoc describing worst and best case big theta values and pre-and post-conditions when appropriate: 20%

Overall presentation including several screenshots: 10%

Good use of abstractions when writing Part 2 made writing Part 3 trivial. 20%

Part 4. Singly linked list puzzle 10%

Write a static method that takes two singly linked lists of characters as input and returns a third singly linked list of characters. The output list will be the concatenation of the two input lists. The singly linked list class will have a toString method and this method will be used by your main driver. It is required that your main driver be interactive. It will read two strings from the user, use the data within those strings to build two lists of simple char data and then call the concatenation routine. The output will be a string – built from the concatenated lists. The detailed design is in your hands.

Part 4. Grading:

You need to submit:

Working and correct concatenation routine: 50%

Working main routine used to test the concatenation logic as described. 40%

Documentation of the code using Javadoc: 10%

Note: A complete submission of Project 1 will contain four directories submitted to Canvas. The four directories will all be contained within a single zipped file named <yourAndrewID>Project1.zip.