Assignment 1 PART 1 Description: ------------ Derive in details the complexity o
ID: 3870157 • Letter: A
Question
Assignment 1
PART 1
Description:
------------
Derive in details the complexity of the following code fragments in terms
of the Big-O notation:
1)
for i = 1 to n do
for j = 1 to n do
x = 2 * y
z = x--
2)
for i = 1 to n do
j = n
while j != 1 do
x++
j = j / 2
3)
i = 1
while i != n do
i++
4)
for i = 1 to n do
if i == 1 or i == n or i == 3 do
for j = 1 to n do
x++
Provide the corresponding big-O notation for the following functions:
n^2 + 3n - 7
5n^3 - 3n^2 + 8n - 2
lg(n) - 2 + 3n
nlg(n) - n + 3
Part 2
PROBLEM DESCRIPTION:
^^^^^^^^^^^^^^^^^^^^
Nobody wants a nuclear power plant in their neighborhood. Unfortunately,
the governor must locate a nuclear power plant somewhere inside a 25 square
mile area containing four cities. The governor, being primarily concerned
with reelection, desires to locate the plant in the location which will
cause the least amount of unhappiness among the constituents. In this lab,
you will write a program to assist the governor in this difficult decision.
METHOD:
^^^^^^^
Assume each city is located in an integer-pair (x, y) valued location
within a 25 x 25 square mile area. For example, a city can be located at
(4, 19), but not at (4.5, 19.8). In other words, there are no real valued
coordinate for a location of a city.
Your program will consider each integer-pair valued location within the area
as a possible site for the nuclear plant, starting at (1, 1) and continuing
across each row until the final site (25, 25) is reached.
At each possible location for the nuclear plant, your program will compute
the average unhappiness if the plant were located there. The following two
rules will be used to compute the unhappiness for a city.
1) If the plant is within two miles or less of a city, the
unhappiness is infinite (that is, assign a very large number
to the unhappiness for that city).
2) Otherwise, the unhappiness is equal to the population of the
city divided by the distance of the plant from the city.
The average unhappiness equals:
Avg. Unhappiness = Sum of the unhappiness of 4 cities /
The total state's population.
Your program should select the site at which the average unhappiness is
smallest.
INPUT:
^^^^^^
The user should be prompted to enter the x and y coordinates and the
population for each of the four cities from the keyboard. Each coordinate
should be checked to ensure it is between 1 and 25. If not, the user should
be prompted to enter a value which is in the correct range. The population
should be entered in thousands of people. For example, if the population
is 10,000, the user should input 10.
OUTPUT:
^^^^^^^
The program should print a message indication the coordinates where
the plant should be located. Following that message, the user should be
prompted to enter a 1 to view a map of the scenario or a 0 to exit the
program.
An Example Scenario:
Enter the x and y for City 1 : 1 1
Enter the Population for City 1: 10
Enter the x and y for City 2 : 1 25
Enter the Population for City 2: 10
Enter the x and y for City 3 : 25 1
Enter the Population for City 3: 10
Enter the x and y for City 4 : 25 25
Enter the Population for City 4: 10
**********
Locate the Plant At: 13 13
Enter 1 to view a Map of the scenario, or 0 to exit: 1
MAP OF SCENARIO
---------------
C2<><><><><><><><><><><><><><><><><><><><><><><>C4
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><>PP<><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
<><><><><><><><><><><><><><><><><><><><><><><><><>
C1<><><><><><><><><><><><><><><><><><><><><><><>C3
Note: The previous scenario is just an example, you need to create your own
test cases to make sure that your program produces the correct results.
Required Implementation:
^^^^^^^^^^^^^^^^^^^^^^^
Implement a State.java file that contains the State class. The state class
contains all the getters and setters for the data. It also contains the
methods that reads in the input calculates the location of the plant, and
displays the output. Another file is required is StatePlant.java which contains
your main program and all it does is instantiate the state, read the input
for the state, calculate the location, print the location, and based on the
user's input, print the map.
So the main should be simple and just contains:
State s = new State(); // you can have your own constructor if you'd like
s.read_input(); // this should populate the values. or you can read
// them in main an pass them here, it's up to you.
s.calc_plant(); // print the location of the plant after you calculate
// ask the user if he/she wants to display the map
if so
s.display_map();
Looking for some guidance on how to start these problems. Thank you
Explanation / Answer
1)
for i = 1 to n do===> This loop will run for n+1 time i.e once more when i>n
for j = 1 to n do==> This loop will run for n+1 time itself and n time becaise of outer loop so n2
x = 2 * y => This will run for n2
z = x--=> This will run for n2
So total time complexity is n +1 + 3n2 => O(n2)
2)
for i = 1 to n do==> This loop will run for n+1 time i.e once more when i>n
j = n==> This loop will run for n time
while j != 1 do==> This loop will run for ( log2 n ) + 1 time lets itself and n times becoz of outer loop so nlogn
x++ ==> We can see that j = j/2 j is reduced by half each time, lets take j = 16 it will run for 16,8,4,2,1 i.e log 16 + 1 = 5
j = j / 2==> This line will run for log n time
So total time complexity is nlog n + .... => O(nlogn)
3)
i = 1
while i != n do======> This loop will run for n+1 time i.e once more when i>n
i++=======> This line will run for n time
So total time complexity is n+1 + n => O(n)
4)
for i = 1 to n do====>This loop will run for n+1 time i.e once more when i>n
if i == 1 or i == n or i == 3 do========> runs n time because of outer loop
for j = 1 to n do==> satisfied 3 times for 1,3 and n runs n time itself
x++
=> n + 3n = O(n)
Provide the corresponding big-O notation for the following functions:
f(n)= n^2 + 3n - 7
We need to find c*g(n) such that c*g(n)>=f(n)
=> 2n2 >= n^2 + 3n - 7
c = 2
i.e f(n) = O(n2)
5n^3 - 3n^2 + 8n - 2
We need to find c*g(n) such that c*g(n)>=f(n)
=> 6n3 >=5n^3 - 3n^2 + 8n - 2
c = 6
i.e f(n) = O(n3)
lg(n) - 2 + 3n
We need to find c*g(n) such that c*g(n)>=f(n)
=> 4n >=lg(n) - 2 + 3n
c = 4
i.e f(n) = O(n)
nlg(n) - n + 3
We need to find c*g(n) such that c*g(n)>=f(n)
=> 2nlog n >=nlg(n) - n + 3
c = 2
i.e f(n) = O(nlog n)
Thanks, let me know if there is any concern.