Java Data strcutres and Algorithm Assignment

Question 1: Java Programming Project: On-line Message Assembler

When Bob wants to send Alice a message (M) on the Internet, he breaks M into n data packets, numbers the packets consecutively, and injects them into the network. When the packets arrive at Alice's computer, they are out of order, so Alice must sort the sequence of n packets in order before she is able to read the entire message.

You are asked to create a Java program, which would help Alice assemble Bob's messages. You can assume that for each message (M), the contents of n received packets, together with their respective sequence numbers, are temporarily stored in a file, as illustrated in Figure 1. An example of such a file, which can be used for test purposes, is available at: http://www.cs.yorku.ca/course/2011/Mystery.txt

Your program design should be based on the following guidelines:

(1) Create DLLNode_class, which will be used to store the content of each individual packet.

(2) Create DLL class, which will be used to store the content of an entire file (i.e. message) - one line/packet per node. The outline of this class is given below. You are allowed to add new methods to this class, as needed.

(3) Create MessageAssembler class, which will contain main() method and act as a tester class. The outline of this class is given below. You are allowed to add new methods to this class, as needed.

Question 2: Algorithm Design

Array A of size n contains all integers form 1 to (n+1) but one!

1) Assuming the array is sorted, propose a (best-running time) algorithm that finds/identifies the missing number, and analyze its worst-case running time in terms of big-O notation.

2) Assuming the array is NOT sorted, propose a (best-running time) algorithm that finds/identifies the missing number and analyze its worst-case running time in terms of big O notation.

Question 3: ADTs / Stacks

Using the regular Stack ADT, design an advanced Stack ADT for which getMinimum() method runs in O(1) time. Pushing and popping n elements to this Stack should each run in O(n) (i.e., you are not allowed to perform any sorting (e.g.) as a part of a different method). You are only allowed to use one additional data structures (e.g., another Stack) in your design.

Describe your solution in words and provide a brief pseudocode for the new push(), pop(), and getMinimum() methods.

Question 4: Big-O Analysis

Sort the following functions by increasing order of growth:

nlg n      n^{lg n}         (lg n)ⁿ    2^{lg n/2}      n²           

Question 5: Running Time Analysis

Express the running time of the following program segment using big-θ notation. Show/justify your work.

Attachment:- Assignment Files.rar