write a C++/Java/Python to solve the following problem: Variation on Scheduling
ID: 3695408 • Letter: W
Question
write a C++/Java/Python to solve the following problem:
Variation on Scheduling Problem(Greedy Algorithm problem):
Cache Optimization problem:
in this problem, we have a fully-way associative cache.
the capacity of this cache is equal to k.we have n read requests from the RAM memory.the order in which these requests are made are given as input.
if the requested data is in the cache, we'll have a cache hit.
if the requested data is not in the cache, we'll have a cache miss; in which case the data is automatically read from the RAM memory and stored onto the cache -->if the cache were to be full, one of the data in the cache would be overritten.
impose that the CPU can only read from the cache, therefore for reading data, the data would have to be stored in the cache, so we are to add the requested data onto the cache memory.
in this problem, we already know all the future requests,its possible that the data at address 17 is only requested once,in which case, bringing the data stored @ address 17 would not be a clever thing to do in real world applications,but in this problem, since the cpu can only read data from the cache, we would have to bring over the data at address 17 over to the cache memory-->in this problem the cpu does not have direct access to the RAM,it has direct access to the cache which has direct access to the RAM. so if we wanted to read something and it wasnt on the cache,it would have to be loaded onto the cache and then onto the cpu.
in this problem,we want you to give two greedy solutions such that:
both of the programs, by getting the size k and the request order as input, would have to specify that in each of the n levels(end of each request),what state the cache would be in.Also, the program
would have to specify how many read requests to the RAM has been made,and the purpose of the program is to decrease the number of read requests from the RAM(one of which is the OPTIMAL SOLUTION).
so i want you to write 2 programs with 2 different greedy approaches to solve the same problem (2 different heuristics), one has to be optimal.
please write what you have taken as your heuristic and explain the algorithm aswell, thanks
the whole point of solving the problem is finding the greedy algorithms(and their heuristics)-->theres only one optimal greedy algorithm, the second one has to be with a heuristic that spits out some sort of answer which is not completely accurate
HINT: This is similar to the activity scheduling problem
at the end, we have to compare the results taken from the 2 programs.
note that you would have to prove formally(on papar or with proper notation) that the program gives the optimal solution.
INPUT/OUTPUT format:
in the first line of input we get k and then we get n.
the next n lines of input are the n requests.
in the output, the first n lines print out the state the cache has at that level --> the state the cache has at the end of the ith request.
on the next line you print out the number of read requests made to the RAM.
NOTE THAT YOUR OUTPUTS MIGHT DIFFER FROM THESE, THESE ARENT NECESSERILY OPTIMAL.=>JUST REMEMBER TO KEEP YOUR INPUT/OUTPUT FORMATS THE SAME
INPUT EXAMPLE 1:
2 7
a b c b c a a
OUTPUT FOR EXAMPLE 1:
a: a
b: a b
c: b c
b: b c
c: b c
a: c a
a: c a
4
INPUT EXAMPLE 2:
2 10
a b c a a c b b b b
OUTPUT FOR EXAMPLE 2:
a: a
b: a b
c: a c
a: a c
a: a c
c: a c
b: c b
b: c b
b: c b
b: c b
4
INPUT EXAMPLE 3:
15 52
A e A A A b b e p p p H A b f A H b e b e A E p e f E E l E Z l l b A p L Y E Y Y Y O e Z Z L Z L Y L l
OUTPUT FOR EXAMPLE 3:
A: A
e: A e
A: A e
A: A e
A: A e
b: A e b
b: A e b
e: A e b
p: A e b p
p: A e b p
p: A e b p
H: A e b p H
A: A e b p H
b: A e b p H
f: A e b p H f
A: A e b p H f
H: A e b p H f
b: A e b p H f
e: A e b p H f
b: A e b p H f
e: A e b p H f
A: A e b p H f
E: A e b p H f E
p: A e b p H f E
e: A e b p H f E
f: A e b p H f E
E: A e b p H f E
E: A e b p H f E
l: A e b p H f E l
E: A e b p H f E l
Z: A e b p H f E l Z
l: A e b p H f E l Z
l: A e b p H f E l Z
b: A e b p H f E l Z
A: A e b p H f E l Z
p: A e b p H f E l Z
L: A e b p H f E l Z L
Y: A e b p H f E l Z L Y
E: A e b p H f E l Z L Y
Y: A e b p H f E l Z L Y
Y: A e b p H f E l Z L Y
Y: A e b p H f E l Z L Y
O: A e b p H f E l Z L Y O
e: A e b p H f E l Z L Y O
Z: A e b p H f E l Z L Y O
Z: A e b p H f E l Z L Y O
L: A e b p H f E l Z L Y O
Z: A e b p H f E l Z L Y O
L: A e b p H f E l Z L Y O
Y: A e b p H f E l Z L Y O
L: A e b p H f E l Z L Y O
l: A e b p H f E l Z L Y O
12
INPUT EXAMPLE 4:
6 41
Y _ v g O v O v b b b E E F L F d F L K K L c r r c r Y r c Y D D o D D U D D o F
OUTPUT FOR EXAMPLE 4:
Y: Y
_: Y _
v: Y _ v
g: Y _ v g
O: Y _ v g O
v: Y _ v g O
O: Y _ v g O
v: Y _ v g O
b: Y _ v g O b
b: Y _ v g O b
b: Y _ v g O b
E: _ v g O b E
E: _ v g O b E
F: v g O b E F
L: v g O b E L
F: v g O b E F
d: v g O b E d
F: g O b E d F
L: g O b E d L
K: g O b E d K
K: g O b E d K
L: O b E d K L
c: b E d K L c
r: b E d K L r
r: b E d K L r
c: b E d K L c
r: b E d K L r
Y: b E d K L Y
r: b E d K L r
c: E d K L r c
Y: d K L r c Y
D: K L r c Y D
D: K L r c Y D
o: K L r c Y o
D: K L r c Y D
D: K L r c Y D
U: K L r c Y U
D: L r c Y U D
D: L r c Y U D
o: r c Y U D o
F: c Y U D o F
30
INPUT EXAMPLE 5:
4 88
l m [ P C O E X Y T l s W v > O s S q o S x e R b G M f H B 1 w d M k E 3 j h 0 m F ` U Q p H B L : m B o > ` y j f y P 1 V n r t j Y 3 f m L v m K O o U 5 B 3 H b ] 9 i ]
OUTPUT FOR EXAMPLE 5:
l: l
m: l m
[: l m [
P: l m [ P
C: l m [ C
O: l [ C O
E: l [ C E
X: l [ C X
Y: [ C X Y
T: [ C X T
l: C X T l
s: X T l s
W: X T l W
v: T l W v
> : T l W >
O: T l W O
s: T l W s
S: l W s S
q: l W s q
o: W s q o
S: W s q S
x: s q S x
e: q S x e
R: S x e R
b: x e R b
G: x e R G
M: e R G M
f: e R G f
H: e R G H
B: e R G B
1: e R G 1
w: e R G w
d: R G w d
M: G w d M
k: w d M k
E: d M k E
3: M k E 3
j: M k E j
h: M k E h
0: k E h 0
m: E h 0 m
F: E h 0 F
`: h 0 F `
U: h 0 F U
Q: h 0 F Q
p: 0 F Q p
H: F Q p H
B: F Q p B
L: F Q p L
:: F Q p :
m: Q p : m
B: Q p : B
o: Q p : o
> : Q p : >
`: p : > `
y: : > ` y
j: : > ` j
f: : > ` f
y: : > ` y
P: > ` y P
1: ` y P 1
: y P 1
: y P 1
V: P 1 V
n: 1 V n
r: V n r
t: V n r t
j: n r t j
Y: r t j Y
3: t j Y 3
f: t j Y f
m: j Y f m
L: j Y f L
v: Y f L v
m: f L v m
K: L v m K
O: v m K O
o: m K O o
U: K O o U
5: O o U 5
B: o U 5 B
3: U 5 B 3
H: 5 B 3 H
b: B 3 H b
]: 3 H b ]
9: 3 H b 9
i: H b 9 i
]: b 9 i ]
87
INPUT EXAMPLE 6:
9 27
2 c w M = X y = [ ^ N A w p v P x y k @ Q 3 s X ^ = Q
OUTPUT FOR EXAMPLE 6:
2: 2
c: 2 c
w: 2 c w
M: 2 c w M
=: 2 c w M =
X: 2 c w M = X
y: 2 c w M = X y
=: 2 c w M = X y
[: 2 c w M = X y [
^: 2 c w M = X y [ ^
N: 2 c w M X y [ ^ N
A: 2 c w M X y [ N A
w: 2 c w M X y [ N A
p: 2 c w M y [ N A p
v: 2 c w M [ N A p v
P: c w M [ N A p v P
x: w M [ N A p v P x
y: M [ N A p v P x y
k: [ N A p v P x y k
@: N A p v P x y k @
Q: A p v P x y k @ Q
3: A p v P x y k @ 3
s: p v P x y k @ 3 s
X: v P x y k @ 3 s X
^: P x y k @ 3 s X ^
=: x y k @ 3 s X ^ =
Q: y k @ 3 s X ^ = Q
25
INPUT EXAMPLE 7:
3 47
3 V S x e 0 H U [ ? ? M 6 @ H 9 N ; h 0 P x G Z 7 ] 4 I S q w ] 9 B 2 ` A U 2 S 2 B G W O U G
OUTPUT FOR EXAMPLE 7:
3: 3
V: 3 V
S: 3 V S
x: 3 V x
e: 3 V e
0: V e 0
H: V e H
U: V e U
[: V e [
?: e [ ?
?: e [ ?
M: [ ? M
6: ? M 6
@: M 6 @
H: 6 @ H
9: @ H 9
N: @ H N
;: H N ;
h: N ; h
0: ; h 0
P: h 0 P
x: 0 P x
G: P x G
Z: P x Z
7: x Z 7
]: Z 7 ]
4: Z 7 4
I: 7 4 I
S: 4 I S
q: 4 I q
w: I q w
]: q w ]
9: w ] 9
B: ] 9 B
2: ] 9 2
`: ] 9 `
A: 9 ` A
U: ` A U
2: ` A 2
S: ` A S
2: A S 2
B: S 2 B
G: 2 B G
W: 2 B W
O: B W O
U: W O U
G: O U G
46
INPUT EXAMPLE 8:
8 33
S o C J t W l J J ` t Q W X o Z X u L I O n L n ] i l u G l l k b
OUTPUT FOR EXAMPLE 8:
S: S
o: S o
C: S o C
J: S o C J
t: S o C J t
W: S o C J t W
l: S o C J t W l
J: S o C J t W l
J: S o C J t W l
`: S o C J t W l `
t: S o C J t W l `
Q: S o C J t W ` Q
W: S o C J t W ` Q
X: S C J t W ` Q X
o: S C J t W ` Q o
Z: C J t W ` Q o Z
X: J t W ` Q o Z X
u: t W ` Q o Z X u
L: t W ` Q o Z X L
I: t W ` Q o Z X I
O: W ` Q o Z X I O
n: ` Q o Z X I O n
L: ` Q o Z X I O L
n: Q o Z X I O L n
]: o Z X I O L n ]
i: Z X I O L n ] i
l: X I O L n ] i l
u: X I O L n ] i u
G: I O L n ] i u G
l: O L n ] i u G l
l: O L n ] i u G l
k: L n ] i u G l k
b: n ] i u G l k b
28
Explanation / Answer
import java.util.Scanner; // importing scanner class to read the data
public class HelloWorld{
public static void main(String []args){
System.out.println("Hello World");
Scanner sc=new Scanner(System.in);
System.out.println("Enter k cache capacity followed by n requests with space : ");
String line=sc.nextLine(); // reading k and n - aline from console
String[] larray=line.split(" "); // splitting string to read with spaces
int k=Integer.parseInt(larray[0]); // converting string to int
int n=Integer.parseInt(larray[1]);
String[] cache=new String[k]; // allocating cache memory with size k
for(int m=0;m<k;m++)
cache[m]="null"; // cache assing with null string
System.out.println("Enter "+n+" requests");
line=sc.nextLine();
String[] req=line.split(" "); // splitting requests to check with cache memory- array
int exists=0,write=0;
int temp=0;int c=0,read=0;
for(int i=0;i<n;i++)
{
System.out.print(req[i]+":");
for(int j=0;j<k;j++)
{
if(cache[j].equals(req[i])) // checking the request exists in cache memory or not
{
exists++;
}
}
if(exists==0)
{
for(int t=0;t<k;t++)
{
if(cache[t].equals("null"))
{
write++;
temp=t;
cache[temp]=req[i]; // fetching request from ram if not exists
read++;
for(int b=0;b<k;b++)
System.out.print(cache[b]+" ");
t=k;
}
else if(write==0 && t==k-1)
{
cache[0]=req[i]; // overriding a process
for(int b=0;b<k;b++)
System.out.print(cache[b]+" ");
read++;
c++;
}
}
}
else
{
for(int a=0;a<k;a++)
System.out.print(cache[a]+" ");
}
System.out.println();
}
System.out.println(read);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.