Week 13: Exercises

1. Polynomials

Design and implement a C# class Polynomial representing a polynomial of a single variable. Your class should include the following:

• a constructor that takes a variable number of arguments of type double, yielding a polynomial with those coefficients. For example,

      new Polynomial(1.0, 4.0, 5.0)

  should yield the polynomial x² + 4x + 5.

• an overloaded operator + that adds two polynomials

• an overloaded operator - that subtracts two polynomials

• an overloaded operator * that multiplies two polynomials, or a polynomial and a scalar

• a method that evaluates a polynomial for a given value of x

• a method that returns the first derivative of a polynomial

• a method that finds an approximate zero of a polynomial, i.e. a value x for which the polynomial evaluates to zero

• a ToString() method that yields a string such as "x^2 + 4x + 5"

• a static method Parse() that parses a string such as "x^2 + 4x + 5", yielding a polynomial. Throw a ParseException if you cannot parse the string.

2. Double-Ended Queue

Design and implement a C# class Deque<T> that implements a deque (i.e. a double-ended queue) using a doubly-linked list. Your class should include the following:

• A method to test if a deque is empty

• Methods that can push or pop elements at either end of the deque. The pop methods should throw an exception if the deque is empty.

• An indexer that returns the n-th element of the deque (in linear time)

• An iterator that allows the caller to traverse the deque using foreach

• A method filter that removes all elements for which a given condition is false

• A method ToArray that converts a dequeue to an array

3. Counting Dequeue

Also write a subclass CountingDeque<T> that keeps track of the total number of values that have ever been pushed to a deque. The subclass should include a read-only property totalPushes that returns this value.

4. Coin Game

Consider the following game. There is a row of N coins on the table, with values V₁, V₂, ... V_N. On each player's turn, they can take either the first coin in the row or the last coin in the row. Write a method that takes an array with the values of the coins, and returns the maximum amount of money that the first player can win if both players play optimally.

5. Box Stacking

You are given a set of N boxes. Each box i has height h_i, width w_i and depth d_i. Write a program that determines the maximum possible height of any stack of boxes, assuming that you can place box b on box c only if w_b > w_c and h_b > h_c.

6. Drawing Squares

Write an application that lets the user draw squares by dragging the mouse. Each square should have a random color. If the user clicks on an existing square, they can drag it to a new position, and it should rise to the top of the Z-order.

7. Bouncing Ball

Write an application that displays a bouncing ball. The ball should lose a bit of velocity each time it hits the ground, so that it eventually comes to a stop.

8. Bouncing Balls

Extend the previous application so that the user can create new balls by clicking the mouse. Each ball should have a random size and color. All the balls should bounce simultaneously.

9. Hexapawn

The game of Hexapawn is played on an N x N chessboard. Each player starts with N pawns on one side of the board. Like in chess, a pawn can move forward one square, or capture by moving forward and diagonally left or right. Unlike in chess, a pawn cannot move two squares forward on its first move. A player loses if they have no legal moves or the other player's pawn reaches the end of the board.

With perfect play, will the first player win or lose if N = 3? If N = 4? Write a program to determine the answer.

10. Visual Hexapawn

Write a Windows Forms program that lets a player play Hexapawn versus the computer.