please write in word and submit in pdf 1. This is an individual assignment. You
ID: 3879598 • Letter: P
Question
please write in word and submit in pdf
1. This is an individual assignment. You should do your own work. Any evidence of copying will result in a zero grade and additional penalties/actions 2. Submissions not handed on the due date and time will incur late penalty(i.e, 10 point deduction for each late hour) unless prior permission has been granted or there is a valid and verifiable excuse 3. Think carefully; formulate your answers, and then write them out concisely using English logic, mathematics and pseudocode (no programming language syntax) 4. Type your final answers in a Word document and submit online as a PDF through Canvas 5. Don't turn in handwritten answers with scribbling, cross-outs, erasures, etc. If an answer is unreadable, it will earn zero points. Neatly and cleanly handwritten submissions are also acceptable (1. 6pts) Computational problem solving: Estimating problem solving time Suppose that there are three algorithms to solve a problem: a O(n) algorithm (A1), a O(ilogni) algorithm (A2), and a O(2) algorithm (A3), where log is to the base 2. Using the techniques and assumptions presented in slide set L2-Butfet(SelectionProblem), determine how long in seconds it will take for each algorithm to solve a problem of size 200 million. You must show your work to get credit, i.e., a correct answer without showing how it is derived will receive zero credit. (2. 4pts) Computational problem solving: Problem specification Problem Definition: You are a member of a software engineering team, which is tasked to develop a mobile application for the SmartCity initiatives sponsored by an enterprise. The application is a transport sharing tool that will connect a driver with empty seats to people traveling to a specific target location. The driver's application will query a remote service to determine specific requests submitted by customers, where each request is defined by the position of the person making the ride sharing request. The location of a person is specified as pair (latitude, longitude). Given a list of requests as input and the computed shortest distances in terms of turn-by-turn directions between each pair of locations, the application generates the shortest possible route that visits each location exactly once (to pick up a customer) and return to the target location. Specify the problem to a level of detail that would allow you to develop solution strategies and corresponding algorithms. State the problem specification in terms of (1) inputs, (2) data representation, and (3) desired outputs. No need to discuss solution strategiesExplanation / Answer
Answer 1:
If input size is 200 i.e.
n=200
i) time complexity is O(n)
Answer =O(200)
ii) time complexity is O(nlogn)
O(200(log200)) = log(200) = log(2*100) = log2 + 2*log(10)
= 0.3010+2 { log 2=0.3010 , log 10 =1}
= 200* 2.3010
Answer=O( 460.2)
iii) time complexity is O(n2)
O(200*200)=O(40000)
Answer = O(40000)
Answer 2:
In this question we can apply breath first search.
First of all make a adjancy matrix like this:
Now apply bfs like this :
class ShortestPAth{
class Point
{
int x;
int y;
point(int x, int y)
{
this.x=x;
this.y=y;
}
}
class queueNode
{
Point point; // The cordinates of a cell
int dist; // cell's distance of from the source
queueNode(int point, int dist){
this.point=point;
this.dist=dist;
}
}
// check whether given cell (row, col) is a valid
// cell or not.
boolean isValid(int row, int col)
{
// return true if row number and column number
// is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
int rowNum[] = {-1, 0, 0, 1};
int colNum[] = {0, -1, 1, 0};
// function to find the shortest path between
//a driver's location to customers location
int BFS(int matrix[row][col], Point src, Point dest)
{
// check source and destination cell
// of the matrix have value 1
if (!matrix[src.x][src.y] || !matrix[dest.x][dest.y])
return INT_MAX;
boolean[] visited= new boolean[row][col];
// Mark the source cell as visited
visited[src.x][src.y] = true;
// Create a queue for BFS
Queue<queueNode> q = LinkedList<>();
// distance of source cell is 0
queueNode s = {src, 0};
q.add(s); // Enqueue drivers location
// Do a BFS starting from drivers location
while (!q.empty())
{
queueNode curr = q.peek();
Point pt = curr.pt;
// If we have reached the customers location,
// we are done
if (pt.x == dest.x && pt.y == dest.y)
return curr.dist;
// Otherwise dequeue the front locations in the queue
// and enqueue its adjacent locations
q.pop();
for (int i = 0; i < 4; i++)
{
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];
// if adjacent location is valid, has path and
// not visited yet, enqueue it.
if (isValid(row, col) && mat[row][col] &&
!visited[row][col])
{
// mark cell as visited and enqueue it
visited[row][col] = true;
queueNode Adjcell = { {row, col},
curr.dist + 1 };
q.push(Adjcell);
}
}
}
//return -1 if destination cannot be reached
return INT_MAX;
}
// Driver program to test above function
static int void main(String args[])
{
int matrix[row][col] =
{
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
};
Point source = {0, 2};
Point dest = {5, 6};
int dist = BFS(mat, source, dest);
if (dist != INT_MAX)
System.out.println("Shortest path is : "+ dist);
else
System.out.println("Shortest Path doesn't exist");
return 0;
}
}
Answer 3:
Function for I largest numbers
static int[] Largest_k(int[] a, int k){
int large[] = new int[k];
int max = 0, index;
for (int j = 0; j < k; j++) {
max = a[0];
index = 0;
for (int i = 1; i < a.length; i++) {
if (max < a[i]) {
max = a[i];
index = i;
}
}
large[j] = max;
a[index] = Integer.MIN_VALUE;
}
return large;
}
Answer 4:
A) input = {1,2,3,4,5,6,7,8,9,10]}= 55
B)input = { -1,-2,-3,-4,-5,-6,-7,-8,-9,-10 }=0
C) input = { 0,0,0,0,0,0,0,0,0,0 } = 0
D) input = { -1,2,-3,4,-5,6,7,-8,9,-10 }= 14
E) What does the function return when array contain all negative input = 0
F) ) What does the function return when array contain all non-negative input = sum of all numbers in array
Answer 5:
steps
Big o complexity
1
O(1)
2
O(1)
3
O(n2)
4
O(1)
5
O(n)
6
O(1)
7
O(1)
8
O(1)
9
O(1)
Complexity of algorithm is O(n2)
steps
Big o complexity
1
O(1)
2
O(1)
3
O(n2)
4
O(1)
5
O(n)
6
O(1)
7
O(1)
8
O(1)
9
O(1)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.