Problem Analysis

1

Department of Electrical Engineering and Computer Science Texas A&M University-Kingsville

CSEN 5303 Foundations of Computer Science Spring 2021

Instructor: Habib M. Ammari, Ph.D. (CSE), Ph.D. (CS) First Project List: Problem Analysis, Problem Solving, and Programming

Date: Jan. 21, 2021 Project 1: We assume that the standard input contains a sequence of non-zero integers between - 121 and 121, which ends with 0. This sequence will be given by the user.

1. Write an algorithm, called Decomposition_Powers_Three, which produces the decomposition of each integer using powers of 3, namely 1, 3, 9, 27, and 81, and the + and – operators. Each power of 3 should appear at most once in the decomposition. Examples: 1 = 1

2 = 3 – 1 3 = 3 4 = 3 + 1 7 = 9 – 3 + 1 14 = 27 – 9 – 3 – 1 43 = 81 – 27 – 9 – 3 + 1 121 = 81 + 27 + 9 + 3 + 1

2. Show that the algorithm Decomposition_Powers_Three is correct using an informal proof (i.e., discussion).

3. Give a program corresponding to Decomposition_Powers_Three, using any of your favorite programming languages.

Observation: The intervals [-121,-41], [-40,-14], [-13,-5], [-4,-2], [-1,-1], [1,1], [2,4], [5,13], [14,40], and [41,121] play a particular role.

Project 2: The mathematician Conway imagined a game, called game of life, which considered cells that are susceptible to reproduce, disappear, or survive when they obey certain rules. These cells are represented by elements on a grid of squares, where a grid has an arbitrary size. Thus, each cell (except those on the boundaries of the grid) is surrounded by eight squares that contain other cells. The rules are stated as follows:

1. Survival: Each cell that has two or three adjacent cells survives until the next generation.

2. Death: Each cell that has at least four adjacent cells disappears (or dies) by overpopulation. Also, each cell that has at most one adjacent cell dies by isolation.

3. Birth: Each empty square (i.e., dead cell) that is adjacent to exactly three cells gives birth to a new cell for the next generation.

It is worth noting that all births and deaths occur at the same time during a generation.

Write a program that simulates this game and displays all successive generations, using any of your favorite programming languages.

The implementation of this game-of-life software should be as structured as possible.

2

Deliverables: Students may choose to work in team of up to two members. You should turn in a report explaining all the design decisions and your code should be commented appropriately for readability and understanding. More precisely, a report should include the problem statement, proposed approach/solution along with a detailed discussion, algorithm (high-level description of all the design parts along with some details when necessary), commented code, tests (input given by the user and output generated by your program execution), and lessons learned from such an implementation experience.

Good Luck!