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

1 how would you use a random number generator to simulate

1. How would you use a random number generator to simulate the drawing of a playing card? 2. What is an "off-by-one error"? Give an example from your own programming experience. 3. Give an example of a for loop in which ...

1 what is a vulnerability scanner how is it used to improve

1. What is a vulnerability scanner? How is it used to improve security? 2. What is the difference between active and passive vulnerability scanners? 3. What kind of data and information can be found using a packet sniffe ...

Question 1 for each part show the sales orders that sold

Question 1: For each part, show the Sales Orders that sold that part. Show the Parts that have no sales as well. Display the PartID, Part Name, Sales Order #, the Quantity sold and the price for the order. Hint: A Left J ...

1 what is the definition of single loss expectancy what is

1. What is the definition of single loss expectancy? What is annual loss expectancy? 2. What is residual risk?

1 write a statement in java that stores the port number

1. Write a statement in Java that stores the port number 62230 in a variable in Java and guarantees that the number is stored as an unsigned number. 2. A socket address is the combination of an IP address and a port numb ...

Read the case study titled a patient information system for

Read the case study titled "A Patient Information System for Mental Health Care", located in Chapter 1 of your textbook. Develop an overall architecture for the system described in the assigned reading. Your architecture ...

1 how does a planner know when a task has been subdivided

1. How does a planner know when a task has been subdivided to an adequate degree and can be classified as an action step? 2. What is a deliverable? Name two uses for deliverables. 3. What is a resource? What are the two ...

Write a program named intarraydemo that stores an array of

Write a program named IntArrayDemo that stores an array of 10 integers. Until the user enters a sentinel value, allow the user three options: (1) to view the list in order from the first to last position, (2) to view the ...

1 what is the size of the key space if all 8 characters are

1. What is the size of the key space if all 8 characters are randomly chosen 8-bit ASCII characters? How long does an average key search take with a single PC? 2. How many key bits are used, if the 8 characters are rando ...

Using a graphics program design several security awareness

Using a graphics program, design several security awareness posters on the following themes: updating antivirus signatures, protecting sensitive information, watching out for e-mail viruses, prohibiting the personal use ...

  • 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

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

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen