User Account

All Pages

Linked List Variations, Data Structure & Algorithms

Assignment Help:
Part1: Deque and Bag Implementation

First, complete the Linked List Implementation of the Deque (as in Worksheet 19) and Bag ADTs (Worksheet 22).
Files Needed:

linkedList.c
LinkedList.h
linkedListMain.c
testLinkedList.c
makefile
Part 2: Comparison

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

Runs an outer loop from 1000 up to 200000, doubling the loop variable,n, at each iteration
In each iteration, it performs n calls to add() followed by n calls to contains()
Prints the time taken by these contains() calls in milliseconds
Your job is to compare the memory requirements and execution time performance of the LinkedList to the Dynamic Array.

Time Comparison

To gather timing and memory usage, you will execute the dynamicArrayMain() program using a tool called valgrind .

To execute valgrind from the command line on flip, simply type:

valgrind --tool=massif [executable]
replacing [executable] with the name of the executable (if you''re using our makeifle, that name is ''prog''). This will result in two outputs. First, the amount of time elapsed for each iteration (in ms) will be printed to the shell. You must copy these times so you can plot them in a tool such as Microsoft Excel.

Memory Comparison

Second, valgrind will produce a file named massif.out.[number]. You will then execute the following at the command line:

ms_print massif.out.[number] > memDump
replacing [number] with the number in the file that valgrind produced. This command (piped to a file!!) will create a file called memDump which looks like THIS

In memDump, find the line that says "Detailed Snapshots: [ 3, 8 ...] ". This set of numbers corresponds to line numbers in the table below it where you will find the amount of memory sampled at each snapShot, in the column labeled total(B). You are to take those memory snapshots and create a graph (in excel, for example), of the memory profile for your execution.

You will repeat this process for the LinkedListMain so that you can compare it to the Dynamic Array

Note that the dynamic array must have a capacity of 1000 to start with. The policy is to double the size when the array is full. We''re providing the dynamic array implementation below.

Answer the following questions:

Which of the implementations uses more memory? Explain why.
Which of the implementations is the fastest? Explain why.
Would you expect anything to change if the loop performed remove() instead of contains()? If so, what? (Note, it''s very easy to run this experiment given the code we''ve provided!)
IMPORTANT NOTES:

# You must run all memory usage and timing tests on flip.

Files needed:

dynamicArray.h
dynamicArray.c
dynamicArrayMain.c
makefile
Part3: Implementation of the Deque ADT Using a Circularly Linked List

For this problem, you will implement the Deque ADT with a Circularly-Doubly-Linked List with a Sentinel. As you know, the sentinel is a special link, does not contain a 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. The header file and the implementation file for this approach are cirListDeque.h and cirListDeque.c, respectively. Complete the functions in cirListDeque.c and write a test harness in listDequeTest.c to test the functionality of your Circularly-Doubly-Linked List.

Notes: The reverse() function should reverse the ordering "in place", meaning it should not allocate any new memory or create a new cirListDeque. Instead, reverse the ordering of the existing DLink elements.

Files needed

cirListDeque.h
cirListDeque.c
testCirListDeque.c
makefile

Related Discussions:- Linked List Variations

Search, What are the conditions under which sequential search of a list is ...

What are the conditions under which sequential search of a list is preferred over binary search?

Algorithm to count number of nodes, Write an algorithm to count number of n...

Write an algorithm to count number of nodes in the circular linked list.                            Ans. Counting No of Nodes in Circular List Let list be a circular h

Relative and direct files, Each data record contains a fixed place in a rel...

Each data record contains a fixed place in a relative file. Each record ought to have associated with it in integer key value which will help identify this slot. Therefore, this ke

State warnock algorithm, Warnock's Algorithm An interesting approach to...

Warnock's Algorithm An interesting approach to the hidden-surface problem was presented by Warnock. His method does not try to decide exactly what is happening in the scene but

Explain the abstract data type assertions, Explain the Abstract data type a...

Explain the Abstract data type assertions Generally, ADT assertions translate into assertions about the data types which implement ADTs, which helps insure that our ADT impleme

Explain critical path and chain, 1.  Using the traditional method of CPM: ...

1.  Using the traditional method of CPM: a.  What activities are on the critical path? b.  What is the expected total lead time of the project? 2.  Using CCPM: a.  What

Big o notation, This notation gives an upper bound for a function to within...

This notation gives an upper bound for a function to within a constant factor. Given Figure illustrates the plot of f(n) = O(g(n)) depend on big O notation. We write f(n) = O(g(n))

Luminous Jewels - The Polishing Game, Byteland county is very famous for lu...

Byteland county is very famous for luminous jewels. Luminous jewels are used in making beautiful necklaces. A necklace consists of various luminous jewels of particular colour. Nec

Deletion of a node from a binary search tree, The algorithm to delete any n...

The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered. If the node to be deleted contains no sons,

Algorithm to merge two sorted arrays with third array, Q. Write down an alg...

Q. Write down an algorithm to merge the two sorted arrays into the third array. Do  not perform the sort function in the third array.                           Ans: void m

Write Your Message!

Captcha
Order Assignment

Featured Services

Order Now

Popular Subjects

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +91-977-207-8620

Phone: +91-977-207-8620

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd