Spring2016.CSCI230Homework2 History

Show minor edits - Show changes to output

Changed line 81 from:
11 3
to:
3 11
Changed line 104 from:
11 3
to:
3 11
Changed line 120 from:
11 3
to:
3 11
Changed lines 65-66 from:
two @@ints@@ depicting the number of rows and columns (0 or more) in the grid, followed by the locations of asterisks within the grid (in increasing order, starting with 0).
to:
two @@ints@@ depicting the number of rows and columns (0 or more) in the grid, followed by the locations of asterisks within the grid (in increasing order, starting with 0, and terminated by -1).
Changed line 82 from:
0 3 4 7 9 10 18 20 21
to:
0 3 4 7 9 10 18 20 21 -1
Changed line 105 from:
0 2 4 8 9 10 16 19 20 22 25
to:
0 2 4 8 9 10 16 19 20 22 25 -1
Changed line 121 from:
2 3 4 6 7 8 15 17 19 26 27 28
to:
2 3 4 6 7 8 15 17 19 26 27 28 -1
Changed line 105 from:
0 2 4 8 9 10 16 19 20 21 25
to:
0 2 4 8 9 10 16 19 20 22 25
Changed line 2 from:
'''Due Date''': Thursday, Feb. 4, 2016\\
to:
'''Due Date''': Tuesday, Feb. 9, 2016\\
Changed line 56 from:
# an iterative method, @@int countDistrictsIterative()@@ (parameter list up to you).
to:
# '''(Bonus)''' an iterative method, @@int countDistrictsIterative()@@ (parameter list up to you).
Changed lines 31-32 from:
For example, there are four districts in the partial grid
to:
For example, there are four districts in the following grid:
Changed lines 38-39 from:
seven districts in
to:
seven districts in this grid:
Changed lines 45-46 from:
and only one in
to:
and only one in this grid:
Added lines 84-90:

which corresponds to the following grid:

|| border=1 width=40%
|| * || || || * || * || || || * || || * || * ||
|| || || || || || || || * || || * || * ||
|| || || || || || || || || || || ||
Changed line 13 from:
* deriving run-time complexity of an algorithm
to:
* deriving the run-time complexity of an algorithm
Changed lines 153-155 from:
# Place your program inside that folder.

# Place your PDF inside that folder.
to:
# Place your Java program inside that folder.

# Place your PDF document inside that folder.
Changed lines 13-14 from:
* Java programming style and documentation
to:
* deriving run-time complexity of an algorithm
Added lines 125-134:
!!Run-Time Analysis

In a separate PDF document, @@RunTimeAnalysis.pdf@@, state the run-time complexity of each of the two methods above, and explain fully why this is the case (see textbook for examples).

You should include all relevant code (just the methods, not everything else).

Note that there are many possible run-time complexities, based on the algorithms you derive to solve the problem.

This document should include similar identification information (name, class, date, etc.) at the top, as your program.
Added lines 154-155:

# Place your PDF inside that folder.
Added lines 1-155:
'''Assigned Date''': Thursday, Jan. 28, 2016\\
'''Due Date''': Thursday, Feb. 4, 2016\\
'''Due Time''': 5 mins before beginning of class

Last modified on {$LastModified} (see [[http://www.cs.cofc.edu/~manaris/index.php/Spring2016.CSCI230Homework2?action=diff&source=n&minor=n | updates]])

!!Purpose

This assignment focuses on:

* deriving both recursive and iterative solutions
* creating and manipulating 2D arrays in Java
* Java programming style and documentation

This is a '''solo''' assignment. '''You may discuss the assignment only with the TA or the instructor.'''

!!Assignment

Create a Java program, @@Gerrymander.java@@, which solves the following problem:

Consider a 2D grid consisting of cells, some of which are empty and some of which contain an asterisk.

Define two asterisks as ''contiguous'' if they are adjacent to each other in the same row or in the same column.

Also, define a ''district'' as follows:

# %alpha% A ''district'' contains at least one asterisk.
# If an asterisk is in a ''district'', then so is any asterisk that is contiguous to it.
# If a ''district'' has more than two asterisks, then each asterisk in it is contiguous to at least one other asterisk in the ''district''.

For example, there are four districts in the partial grid

|| border=1 width=40%
|| * || || || * || * || || || * || || * || * ||
|| || || || || || || || * || || * || * ||
|| || || || || || || || || || || ||

seven districts in

|| border=1 width=40%
|| * || || * || || * || || || || * || * || * ||
|| || || || || || * || || || || * || ||
|| * || || || || * || || || || || || ||

and only one in

|| border=1 width=40%
|| || || * || * || * || || * || * || * || || ||
|| || || || || * || || * || || * || || ||
|| || || || || * || * || * || || || || ||

Your program should contain the following two methods (it may also contain additional, auxiliary ones - up to you):

# a recursive method, @@int countDistrictsRecursive()@@ (parameter list up to you), and

# an iterative method, @@int countDistrictsIterative()@@ (parameter list up to you).

Each method should return the number of districts in a 2D grid.

!!Input

The program should accept several lines of input, as follows:

an @@int@@ (e.g., 1), which specifies which method to run (e.g., the first method above)\\
two @@ints@@ depicting the number of rows and columns (0 or more) in the grid, followed by the locations of asterisks within the grid (in increasing order, starting with 0).

You may assume that the input is formatted properly and is valid.

Your program should create a 2D array to store the above information.

!!Output

The program should output the value returned by the method called. Nothing more.

!!! I/O Sample 1

For example, given this input:

(:source lang=Python tabwidth=3 -trim :)
1
11 3
0 3 4 7 9 10 18 20 21
(:sourcend:)

the output of your program should be:

(:source lang=Python tabwidth=3 -trim :)
4
(:sourcend:)

!!! I/O Sample 2

For example, given this input:

(:source lang=Python tabwidth=3 -trim :)
2
11 3
0 2 4 8 9 10 16 19 20 21 25
(:sourcend:)

the output of your program should be:

(:source lang=Python tabwidth=3 -trim :)
7
(:sourcend:)

!!! I/O Sample 3

For example, given this input:

(:source lang=Python tabwidth=3 -trim :)
2
11 3
2 3 4 6 7 8 15 17 19 26 27 28
(:sourcend:)

the output of your program should be:

(:source lang=Python tabwidth=3 -trim :)
1
(:sourcend:)

and so on.

!!Documentation

Follow the Golden Rule of Style: "A program should be as easy for a human being to read and understand as it is for a computer to execute." [1]

In general, you should comment any variable, obscure statement, block of code, method, and class you create.

Your comments should express '''why''' something is being done, as opposed to '''how''' the how is shown by the code.

Also see the course documentation standards in [[Spring2016.CSCI230Homework1 | homework #1]].

'''NOTE:''' You may use [[https://en.wikipedia.org/wiki/Javadoc | Javadoc]] formatting, if you prefer. If so, do it consistently.

!!Submissions

Submit via OAKS as follows:

# Create a folder named 'First.Last', where 'First' is your first name, and 'Last' is your last name.

# Place your program inside that folder.

# Compress the folder as a .zip file.

# Upload on OAKS.

!!Grading

Your grade will be based on how well you followed the above instructions, and the depth/quality of your work.

!!Reference

# Cooper, D. and Clancy, M. (1985) "Oh! Pascal", 2nd ed., W.W. Norton & Company, New York, p. 42.