CS100 M Spring 2001
Project 4: Catching Up
Due Online by 8am, Thursday, 3/08/2001

P4.1
rightmost, longest, arithmetic subsequence		 P4.2
polynomials		 P4.3
catch up		 P4.4
submission

0. Objectives and Modification History

Completing all tasks in this assignment should teach you:

Note: When developing your code, please feel free to display as much information as you find useful. However, the code you turn in should not produce any extraneous output. It is acceptable to print prompts, error messages, appropriate warning messages, and the information we've requested.

Modification History

1. Rightmost, Longest, Arithmetic Subsequence

Topics: While loops, loop invariants, input sequences.

Setup: An arithmetic sequence is a sequence a, a+d, a+2d, a+3d, a+4d, ... where the gap d between successive numbers is constant. For example, 5, 5, 5, ... and 1, 3, 5, 7, 9, ... are arithmetic sequences, but 1, 3, 6, 10 is not.

Task: Write a script read_long_arith.m to

Requirements:

Example: If the user's input was 1, 2, 0, 3, 6, 9, 12, 14, 7, 0, 2, 1, 0, -1, the program should display [0 3 6 9 12] as the answer. Think about what should happen if -1 is the first or the second number entered at the keyboard. Make sure your program treats these situations gracefully and gives a reasonable response.

2. Polynomials

Topics: Functions, array manipulations, error-checking.

Setup: Many computational problems are ultimately solved using polynomials, even if the theoretical (i.e. purely mathematical) solutions don't even refer to them. One reason for this is that very often it is impossible, or impractical, to directly handle the very complex functions that theoretical methods involve. Because almost all functions important in practice can be approximated with any desired precision by using polynomials, they are very often used to simplify the original problem and make the finding of an approximate solution feasable.

Although Matlab does provide support for polynomials, most programming languages do not. This provides us with an opportunity. In case you need to manipulate polynomials in a programming language that does not support them, your role in this part is to implement a set of functions that manipulate polynomials. The skills you learn will apply to just about any programming language you are likely to encounter. Since Matlab already provides support, this is a means for you to compare your answers with Matlab's.

We will represent polynomials by using arrays. Polynomial an*xn+an-1*xn-1+...+a2*x2+a1*x+a0 will be represented by the array [a0, a1, a2, ..., an-1, an].

Note that the array stores the coefficients in right-to-left order. Matlab, however, stores coefficients in left-to-right order; therefore, to convert between our representation and Matlab's, you should use the fliplr function. To make the polynomial representation unique, we will impose the condition that the representation be in canonical form: the leading coefficient an (last number in the vector) must be non-zero for all polynomials except the constant polynomial 0.

We will consider the following operations for/on polynomials: creation, addition, subtraction, multiplication, division, and evaluation. Remember that polynomial divisions typically generate a remainder. (See Examples below.)

Since part of programming is debugging and testing, we will ask you to write a Matlab script file that performs some tests to check that your implementation works.

Task: Implement Matlab functions for all the operations mentioned above and a Matlab script file that tests your functions. Except for makepoly, your functions may assume their arguments are in canonical form. The respective functions and script should have the arguments and behavior specified below:

Function Name Required Functionality
makepoly (p) Compute canonical form for polynomial p (provided already as a vector of coefficients): strip off "leading" 0s (trailing 0s in the vector).
addpoly (p1, p2) Compute and return p2+p1.
subpoly (p1, p2) Compute and return p2-p1.
mulpoly (p1, p2) Compute and return the multiplication of polynomial p1 and p2.

Note: do not type the strings conv or deconv anywhere in your function file.
divpoly (p1, p2) Compute and return the quotient and remainder of dividing p1 by p2. When called with one return argument (e.g. q= divpoly(p1, p2)) the function should return the quotient only. When called with two arguments (e.g. [q r] = divpoly(p1, p2)), the function should return the quotient and the remainder in the first and second argument, respectively.

Note: do not type the strings conv or deconv anywhere in your function file.
evalpoly (p, x0) Compute and return value of polynomial p at point x0.
Script Name Required Functionality
testpoly Run various tests and checks on your functions. Give enough examples to be convincing, but not too many. Spend some time thinking of how to choose relevant examples only. Include degenerate cases, but otherwise avoid trivial examples. Include comparisons with Matlab's polynomial functions: polyval, conv, deconv.

Turn in the functions and script listed above. You may not define other functions or scripts except as permitted in a recent post to the newsgroup:

[3/06] Revision posted to the newsgroup: 

! if you find testpoly using repetitive code to display values,
! you may --but are not required to-- define subfunctions to reduce
! redundancy.  since subfunctions are not allowed within functions, to
! allow you do do this, we will also allow you to make testpoly a
! function with no input variables and either no output variable or one
! output variable bad that is 0 is all tests are passed and
! non-zero if some tests are flunked:
! 
!     function [] = testpoly    or    function bad = testpoly
! 	  <your code>                       <your code>
! 
! where [] means "no output variables" and the lack of
! parenthesized variables after testpoly means "no input variables".

HINT: Ask on help for nargout. TKY didn't, but you might find it useful for this assignment.

Examples:

3. Catch up

Task: Get caught up, e.g.:

4. Submitting Your Work

The online submission system is up. Make sure to include the information requested in the Submission Rules. Your script and function files may not start with a space or blank line: Your script files must start with a comment and your function files must start with the function keyword (place the required identification comment block (you and your partner's name, cuid, section, etc.) below the comment specifying the behavior of the function).

You may submit files as you complete them (recommended). You don't have to submit everything all at once.

Please post/e-mail about any problems you have so that we can quickly fix things.

Note: Many people on Project P2 made up their own variable names; doing that on P4 will cost you points. Make sure to use verbatim (spelling, upper-/lowercase, etc.) the function and variable names we specify. (Script names on P4 don't have to match.)

Early Bonus: We will award bonus points for submitting the entire project early: No early bonus points for partial submissions.

Note: 15% of 5 is .75 and bonuses count less than core points, so it is better to submit a correct answer than an early answer.

Note: If you already submitted some polynomial code as part of P3: