In Prim's, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighbouring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be mRead more
In Prim’s, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighbouring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be merged to the current one if we have a connected graph.
In Kruskal’s, you do not keep one connected component but a forest. At each stage, you look at the globally smallest edge that does not create a cycle in the current forest. Such an edge has to necessarily merge two trees in the current forest into one. Since you start with N single-vertex trees, in N-1 steps, they would all have merged into one if the graph was connected.
Use Prim’s algorithm when you have a graph with lots of edges.
For a graph with V vertices E edges, Kruskal’s algorithm runs in O(E log V) time and Prim’s algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.
Prim’s algorithm is significantly faster in the limit when you’ve got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.
M=20 (total capacity of bag) N=4 (no of items) Let’s find Pi/Wi (profit/weight) for each items: P1/W1=3/5 = 0.60 (O1) P2/W2=10/13= 0.76(O2) P3/W3= 15/12 = 1.25 (O3) P4/W4 = 5/8 = 0.62 (O4) Where O is object no Let’s arrange them in order: 1.25 >> 0.76 >> 0.62 >> 0.60 Object takRead more
M=20 (total capacity of bag)
N=4 (no of items)
Let’s find Pi/Wi (profit/weight) for each items:
P1/W1=3/5 = 0.60 (O1)
P2/W2=10/13= 0.76(O2)
P3/W3= 15/12 = 1.25 (O3)
P4/W4 = 5/8 = 0.62 (O4)
Where O is object no
Let’s arrange them in order: 1.25 >> 0.76 >> 0.62 >> 0.60
Object taken
profit
weight
Remaining weight
O3
15
12
8
O2
10
13
0
O4
5
8
0
O1
3
5
0
Now,
Knapsack weight left to be filled is 8 kg but item-2 has a weight of 13 kg.
Since in fractional knapsack problem, even the fraction of any item can be taken.
A sorting algorithm is In-place if the algorithm does not use extra space for manipulating the input but may require a small but nonconstant extra space for its operation. Or we can say, a sorting algorithm sorts in-place if only a constant number of elements of the input array are ever stored outsiRead more
A sorting algorithm is In-place if the algorithm does not use extra space for manipulating the input but may require a small but nonconstant extra space for its operation. Or we can say, a sorting algorithm sorts in-place if only a constant number of elements of the input array are ever stored outside the array.
A sorting algorithm is stable if it does not change the order of elements with the same value.
If we talk about Optimality: In the Greedy method approach, there is no guarantee of getting the optimal solution, Generally, it gives the optimal local solution. while In the dynamic approach, there is a guarantee of getting an optimal solution as it considers all the cases as long to get optimal.Read more
If we talk about Optimality:
In the Greedy method approach, there is no guarantee of getting the optimal solution, Generally, it gives the optimal local solution.
while
In the dynamic approach, there is a guarantee of getting an optimal solution as it considers all the cases as long to get optimal. It gives optimal global solutions.
For example, let’s say that you have to get from point A to point B as fast as possible, in a given city, during rush hour. A dynamic programming algorithm will look into the entire traffic report, looking into all possible combinations of roads you might take, and will only then tell you which way is the fastest. Of course, you might have to wait for a while until the algorithm finishes, and only then can you start driving. The path you will take will be the fastest one (assuming that nothing changed in the external environment).
On the other hand, a greedy algorithm will start you driving immediately and will pick the road that looks the fastest at every intersection. As you can imagine, this strategy might not lead to the fastest arrival time, since you might take some “easy” streets and then find yourself hopelessly stuck in a traffic jam.
The list of debugging tools is listed below. AppPuncher Debugger is used for debugging Rich Internet Applications AQtime debugger CA/EZ TEST is a CICS interactive test/debug software package CharmDebug is a Debugger for Charm++ CodeView debugger DBG is a PHP Debugger and Profiler dbx debugger DistriRead more
The list of debugging tools is listed below.
AppPuncher Debugger is used for debugging Rich Internet Applications
AQtime debugger
CA/EZ TEST is a CICS interactive test/debug software package
CharmDebug is a Debugger for Charm++
CodeView debugger
DBG is a PHP Debugger and Profiler
dbx debugger
Distributed Debugging Tool (Allinea DDT)
DDTLite — Allinea DDTLite for Visual Studio 2008
DEBUG is the built-in debugger of DOS and Microsoft Windows
Debugger for MySQL
Opera Dragonfly
The dynamic debugging technique (DDT)
Embedded System Debug Plug-in is used for Eclipse
FusionDebug
Debugger OpenGL, OpenGL ES, and OpenCL Debugger and Profiler. For Windows, Linux, Mac OS X, and iPhone
GNU Debugger (GDB), GNU Binutils
Intel Debugger (IDB)
The system is used as circuit debugger for Embedded Systems
GNU Debugger, which is also called gdb, is the most popular debugger for UNIX systems to debug C and C++ programs.
GNU Debugger helps you in getting information about the following:
If a core dump happened, then what statement or expression did the program crash on?
If an error occurs while executing a function, what line of the program contains the call to that function, and what are the parameters?
What are the values of program variables at a particular point during execution of the program?
What is the result of a particular expression in a program?
How GDB Debugs?
GDB allows you to run the program up to a certain point, then stop and print out the values of certain variables at that point, or step through the program one line at a time and print out the values of each variable after executing each line.
To evaluate the maximum number of pages required when a system supports a 16-bit address line and a 1K (1024 Bytes) page size, we can break it down as follows: 16-bit Address Line: A 16-bit address line can address up to 216 locations (bytes). Page Size: Given a page size of 1K, which is equivalentRead more
To evaluate the maximum number of pages required when a system supports a 16-bit address line and a 1K (1024 Bytes) page size, we can break it down as follows:
16-bit Address Line:
A 16-bit address line can address up to 216 locations (bytes).
Page Size:
Given a page size of 1K, which is equivalent to 1024 Bytes (Ref: 1 KB = 1024 Bytes).
Now, calculate the maximum number of pages needed:
Total Addressable Locations= 216= 65536 locations.
Page Size = 1024 Bytes.
To find the total number of pages, divide the total addressable locations by the page size:
Total Pages= Total Addressable Locations/Page Size= 65536/1024= 64 pages.
Hence, in a system with a 16-bit address line and a 1K page size, the maximum number of pages required is 64.
Which algorithm is more efficient in constructing the minimum spanning …
In Prim's, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighbouring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be mRead more
In Prim’s, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighbouring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be merged to the current one if we have a connected graph.
In Kruskal’s, you do not keep one connected component but a forest. At each stage, you look at the globally smallest edge that does not create a cycle in the current forest. Such an edge has to necessarily merge two trees in the current forest into one. Since you start with N single-vertex trees, in N-1 steps, they would all have merged into one if the graph was connected.
Use Prim’s algorithm when you have a graph with lots of edges.
For a graph with V vertices E edges, Kruskal’s algorithm runs in O(E log V) time and Prim’s algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.
Prim’s algorithm is significantly faster in the limit when you’ve got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.
See lessSolve using fractional knapsack: M=20, n=4 P= (3, 10, 15, …
M=20 (total capacity of bag) N=4 (no of items) Let’s find Pi/Wi (profit/weight) for each items: P1/W1=3/5 = 0.60 (O1) P2/W2=10/13= 0.76(O2) P3/W3= 15/12 = 1.25 (O3) P4/W4 = 5/8 = 0.62 (O4) Where O is object no Let’s arrange them in order: 1.25 >> 0.76 >> 0.62 >> 0.60 Object takRead more
M=20 (total capacity of bag)
N=4 (no of items)
Let’s find Pi/Wi (profit/weight) for each items:
P1/W1=3/5 = 0.60 (O1)
P2/W2=10/13= 0.76(O2)
P3/W3= 15/12 = 1.25 (O3)
P4/W4 = 5/8 = 0.62 (O4)
Where O is object no
Let’s arrange them in order: 1.25 >> 0.76 >> 0.62 >> 0.60
Object taken
profit
weight
Remaining weight
O3
15
12
8
O2
10
13
0
O4
5
8
0
O1
3
5
0
Now,
< O3,(8/13)O2 >
See lessWhen can we say that a sorting algorithm is stable …
A sorting algorithm is In-place if the algorithm does not use extra space for manipulating the input but may require a small but nonconstant extra space for its operation. Or we can say, a sorting algorithm sorts in-place if only a constant number of elements of the input array are ever stored outsiRead more
See lessWhy dynamic approach is preferred over greedy technique?
If we talk about Optimality: In the Greedy method approach, there is no guarantee of getting the optimal solution, Generally, it gives the optimal local solution. while In the dynamic approach, there is a guarantee of getting an optimal solution as it considers all the cases as long to get optimal.Read more
If we talk about Optimality:
In the Greedy method approach, there is no guarantee of getting the optimal solution, Generally, it gives the optimal local solution.
while
In the dynamic approach, there is a guarantee of getting an optimal solution as it considers all the cases as long to get optimal. It gives optimal global solutions.
For example, let’s say that you have to get from point A to point B as fast as possible, in a given city, during rush hour. A dynamic programming algorithm will look into the entire traffic report, looking into all possible combinations of roads you might take, and will only then tell you which way is the fastest. Of course, you might have to wait for a while until the algorithm finishes, and only then can you start driving. The path you will take will be the fastest one (assuming that nothing changed in the external environment).
On the other hand, a greedy algorithm will start you driving immediately and will pick the road that looks the fastest at every intersection. As you can imagine, this strategy might not lead to the fastest arrival time, since you might take some “easy” streets and then find yourself hopelessly stuck in a traffic jam.
See lessList down various debugging tools. Elaborate any one of them
The list of debugging tools is listed below. AppPuncher Debugger is used for debugging Rich Internet Applications AQtime debugger CA/EZ TEST is a CICS interactive test/debug software package CharmDebug is a Debugger for Charm++ CodeView debugger DBG is a PHP Debugger and Profiler dbx debugger DistriRead more
The list of debugging tools is listed below.
GNU Debugger
GNU Debugger, which is also called gdb, is the most popular debugger for UNIX systems to debug C and C++ programs.
GNU Debugger helps you in getting information about the following:
How GDB Debugs?
GDB allows you to run the program up to a certain point, then stop and print out the values of certain variables at that point, or step through the program one line at a time and print out the values of each variable after executing each line.
GDB uses a simple command line interface.
See lessEvaluating the maximum number of pages needed, if a system supports 16 bit address line and 1K page size
To evaluate the maximum number of pages required when a system supports a 16-bit address line and a 1K (1024 Bytes) page size, we can break it down as follows: 16-bit Address Line: A 16-bit address line can address up to 216 locations (bytes). Page Size: Given a page size of 1K, which is equivalentRead more
To evaluate the maximum number of pages required when a system supports a 16-bit address line and a 1K (1024 Bytes) page size, we can break it down as follows:
16-bit Address Line:
Page Size:
Now, calculate the maximum number of pages needed:
Total Addressable Locations= 216= 65536 locations.
Page Size = 1024 Bytes.
To find the total number of pages, divide the total addressable locations by the page size:
Total Pages= Total Addressable Locations/Page Size= 65536/1024= 64 pages.
Hence, in a system with a 16-bit address line and a 1K page size, the maximum number of pages required is 64.
See less