Algorithms Answers

Sort the following elements using merge sort technique 

using the Divide and Conquer strategy. {12,45, 6, 18, 10, 4, 3, 1, 13, 15, 16}

Determine the time and space complexity of the following algorithm.

Algorithm A(x,n)

Begin

for i := 1 to n do

 for j : = 1 to i do

 for k := 1 to j do

 x := x+1;

End

Write the algorithm, draw the flowchart, write and execute the Dart code for the following problem.

A student’s Midterm grade is 60 and the Final Grade is 80. The weight of Midterm and Final exams are % 40 and % 60 respectively.

Find the semester grade for this student.

Using appropriate diagrams, analyses the process flow for recognition evolvement, typically arranged as a hierarchy

Prove the theorem

The elass of regular languages is closed under union operation. In othe words, if Al

and A2 are regular languages, so is (Ai UA2)"for the following languageL-twiw acepts even mumber of 'a' or even number of "b'.

On the MIPS architecture, for example, the load-linked and store-conditional instructions can be

used in tandem to build locks and other concurrent structures. The C pseudocode for these

instructions is shown below. Alpha, PowerPC, and ARM provide similar instructions.

// Actions of thread Ti

1: int LoadLinked(int *ptr) {

2: return *ptr;

3: }

4: int StoreConditional(int *ptr, int value) {

5: if (no other thread has updated *ptr since the last LoadLinked access to *ptr by thread Ti)

6: {

7: *ptr = value;

8: return 1; // success

9: }

10: else {

11: return 0; // failed to update

12: }

13: }

The key difference comes with the store-conditional, which only

succeeds (and updates the value stored at the address just load-linked from) if no intervening store

by another thread to the address has taken place. In the case of success, the store-conditional returns

1 and updates the value at ptr to value; if it fails, the value at ptr is not updated and 0 is returned.

Please develop a mutex lock using this instruction.

The following flowchart finds if the triangle is isosceles, equilateral, or scalene. Some boxes in the flowchart are filled in for you, fill in the rest of the details.

Hint: In an equilateral triangle three sides are equal.

 In an isosceles triangle two sides are equal.

 In a scalene triangle three sides are not equal. 

 A, B, C are the marks scored by a student in Science, Mathematics and English. Refer the flowchart and answer the questions and fill in the rest of the details. A student whose average marks is above 75 is awarded a star. Fill in the following phrases in the flowchart for finding if a student gets a star or not. 

Yes, ____

No, ____ 

Award a star,____ 

Do better to get a star, ____

Is average greater than 75 ____

EXPLAIN IN DETAIL

A network G = (V, E) has 2²⁰ nodes. Each node v is labeled by a unique number L(v) between 0 to

2²⁰-1. No two nodes have the same label and there is a label for every node.

Two nodes u and v have an undirected edge (u, v) between them if and only if the following is true:

(i)The labels of the nodes L(u) and L(v) differ by a Hamming distance of at most 2 in their

binary representation, and

ii)The magnitude of the difference between the two numbers in the two labels is no

more than 9, i.e. | L(u) – L(v) | < 9. 

Answer all of the following questions:

(a) How many nodes in the graph are unreachable from the node with the label

00000000000000000111?

(b) Is the node 11110000000000000000 reachable from the node 00000000000000001111?

(c) How many edges are present in this graph?

(d) Is this graph bipartite?

(e) How many connected components are present in this graph?

convert the regular expression to E-NFA

1) a*

2) a+

3) a+b

4) a.b