[Solved] CS261-Assignment 3

Problem 1: Linked List Deque and Bag implementation

First, complete the linked list implementation of the deque (as in Worksheet 19) and bag ADTs (Worksheet 22). To do this, implement all functions with the // FIXME comments in

Problem 2: Linked List vs Dynamic Array performance comparison

The files linkedListMain.c and dynamicArrayMain.c each contain code which does the following:

1. Takes an integer argument (say n) from the command line and adds that many elements to the bag.
2. Prints the memory in KB used by the bag.
3. Calls the contains function for each element in the bag.
4. Prints the time taken by these contains calls in milliseconds.

Your job is to compare the performance of the linked list implementation vs the dynamic array implementation over various numbers of elements. Create a plot comparing performance over element counts from n=2¹⁰ to n=2¹⁸, doubling n for each data point, for each of the following metrics:

1. Memory usage linked list vs dynamic array for n in [2¹⁰, 2¹⁸].
2. Running time linked list vs dynamic array for n in [2¹⁰, 2¹⁸].

Important: Please run all memory usage and timing tests using valgrind on flip for consistency. The memory calculation code runs on flip only. Please follow the instructions in linkedListMain.c and dynamicArrayMain.c to comment out the memory code if you develop your programs in Visual Studio.

You must also implement the dynamic array. Use the implementation from Assignment 2 or the previous weeks worksheets. Note that in dynamicArrayMain.c the dynamic array must have a capacity of 2¹⁰ to start with.

After creating the two plots, answer the following questions:

1. Which of the implementations uses more memory? Explain why.
2. Which of the implementations is the fastest? Explain why.
3. Would you expect anything to change if the loop performed remove() instead of contains()? If so, why?

Problem 3: Circularly Linked List Deque implementation

For this problem, you will implement the Deque ADT with a CircularlyDoublyLinked List with a Sentinel. As you know, the sentinel is a special link, does not contain a meaningful value, and should not be removed. Using a sentinel makes some linked list operations easier and cleaner in implementation. This list is circular, meaning the end points back to the beginning, thus one sentinel suffices. Implement all functions with the // FIXME comments in circularList.c .