DOC PREVIEW
UE CS 215 - CS 215 - Fundamentals of Programming II - Project 2

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 215 - Fundamentals of Programming IISpring 2005 - Project 220 pointsOut: January 30, 2008Due: February 6, 2008Reminder: Programming Projects (as opposed to Homework problems) are to be your own work. See syllabus for definitions of acceptable assistance from others.For this project, you will develop a simplified version of an algorithm used in image processing to find objects in a scene. Problem Statement Consider a square grid, some of whose cells contain asterisks and others that contain periods. On an 8X8 grid, we might have the following two examples: **...... .**..*.. **..*..* ****.*.. ..**.**. ...**... ..**.**. .*.*..** .*..*..* .*...*.* ..**.**. .****... ..**.**. .*.**... .*..*..* .*.**...Define two cells to be contiguous if they are adjacent to each other in the same row or in the same column. Now suppose we define a blob as follows: ● A blob contains at least one asterisk ● If an asterisk is in a blob, then so is any asterisk that is contiguous to it. ● If a blob has more than two asterisks, then each asterisk in it is contiguous to at least one other asterisk in the blob. We would like a program that determines the number of blobs and the placement of these blobs in a grid. The left example above has 13 blobs and the right example has 5 blobs. We will indicate the placement of blobs by replacing the asterisks with a unique letter (starting with a and identifying them in order of the upper-leftmost asterisk in each blob) indicating which blob a cell belongs to. For the examples above, the output would be: 01/29/08 1 of 3aa...... .aa..b.. aa..b..c aaaa.b.. ..dd.ee. ...aa... ..dd.ee. .c.a..dd .f..g..h .c...e.d ..ii.jj. .cccc... ..ii.jj. .c.cc... .k..l..m .c.cc...Design Notes Here are some suggestions for how to structure this program. ● One can use an (n+2)X(n+2) array with properly marked cells. The two additional rows and columns constitute a frame of periods surrounding the entered square to simplify the implementation. For example, the examples above could be stored as: .......... .......... .**....... ..**..*... .**..*..*. .****.*... ...**.**.. ....**.... ...**.**.. ..*.*..**. ..*..*..*. ..*...*.*. ...**.**.. ..****.... ...**.**.. ..*.**.... ..*..*..*. ..*.**.... .......... ..........● The main idea is to traverse the grid row by row and, for the first (unvisited) asterisk, call a function that processes the cell. The secret is to mark the cell by replacing the asterisk with the blob's identifying letter, and in using up to four recursive calls in the function for each unvisited contiguous asterisk.Assignment Write a program that is given an input file name on the command line. This file will contain an integer on the first line that is the size of the square grid, followed by a square grid of that size of asterisks and periods as shown above. (Note this means that you do not need to test for end of file!) You may assume that this grid will be no larger than 50X50, and that there will be no more than 26 blobs contained in the grid (to be marked from a up to possibly z). Example input files are available on csserver in directory /home/hwang/cs215/pro ject2 After reading the input grid from the input file, the program should determine the number of blobs and the placement of the blobs as indicated above. Finally, it should output the number of blobs found and the modified grid (without any 01/29/08 2 of 3extra frame cells) to the screen as shown below for the left example: Ther e are 13 blob(s) in th is file. aa...... aa..b..c ..dd.ee. ..dd.ee. .f..g..h ..ii.jj. ..ii.jj. .k..l..mThe blob processing must be done using a recursive function as indicated above. In addition, the output of the grid must be handled by a PrintGr id function that receives the grid to be printed. Note that this print function may be used a debugging tool by printing out the grid at various intermediate points, for example, after finding each blob. However, make sure such code is removed or commented out before submitting your project. (Reminder: global variables are not allowed in the course.) You must submit a makefile named Makefile.project2 for your project even though there is only one file for this project. It should be a full makefile with separate targets for the compile and link phases. The executable program must be named blobfinder. Submissions without working makefiles will be assessed up to a 3-point penalty as indicated in the syllabus. It should conform to the examples given in the handout Very Basic make and demonstrated in class. REMINDER: Your project must compile for it to be graded. Submissions that do not compile will be returned for resubmission and assessed a late penalty. Submissions that do not substantially work also will be returned for resubmission and assessed a late penalty.Follow the guidelines in the C++ Programming Style Guideline handout. As stated in the syllabus, part of the grade on a programming project depends on how well you adhere to the guidelines. The grader will look at your code listing and grade it according to the guidelines. What to submit Electronically submit a tarfile containing Makefile.pro ject2 and your program file as explained in the handout Submission Instructions for CS 215. Also hand in hard-copy printouts of these files as explained in the handout. Do not submit object files or executable files.01/29/08 3 of


View Full Document

UE CS 215 - CS 215 - Fundamentals of Programming II - Project 2

Documents in this Course
Lecture 4

Lecture 4

14 pages

Lecture 5

Lecture 5

18 pages

Lecture 6

Lecture 6

17 pages

Lecture 7

Lecture 7

28 pages

Lecture 1

Lecture 1

16 pages

Lecture 5

Lecture 5

15 pages

Lecture 7

Lecture 7

28 pages

Load more
Download CS 215 - Fundamentals of Programming II - Project 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 215 - Fundamentals of Programming II - Project 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 215 - Fundamentals of Programming II - Project 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?