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 4th Edition. I am able to understand the above but I can't understand the following: I can’t understand the following stuff: 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: 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: 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 : 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: 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, 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: 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: 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.