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

Consider the following many to many relationshipan aircraft

Consider the following many to many relationship: An aircraft can be owned by many people. A person can own many aircraft. What would be the most appropriate way to handle the foreign keys to maintain this relationship? ...

1 write a program to find the sum of the first n natural

1. Write a program to find the sum of the first n natural numbers, where the value of n is provided by the user. 2. Write a program to find the sum of the cubes of the first n natural numbers where the value of n is prov ...

The ring offshore company in the north sea has deployed 13

The Ring Offshore company, in the North Sea, has deployed 13 drilling platforms to be connected through a network of pipelines with a hub assembly whose best position can be determined by solving a SCSE continuous locati ...

1 what is the best page size if entries now become 128

1. What is the best page size if entries now become 128 bytes? 2. Based on 5.10.1, what is the best page size if pages are half full? 3. Based on 5.10.2, what is the best page size if using a modern disk with a 3 ms late ...

Make a class employee with a name and salary make a class

Make a class Employee with a name and salary. Make a class Manager inherit from Employee. Add an instance variable, named department, of type String. Supply a method to String that prints the manager's name, department, ...

Computer science paper multiple perspectives on ethicswrite

Computer Science Paper: Multiple Perspectives on Ethics Write a 3 pages paper on the ethical issues/dilemma you might face in interacting with customers and project team, talk about how you understand ethical in computer ...

Discuss the impact of threaded binary tree on the tree

Discuss the impact of threaded binary tree on the tree traversal procedure. g. Obtain the optimal Huffman codes for the messages (M1,...,M7) with relative frequencies (q1,...,q7)=(4,5,7,8,10,12,20). Draw the decode tree ...

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 ...

1 what is the standard for encryption currently recommended

1. What is the standard for encryption currently recommended by NIST? 2. What is the most popular symmetric encryption system used over the Web? The most popular asymmetric system? Hybrid system?

1 assume a client sends a syn segment to a server when the

1. Assume a client sends a SYN segment to a server. When the server checks the well-known port number, it finds that no process defined by the port number is running. What is the server supposed to do in this case? 2. Ca ...

  • 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