Data Structures and Algorithms University of California, Irvine
Homework 2
Due on Friday, February 8, 2019 by midnight
January 25, 2019 EECS 114
1 (25 Points) Queue
Write a program that implements a queue of floating point numbers with enqueue and dequeue
operations.
1. Your program should take two arguments n and t as inputs. The following operations are to be performed initially:
(a) Create an empty queue.
(b) Enqueue n random floating point numbers into the queue.
(c) Then do the pair of operations: dequeue a floating point number x and then enqueue x, t times.
The purpose of this program is to measure how much time each pair of dequeue and enqueue operations takes to execute for a queue of size n. Individual enqueue and dequeue operations are too short to measure accurately, so you should record t repetitions and then compute the average time for a dequeue/enqueue pair. You can reuse the timer from homework 1.
2. Execute the program for n = {1, 10, 100, 1000, 10000, ………, 1000000} and t ≈ 10, 000. Record the average execution times for a dequeue and enqueue sequence in a table. Vary n until its value is 1000000 or the program runs out of memory.
3. State the complexity of a sequence of one enqueue and one dequeue operation as a func- tion of the size of the queue (n) using asymptotic notation. Provide an argument for the correctness of your stated complexity by analyzing the code for each operation.
4. The queue must strictly be implemented using custom structures (in C) or classes (in C++). You may not use arrays or any other library data structures to define the queue.
First create a subdirectory named hw2. Then, use your editor to create a C/C++ file named queue.c or queue.cc.
1
2 (25 Points) Doubly Linked List
Implement a doubly linked list with and the following methods
• add a node to the front of the list
• add a node to the back of the list
• return the first node
• return the last node
• remove a node
• return the previous node (given a node)
• return the next node (given a node)
• search for a node that contains a given value
1. Provide a test program that takes an integer n as the input.
• Create an empty doubly linked list.
• Add ‘n’ integers [1, 2, …n] into the list.
• Repeat the following operations several times and compute the average time taken to perform the ‘remove’ operation (you can use the same timer as homework 1):
– Generate a random number between 1 and n.
– Search for the corresponding node in the list and remove it from the list. – Add the removed item to the front of the list.
Execute the program for different sized lists, i.e., n = 1,10,100,1000, 10000,…. Vary n until the total execution time taken by the program becomes >2 seconds or the program runs out of memory.
2. State the complexity of the remove operation in terms of the size of the input (n) using asymptotic notation and provide an argument (analyzing the code for the delete operations) why the stated complexity is correct.
Use your editor to create a C/C++ file named dlist.c or dlist.cc inside hw2 directory.
Submission
When you’ve written up answers to all of the above questions, turn in your write-up and zip/- tarball of your code (hw2 directory) by uploading it to Canvas.
2