Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

Introduction:

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.

Input:

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

Syntax:

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.

exs:

INPUTS

input1.txt
----------------------------------------------
alpha beta gamma delta Alpha

input2.txt
----------------------------------------------
cat dog bird
input3.txt
----------------------------------------------
alphA
dog
input.script
----------------------------------------------
read(l1,’input1.txt’)
read(l2,’input2.txt’)
read(l3,’input3.txt’)
union(l1,l2,lu1)
prepare(lu1,’out1.txt’,forward)
union(lu1,l3,lu2)
prepare(lu2,’out2.txt’,reverse)
intersection(l1,l2,li1)
prepare(li1,’out3.txt’,forward)
intersection(l3,lu1,li2)
prepare(li2,’out4.txt’,reverse)

RESULTS

out1.txt
----------------------------------------------
alpha 2
beta 1
bird 1
cat 1
delta 1
dog 1
gamma 1

out2.txt
----------------------------------------------
gamma 1
dog 2
delta 1
cat 1
bird 1
beta 1
alpha 3

out3.txt
----------------------------------------------

out4.txt
----------------------------------------------
dog 1
alpha 1

Requirements:

• 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 a network consists of n hosts assuming that cryptographic

1. A network consists of n hosts. Assuming that cryptographic keys are distributed on a per-hostpair basis, compute how many different keys are required. 2. One cryptographic checksum is computed by applying the DES in C ...

1 unlike infrared wireless devices bluetooth technology

1. Unlike Infrared wireless devices, Bluetooth technology uses radio waves to communicate. What are the advantages of Bluetooth over these devices and also over 802.11 technology? 2. Study and discuss the reasons why WEP ...

Using the extended euclidean algorithm compute the greatest

Using the extended Euclidean algorithm, compute the greatest common divisor and the parameters s,t of 1. 198 and 243 2. 1819 and 3587 For every problem check if sr0 +t r1 = gcd(r0,r1) is actually fulfilled. The rules are ...

Equation 1374 tells us on average how many vertices are a

Equation (13.74) tells us on average how many vertices are a distance d away from a given vertex. a) Assuming that this expression works for all values of d (which is only a rough approximation to the truth), at what val ...

Design an algorithm that reads lines of text reformats it

Design an algorithm that reads lines of text, reformats it and writes it out in pages of two columns (each forty characters wide) separated by a 10-space gap. The first column of the output should correspond to the first ...

A 2 gb ie 2 230nbspbyte memory system with 32-bit

A 2 GB (i.e., 2 * 2 30  byte) memory system with 32-bit addresses is used with a 4-way set associative cache that contains a total of 65536 lines (each line is 512 bytes in size).  How many different memory blocks could ...

Alter the program from the last discussion question in the

Alter the program from the last discussion question in the following ways: (a) Make it draw squares instead of circles. (b) Have each successive click draw an additional square on the screen (rather than moving the exist ...

1 the ieee 80211 task group i tgi is developing new wlan

1. The IEEE 802.11 Task Group i (TGi) is developing new WLAN security protocols named TKIP and CCMP. CCMP is envisioned to supersede WEP and TKIP. Research and study these efforts and comment on the progress. 2. It has b ...

A circle 2n - 1 units in diameter has been drawn

A circle, 2n - 1 units in diameter, has been drawn symmetrically on a 2n × 2n chessboard, illustrated here for n = 3: a How many cells of the board contain a segment of the circle? b Find a function f(n, k) such that exa ...

Implement the linear quotient hashing method described in

Implement the linear quotient hashing method described in note 6 and compare its performance with the algorithm above for a load factor of 80%. Use a random number generator to provide the key set. Make tests for sets of ...

  • 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