# CS 1025 Computer Science Fundamentals I

Assignment 5

*Department of Computer Science*

*University of Western Ontario*

Given: November 20, 2012

Due: December 4, 2012

This assignment is out of a total of 60 points.
By answering the bonus question,
you can get up to 120 points out of 60.
These bonus points can be used to make up for points missed on other
assignments (other assignments in this course only, however).

## Introduction

The ACM annually runs a university-level programming contest.
Western has participated in each of the past few years. Our university
falls in the East Central North American region, in which 130 teams competed this year. Western placed 29th in this region, which ranked us as the 10th Canadian team. For more details, see the news item
"UWO Programming Teams Attend ACM Competition". This assignment uses problems from that competition.

The way the contest works is as follows: In each region, teams in several locations are are simultaneously given a problem set. The teams try to solve as many problems as possible in five hours using C, C++ or Java. The teams are made up of three students each. These students may bring as much printed material as they like, but they may not bring electronic devices. Each team has a single computer on which to work. This computer has a simple text editor and the necessary compilers, but no IDEs or online documentation. The team solving the most problems wins. If more than one team solves the most problems, then the team who solves them fastest wins. There is a penatly scheme for incorrect solutions.

The problem set for this year is given here. The winning team solved problem B in 7 minutes. The Mustangs solved three problems in all, and had two additional problems almost working when the time ran out.

For this assignment you can solve any problems you like from this problem set using Java. It is possible to find published solutions to these problems, but you must produce your own solutions. (If you develop your solution without looking at any solutions, then it is your own solution.) each answer must have

- a Java program that solves the problem
- comments to explain how the program works, both at a high level, and in the details
- a set of test cases of your own devising
- the output your program generates for your test cases.

## Question 1 (60 points)

Solve any problem from
the 2012 problem set.

## Question 2 [BONUS] (60 points)

Solve a second problem from the 2012 problem set.