Ask Question, Ask an Expert


Ask Computer Engineering Expert


You will prepare a C++ program to find the intersection and/or union of two doubly linked lists using recursion. You are not allowed to use the STL Library.

A set is a collection of distinct entities regarded as a unit, being either individually specified or (more usually) satisfying specified conditions. In set theory the union of two sets A and B, is the is the set of all distinct elements in A and B. The intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. In mathematics, the notion of bag (or multiset) is a generalization of the notion of set in which members are allowed to appear more than once. For this homework we will work with bags.


The input is one script file, in the same format as the script file from Homework 1, and two or more data files containing words. The script file will ask you to read 2 or more files into doubly linked lists and operate on them. Two new operations will be introduced:

union(L1, L2, L3)

will find the union of sets L1 and L2 and store the result in L3.

intersection(L1, L2, L3)

will find the intersection of sets L1 and L2 and store the result in L3.

These new operations will require the modification of the script parser provided by the TA’s. A new version of the parser is posted.

We will define a word as a sequence of characters. These characters can be any of the 95 printable characters, except the space, which will be used as a separator. Words will be up to 30 characters long and will be separated, as mentioned before, by spaces and carriage returns (’\n’). We will not test you with longer words, and we will not use any non-printable characters other than the carriage return and the EOF character.

Notice that words can be capitalized. This should not interfere with your results: a capitalized word is the same as a non-capitalized word for the purposes of this homework. Uppercase letters can be anywhere in the word, for ex.: ”Hungry”, ”hungry” and ”hUngry” should be counted as the same word. By default all uppercase letters should be changed to lowercase. Words will be separated by one or more spaces and one or more carriage returns. For this homework we will not use other separators. The input files will contain no punctuation.Another important detail is that input files might be empty, since the empty set(∅) is a valid in set theory. You can use the properties of the empty set:

A ∪ ∅ = A
A ∩ ∅ = ∅

to produce your results.

In order to simplify the problem, the formatting of the original files will be discarded. All uppercase characters must be changed to lower case. When creating the doubly linked lists in memory you should create them in alphabetical order. You should also keep track of how many times each word appears in the input file. Typically this can be done adding a new field to your node, but you are free to devise your own method.

Program and output specification:

The main program should be called ”recursion”.


recursion script=input.script

Note that the file name will not necessarily be the same every time, so your program will have to take that into account. You can use the Command Line Parser that is provided in the TA’s homepage. When asked to output a doubly linked list to a file you must prepare one word per line followed by a space and the number of occurrences of the word. Please note this change from the previous homework. If the number of occurrences is 0 you must not output the word. Similarly, if the linked list is empty, the file created will be empty. When calculating the intersection of two linked lists you must only keep one copy of each word in the output list.



alpha beta gamma delta Alpha

cat dog bird


alpha 2
beta 1
bird 1
cat 1
delta 1
dog 1
gamma 1

gamma 1
dog 2
delta 1
cat 1
bird 1
beta 1
alpha 3


dog 1
alpha 1


• Your program must be able to create and handle multiple doubly linked lists. (Hint: Think about creating a linked list of linked lists or an array of linked lists)

• When writing to a file you will be asked to prepare either in alphabetical order or in reverse alphabetical order. Since your linked lists will be created in order, this will involve writing starting from the head or from the tail. You don’t need to use recursion to print your files.

• When performing the union and intersection of the linked lists you must use only recursion. Iterators and loops are not allowed. This will be strictly enforced.

• You are allowed to use loops and iterators when reading and writing from a file, in order to recycle the code you used in the previous homework set. However you must create a recursive search method and a recursive list traversing method.

• You must create a log file that records the length of each linked list after each operation. This log file should also be used to output any warnings and errors you might encounter.

• The program should not halt when encountering errors in the script. It should just send a message to the log file and continue with the next line. The only error that is unrecoverable is a missing script file.

• Do not use the STL library.

• Your program should prepare error messages to the screen. Your program should not crash, halt unexpectedly or produce unhandled exceptions. Consider empty input, zeroes and inconsistent information. Each exception will be -10.

• Test cases. Your program will be tested with 10 test scripts, going from easy to difficult. You can assume 80% of test cases will be clean, valid input files.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M9875

Have any Question? 

Related Questions in Computer Engineering

Computer science assignmentanswer the questions clearly

Computer Science Assignment Answer the questions clearly, explain your answer, and show your work. Answers, even if right but without an explanation, will get no credit. The explanations need to be brief, but complete, l ...

1 in what ways is network design an iterative process why

1. In what ways is network design an iterative process? Why does the need for network documentation arise in many phases of a network design project? 2. When responding to an RFP, why is it important to pay attention to ...

1 indicate dependences and their type2 assume there is no

1. Indicate dependences and their type. 2. Assume there is no forwarding in this pipelined processor. Indicate hazards and add nop instructions to eliminate them. 3. Assume there is full forwarding. Indicate hazards and ...

Based on klamaths requirements select some network

Based on Klamath's requirements, select some network optimization technologies that will help maintain video quality for the distance-learning program. Based on Figure 11-6, "New Core WAN at Klamath," draw a network topo ...

1 analyze the quick sort algorithm to show the worst case

1. Analyze the quick sort algorithm to show the worst case time is O(n 2 ). 2. Analyze the mergeVirtualSeq() function and show that it is a linear time operation in the worst case. 3. Analyze the linked list version of t ...

Kirchoffs laws75 to 150 wordsdiscuss how kirchoffs voltage

Kirchoff's Laws75 to 150 words Discuss how Kirchoff's Voltage and Current Laws can be used to help analyze any type of circuit. Discuss the differences between a loop and a mesh.

In el farol extension 3 we now graph the actual award

In El Farol Extension 3, we now graph the actual award distribution using a histogram. Another common way of displaying wealth distributions like this is to use a cumulative distribution function, where the y-value at an ...

As a continuation of our course project due in unit viii a

As a continuation of our course project due in Unit VIII, A Permit By Rule (PBR) Application for an Interior Surface Coating Facility, complete the next section, "Operational Air Emission Rates," of your proposal by foll ...

Using the kronecker product recursion 5104 prove that a 2n

Using the Kronecker product recursion (5.104), prove that a 2n x 2n Hadamard transform is orthogonal.  Calculate and plot the energy packed in the first 1, 2, 4, 8, 16 sequency ordered samples of the Hadamard transform o ...

A program is to perform two products one is a vector

A program is to perform two products: one is a vector product of two 100-element vectors and the other is the product produced by multiplying the corresponding elements of a 1000 by 1000 element matrix by a scalar consta ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro