CMPT 130 Assignment 4 – Arrays, Strings and Pointers

 

This assignment consists of writing functions to solve several unrelated problems. Your program will be marked by compiling it using g++ on Linux; therefore you should test your program with this compiler and in the Linux OS before submitting it. If you fail to do this, and if your program does not compile it will not be marked. This assignment is worth 5% of your final grade.

 

Common Reqirements

 

Function Specification

Your function name and parameter and return types must be exactly as specified in the assignment.

 

Submission Format

Your program should include the iostream, string and iomanip libraries and may also include the cmath library but may not include any other libraries. You should thoroughly test your functions in a main function. However, we will be running our own tests on your functions so please comment out or remove your main function before submitting your solution.

 

Input Errors

Unless stated otherwise your functions are not responsible for dealing with inappropriate values for parameters.

 

1 - Sum of Squares

Write a function called sumSquares that returns the sum of the squares of its double array parameter. The function should have a second (integer) parameter that specifies the size of the array. If the input array is empty the function should return zero.

 

Example

If arr contained the values {2.0, 3.0, 4.0} then sumSquares(arr, 3) should return the value 29 (from 22 + 32 + 42).

 

2 – Binary to Decimal

Write a function called binaryToDecimal that returns an integer that represents the decimal equivalent of the function's single string parameter.  The string parameter is expected to contain only binary digits (e.g. "1011101"). Your function should return -1 if it is passed an invalid string, i.e. one that contains characters that are not '1's or '0's.  You are not required to deal with negative binary numbers.

 

Some Hints

This question only requires you to use the few features of strings that were discussed in class. Recall that you can use a string's size method to find out how many characters are in it and that you can index a string just like you can an array. A good start would be to declare an integer variable for the result and initialize it to zero. Then do all the work in a for loop that processes each character in the string. Remember that strings store characters not numbers, so you should making a string from '1's and '0's, not 1s and 0s.

 

Examples

§  cout << binaryToDecimal("11010"); should print 26

§  cout << binaryToDecimal("11x10"); should print -1

§  cout << binaryToDecimal("10011110111"); should print 1271

 

3 – Column Total

Write a function called columnTotals that returns a pointer to an array of integers in dynamic memory that contains the totals of the columns of the function's two-dimensional integer array parameter. The array parameter represents a table with a variable number of columns and a fixed number of rows and is represented by an array of integer arrays of size ROW (i.e. a fixed number of rows in each column). The function should have an additional integer parameter that represent the number of columns; that is, the number of arrays (of arrays) in its two-dimensional array parameter. The row size of the two-dimensional array parameter should be specified with the global constant ROW that should be assigned the value 3.  The function prototype is shown below.

 

 int* columnTotals(int m[][ROW], int n);

 

The ROW constant should be defined below your include (and using) statements and just above your main function.

 

Example

If int table[5][ROW] = { {1,2,3},{4,5,6},{7,8,9},{3,3,3},{5,2,3} }; //where ROW = 3

Then columnTotal(table, 5) should return an array containing these values: {6,15,24,9,10}.

 

4 – Longest Strings

Write a function called longestStrings that returns a pointer to an array of strings. The function should return a pointer to an array of strings in dynamic memory that contains the longest strings in its string array parameter. The function should have three parameters, the array of strings from which the longest strings are to be obtained, an integer that represents the size of this array and an integer reference parameter whose value should be set to the size of the returned array.

 

The length of a string should be determined by calling its size() method. The function has to return (a pointer to) an array because the array parameter may contain multiple longest strings of the same length. If the array parameter contains duplicate longest strings, then the returned array should also contain duplicate strings.

 

Example

If string sarr[8] = {"bob","alice","kate","dr no","alice","sue","lee","min"}

Then longestStrings(sarr, 8, n) should return a pointer to an array containing the strings {"alice", "dr no", "alice"} and the parameter n should be set to 3.

 

5 - Fibonacci Sequence

Write a function called fibonacci that returns an integer pointer to an array in dynamic memory that contains the first n values of the Fibonacci sequence where n is the function's single integer parameter. 

 

Fibonacci Sequence

The Fibonacci sequence is a sequence of integers where the first two values in the sequence are 0 and 1, and each successive value is generated by adding the preceding two values in the sequence. The first eight values in the sequence are shown below.

 

0 1 1 2 3 5 8 13 from 0 1 0+1 1+1 1+2 2+3 3+5 5+8

 

You can find out more about the Fibonacci sequence here, or here, or here.

 

Examples

§  fibonacci(1) should return a pointer to {0}

§  fibonacci(3) should return a pointer to {0,1,1}

§  fibonacci(9) should return a pointer to {0,1,1,2,3,5,8,13,21}

 

6 – Decimal to Binary

Write a function called decimalToBinary that returns a string that represents the unsigned binary equivalent of the function's single integer parameter.  Your function should return the empty string (i.e. "") if it is passed a negative integer.

 

Creating Your Bit String

Your function should generate a string of '1's and '0's that represents the binary equivalent of the decimal integer parameter. I would suggest starting off your function by creating an empty string that you can return if the parameter is invalid (negative). Like this.

 

string result = "";

 

You can then generate the bit string by following this pseudocode algorithm:

 

powerOf2 = largest power of 2 less than x (where x is the parameter)

while powerOf2 > 0

             if x >= powerOf2 then result = result + "1" and x = x – powerOf2

             otherwise result = result + "0"

             powerOf2 = powerOf2 / 2

end while

 

There are a couple of issues that you are to deal with here.

§  Finding the largest power of 2 less than x – this part is maths, and I'm not going to tell you how to do it (the internet is your friend here)

§  The pseudocode also doesn't tell you how to deal with the input when it is 1 or 0. Again, this is left up to you to figure out

 

Examples

§  decimalToBinary(5) should return "101"

§  decimalToBinary(62) should return "111110"

§  decimalToBinary(1271) should return "10011110111"

 

7 – Print in Columns

Write a void function with six parameters called printColumns that prints its double array parameter in columns. The parameters represent the following and should appear in this order:

1.      The array to be printed – a double array

2.      The number of values in the array – an integer

3.      The number of columns – an integer

4.      The field width of the columns – an integer

5.      The number of digits that should be printed to the right of the decimal place – an integer

6.      A Boolean parameter that indicates whether the rows or columns should be filled first (see below) – a bool, true if rows should be filled first

 

Print Order

The last parameter affects the order in which the numbers should be printed. Assume the array contains the numbers 1 to 9, in that order, and that they are to be printed in three columns. See the two examples for what to do if the size of the array is not divisible by the number of columns.

 

Row First Order

1           2           3

4           5           6

7           8           9

 

Column First Order

1           4           7

2           5           8

3           6           9

 

Printing in row first order is straightforward. Print each row in turn, printing numbers in the order in which they appear in the array. Column order is more complex. Don't try to write code that actually prints the first column, then the second, and so on. As far as I know this isn't possible in a Console program. Find another way to do it.

 

Examples

printColumns(arr1, 9, 2, 5, 1, true)

where double arr1[] = {1.1, 2.22, 3.333, 4.444, 5.555, 6.66, 7.7, 8.888, 9.199}

  1.1  2.2

  3.3  4.4

  5.6  6.7

  7.7  8.9

  9.2

 

printColumns(arr2, 14, 4, 10, 2, false)

where double arr2[] = {3.1415, 11, 12.875, 21.33, 100.1234, 9.3, 10.111, 5.54, 89.1, 3.8, 11.7, 19.42, 5420.786, 1.1}

      3.14    100.12     89.10   5420.79

     11.00      9.30      3.80      1.10

     12.88     10.11     11.70

     21.33      5.54     19.42

 

8 – Sorted

Write a function called sorted that returns true if its integer array parameter is in ascending order from 0 to a given index and false otherwise.  The function should have a second parameter that gives the index of the last element of the range of values in the array to be checked. The function must be implemented recursively and must not contain a loop. Your function is not responsible for checking that the index parameter is within the bounds of the array.

 

Hint: start with arr[size-1] and work your way down to arr[0].

 

Examples

§  If arr = {3,5,23,91} then sorted(arr, 3) should return true (as the array is sorted)

§  If arr = {1,2,4,3,5} then sorted(arr, 4) should return false (as the array is not sorted)

§  If arr = {1,2,4,3,5} then sorted(arr, 2) should return true (as the elements of the array from index 0 to 2 inclusive are sorted)

§  If arr = {12} then sorted(arr, 0) should return true

 

Assessment

The assignment is out of 50.  Marks are assigned as follows:

§  Parts 1 to 8 - 5 marks each

§  Indentation – 2

§  Naming – 4

§  Comments – 2

§  Penalty – failure to write headers exactly as described will result in a 1-mark penalty for each function incorrectly specified. This includes function name, parameter list (including order) and return type.

§  Penalty – if your file contains a main function (that is not commented out) you will receive a 2-mark penalty.

 

Submission

You should submit your assignment online to the CoursSys submission server.  You must submit a single .cpp file named arrays.cpp, please read the documentation on site for further information.  The assignment is due by 11:59 pm on Wednesday the 14th of November.

 

To reiterate what it says at the start of the assignment – you should remove or comment out your main function so that your solution consists just of your include and using statements, constant declarations, function prototypes and your function definitions to solve each question. If you are unable to get one of the functions to work correctly then have it return a default value of the appropriate type and print a message (using cout) saying that you were unable to implement it.

 

 

CMPT 130 Home

 

John Edgar (johnwill@sfu.ca)