Introduction

The assignment for this week will involve designing recursive functions.

We will also be grading for meeting requirements, using “class legal” code, and plagiarism. So, it is not enough for your lab to just pass the Gradescope autograder! Please read the instructions herein carefully.

It is highly recommended that you develop the algorithms for each program first and then develop the C++ code for it.

Step 1: Getting ready

Either through a graphical file system explorer or through the terminal:

1. Navigate to your cs16 directory:

   • For example, from the terminal:

   $ cd cs16

2. Create and navigate to the lab9 directory:

   • From example, from the terminal:

   $ mkdir lab9
   $ cd lab9

3. Download the starter files to your lab9 directory. Either:

   1. Download these starter files from the course website next to the Lab 9 instructions link: http://sites.cs.ucsb.edu/~zsisco/cs16/#labs

   2. Or, if you are using CSIL, run the following commands from your lab9 directory:

   $ cp ~zsisco/public_html/cs16/lab9-files.zip . 
   
   $ unzip lab9-files.zip

Step 2: Create and edit your C++ programs

This week, you will need to create multiple files for both exercises in this lab, described below. Each exercise is worth 50 points.

Important Note: We will take major points off if you use C++ instructions/libraries/code that either (a) was not covered in class, or (b) was found to be copied from outside sources (or each other) without proper citation.

selectionSort.cpp

Remember we covered the Selection Sort algorithm in lecture. You have to write a recursive version of this algorithm to be able to sort an array of integers into either ascending or descending order using the following idea: Place the smallest/largest element in the first position, then sort the rest of the array by a recursive call. Note: Simply taking the program from lecture and plugging in a recursive version of the function index_of_smallest will not suffice. The function to do the sorting (called sort here) must itself be recursive and not merely use a recursive function.

Requirements

1. Be sure to utilize only techniques we’ve covered in lecture. Do not use vectors, do not use built-in sorting functions, etc. You will get zero points if you do.

2. You are given 2 skeleton programs and 1 example final program: headers.h, functions.cpp, and selectionSort.cpp, respectively. You must complete the first 2 files and submit them. The third file, selectionSort.cpp, is an example of a program running and testing an integer array with the sort algorithm. In this program, the array is read from an input file, very much like what we did in Lab 4’s array.cpp exercise.

3. In both skeleton files, there are comments in there as guidelines to help you finish this exercise. You should read them carefully before you submit.

4. There are four functions that you must define for this exercise. Declare them in headers.h and define them in functions.cpp. The function requirements are detailed below:

   1. The function getArray is the same one we used in Lab 4’s arrays.cpp exercise. This function reads a text file that contains only integers and places them in an array. The size of the array and the name of the file are found in global variables already defined for you in the headers.h file. An input text file, ArrayFile.txt, is also provided for you to test out your final program.

   2. The function sort is the recursive function that you must design. It is based on the Selection Sort function sort() that I introduced to you in lecture. You have to re-design it to be a recursive function. If you fail at meeting this requirement, you will get a zero on this entire exercise, even if your code passes the autograder. This function calls 2 other functions (just like the example in lecture—but read the details below for more information) and it must have 4 arguments (in this order):

      1. a Boolean variable that holds the sorting direction choice “Descending Sort”(true) or “Ascending Sort” (false).
      2. An integer array that needs sorting
         
      3. An integer that indicates the size of the array (or sub-array) that needs sorting.
      4. An integer that indicates the starting index of the array that needs sorting. This is set to zero at first by the calling routing (i.e. the main function that calls sort).

   3. The function find_index_of_swap is a non-recursive function that you must design. It is based on the Selection Sort function index_of_smallest() that I introduced to you in lecture. You have to re-design it to work with the Descending/Ascending choice. This function must have 4 arguments (in this order):

      1. The aforementioned Boolean variable for sorting direction.
      2. The integer array.
      3. The integer for size of the array (or sub-array).
      4. The integer that indicates the starting index of the array that needs sorting.

   4. The function swap_values is the same one we used in the lecture’s Selection Sort example.

A session should look like one of the following examples (including whitespace and formatting). This is what you would see if you ran your (correctly done) functions via the main function in selectionSort.cpp.

$ ./selectionSort
Original array:
23 22 -5 -21 21 0 -12 -55 91 123 1 5 3 6 9 12 -11 17 8 -1
Ascending (0) or Descending (1): 0
Sorted array:
-55 -21 -12 -11 -5 -1 0 1 3 5 6 8 9 12 17 21 22 23 91 123
$ ./selectionSort
Original array:
23 22 -5 -21 21 0 -12 -55 91 123 1 5 3 6 9 12 -11 17 8 -1
Ascending (0) or Descending (1): 1
Sorted array:
123 91 23 22 21 17 12 9 8 6 5 3 1 0 -1 -5 -11 -12 -21 -55

Hints

Let’s say you have this integer array and you want to sort it in ascending fashion:

23 22 -5 0 1 2

Per the selection sort algorithm, you first find the minimum value (-5) and then swap it with the first element (23, index of 0). So, your array becomes:

-5 22 23 0 1 2

Since the first element (index 0) is now in its correct place, you can recursively do the sort if you now only consider your sub-array that starts at the next element (index 1). Then you re-do the recursion starting at next element after that (index 2), etc., until you are done!

palindrome.cpp

A palindrome is a word or phrase whose meaning may be interpreted the same way in either forward or reverse direction. Famous examples include “Amore, Roma”, “A man, a plan, a canal: Panama” and “No ‘x’ in ‘Nixon’”.

Write a recursive function called isPalindrome that returns a Boolean value of true if an input string is a palindrome and false if it is not. You can do this by checking if the first character equals the last character, and if so, make a recursive call with the input string minus the first and last characters. You will have to define a suitable stopping condition. If you fail at meeting the requirement of making this function a recursive one, you will get a zero on this entire exercise, even if your code passes the autograder.

Important: the string may contain any character, like whitespaces, punctuation, hash-tags, numbers, etc. You should only be checking if the alphabet characters constitute a palindrome (ignore the character case). An input string that has no letters (or is empty) is considered to be a palindrome (nothing backwards is still nothing).

Look at the palindrome.cpp program provided and the main() function therein. It takes in a string as user input, then calls 2 functions (cleanUp and isPalindrome) and, on the basis of the answer it sees, it outputs the result.

You have to: 1. Figure out the definitions (and declarations!) of these 2 functions. 2. Again, the function isPalindrome must be a recursive function. 3. You can create more than those 2 functions if you like, but you do not need to and likely will not need to either.

Here are a few example sessions. The program should print a string of text to the terminal before getting the inputs from the user. A session should look like one of the following examples (including whitespace and formatting):

$ ./palindrome
Enter sentence:
hello
It is not a palindrome.
$ ./palindrome
Enter sentence:
Madam, I'm Adam
It is a palindrome.
$ ./palindrome
Enter sentence:
MADAM!! I'M a d am!?
It is a palindrome.
$ ./palindrome
Enter sentence:
Madam I'm ada
It is not a palindrome.
$ ./palindrome
Enter sentence:
A Santa dog lived as a devil God at NASA
It is a palindrome.
$ ./palindrome
Enter sentence:
...Maps, DNA, and spam...
It is a palindrome.
$ ./palindrome
Enter sentence:
Just as I suspected...
It is not a palindrome.
$ ./palindrome
Enter sentence:

It is a palindrome.

Hints

Let’s take the example of the string: “Madam, I’m Adam”, a famous palindrome. You start off by “cleaning it up” of all punctuation, white spaces, and convert upper-case letters to get: “madamimadam”. Now you compare string[0] with string[last_position] (i.e. ‘m’ and ‘m’), if they are equal, you continue.

[m] a d a m i m a d a [m]

Now you no longer need these end letters. You can ignore them:

[a] d a m i m a d [a]

Now, again, you compare string[0] with string[last_position] (i.e. ‘a’ and ‘a’), if they are equal, you continue. Again, you can ignore these end letters (you can even discard them):

[d] a m i m a [d]

You keep doing this until there is nothing left to compare (think about how that is determined because this is your base case). If, along the way, every comparison was equal, then you have a palindrome. If even one comparison was not equal, then you don’t have a palindrome.

Step 3: Create a makefile and compile the code

In order to learn another way to manage our source codes and their compilations, we will first create a Makefile and put in the usual g++ commands in it. Afterwards, whenever we want to compile our programs, the command is a lot shorter—so this is a convenience.

Using your text editor, create a new file called Makefile and enter the following into it:

all: selectionSort palindrome

selectionSort: selectionSort.cpp headers.h functions.cpp
    g++ -o selectionSort selectionSort.cpp -Wall -std=c++11

palindrome: palindrome.cpp
    g++ -o palindrome palindrome.cpp -Wall -std=c++11

clean:
    rm -f a.out *.o selectionSort palindrome

Then from the command line, you can issue one command that will compile both exercises, like so:

$ make

If the compilation is successful, you will not see any output from the compiler. You can then run your program like this:

$ ./selectionSort

Or:

$ ./palindrome

If you encounter an error, use the compiler hints and examine the line in question. If the compiler message is not sufficient to identify the error, you can search online to see when the error occurs in general.

Remember to re-compile the relevant files after you make any changes to the C++ code.

Step 4: Submit your programs for grading

Once you are satisfied your programs are correct, then it’s time to submit them. While working with others is OK, you still must submit your own lab. Even if you’re working with another person, do not copy each other’s code.

Log into Gradescope and select CMPSC 16 under Summer 2021, and navigate to the Lab 9 assignment. Then click on the “Upload Submission” button on the bottom right corner to make a submission.

You will be given the option of uploading files from your local machine or submitting code from a GitHub repo. Follow the steps to upload all 3 files (headers.h, functions.cpp, and palindrome.cpp) to Gradescope (do not upload any other files). If your files do not have those exact names as presented in this lab, the autograder will not grade them. You can resubmit your files as many times as you like before the assignment deadline.