zak100

Hi,

I was reading an article related to MonteCarlo Method. The link of the article is:

http://ib.berkeley.edu/labs/slatkin/eriq/classes/guest_lect/mc_lecture_notes.pdf

I found the equation in the following attached image. 

1)In the equation related to the attached image, we are assigning a value to a function. What does this mean?

2)What the expected function will do with this value?

3)Please guide me by providing examples of function fX(ꭓ), E(g(X)) and g(ꭓ).

Zulfi.

Hi,

I am trying to apply PTAS on an algorithm. I think that we apply PTAS on the running time equation of the algorithm. We use the term (1-ϵ) and (1+ ϵ) in the running time of the algorithm but I don’t know how we insert these terms in the running time equation of the algorithm, and that’s what I want to understand. Also how we evaluate the value of ϵ.

Let suppose we have a algorithm:

M = K * Y

Let’s the running time of algorithm is pseudo-polynomial i.e p(n) * K where k and p(n)  are polynomial in n.

Somebody please guide me.

Zulfi.

Hi,

I received a response at:

https://math.stackexchange.com/questions/3668486/set-cover-problem-how-to-calculate-the-denominator

I have following questions:

(1)Why start with Z, cost is 7, cost of X is 6, we have to choose the least cost effective? (2) How are we choosing the denominators? In case of Z, denominators are 7, 5, 5, Z has 7 dots (or cardinality) but 5 are shareable and 2 are non-shareable? X has 5 shareable dots, 2 shared with Z and 3 shared with Y, denominators are 3 and 5 how?, Y has 5 elements 3 shareable with X and 2 non-shareable, denominator is 2, why? (3) What is the purpose of these 3 rounds? (4) What is the answer of set Cover? Example says optimal cost is 22? What is the cost in case of greedy algorithm?

Somebody please guide me.

Zulfi

Hi,

I am trying to understand the set cover problem. I found the algorithm at:

https://.mit.edu/~goemans/18434S06/setcover-tamara.pdf

I found the example:

Somebody please guide me how we evaluate the denominator |S-C|?

Zulfi.

Hi,

Answer: I think it also works in the same way as LRU for hardware which is done with the help of matrix, software is done by keeping a counter for each page. For example, figure (a) tells us the bit pattern corresponding to each page. And we can choose  one of 1 or 3 at random to evict if the page fault occurs. In (e), we can choose either page3 or page 5 but we can prefer page 5 in the memory because it was referenced two clock cycles earlier.

Zulfi.

Hi,

Thanks.

In figure (a) page 0 column is zero  and row is 1, so page 0 is in memory, in (b) page 1 column is 0 and its row is 1, so  page 1 is also in memory. In (c) page 2 row is 1 and column is zero so page 2 is also in memory. In (d) page 3 row is 1 and column is 0 , so page 3 is in memory. So we have 4 pages  in memory and the h/w is indicating this from figure (a) to (d).

I though at (e) we have to evict a page 2 but I think its not correct,  we are not evicting any page, we always have pages: 0, 1, 2, 3 and the matrix is telling us which is the least recently page.

At (e), page 0 is shown as the least recently used page because its row has the lowest binary value.

Thanks a lot. God bless you.

Zulfi.

Hi,

I am trying to understand the aging algorithm. I found the algorithm in the “Modern Operating Systems” book 4^th Edition.

Quote

Figure 3-17 illustrates how the modified algorithm, known as aging, works. Suppose that after the first clock tick the R bits for pages 0 to 5 have the values 1,  0, 1, 0, 1, and 1, respectively (page 0 is 1, page 1 is 0, page 2 is 1, etc.). In other words, between tick 0 and tick 1, pages 0, 2, 4, and 5 were referenced, setting their R bits to 1, while the other ones remained 0.

I am able to understand the above but I can't understand the following:

I can’t understand the following stuff:

Quote

 

After the six corresponding counters have been shifted and the R bit inserted at the left, they have the values shown in Fig. 3-17(a). The four remaining columns show the six counters after the next four clock ticks.

 

I think what it talks above happens in the row 0 which is my second figure, I have uploaded just the row correspond to Page 0:

Somebody please guide me about the working of the algorithm according to the figure.

Zulfi.

Hi,

I am trying to understand the hardware implementation of LRU. I got its explanation from the following link:

LRU implementation using a Matrix

I can't understand can we use this technique to tell (i)which page has been evicted and (ii) which pages are in the memory

I have attached its image:

Somebody please guide me.

Zulfi.

Hi,

I am trying to find out the number of page faults. I have found an example question with solution:

Quote

A memory system has three frames and eight virutal pages. Consider
the reference string 01232304523143263212.
1) How many page faults will occur when FIFO, LRU, and Optimal
algorithms are used respectively?

I am trying to solve it using LRU. The solution says that LRU would generate 14 page faults and optimal would generate 10 page fault. However I am getting 10 page fault.

The solution is given below (sorry , I can't understand the solution):

My solution is:

01232304523143263212.

0 0  0     0    4     5       1      4      6   1

   1   1     3    3     3       3     3      3    3

         2    2    2     2       2     2       2    2

My solution is working like optimal solution. Somebody please guide me what is the between optimal and LRU.

Zulfi..

Hi,

I think LRU, looks at the past referenced and replaces the oldest past referenced page whereas optimal looks at the future and replaces the page which is furthest to use.

Please guide me if this answer is correct or not.

Zulfi.

Hi,

Thanks a lot.

Zulfi.

Hi,

I was going through a solution and I found the above question with the answer:

Quote

Recall that paging is implemented by breaking up an address into a page
and offset number. It is most efficient to break the address into X page
bits and Y offset bits, rather than perform arithmetic on the address
to calculate the page number and offset. Because each bit position
represents a power of 2, splitting an address between bits results in
a page size that is a power of 2.

Is there a better answer for this? What I understand is that we are using a binary number system, that's why page sizes should be powers of 2. Somebody please guide me whether I am right or wrong?

Zulfi.

Hi,

I am trying to understand ILP for vertex cover.

I have got following example:

Some body please guide me how we this example is working?

Zulfi.

Hi,

I am trying to understand the FPTAS for the knapsack problem. I have got the following from wikepedia:

I have following questions:

(a)It shows two 2 ‘k’ symbols. I can’t understand the difference between them.

(b)Why its dividing the value  v_i with the value of ‘K’ which is a ratio of P/n multiply by epsilon

(c)what is the significance of Epsilon?

(d)why rounding would convert the problem into a polynomial time problem?

Somebody please guide me.

Zulfi.

Hi,

(1-P^n)/n is the average case.

<

So 1-(0.3)^5 then is the probability having at least one process in a running state and not waiting, hence able to consume CPU.>

I think this is the correct way.

God bless you.

Thanks.

Zulfi.

Hi,

Thanks. For the update otherwise I would be doing it wrongly. I found the formula which I wrote in my  (Question) post from google. But your formula is looking correct also. I have to discuss it with somebody. God bless you.

Zulfi.

Hi,

I am trying to solve the following question:

What is the CPU utilization if there are 5 processes running at the same time, and on average the CPU spends 30% of its time waiting on I/O completion?

The formula is :

Quote

The formula for CPU utilization is 1−pn, in which n is number of process running in memory and p is the average percentage of time processes are waiting for I/O.

What is P in this formula?: 1-P ^n

I found a solution which finds the CPU utilization for each process separately.

Can we do it in the following way:

1- (0.3)^5

= 0.9975

Is the above answer correct?

Somebody please guide me.

Zulfi.

Hi,

I am trying to understand the following text. I can’t understand the term Summation of (j tj). Are we multiplying j and tj. But the text is not talking about multiplying, it says”Total processing time.

Somebody please guide me.

Zulfi.

Hi,

Thanks. Its not "j * tj"

Zulfi.

I got it.

Zulfi.

Hi my friends Ghideon and Strange,

Thanks a lot.

Your efforts helped me to understand the problem specially Strange's figure and Ghideon's calculation.

I did my calculation:

a =0.00795

==

1/7+0.00795=0.15075*6 = 0.9045 (1 bin)

½ +0.00795=0.50795= (6 bins)

1/3+.00795 = 0.3333+.00795= 0.34125 (2 can fit in one  bin) and 6 will require 3 bin. Therefore total is 10 bins.

'a' is not perfect but its almost perfect.

Its now clear to me.

God bless you guys.

Zulfi.

Hi,

Sorry correcting above:

Can't we input only two groups in the above figure? Figure shows that the circuit can only input two groups. How in case of multi-party computation, the circuit uses the two groups to do n * n computation?

Zulfi.

Hi,

Thanks for your response.

Don't we have two groups in multi-party computation? Figure shows that the circuit can only input two groups. How in case of multi-party computation, the circuit uses the two groups to do n * n computation?

Zulfi.

Hi,

I got following text from the paper:

Quote

In secure stable matching, the match list is computed while
keeping the preference lists private to their respective owners.
This problem has been studied in the recent literature [21],
[22] where the secure stable matching problem is reduced to a
two-party secure computation scenario. Each individual XORshares
her preference list and sends it to two non-colluding
servers who perform the secure computation. However, stable
matching is inherently a multi-party problem and the assumption
of two non-colluding servers may not be feasible in
practice. To the best of our knowledge, we provide the first
solution for multi-party secure stable matching.

I can't understand why its multi-party circuit? Its inputting two groups. But how its performing n * n  computation instead of 2 * 2 computation.

Somebody please guide me.

Zulfi

Hi my friend Ghideon,

Quote

1+4+6=10

What you are saying is right but then we have 11m bins required not 10 m as the book says. And how the "simple packing" i.e. optimum requires 6m bins?

Zulfi.

Hi,

I mean greek symbol like E. You can consider 'a' instead of absolon.

Zulfi

Hi,

I am having problem in understanding the following text of the book:

Quote

The input consists of 6m items of size 1/7+ Absolon, followed by 6m items of size 1/3+ Absolon , followed by 6m items of size  1/2 + Absolon. One
simple packing places one item of each size in a bin and requires 6m bins.

If m = 1 then its possible to have 6 bins.

All1/7 elements would go into 1 bin.

All 6*1/3 items would go into 2 bins

All 6 *1/2 items would go into 3 bins.

Total = 6 bins

It further says:

Quote

First fit requires 10m bins.

Why First Fit would require 10 bins. I think First Fit would also require 6 bins.

Somebody please guide me why First Fit would need 10 bins?

Zulfi.

Hi,

Thanks.

The running time is O(n log n) because they are using  segment array whose running time is O(n log n).

I think my answer is correct.

Zulfi.