problem17
.pdf
keyboard_arrow_up
School
University of Colorado, Denver *
*We aren’t endorsed by this school
Course
6040
Subject
Computer Science
Date
Apr 28, 2024
Type
Pages
25
Uploaded by hhfehiiue on coursehero.com
4/26/24, 11:09 PM
problem17
file:///Users/mingjingyang/Desktop/OMSA/6040/cse6040-pfx/problem17/problem17.html
1/25
Problem 17: Spectral graph partitioning
Version 1.3
Changelog:
1.3: Added another more informative error message. [Dec 5, 2019]
1.2: Added more hints and more informative error messages. [Dec 3, 2019]
1.1: Added more examples; no changes to code or test cells. [Dec 2, 2019]
1.0: Initial version
In this problem, you'll consider the data mining task of "clustering" a graph. That is, given a graph or network of
relationships, can you identify distinct communities within it? This problem assesses your Pandas and Numpy
skills.
Exercises.
There are six exercises, numbered 0-5, worth a total of ten (10) points. However, only Exercises 0-4
require you to write code. If you have done them correctly, then Exercise 5, which consists only of a hidden test
cell, should pass when submitted to the autograder.
Regarding dependencies and partial credit:
Exercise 1 (1 points) depends on a correct Exercise 0 (2 points).
Exercises 2 (2 points) and 3 (2 points) are independent. Neither depends on Exercises 0 or 1.
Exercise 4 (2 points) relies on all earlier exercises.
Exercise 5 (1 point) depends on Exercise 4.
As always
, it is possible that you will pass Exercises 0-4 but not pass Exercise 5 if there is a subtle bug that the
test cells happen not to catch, so be prepared for that possibility!
Setup
The main modules you'll need are pandas
, numpy
, and scipy
. The rest are auxiliary functions for loading data,
plotting results, and test code support. Start by running the following cell.
4/26/24, 11:09 PM
problem17
file:///Users/mingjingyang/Desktop/OMSA/6040/cse6040-pfx/problem17/problem17.html
2/25
In [1]:
# Main modules you'll need:
import
numpy
as
np
import
scipy
as
sp
import
pandas
as
pd
from
pandas
import
DataFrame
# Support code for data loading, code testing, and visualization:
import
sys
sys.path.insert(0, 'resource/asnlib/public')
from
cse6040utils
import
tibbles_are_equivalent, pandas_df_to_markdown
_table, hidden_cell_template_msg, cspy
from
matplotlib.pyplot
import
figure, subplots
%
matplotlib
inline
from
networkx.convert_matrix
import
from_pandas_edgelist
from
networkx.drawing.nx_pylab
import
draw
from
networkx
import
DiGraph
from
networkx.drawing
import
circular_layout
# Location of input data:
def
dataset_path(base_filename):
return
f"resource/asnlib/publicdata/
{base_filename}
"
Background: Relationship networks and partitioning
Suppose we have data on the following five people, stored in the nodes
data frame (run the next cell):
In [2]:
nodes = DataFrame({'name': ['alice', 'bob', 'carol', 'dave', 'edith'],
'age': [35, 18, 27, 57, 41]})
nodes
Also suppose we have some information on their relationships, as might be captured in a social network or
database of person-to-person transactions. In particular, if some person follows another person , we say is
the source
and is the target
. For the people listed above, suppose these relationships are stored in a data
frame named edges
(run this code cell):
Out[2]:
name age
0
alice
35
1
bob
18
2
carol
27
3
dave
57
4
edith
41
4/26/24, 11:09 PM
problem17
file:///Users/mingjingyang/Desktop/OMSA/6040/cse6040-pfx/problem17/problem17.html
3/25
In [3]:
edges = DataFrame({'source': ['alice', 'alice', 'dave', 'dave', 'dav
e', 'bob'],
'target': ['dave', 'edith', 'alice', 'edith', 'car
ol', 'carol']})
edges
We can visualize these relationships as a directed graph
or directed network
, where the people are shown as
nodes
(circles) and the follows-relationships are shown as edges from source to target. Run the next code cell
to see the relationships in our example.
In [4]:
G = from_pandas_edgelist(edges, source='source', target='target', crea
te_using=DiGraph())
figure(figsize=(4, 4))
draw(G, arrows=
True
, with_labels=
True
, pos=circular_layout(G),
node_size=1200, node_color=
None
, font_color='w',
width=2, arrowsize=20)
Out[3]:
source target
0
alice
dave
1
alice
edith
2
dave
alice
3
dave
edith
4
dave
carol
5
bob
carol
4/26/24, 11:09 PM
problem17
file:///Users/mingjingyang/Desktop/OMSA/6040/cse6040-pfx/problem17/problem17.html
4/25
Observation 0:
From the edges
data frame, recall that alice
follows edith
; therefore, there is an arrow (or
edge) pointing from alice
to edith
. Since alice
and dave
both follow one another, there is a double-headed
arrow between them.
Observation 1:
One can arguably say there are two distinct "groups" in this picture. One group consists of
alice
, dave
, and edith
, who have at least 1 one-way follow-relationships among all pairs of them. Similarly,
bob
and carol
have a one-way relationship between them. However, there is only one relationship between
someone from the first group and someone from the second group.
In this problem, we might ask a data mining question, namely, whether we can automatically identify these
clusters or groups, given only the known relationships. The method you will implement is known as spectral
graph partitioning
or spectral graph clustering
, which is formulated as a linear algebra problem.
Exercises
Exercise 0
(2 points -- 0.5 exposed, 1.5 hidden). For our analysis, we won't care whether follows or follows , only that there is some interaction between them. To do so, let's write some code to "symmetrize" the
edges. That is, if there is a directed edge from node to node , then symmetrize will ensure there is also a
directed edge to , unless one already exists. (
Recall Notebook 10!
)
For example, a symmetrized version of the edges
data frame from above would look like the following:
source target
alice
dave
alice
edith
bob
carol
carol
bob
carol
dave
dave
alice
dave
carol
dave
edith
edith
alice
edith
dave
Complete the function, symmetrize_df(edges)
, below, so that it symmetrizes edges
. Assume that edges
is
a pandas DataFrame
with source
and target
columns. Your function should return a new pandas
DataFrame
with the edges symmetrized. Your function should also reset the index, so that the output is a
proper "tibble."
4/26/24, 11:09 PM
problem17
file:///Users/mingjingyang/Desktop/OMSA/6040/cse6040-pfx/problem17/problem17.html
5/25
Note 0:
The order of the edges in the output does not
matter.
Note 1:
You may assume the input data frame has columns named 'source'
and 'target'
.
Note 2:
You should drop any duplicate edges. In the example, the edges 'dave'
'alice'
and 'alice'
'dave'
already exist in the input. Therefore, observe that they appear in the
output, but only once each.
Note 3:
Your function should work even if there is a "self-edge," i.e., an edge . The
example above does not contain such a case, but the hidden test might check it.
In [5]:
def
symmetrize_df(edges):
assert
'source' in
edges.columns
assert
'target' in
edges.columns
### BEGIN SOLUTION
from
pandas
import
concat
edges_transpose = edges.rename(columns={'source': 'target', 'targe
t': 'source'})
edges_all = concat([edges, edges_transpose], sort=
False
) \
.drop_duplicates() \
.reset_index(drop=
True
)
return
edges_all
### END SOLUTION
# Demo of your function:
symmetrize_df(edges)
Out[5]:
source target
0
alice
dave
1
alice
edith
2
dave
alice
3
dave
edith
4
dave
carol
5
bob
carol
6
edith
alice
7
edith
dave
8
carol
dave
9
carol
bob
4/26/24, 11:09 PM
problem17
file:///Users/mingjingyang/Desktop/OMSA/6040/cse6040-pfx/problem17/problem17.html
6/25
In [6]:
# Test cell: `ex0_symmetrize_df__visible` (1 point)
edges_input = DataFrame({'source': ['alice', 'alice', 'dave', 'dave', 'dave', 'bob'],
'target': ['dave', 'edith', 'alice', 'edit
h', 'carol', 'carol']})
edges_output = symmetrize_df(edges_input)
# The following comment block suggests there is hidden content in this cell, but there really isn't.
### BEGIN HIDDEN TESTS
from
os.path
import
isfile
if
not
isfile(dataset_path('symmetrize_soln.csv')):
symmetrize_df_soln0__ = edges_output.sample(frac=1) \
.sort_values(by=['source', 'ta
rget'])
print(pandas_df_to_markdown_table(symmetrize_df_soln0__))
symmetrize_df_soln0__.to_csv(dataset_path('symmetrize_soln.csv'), index=
False
)
### END HIDDEN TESTS
edges_output_soln = pd.read_csv(dataset_path('symmetrize_soln.csv'))
assert
tibbles_are_equivalent(edges_output, edges_output_soln), \
"Your solution does not produce the expected output."
print("
\n
(Passed.)")
(Passed.)
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Related Questions
On a 32-bit processor, a baggy bounds scheme is expected to set all of the bounds table entries to 31 at initialization time. Assume that a buggy implementation with a slot size of 32 bytes performs bounds table initialization inappropriately, resulting in random entries being incorrectly set to 1.
Assume that a networked server processes network messages using an uninstrumented library. Assume that this library does not include some buffer overflow bugs (i.e., it never calls unsafe functions such as gets()).
However, the server suffers from the above-mentioned bounds table initialization issue, and an attacker may submit messages to the server that force the library to dynamically assign and write memory in an attacker-controlled amount using uninstrumented code that looks like this:
/ N is the size of the buffer that the intruder gets to choose.for (int I = 0; I N/4; i++, p += 4)
char *p = malloc(N);
*p = 'a';
*(p+1) = 'b';
*(p+2) = 'c';
*(p+3) = 'd';
Assume the server is using a…
arrow_forward
Using the following page replacement algorithms, determine the number of faults in the following reference string given a physical memory size of 4 frames:
5 6 5 4 4 4 8 2 9 9 0 4 5 3 9 6 8 1 9 1 6 1 0 0 5
Replacement algorithm
3 frames
FIFO
OPT
LRU
LFU
MFU
arrow_forward
a) Consider the following page reference string: 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6
a) A paging scheme with THREE (3) frames initially empty are considered. Trace the allocationof pages to frames and determine the number of page faults occur using the First-in-First-out(FIFO) page replacement algorithm.
b) Assume a system is able to support up to 2,000 users. Suggest a UNIX protection schemewhich allows access to a single file named “MPX.pdf” for 1,990 users. How would you treatthe remaining 10 users who shall not be given access to the file?
arrow_forward
Consider the following code snippet in C:
char *base_url = malloc(11 * sizeof(char));
printf("Enter an 11 character URL: ");
scanf("%s", base_url);
char src[11];
char dst[11];
// copies base_url to src
strncpy(src, base_url, 11);
// copies src to dest
strcpy(dst, src);
printf("src: %s dst: %s\n", src, dst);
Identify at least one potential buffer overflow vulnerability and explain why/how it can be exploited (i.e., not just that it’s a buffer overflow, but where the problem will manifest itself).
arrow_forward
Using the following page replacement algorithms, determine the number of faults in the following reference string given a physical memory size of 4 frames:
5 6 5 4 4 4 8 2 9 9 0 4 5 3 9 6 8 1 9 1 6 1 0 0 5
OPT. 3 frames
arrow_forward
Consider the following page reference string:
7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1.
Assuming pure demand paging with three frames (3 pages can be in memory at a time).
a)Using FIFO replacement algorithm, show the content of the memory (which pages are in memory) for each page reference.
b) How many page faults resulted from this algorithm?
c) Repeat a) and b)above with LRU algorithm.
arrow_forward
5.03-1. Dijkstra's Algorithm (3, part 1). Consider the network shown below, and Dijkstra’s link-state algorithm. Here, we are interested in computing the least cost path from node E (note: the start node here is E) to all other nodes using Dijkstra's algorithm. Using the algorithm statement used in the textbook and its visual representation, complete the "Step 0" row in the table below showing the link state algorithm’s execution by matching the table entries (i), (ii), (iii), and (iv) with their values.
arrow_forward
Consider the bitmap representation of the free-space map, where for eachblock in the file, two bits are maintained in the bitmap. If the block is between0 and 30 percent full the bits are 00, between 30 and 60 percent the bits are01, between 60 and 90 percent the bits are 10, and above 90 percent the bitsare 11. Such bitmaps can be kept in memory even for quite large files. Outline the benefit of the bitmap technique over free lists in searching for free space and in updating free space information.
arrow_forward
Consider the following page reference string:2 4 2 8 5 4 3 7 5 2 8 4 6 8 3Assume that FOUR (4) frames are initially empty in the memory. Perform the page faults trace analysis to determine the number of page faults that will occur for each of the following page replacement algorithms.
(i) First-In-First-Out (FIFO), Least-Recently-Used (LRU) and Optimal Page Replacement
arrow_forward
question 3 : With the same physical memory and the same initial page assignments as in question 1, how many page faults will occur If Optimal page replacement is used ? Assume the reference string (RS) is the same 0172327103?
Time t
0
1
2
3
4
5
6
7
8
9
10
RS
0
1
7
2
3
2
7
1
0
3
Frame 0
0
Frame 1
1
Frame 2
2
Frame 3
3
please find the below question 1 for reference as stated in question 3 above and please answer question 3 accordingly:
question 1 : The physical memory consists of 4 frames: 0 through 3. Initially, the frames contain the pages 0 through 3 (as shown at time 0). If FIFO page replacement is used, how many page faults will occur with the reference string (RS) 0172327103?
arrow_forward
Suppose that a disk drive has 5,000 cylinders, numbered 0 to 4,999. The drive is currently serving a request at cylinder 2,150, and the previous request was at cylinder 1,805. The queue of pending requests, in FIFO order, is:2,069 1,2122,2962,8005441,6183561,5234,9653681a. FCFSb. SSTFc. SCANd. LOOKe. C-SCANf. C-LOOK
arrow_forward
1(c) What is the best-case time complexity for inserting n items into a hash table of size m? When willthe performance of an open addressing hash table degrade no matter what collision resolutionscheme is used?
arrow_forward
Consider the following page address stream:
2 1 4 3 5 3 2 4 5 2 1 2 4 3 1
Which of the following causes the most page faults to occur on a machine with 3 frames?
Scheme that causes the most faults:
a) First in First out
b) LRU and FIFO are the same number of faults
c) FIFO and Opitimal are the same number of faults
d) All have the same number of faults
e) Least Recently Used
f) No faults occurs
g) LRU and Optimal are the same number of faults
h) Optimal
NUMBER OF FAULTS CAUSED:
a)
arrow_forward
Implement c/c++ to evaluate round robin algorithm with i/o burst.I want my code to able to read csv. The link is to my csv file https://jpst.it/2IURz. The code must also have input for quantum time.
The code must contain this following:(i) Turnaround time of the jobs;(ii) Waiting time of the jobs; and(iii) Number of interrupts incurred
arrow_forward
Q 1
Computer Science
Theory and Fundamentals of Operating Systems:
Reference String: 7,6,8,2,6,3,6,4,2,3,6,3,2,8,2,6,8,7,6,8
How many page faults will occur if the program has three page-frames available to it and use Optimal replacement?
arrow_forward
Consider the following page reference string for a 12-page executable. 0,1,1,3,4,10,5,2,2,10,6,6,10,11,7,8,7,9,9,6,5,11,9,11How many page faults would occur for the following replacement algorithms, assuming one, two, and four frames?Remember that all frames are initially empty, so your first unique pages will cost one fault each.a. LRU replacementb. FIFO replacementc. Optimal replacement
arrow_forward
1. Which algorithm chooses the page that has not been used for the longest period of time whenever the page required to be replaced?
a.)Optimal
b.)LRU
c.)Second chance
d.)Clock
2. In memory management with valid–invalid bit, the valid bit indicates that the page is:
a.) illegal access.
b.)not in memory
c.)in memory.
d.)not legal.
arrow_forward
“Dirty bit is used to reduce the overhead of page transfer”. Statewhether the given statement is true or false. Justify your answer withsuitable example.
arrow_forward
5.14. SDN implementation of Dijkstra’s algorithm. Consider the implementation of Dijkstra’s algorithm in an SDN framework. Which of the following statements are true? (Hint: more than one statement is true.)
Group of answer choices
a. When executing, Dijkstra’s algorithm will need to send messages to all of the routers to gather their link costs.
b. When executing, Dijkstra’s algorithm will use the link-state database that is maintained within the SDN controller.
c. When executing, Dijkstra’s algorithm will execute within the operating system of the SDN controller
d. When executing, Dijkstra’s algorithm will run as a network control application “on top” on the SDN controller.
e. If a router’s forwarding table should be changed as a result of running Dijkstra’s algorithm, the new flow table for that router will be updated by the SDN controller via the southbound API using the Openflow protocol.
f. If a router’s forwarding table should be changed as a result of running Dijkstra’s…
arrow_forward
Suppose that a disk drive has 5,000 cylinders, numbered 0 to 4,999. The drive is currently serving a request at cylinder 2,150, and the previous request was at cylinder 1,805. The queue of pending requests, in FIFO order, is: 2,069, 1,212, 2,296, 2,800, 544, 1,618, 356, 1,523, 4,965, 3681 Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests for each of the following disk- scheduling algorithms?
e. C-SCAN
f. C-LOOK
arrow_forward
5.01-3. Dijkstra's Algorithm (1, part 3). Consider the network shown below, and Dijkstra’s link-state algorithm to find the least cost path from source node U to all other destinations. Using the algorithm statement and its visual representation used in the textbook,complete the third row in the table below showing the link state algorithm’s execution by matching the table entries (a), (b), (c), (d) and (e) with their values
arrow_forward
Consider the following page reference string: 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 What are the last pages in main memory in their order, and how many page faults would occur for the following page replacement algorithms? Assuming 4 frames.
A) FIFO
B) Optimal
C) LRU
arrow_forward
Use C, C++, python or matlab to develop a program whose main routine accepts two parameters n and k, i.e. when you invoke your program from the shell, you pass it two parameters, n and k, where n >=16 and k >=8and is in powers of 2 (e.g. 8, 16, 32, etc.). Your main routine shall generate a random page trace of length n, where the page numbers have values ranging from 0 to ? − 1. Develop a subroutine within your program that implements the FIFO page replacement algorithm (as a separate function within your program). The function shall accept a page trace and a parameter f for the number of frames allocated. Your main routine shall then apply the random page trace to the subroutine implementing the page replacement algorithm, multiple times (using only one trace, randomly generated), passing a parameter f (number of page frames used) that ranges from 4 to k. Your main routine shall then record the number of page faults for each run (i.e. for each f).Run your program using a page…
arrow_forward
A computer uses virtual memory, and a new solid-state drive (SSD) as space for paging. Refer to the last ppt file. In the case presented there, the hard disk drive (HDD) required 25 ms to read in a page, and a rate of 1 page fault per 1000 references introduced a 250 slowdown. If the SSD offers a time of only 80 µs, what is the slowdown in performance caused by 1 pf per 1000 references (you are not concerned with dirty vs. clean pages). What is the maximum rate of page faults you can accept if you want no more than a 5% slowdown in execution using virtual memory? Know your metric prefixes and symbols for time: s for seconds, ms for milliseconds, µs for microseconds, ns for nanoseconds.
arrow_forward
Write OPT Page Replacement Algorithm In C
The user of your program should be able to:
Specify a data file of page requests using a command line argument.
Specify the size of the resident set (number of frames) using a command line argument.
Specify the number of pages in the program using a command line argument.
Simulate the running of each page replacement algorithm and determine the number of page faults.
arrow_forward
SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education
Related Questions
- On a 32-bit processor, a baggy bounds scheme is expected to set all of the bounds table entries to 31 at initialization time. Assume that a buggy implementation with a slot size of 32 bytes performs bounds table initialization inappropriately, resulting in random entries being incorrectly set to 1. Assume that a networked server processes network messages using an uninstrumented library. Assume that this library does not include some buffer overflow bugs (i.e., it never calls unsafe functions such as gets()). However, the server suffers from the above-mentioned bounds table initialization issue, and an attacker may submit messages to the server that force the library to dynamically assign and write memory in an attacker-controlled amount using uninstrumented code that looks like this: / N is the size of the buffer that the intruder gets to choose.for (int I = 0; I N/4; i++, p += 4) char *p = malloc(N); *p = 'a'; *(p+1) = 'b'; *(p+2) = 'c'; *(p+3) = 'd'; Assume the server is using a…arrow_forwardUsing the following page replacement algorithms, determine the number of faults in the following reference string given a physical memory size of 4 frames: 5 6 5 4 4 4 8 2 9 9 0 4 5 3 9 6 8 1 9 1 6 1 0 0 5 Replacement algorithm 3 frames FIFO OPT LRU LFU MFUarrow_forwarda) Consider the following page reference string: 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6 a) A paging scheme with THREE (3) frames initially empty are considered. Trace the allocationof pages to frames and determine the number of page faults occur using the First-in-First-out(FIFO) page replacement algorithm. b) Assume a system is able to support up to 2,000 users. Suggest a UNIX protection schemewhich allows access to a single file named “MPX.pdf” for 1,990 users. How would you treatthe remaining 10 users who shall not be given access to the file?arrow_forward
- Consider the following code snippet in C: char *base_url = malloc(11 * sizeof(char)); printf("Enter an 11 character URL: "); scanf("%s", base_url); char src[11]; char dst[11]; // copies base_url to src strncpy(src, base_url, 11); // copies src to dest strcpy(dst, src); printf("src: %s dst: %s\n", src, dst); Identify at least one potential buffer overflow vulnerability and explain why/how it can be exploited (i.e., not just that it’s a buffer overflow, but where the problem will manifest itself).arrow_forwardUsing the following page replacement algorithms, determine the number of faults in the following reference string given a physical memory size of 4 frames: 5 6 5 4 4 4 8 2 9 9 0 4 5 3 9 6 8 1 9 1 6 1 0 0 5 OPT. 3 framesarrow_forwardConsider the following page reference string: 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1. Assuming pure demand paging with three frames (3 pages can be in memory at a time). a)Using FIFO replacement algorithm, show the content of the memory (which pages are in memory) for each page reference. b) How many page faults resulted from this algorithm? c) Repeat a) and b)above with LRU algorithm.arrow_forward
- 5.03-1. Dijkstra's Algorithm (3, part 1). Consider the network shown below, and Dijkstra’s link-state algorithm. Here, we are interested in computing the least cost path from node E (note: the start node here is E) to all other nodes using Dijkstra's algorithm. Using the algorithm statement used in the textbook and its visual representation, complete the "Step 0" row in the table below showing the link state algorithm’s execution by matching the table entries (i), (ii), (iii), and (iv) with their values.arrow_forwardConsider the bitmap representation of the free-space map, where for eachblock in the file, two bits are maintained in the bitmap. If the block is between0 and 30 percent full the bits are 00, between 30 and 60 percent the bits are01, between 60 and 90 percent the bits are 10, and above 90 percent the bitsare 11. Such bitmaps can be kept in memory even for quite large files. Outline the benefit of the bitmap technique over free lists in searching for free space and in updating free space information.arrow_forwardConsider the following page reference string:2 4 2 8 5 4 3 7 5 2 8 4 6 8 3Assume that FOUR (4) frames are initially empty in the memory. Perform the page faults trace analysis to determine the number of page faults that will occur for each of the following page replacement algorithms. (i) First-In-First-Out (FIFO), Least-Recently-Used (LRU) and Optimal Page Replacementarrow_forward
- question 3 : With the same physical memory and the same initial page assignments as in question 1, how many page faults will occur If Optimal page replacement is used ? Assume the reference string (RS) is the same 0172327103? Time t 0 1 2 3 4 5 6 7 8 9 10 RS 0 1 7 2 3 2 7 1 0 3 Frame 0 0 Frame 1 1 Frame 2 2 Frame 3 3 please find the below question 1 for reference as stated in question 3 above and please answer question 3 accordingly: question 1 : The physical memory consists of 4 frames: 0 through 3. Initially, the frames contain the pages 0 through 3 (as shown at time 0). If FIFO page replacement is used, how many page faults will occur with the reference string (RS) 0172327103?arrow_forwardSuppose that a disk drive has 5,000 cylinders, numbered 0 to 4,999. The drive is currently serving a request at cylinder 2,150, and the previous request was at cylinder 1,805. The queue of pending requests, in FIFO order, is:2,069 1,2122,2962,8005441,6183561,5234,9653681a. FCFSb. SSTFc. SCANd. LOOKe. C-SCANf. C-LOOKarrow_forward1(c) What is the best-case time complexity for inserting n items into a hash table of size m? When willthe performance of an open addressing hash table degrade no matter what collision resolutionscheme is used?arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education