Assignment 3 CMPT 125
Assignment 3 consists of 4 short problems. Each problem is worth 25 points. Please make your outputs match the provided examples exactly. These problems will be automatically graded.
This assignment may be completed individually or may be completed in pairs (two students working together). Before you submit your solutions, please join one of the assignment 3 groups alone or with your partner. Then make your submission to your chosen group
PROBLEM 1 (25 points)
1. You will write a function, RunningMean, and a simple main function to use it. The prototype of the function RunningMean should be
void RunningMean(double* measurements,
double* runningMean, int numInRunningMean);
The running mean is defined as
runningMean[k] = (measurement[k] + measurements[k+1] + measurements[k+2]) / 3 0 <= k <= numInRunningMean-2
You must verify that data values are read, that data values are in range, that memory is allocated and that files are opened. Appropriate error messages and other actions for the cases where these verifications fail will be provided in the sample outputs. Write all error messages to stderr. Your code must match the provided sample outputs character by character.
Your main program should do each of the following:
1. Prompt for and read an input file name
2. Open the input file
3. Prompt for and read the number of data points to be analyzed, numMeas. Use scanf.
4. Dynamically allocate the arrays myMeasurements and myRunningMean to each have numMeas elements.
5. Read numMeas double values from the file into the 1-D dynamic array myMeasurements. You may assume the values being read from the file are all doubles and are separated by white space.
6. There may, or may not, be exactly numMeas elements in the file. If there are more than numMeas double values in the file ignore the extra values. If there are less than numMeas elements in the file AND there are at least three measurements in the file, proceed to calculate the running means for the data that are in the file. If there are less than three measurements in the file, then clean up and terminate the program. (see example outputs below)
7. Determine the running means of the measurements read from the file by calling the function RunningMean. The calculated running means will be stored in the array myRunningMean. Make sure you do not try to access array elements outside the allocated array.
8. Print the array of running Means to the screen, 5 per line. Each running mean should be printed in a field 10 characters wide and show 2 digits after the decimal point.
9. Make sure you have no memory leaks or dangling pointers. Make sure you have no open files when you terminate your program (for termination anywhere in your program),
TEST 1: can’t open input file
Enter the name of the input file: nonexistant1
ERROR: Input file nonexistant1 not opened
Enter the name of the input file: nonexistant2
ERROR: Input file nonexistant2 not opened
Enter the name of the input file: elephant
ERROR: Input file elephant not opened
ERROR: too many failures opening input file
TEST 2: can’t read numMeas, numMeas out of range
Enter the name of the input file: in1.txt
Enter the number of measurements: a3252
ERROR: Did not read an integer
Enter the number of measurements: 41
ERROR: numMeas is out of range
enter 0
Enter the number of measurements: 0
ERROR: numMeas is out of range
enter 0
ERROR: too many failures reading the number of measurements
TEST 3: Input file is empty
Enter the name of the input file: in3.txt
Enter the number of measurements: 12
ERROR: input file is empty
`
TEST 4: Input file contains less than 3 measurements
Enter the name of the input file: in4.txt
Enter the number of measurements: 8
ERROR: insufficient data to calculate a running average
TEST 5: Input file contains less data than expected
Enter the name of the input file: in5.txt
Enter the number of measurements: 8
ERROR: fewer than numMeas measurements in the file
The running sums are
14.37 13.90 38.53 39.27 0.00
0.00
You should also test, with your own test cases, including the correct amount of data in the file and for extra data in the file.
PROBLEM 2: (25 points)
You will write a recursive function to print the pattern that is shown in the examples below. You will also write a main program to test your function. Examples are given of the output on your screen for two values of number of rows. Your program must work for all values of number of rows > 0 and <= 20. While verifying your value of the number of rows you may need to print any one of the following error messages or prompts.
Enter the number of rows:
ERROR: The number of rows is out of range.
ERROR: Too many tries attempting to read the number of rows for the pattern.
Enter the number of rows: 11
|
|
|
|
|
|
1
|
|
|
|
|
|
|
|
|
|
|
1
|
3
|
1
|
|
|
|
|
|
|
|
|
1
|
3
|
6
|
3
|
1
|
|
|
|
|
|
|
1
|
3
|
6
|
10
|
6
|
3
|
1
|
|
|
|
|
1
|
3
|
6
|
10
|
15
|
10
|
6
|
3
|
1
|
|
|
1
|
3
|
6
|
10
|
15
|
21
|
15
|
10
|
6
|
3
|
1
|
|
|
1
|
3
|
6
|
10
|
15
|
10
|
6
|
3
|
1
|
|
|
|
|
1
|
3
|
6
|
10
|
6
|
3
|
1
|
|
|
|
|
|
|
1
|
3
1
|
6
3
1
|
3
1
|
1
|
|
|
|
Enter the number of rows: 8
HINT: the numbers in each row are determined using the same pattern, for example for the longest row in the second example:
Second number = first number + 2
Third number = second number + 3
Fourth number = Third number + 4
Fifth number = fourth number -4
Sixth number = fifth number -3
Seventh number = sixth number -2
1) If you wish you can write an iterative function to print one line of one of these patterns.
The line printed will contain an odd number P of integers following the pattern given in the hint above. You may also elect to include the iterative code to print the single line of the pattern within your recursive function to print the entire pattern.
2) You will write a recursive function to print the entire pattern line by line. Recursion is with respect to the lines of the pattern not numbers in each line of the pattern.
3) When you look at the examples you will see that the pattern always has an odd number of lines. If you ask for an even number of lines, Neven, the pattern will be the same as if you asked for the pattern for Neven-1 lines.
4) You will write a main program. The main program will read the number of rows. You may assume the user enters an integer. If the integer entered is out of range re-prompt, reread and re-test the value supplied. You should prompt a maximum of 5 times, terminating your program if no valid value of the number of rows is read in 5 tries.
5) You will call your recursive function to print the pattern
TEST 1: too many tries to read numRows
Enter the number of rows: 21
ERROR: The number of rows out of range
1 <= number of rows <= 20
Enter the number of rows: 0
ERROR: The number of rows out of range
1 <= number of rows <= 20
Enter the number of rows: 99
ERROR: The number of rows out of range
1 <= number of rows <= 20
Enter the number of rows: -43
ERROR: The number of rows out of range
1 <= number of rows <= 20
Enter the number of rows: 88
ERROR: The number of rows out of range
1 <= number of rows <= 20
ERROR: Too many tries attempting to read the number of rows for the pattern.
TEST 2: numRows is 5
Enter the number of rows: 5
PROBLEM 3: (25 points)
In this problem you will write all or part of two functions that sort an unsorted linked list into descending order. You will write all of one function, InsertionListDescendingIter. This function uses the insertion sort algorithm to sort the input linked list into a new linked list. You will also write two helper functions to implement the selection sort algorithm SelectionListDescendingRec. The selection sort will modify the input list. The prototype of these two sorting functions will be,
LinkedList * InsertionListDescendingIter(const LinkedList* head);
voidSelectionListDescendingRec(const LinkedList* head);
To help you complete these tasks you will be supplied with a file containing the following framework:
. the definitions of the LinkedList and LinkNode structures.
. the implementations of two functions which you may use in your insertion sort function.
void insertListNode(LinkedList* list, double val);
LinkedList* createLinkedList();
. the implementation of function SelectionListDescendingRec.
. the implementation of other LinkedList functions that may be used in testing of your functions. These functions may not be used within the functions you write.
. Two initial tests, using the functions described in the previous point that should produce the following output. You will need to do additional testing yourself to make sure your code
functions for all possible cases.
Original linked list:
88.000000 23.000000 36.000000 17.000000 2.000000 63.000000 28.000000
Insertion sort sorted linked list:
88.000000 63.0000006.000000 28.000000 23.000000 17.000000 2.000000
Original List
88.000000 83.000000 45.000000 27.000000 91.000000 76.000000 62.000000
Selection sort sorted List
91.000000 88.000000 83.000000 76.000000 62.000000 45.000000 27.000000
The functions you will write are:
A. Two helper functions called by the selection sort function, SelectionListDescendingRec:
1. void swapValues(ListNode* node1, ListNode* node2);
Function, swapValues, takes pointers to two ListNodes as its arguments. The function exchanges the values in the two ListNodes pointed to by the two pointers.
2. ListNode* findMax(ListNode* start, ListNode* maxNode);
Function findMax
. recursively finds the pointer to the ListNode with the largest value.
. The pointer to the ListNode containing the largest pointer is returned as return value of the value of the function.
. Begins looking for the ListNode with the largest value at the ListNode pointed to by pointer start. The ListNode pointed to by the pointer start can be any ListNode in the linked list.
B. LinkedList * InsertionListDescendingIter(const LinkedList* head);
Consider the function, InsertionListDescendingIter, for insertion sort.
. The pointer to the original unsorted linked list is passed into the function. The list pointed to by this pointer will not be changed in any way by your insertion sort function.
. Your insertion sort function will create a new sorted linked list containing links holding the same values as the original list.
. All new links will be allocated dynamically.
. The pointer to the new list will be passed back to the calling function as its return value.
. The solution inside your insertion sort function may call only the supplied functions listed below:
void insertListNode(LinkedList* list, double val);
LinkedList* createLinkedList();
To implement the insertion sort, repeat the next 3 steps until all nodes have been inserted into the new list:
. Select the next linkin the linked list.
. Make a new link containing the value in the selected link.
. Insert the new link into the new list.
. Stop when the next pointer in the current node is NULL.
Please note the following constraints for all three functions:
. You may not use global variables.
. Your code must not contain memory leaks or dangling pointers.
PROBLEM 4: (25 points)
You will write two C++ classes. One class will implement a linked list. The second class will implement a stack, using the linked list. You are given the LinkedList.h and Stack.h files which contain the definitions of the two classes. You will write the LinkedList.cpp and Stack.cpp files that will contain the implementation of these classes. You will also need to write a main program to test your classes. You are also given a Driver.cpp file that contains two simple tests that are a beginning to the comprehensive testing of the classes.
When you write your class to implement the linked list you do not need to start from scratch unless you want to. You may begin with the C implementation of the linked list that was discussed in class. This implementation is also posted with this assignment. The linked list class will contain the same functions as the C implementation posted with this assignment, with one exception. You will need to add the void removeNodeN(int N); function that removes the Nth node from the list. This function will consider the first node in the list to be node 1.
You will implement your stack using a linked list. Whenever possible you, when you write your stack class you should use the linked list functions to simplify the code for your stack. The head of the linked list should be attached to the bottom element in the stack. This means that adding to the top of the stack is appending to the linked list. The top of the stack is the last node in the list. Make sure to use the keyword const to indicate when methods may not change the object they are acting on.