1. Write a recursive function square which takes a non-negative integer as an argument and returns that integer raised to the second power. 2. Write a recursive function pow which takes a base as an integer and a non-negative exponent as an integer and returns the base raised to the exponent. 3. Write a recursive function selsort which takes an array of integers and its size as an integer as arguments and sorts the array using the selection sort algorithm presented in class. 4. Write a recursive function stringReverse that takes a character array containing a string as an argument, prints the string backwards and returns nothing. The function should stop processing and return when the terminating null character is encountered. 5. Implement the insertion sort algorithm. Insertion sort is a sorting algorithm which picks up successive elements from an unsorted array and "inserts" each of these into the correct position in an already sorted subarray (at one end of the array being sorted). The array to be sorted is divided into a sorted subarray and an unexamined subarray. Initially, the sorted subarray is empty. Each element of the unexamined subarray is picked and inserted into its correct position in the sorted subarray. The following illustrates how an unsorted array is modified by insertion sort. // initial unsorted array 8 6 10 2 16 4 18 14 12 10 8 6 10 2 16 4 18 14 12 10 6 8 10 2 16 4 18 14 12 10 6 8 10 2 16 4 18 14 12 10 2 6 8 10 16 4 18 14 12 10 2 6 8 10 16 4 18 14 12 10 2 4 6 8 10 16 18 14 12 10 2 4 6 8 10 16 18 14 12 10 2 4 6 8 10 14 16 18 12 10 2 4 6 8 10 12 14 16 18 10 // final sorted array 2 4 6 8 10 10 12 14 16 18 Write a function insertion_sort which takes an array of integers and its size as an integer as arguments and sorts the array using the insertion sort algorithm above. What is the run-time complexity of the insertion sort algorithm? 6. Use a two-dimensional array to solve the following problem. A company has four salespeople (1 to 4) who sell five different products (1 to 5). Once a day, each salesperson submits a slip for each of the different type of products sold. Each slip contains the following: a) the salesperson number b) the product number c) the total dollar value of that product sold that day Thus, each salesperson submits between 0 and 5 sales slips per day. Write an efficient program that will read an unknown number of triples (max 100) of positive numbers from standard input (do not prompt for input) representing the sales data, summarize the total sales by salesperson by product, and print the summary to standard output. Each triple consists of a salesperson number, a product number, and the dollar amount of that product sold by that salesperson in one day. No individual slip will contain a dollar amount of more than $9949.95. All totals should be stored in the two-dimensional array sales. After processing all the information print the results in a tabular format with each of the columns representing a particular salesperson and each row representing a particular product. Cross-total each row to get the total sales of each product; cross-total each column to get the total sales by salesperson. Your tabular printout should include these cross totals to the right of the totaled rows and to the bottom of the totaled columns. 7. A magic square is a square of numbers with n rows and n columns in which each of the integer values from 1 to n*n appears exactly once and the sum of each column, each row, and each diagonal is the same value. For example, the following is a magic square of size n=3. 8 1 6 3 5 7 4 9 2 Write a function magic_square which takes an odd number n as an argument and prints a magic square of size n. 8. Write an efficient function binsearch which implements the iterative binary search algorithm. The function must return the index of the target which has been found or -1 to indicate that the target is not in the array. 9. Write an efficient program to help a local restaurant automate its breakfast billing system The program should do the following: a) Show the customer the different breakfast items offered. b) Allow the customer to select more than one item from the menu. c) Calculate and print the bill. Assume that the restaurant offers the following breakfast items. Plain Egg $1.45 Bacon and Egg $2.45 Muffin $0.99 French Toast $1.99 Fruit Basket $2.49 Cereal $0.69 Coffee $0.50 Tea $0.75 Use an array menu_list of the struct menu_item_type (shown below). struct menu_item_type { string menu_item; double menu_price; }; Your program must contain the following functions. - get_data: loads the data into the array menu_list - show_menu: shows the different items offered and tells the users how to select items - print_check: calculates and prints the check (note: include a 7.5% sales tax). Format your output with two decimal places. The name of each item in the output must be left-justified. A customer may select multiple items of a particular type. A sample output is: Welcome to Johnny's Breakfast Paradise 1 Bacon and Egg $2.45 2 Muffin $1.98 1 Coffee $0.50 Tax $0.37 Amount Due $5.30 French Toast $1.99 Fruit Basket $2.49 Cereal $0.69 Coffee $0.50 Tea $0.75 10. Write an efficient program to print a grade report for two classes sections of 19 and 21 students each. Read 160 real values from standard input which correspond to four exams scores for each student. Print two labeled reports with an ordinal number, four exam scores (printed to the nearest tenth), a mean score (printed to the nearest hundredth) for each student per row. Use a pair of two-dimensional arrays to store the exam scores. In addition, use a pair of one-dimensional arrays to store student means. At the end of each report, print the highest and lowest student mean and their machine addresses. Use the following six functions: void load_scores_array(); // called twice void load_means_array(); // called twice void print_report(); // called twice double* find_addr_max_avg(); // called twice double* find_addr_min_avg(); // called twice void print_mean_and_addr (float *addr_avg); // called four times The fourth and fifth functions use pointer arithmetic to scan an array. The sixth function prints out both the machine address received as an argument and the mean score stored at that address. Use the following program as a helpful example. #include using namespace std; main() { int x[3] = {1, 3, 2}; int* y = x; for (int i=0; i < 3; i++) cout << y[i] << " " << y+i << endl; }