Testing and Judging Programs; Getting Interesting Problems. Do all the exercises below. Hand in only what is asked in 1a, 1b, and 2, preferably by sending me an email before the class, or alternatively by bringing a hardcopy to the class.

Problem 1. Testing and judging programs

Write the programs in C for Problems 1-3 from Handout E1. Test and improve them.

a. Suppose we can write programs using either recursion (recursive functions) or iteration (loops), and suppose we have automatic garbage collection. For list element removal, assuming it is safe to update inputs, give complete C programs for what you think is the clearest version and what you think is the most efficient version, and justify in whatever way you can. Your programs can do whatever you like for input and output, but comment what "whatever you like" is.

b. Give your recursive functions for selection sort, and describe what functions what1 and what2 do. How sure are you with your answers? How much did testing help in each case?

Problem 2. Getting interesting problems

Describe three possible problems for the course project. For each one, describe the motivation, precise problem, existing algorithms if any, and references if any.

Good motivation and precise description are essential for us to evaluate the problem in the first place. Finding existing results and references is a critical first step for solving the problem.