Name:
(as it would appear on official course roster)
Umail address:	@umail.ucsb.edu	section 9am or 10:30am
Optional: name you wish to be called if different from name above.
Optional: name of "homework buddy" (leaving this blank signifies "I worked alone"

h15: Homework 15

ready?	assigned	due	points
true	Tue 11/22 02:00PM	Tue 11/29 02:00PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE/LAB LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the three lowest scores (if you have zeros, those are the three lowest scores.)

Please:

No Staples.
No Paperclips.
No folded down corners.

Reading: Read Chapter 14. If you do not have a copy of the textbook yet, there is one on reserve at the library under “COMP000-STAFF - Permanent Reserve”.

PLEASE MARK YOUR HOMEWORK CLEARLY, REGARDLESS OF IF YOU WRITE IT OUT IN INK OR PENCIL! FOR BEST RESULTS, SAVE THIS PAGE AS A PDF, THEN PRINT THE PDF.

1.(2 pts) Name 2 useful data structures that utilize pointers in programming.

2.(2 pts) How does a recursive function know when to stop recursing?

3.(3 pts) What is a LIFO scheme and how does it relate to stacks?

4.(3 pts) What is stack overflow?

5.(15 pts) Copy the binary search function found at this URL: http://cs.ucsb.edu/~zmatni/cs16/hw15/binarySearch.cpp

It has a few mistakes: fix them and get the program to work correctly. I recommend you do this by examining the code, compiling it, see what errors come up, then edit the code, and repeat the process until you have it working. Do NOT turn in the completed, fixed program. Instead write out in bullet points in the space below, EVERYTHING you had to fix to get the program working.

6.(15 pts) Write a recursive function program to find the nth element in the following arithmetic numerical sequence: 3, 11, 27, 59, 123, …

Hint: You first have to figure out what is the recursive pattern. You also have to identify the base case. If you cannot write out the program in the space provided below, then print out the program on a separate sheet of paper and attach that to this homework. Please do not use more than 1 page, one sided.

Some correct example outputs would look like this (there is no repeating loop - these are 2 separate runs):

Which element of the sequence would you like to know?
4
Element number 4 in the sequence is 59.


Which element of the sequence would you like to know?
7
Element number 7 in the sequence is 507.