### Monday, September 27, 2021

## P versus NP problem

The general class of questions for which some algorithm can provide an answer or solution in polynomial time is called

The

Consider Sudoku, a game where the player is given a partially filled-in grid of numbers and attempts to complete the grid following certain rules. Given an incomplete Sudoku grid, of any size, is there at least one legal solution? Any proposed solution is easily verified, and the time to check a solution grows slowly (polynomially) as the grid gets bigger. However, all known algorithms for finding solutions take, for difficult examples, time that grows exponentially as the grid gets bigger. So, Sudoku is in NP (quickly checkable) but does not seem to be in P (quickly solvable).

An answer to the

P is subset of NP (any problem that can be solved by deterministic machine in polynomial time can also be solved by non-deterministic machine in polynomial time).

P is set of problems that can be solved by a deterministic Turing machine in Polynomial time.

NP is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time.

References:

**"class P"**or just**"P"**. For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. The class of questions for which an answer can be verified in polynomial time is called**NP**, which stands for "nondeterministic polynomial time".The

**P versus NP problem**is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified (technically, verified in polynomial time) can also be solved quickly (again, in polynomial time).Consider Sudoku, a game where the player is given a partially filled-in grid of numbers and attempts to complete the grid following certain rules. Given an incomplete Sudoku grid, of any size, is there at least one legal solution? Any proposed solution is easily verified, and the time to check a solution grows slowly (polynomially) as the grid gets bigger. However, all known algorithms for finding solutions take, for difficult examples, time that grows exponentially as the grid gets bigger. So, Sudoku is in NP (quickly checkable) but does not seem to be in P (quickly solvable).

An answer to the

**P = NP**question would determine whether problems that can be verified in polynomial time, like Sudoku, can also be solved in polynomial time. If it turned out that P ≠ NP, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.P is subset of NP (any problem that can be solved by deterministic machine in polynomial time can also be solved by non-deterministic machine in polynomial time).

P is set of problems that can be solved by a deterministic Turing machine in Polynomial time.

NP is set of decision problems that can be solved by a Non-deterministic Turing Machine in Polynomial time.

**NP-complete**problems are the hardest problems in NP set. Two conditions must be satisfied for a problem L to be NP-complete:- Problem L should be in NP
- Every problem in NP is reducible to L in polynomial time.

A problem is

**NP-Hard**if it follows property 2 mentioned above, doesn’t need to follow property 1. Therefore, NP-Complete set is also a subset of NP-Hard set.References:

- https://en.wikipedia.org/wiki/P_versus_NP_problem
- https://www.geeksforgeeks.org/np-completeness-set-1/

### Sunday, September 30, 2018

## Android: Change color of the downloaded material icon

Add below two lines in your ImageButton or ImageView

android:tint="@color/colorPrimary"

android:tintMode="@color/colorPrimary"

Check the example shown below:

android:tint="@color/colorPrimary"

android:tintMode="@color/colorPrimary"

Check the example shown below:

### Tuesday, September 11, 2018

## Android Studio: Change Toolbar font

Step 1: Click the link below and follow the steps used to use a custom font in your project. Refer: http://www.btechonline.org/2018/09/android-studio-how-to-use-custom-font.html

Step 2 : Define Toolbar Theme

Open res/values/styles.xml define the following

<style name="ToolbarTheme" parent="ThemeOverlay.AppCompat.ActionBar"> <item name="android:fontFamily">@font/roboto_condensed_bold</item> </style>

Step 3: Add the following to your toolbar layout

**android:theme="@style/ToolbarTheme"**

Run the app...

## Android Studio: How to use custom font in an Android project

Step 1: Right-click the res folder and go to New > Android Resource Directory.

Step 2: From Resource type list, select font, and then click OK.

Step 3: Copy your font files (.ttf) and paste it in the font directory created in Step 2. (file name of the fonts should must contain only lowercase a-z, 0-9, or underscore)

Step 4: Now you can assign your font in the xml file using @font/font_name

Step 2: From Resource type list, select font, and then click OK.

Step 3: Copy your font files (.ttf) and paste it in the font directory created in Step 2. (file name of the fonts should must contain only lowercase a-z, 0-9, or underscore)

Step 4: Now you can assign your font in the xml file using @font/font_name

### Sunday, September 2, 2018

### Saturday, August 25, 2018

## Create a Navigation Drawer using Android Studio with Kotlin Support

Refer to the link below. The page shows you how to implement a navigation drawer using Drawer Layout.

**http://cseforstudents.in/book-android/navigation/navigation_drawer.php**### Sunday, April 15, 2018

## GATE-Computer Networks-Flow Control

**Previous GATE questions with solutions on Computer Networks (Flow Control) - CS/IT**

*GATE -2015*
1. Since it is a network that uses switch, every packet goes through two links, one from source to switch and other from switch to destination.

Since there are 10000 bits and packet size is 5000, two packets are sent. Transmission time for each packet is 5000 / 10

^{7}seconds
Two hosts are connected via a packet switch with 107 bits per second links. Each link has a propagation delay of 20 microseconds. The switch begins forwarding a packet 35 microseconds after it receives the same. If 10000 bits of data are to be transmitted between the two hosts using a packet size of 5000 bits, the time elapsed between the transmission of the first bit of data and the reception of the last bit of the data in microseconds is _________.

(a) 1075 (b) 1575 (c) 2220 (d) 2200

Ans: option (b)

Explanation:

It is given that there are 10,000 bits and since the packet size id 5000 it means we have 2 packets to send.

Transmission time for one packet = 5000 / 10

^{7}seconds = 500μs
Transmission time is the time taken to transmit a packet from host to the outgoing link.

It is also given that the propagation delay of links is 20μs. Propagation delay is the time taken by a bit to reach from sender to receiver (in this case from sender to switch it is 20μs and from switch to receiver it 20μs)

=500μs + 20μs = 520μs

Once P1 reaches the switch, the switch will take 35μs to process the packet and then it takes 500μs to transmit it to the link and then the packet will take 20μs to reach the receiver.

Therefore Time taken by P1 to reach from switch to receiver = 35μs + 500μs+ 20μs = 555μs

Therefore time taken by P1 to reach from sender to receiver = 520μs+555μs = 1075μs

But we need to note that after 520μs the switch starts receiving second packet (P2).

i.e. At 520μs+500μs = 1020μs P2 is completely received by switch.

Now Time taken by P2 to reach from switch to receiver = 35μs + 500μs+ 20μs = 555μs

It means that at 1575μs (1020μs+555μs) P2 reaches the destination.

*Gate-2015*2. Suppose that the stop-and-wait protocol is used on a link with a bit rate of 64 kilobits per second and 20 milliseconds propagation delay. Assume that the transmission time for the acknowledgement and the processing time at nodes are negligible. Then the minimum frame size in bytes to achieve a link utilization of at least 50% is_________________.

(a) 160 (b) 320 (c) 640 (d) 220

Ans: option (b)

Explanation:

Since the link utilization should be atleast 50% it means that efficiency, η≥ 50%

Since it is mentioned that it is a stop&wait protocol, the efficiency of the link can be calculated as below:

**η = 1 /( 1 + 2a)**

a = Tp/Tt

*(where Tp =*

*Propagation delay & Tt = Transmission Time)*

Lets see the length of the packet to achieve a link utilization of 50%

50/100 = 1 /( 1 + 2a)

1/2 = 1 /( 1 + 2a)

a = 1/2

Tp/Tt = 1/2

20/Tt=1/2

Tt = 40ms

Tt = transmission time = L/B

*(where L = length of packet and B = bandwidth)*

L/B = 40

L =40 * B = 40 ms * 64 Kbps = 40*10-3 *64*103 = 2560 bits

Since we need to determine the frame size in bytes L = 2560/8 = 320 bytes.

Therefore, the minimum frame size in bytes to achieve a link utilization of at least 50% is 320bytes

Subscribe to:
Posts (Atom)