Wireless Sensor Networks
Warning: you must not attempt to get help from external sources such as online sites that offer solutions. Any submission for grading must be your own work. You must not copy from others or allow your work to be copied. We will check for similarities of code. Any violation will result in your receiving zero for this project. No exception.
Your report must adequately describe your solutions, such as algorithm design, pseudo code, time complexity etc.
Total points: 10
This lab needs to be completed using Java and is an individual project. Naming of your programs must strictly follow the following convention: (1) one file for each part; (2) Lab2 followed by your Uid and I for part I (for example Lab1U00998499I.java). Upload only your source code (one file for each part) to the Pilot dropbox.
A wireless sensor network consists of autonomous sensors scattered in an environment where they monitor/detect/track objects and conditions such as temperature, sound, and pressure. In this lab, you are going to process information collected by sensor networks to detect possible objects and regions of interest.
The solution time complexity for this lab is an important consideration in grading. Therefore, you should design and implement your solutions carefully. Test cases will exercise your programs thoroughly. Your programs should efficiently handle potentially large problems. Expect that your program produces results for all test cases within 4-5 seconds.
Part I. Object Detection
A sensor network is deployed in a 2D field (a 2D rectangular grid) to detect objects of interest. For ease of data presentation, the collected sensor data is described by an N×N grid of characters. The characters are in the range A…Z. The object could be an animal or a vehicle of some shape or color. Let the characters represent one of 26 possible colors. As the designer of the sensor network, you know roughly what you plan to detect. We define a potential object of interest (POI) as follows. A POI is a rectangular sub-grid (possibly the entire 2D grid) with sides parallel to the sides of the sensor network field which is a square. We stipulate that a POI must not be contained within any other POI. That is, no smaller subset of a POI is also a POI. Additionally, we expect a POI must contain exactly two colors. One of the two colors forms a contiguous region. The other color forms two or more contiguous regions. A real-world case would be to identify vehicles with camouflage. A region is considered to be contiguous if one can traverse the entire region by moving repeatedly from one cell in the region to another cell in the region taking steps up, down, left, or right (diagonals moves are not allowed).
For example, a 2D sensor field may produce sensor data as a rectangle with the following colors
CCCCC
CBCBC
CCCBB
This turns out to be a valid POI because the color C forms a single contiguous region and color B forms more than one contiguous region. In this dataset, we may have detected part of a vehicle.
In Part I, you are asked to write a program to determine the number of potential objects of interest in the given 2D sensor data set.
INPUT FORMAT (file sensor1.txt):
The first line of input specifies the size of the sensor field N (where 1≤N≤20). The field is an NxN square. The next N lines describe the data produced by the sensor network. Each line consists of N colors represented by N characters.
OUTPUT FORMAT (file sensor1out.txt):
Your solution must produce a single integer to indicate the number of potential objects of interest detected in the sensor field.
SAMPLE INPUT:
4
DBBZ
BBBZ
DDBB
DBBZ
SAMPLE OUTPUT:
2
In the example above, we can detect two potential objects of interest.
DBB
BBB
DDB
DBB
and
BZ
BZ
BB
BZ
Part II. Region of Interest
In Part II, we use the same sensor network to monitor a field. However, the objective is different. Instead of detecting objects of interest, we are interested in finding out the size of regions of interest. As in Part I, we have a sensor field of NxN square cells. Each sensor reports the “status” of a cell using an integer. Neighboring cells (cells either above, below, left, or to the right) reporting the same
“status” form a contiguous region. We do not count diagonal cells with the same “status” as part of the same contiguous region however.
Your task is to write software to determine two things: (1) the size of the maximum contiguous region (i.e., count the number of cells) of the same “status”; (2) the size of the maximum contiguous region that shows two different “status”. This kind of contiguous region must have two different “status”, not just one “status”.
INPUT FORMAT (file sensor2.txt):
The first line of input specifies the size of the sensor field N (where 1≤N≤250). The field is an NxN square of cells. This is followed by N lines. Each of the N lines contains N integers “status” of the sensor reading of the cell (the sensor “status” value is between 0 and 106). The sensor network designer knows that there are at least two different “status” values that will be produced by the sensor network in the sensor field.
OUTPUT FORMAT (file sensor2out.txt):
Produce two pieces of information in two separate lines: (1) the size of the largest contiguous region that shows the same “status”; (2) the size of the largest contiguous region that shows two different “status”.
SAMPLE INPUT:
4
8 3 9 3
4 9 9 2
9 9 2 7
8 2 2 9
SAMPLE OUTPUT:
5
10
Why Work with Us
Top Quality and Well-Researched Papers
We always make sure that writers follow all your instructions precisely. You can choose your academic level: high school, college/university or professional, and we will assign a writer who has a respective degree.
Professional and Experienced Academic Writers
We have a team of professional writers with experience in academic and business writing. Many are native speakers and able to perform any task for which you need help.
Free Unlimited Revisions
If you think we missed something, send your order for a free revision. You have 10 days to submit the order for review after you have received the final document. You can do this yourself after logging into your personal account or by contacting our support.
Prompt Delivery and 100% Money-Back-Guarantee
All papers are always delivered on time. In case we need more time to master your paper, we may contact you regarding the deadline extension. In case you cannot provide us with more time, a 100% refund is guaranteed.
Original & Confidential
We use several writing tools checks to ensure that all documents you receive are free from plagiarism. Our editors carefully review all quotations in the text. We also promise maximum confidentiality in all of our services.
24/7 Customer Support
Our support agents are available 24 hours a day 7 days a week and committed to providing you with the best customer experience. Get in touch whenever you need any assistance.
Try it now!
How it works?
Follow these simple steps to get your paper done
Place your order
Fill in the order form and provide all details of your assignment.
Proceed with the payment
Choose the payment system that suits you most.
Receive the final file
Once your paper is ready, we will email it to you.
Our Services
No need to work on your paper at night. Sleep tight, we will cover your back. We offer all kinds of writing services.
Essays
No matter what kind of academic paper you need and how urgent you need it, you are welcome to choose your academic level and the type of your paper at an affordable price. We take care of all your paper needs and give a 24/7 customer care support system.
Admissions
Admission Essays & Business Writing Help
An admission essay is an essay or other written statement by a candidate, often a potential student enrolling in a college, university, or graduate school. You can be rest assurred that through our service we will write the best admission essay for you.
Reviews
Editing Support
Our academic writers and editors make the necessary changes to your paper so that it is polished. We also format your document by correctly quoting the sources and creating reference lists in the formats APA, Harvard, MLA, Chicago / Turabian.
Reviews
Revision Support
If you think your paper could be improved, you can request a review. In this case, your paper will be checked by the writer or assigned to an editor. You can use this option as many times as you see fit. This is free because we want you to be completely satisfied with the service offered.