Algorithms Answers

Has Path

Time Limit: 2 sec

Memory Limit: 128000 kB

Problem Statement

Given an undirected graph G (V, E) and two vertices v1 and v2 (as integers), check if there exists any path between them or not. Print true or false.

V is the number of vertices present in graph G and vertices are numbered from 0 to V-1.

E is the number of edges present in graph G.

Input

Line 1: Two Integers V and E (separated by space)

Next E lines: Two integers a and b, denoting that there exists an edge between vertex a and vertex b (separated by space)

Line (E+2): Two integers v1 and v2 (separated by space)

Constraints :

2 <= V <= 1000

1 <= E <= 1000

0 <= v1, v2 <= V-1

Output

For each testcase in new line, you need to print true or false.

Example

Sample Input 1 :

4 4

0 1

0 3

1 2

2 3

1 3

Sample Output 1 :

true

Explanation:

There are multiple path exists between 1 and 3. One of them is as such: 1 -> 2 -> 3.

Rotten Oranges

Time Limit: 2 sec

Memory Limit: 128000 kB

Problem Statement

Given a matrix of dimension n*m where each cell in the matrix can have values 0, 1 or 2 which has the following meaning:

0: Empty cell

1: Cells have fresh oranges

2: Cells have rotten oranges

So we have to determine what is the minimum time in sec required so that all the oranges become rotten. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in 1 sec. If it is impossible to rot every orange then simply print -1.

Input

First line of input has two integers n & m .

Then n lines follows having m space seperated integers which can be 0,1 or 2.

You are facing a river that stretches for a very long distance in both directions, in a straight line. There is a bridge but you do not know how far away or in what direction. It is dark and you only have a flashlight that allows you to see only see a bridge when you are right next to it. Design an algorithm that takes you to the bridge by walking at most O(n) steps where n is the distance between your initial position and the bridge. Analyze the number of steps you walk in the worst case exactly (i.e., without using asymptotics). Argue that it is not possible to do asymptotically better than this algorithm.

please make it as clear as possible and use more specifications.

Consider the table below and answer questions 23 to 25. The table depicts the running time (seconds) dependant on input size (n) of three algorithms Algorithm n = 100 n = 1000 n = 10 000 A 4 400 40 000 B 9 90 900 C 21 31 41 Question 23 What is the running time complexity of algorithm A? 1. O(n) 3. O(log n) 2. O(n2 ) 4. O(2n ) Question 24 What is the running time complexity of algorithm B? 1. O(n) 3. O(log n) 2. O(n2 ) 4. O(2n ) Question 25 What is the running time complexity of algorithm C? 1. O(1) 3. O(log n) 2. O(n) 4. O(1/n

Write briefly, as a group, the type of system/solution you are proposing, indicate from which category of the NDP2030 plan is the problem you identified and why you chose that area. Provide a list of your proposed system objectives (i.e. the requirements of the proposed solution) . Prepare a word document proposal containing detailed description of the problem, the current structure (algorithm) or what is currently happening, one or two paragraphs explaining the algorithm, and how you intent to solve the defined problem (problem solution).

A binary tree has its pre-order traversal as ABDCEGFHI and in-order traversal as BDAGECHFI. Construct the binary tree using these two traversals. 

List the properties of binary search tree and apply the properties to construct binary search

Part of the processing of the data is to calculate the amount of tax which needs to be paid.

. The person's total income for the year is input to the system

. The first $500 is not taxed

. The remainder is taxed at 10%

. Either the tax to be paid is output from the system OR a message is output to say there is no tax to pay

(a) Using ''I'' to stand for the total income and ''T'' to stand for the tax to be paid, produce an algorithm which will take I as its input and then calculate the tax.

(b) Explain why ''I'' and ''T'' are unsuitable as variable names and say how they can be improved.

(c) Describe how the algorithm can be used to calculate the tax for each person in the city without it having to be rerun.