Monday, September 27, 2021

P versus NP problem

No comments:
The general class of questions for which some algorithm can provide an answer or solution in polynomial time is called "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:

  1. Problem L should be in NP
  2. 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:

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


Sunday, September 30, 2018

Android: Change color of the downloaded material icon

No comments:
Add below two lines in your ImageButton or ImageView

android:tint="@color/colorPrimary"
android:tintMode="@color/colorPrimary"

Check the example shown below:

Tuesday, September 11, 2018

Android Studio: Change Toolbar font

No comments:
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

3 comments:
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




Saturday, August 25, 2018

Create a Navigation Drawer using Android Studio with Kotlin Support

No comments:
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

2 comments:

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 / 107 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 / 107 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)

Time for the first packet (P1) to reach switch =Transmission time + Propagation delay
=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