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

Note solving this problem is best done with use of

(Note: solving this problem is best done with use of probability through the level of Markov chains.) You are designing a computer system to control the power grid for the Northeastern United States. If your system goes ...

1 define cir bc and be and explain how a frame relay

1. Define CIR, Bc, and Be and explain how a Frame Relay service provider uses them. 2. What are the most important criteria for selecting a WAN service provider? 3. Why are QoS features often necessary in WAN routers? 4. ...

Repeat problem p4-3 for the differential manchester

Repeat Problem P4-3 for the differential Manchester scheme. Prob. 4.3 Draw the graph of the NRZ-L scheme using each of the following data streams, assuming that the last signal level has been positive. From the graphs, g ...

1 what special function does a cache server perform why is

1. What special function does a cache server perform? Why is this useful for larger organizations? 2. Describe how the various types of firewalls interact with the network traffic at various levels of the OSI model.

Cryptography projectlets suppose that alice and bob have

Cryptography Project Let's suppose that Alice and Bob have each a number n_A and respectively n_B between 1 and 10 and they want to know if they have the same number or not. The problem is that in case they don't have th ...

1 show the encoding for the integer 1456 using ber2 show

1. Show the encoding for the INTEGER 1456 using BER. 2. Show the encoding for the OCTET STRING "Hello world." using BER. 3. Show the encoding for the IPAddress 112.56.23.78 using BER. 4. Show the encoding for the object ...

1 discuss two security mechanisms applied at the

1. Discuss two security mechanisms applied at the application layer. Are they safer than those applied at the lower network layer? Support your response. 2. Are there security mechanisms applicable at transport layer? Is ...

A program runs on a superscalar processor with a 2 ghz

A program runs on a superscalar processor with a 2 GHz clock rate within a NUMA (non-uniform memory access) system. The number of instructions executed in the program is IC. The superscalar processor achieves an IPC (ins ...

1 list and describe the three fundamental ways that data

1. List and describe the three fundamental ways that data can be intercepted. How does a physcial security program protect against each of these data interception methods? 2. What can you do to reduce the risk of laptop ...

Create a simple structure using the information from your

Create a simple structure using the information from your book for help. Populate the structure. And print an example of one of the structure. Give example of the use of the dot operator.

  • 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