Question
In: Computer Science
Implement the MSI cache coherence protocol in your favorite programming language (C, C++, Java, python, etc.)....
Implement the MSI cache coherence protocol in your favorite programming language (C, C++, Java, python, etc.). Wikipedia has a nice high level description of the protocol. Consider only one level of cache which is a write back cache. Moreover, assume that there are 4 processing cores working on a single shared memory. To simplify, assume that you are writing the code for only one block of cache and that block can hold 4 different memory locations.
Solutions
Expert Solution
MSI cache coherence protocol - Using C++
Code:
#include <stdlib.h>
#include <assert.h>
#include <fstream>
#include <sstream>
#include <string>
#include <istream>
#include <vector>
#include <iomanip>
#include "cache.h"
using namespace std;
void MSI(vector <Cache*> cacheArray, int proc_num, ulong address, char op, int num_proc)
{
//For NULL State
if (cacheArray[proc_num]->findLine(address) == NULL)
{ //PrRd --- For Read : NULL ---> SHARED | FOR Write : NULL ---> MODIFIED
if (op == 'r')
{
cacheArray[proc_num]->Access(address, op);
//cacheArray[proc_num]->num_of_mem_trans++;
cacheArray[proc_num]->findLine(address)->setFlags(SHARED);
//Generate BusRD to turn modified to shared
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
if ((cacheArray[i]->findLine(address))->getFlags() == MODIFIED)
{
cacheArray[i]->num_of_flushes++;
cacheArray[i]->writeBack(address);
cacheArray[i]->num_of_interventions++;
//cacheArray[i]->num_of_mem_trans++;
(cacheArray[i]->findLine(address))->setFlags(SHARED);
}
}
}
return;
}
else
{ //NULL ---> Modified
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
//cacheArray[proc_num]->num_of_mem_trans++;
//Generates BusRDx to invalidate other caches
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
if((cacheArray[i]->findLine(address)->getFlags())==MODIFIED)
{
//cacheArray[i]->num_of_mem_trans++;
}
(cacheArray[i]->findLine(address))->invalidate();
cacheArray[i]->num_of_invalidations++;
cacheArray[i]->num_of_flushes++;
cacheArray[i]->writeBack(address);
//cacheArray[i]->num_of_mem_trans++;
}
}
return;
}
}
//For INVALID State
if ((cacheArray[proc_num]->findLine(address))->getFlags() == INVALID)
{ //PrRd --- For Read : INVALID ---> SHARED | FOR Write : INVALID ---> MODIFIED
if (op == 'r')
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(SHARED);
//cacheArray[proc_num]->num_of_mem_trans++;
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
if ((cacheArray[i]->findLine(address))->getFlags() == MODIFIED)
{
cacheArray[i]->num_of_flushes++;
cacheArray[i]->writeBack(address);
cacheArray[i]->num_of_interventions++;
//cacheArray[i]->num_of_mem_trans++;
(cacheArray[i]->findLine(address))->setFlags(SHARED);
}
//(cacheArray[i]->findLine(address))->setFlags(SHARED);
}
}
return;
}
else
{ //Invalid ---> Modified
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
//cacheArray[proc_num]->num_of_mem_trans++;
//Generates BusRDx to invalidate other caches
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
if((cacheArray[i]->findLine(address)->getFlags())==MODIFIED)
{
//cacheArray[i]->num_of_mem_trans++;
}
(cacheArray[i]->findLine(address))->invalidate();
cacheArray[i]->num_of_invalidations++;
}
}
return;
}
}
//For SHARED State
if ((cacheArray[proc_num]->findLine(address))->getFlags() == SHARED)
{
/*READ*/
if (op == 'r')
{
cacheArray[proc_num]->Access(address, op);
return;
}
/*WRITE*/
else
{ //Shared ----> Modified
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
cacheArray[proc_num]->num_of_mem_trans++;
//Generates BusRDx to invalidate other caches
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
if((cacheArray[i]->findLine(address)->getFlags())!=INVALID)
{
cacheArray[i]->num_of_invalidations++;
(cacheArray[i]->findLine(address))->invalidate();
}
}
}
return;
}
}
//For MODIFIED State
if ((cacheArray[proc_num]->findLine(address))->getFlags() == MODIFIED)
{
if (op == 'r')
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
return;
}
else
{
cacheArray[proc_num]->Access(address, op);
//cacheArray[proc_num]->num_of_mem_trans++;
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
return;
}
}
return;
}
void MESI(vector <Cache*> cacheArray, int proc_num, ulong address, char op, int num_proc)
{
//For INVALID State
if (cacheArray[proc_num]->findLine(address) == NULL)
{ //PrRd --- For Read(C) : INVALID ---> SHARED | For Read(!C) : INVALID ---> EXCLUSIVE | FOR Write : INVALID ---> MODIFIED
bool C = false;
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
C = true;
}
}
if (op == 'r')
{
if (C == true)
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(SHARED);
//Cache to Cache Transfer when Line exists in another processor and State INVALID-->SHARED
cacheArray[proc_num]->num_of_cache_to_cache_transfer++;
//Generate BusRD to turn modified to shared
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
if ((cacheArray[i]->findLine(address))->getFlags() == MODIFIED)
{
cacheArray[i]->num_of_interventions++;
cacheArray[i]->num_of_flushes++;
cacheArray[i]->writeBack(address);
//cacheArray[proc_num]->num_of_chache_to_cache_transfer++;
}
else if ((cacheArray[i]->findLine(address))->getFlags() == EXCLUSIVE)
{
cacheArray[i]->num_of_interventions++;
//cacheArray[proc_num]->num_of_chache_to_cache_transfer++;
}
(cacheArray[i]->findLine(address))->setFlags(SHARED);
}
}
}
else
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(EXCLUSIVE);
}
return;
}
else
{ //Invalid ---> Modified
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
//Generates BusRDx to invalidate other caches
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
if ((cacheArray[i]->findLine(address))->getFlags() == SHARED)
{
cacheArray[i]->num_of_invalidations++;
cacheArray[proc_num]->num_of_cache_to_cache_transfer++;
}
else if ((cacheArray[i]->findLine(address))->getFlags() == MODIFIED)
{
cacheArray[i]->num_of_flushes++;
cacheArray[i]->writeBack(address);
cacheArray[i]->num_of_invalidations++;
cacheArray[proc_num]->num_of_cache_to_cache_transfer++;
}
else
{
cacheArray[i]->num_of_invalidations++;
}
(cacheArray[i]->findLine(address))->invalidate();
}
}
return;
}
}
//For Exclusive State
if ((cacheArray[proc_num]->findLine(address))->getFlags() == EXCLUSIVE)
{ //PrRd --- For Read : EXCLUSIVE ---> EXCLUSIVE | FOR Write : EXCLUSIVE ---> MODIFIED
if (op == 'r')
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(EXCLUSIVE);
return;
}
else
{ //EXCLUSIVE ---> MODIFIED
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
return;
}
}
//For SHARED State
if ((cacheArray[proc_num]->findLine(address))->getFlags() == SHARED)
{
/*READ*/
if (op == 'r')
{
cacheArray[proc_num]->Access(address, op);
return;
}
/*WRITE*/
else
{ //Shared ----> Modified
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
//Generates BusUPGR to invalidate other caches
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
if ((cacheArray[i]->findLine(address))->getFlags() == SHARED)
{
cacheArray[i]->num_of_invalidations++;
//cacheArray[i]->num_of_chache_to_cache_transfer++;
}
else
{
cacheArray[i]->num_of_invalidations++;
}
(cacheArray[i]->findLine(address))->invalidate();
}
}
return;
}
}
//For MODIFIED State
if ((cacheArray[proc_num]->findLine(address))->getFlags() == MODIFIED)
{
if (op == 'r')
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
return;
}
else
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
return;
}
}
return;
}
void DRAGON(vector <Cache*> cacheArray, int proc_num, ulong address, char op, int num_proc)
{
// state: null, Sc, Sm, E, Modified
// test if any copy exists
bool C = false;
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL && cacheArray[i]->findLine(address)->getFlags() != INVALID)
{
C = true;
}
}
// state null, read: null -> SharedClean(C), Exclusive(!C) write: null -> SharedWrite(C), Modified(!C)
if(cacheArray[proc_num]->findLine(address) == NULL || cacheArray[proc_num]->findLine(address)->getFlags() == INVALID)
{
if(op=='r')
{
cacheArray[proc_num]->Access(address, op);
if(C==true)
{
(cacheArray[proc_num]->findLine(address))->setFlags(SHARED_CLEAN);
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL && cacheArray[i]->findLine(address)->getFlags() != INVALID)
{
if ((cacheArray[i]->findLine(address))->getFlags() == MODIFIED)
{
cacheArray[i]->num_of_interventions++;
cacheArray[i]->num_of_flushes++;
cacheArray[i]->writeBack(address); // write back
(cacheArray[i]->findLine(address))->setFlags(SHARED_MODIFIED);
continue;
}
if ((cacheArray[i]->findLine(address))->getFlags() == EXCLUSIVE)
{
cacheArray[i]->num_of_interventions++;
(cacheArray[i]->findLine(address))->setFlags(SHARED_CLEAN);
}
if ((cacheArray[i]->findLine(address))->getFlags() == SHARED_MODIFIED)
{
cacheArray[i]->num_of_flushes++; // snoop a busRd, flush, according to FSM
cacheArray[i]->writeBack(address); // write back
}
}
}
}
else
{
// no copy, set exclusive
//cacheArray[proc_num]->num_of_mem_trans++;
(cacheArray[proc_num]->findLine(address))->setFlags(EXCLUSIVE);
}
return;
}
else
{
// now it's write
cacheArray[proc_num]->Access(address, op);
if(C==true)
{
(cacheArray[proc_num]->findLine(address))->setFlags(SHARED_MODIFIED);
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL && cacheArray[i]->findLine(address)->getFlags() != INVALID)
{
if ((cacheArray[i]->findLine(address))->getFlags() == MODIFIED)
{
cacheArray[i]->num_of_interventions++;
cacheArray[i]->num_of_flushes++;
cacheArray[i]->writeBack(address); // write back
}
if ((cacheArray[i]->findLine(address))->getFlags() == EXCLUSIVE)
{
cacheArray[i]->num_of_interventions++;
//cacheArray[i]->writeBack(address);
}
if((cacheArray[i]->findLine(address))->getFlags() == SHARED_MODIFIED)
{
cacheArray[i]->num_of_flushes++;
cacheArray[i]->writeBack(address); // write back
}
(cacheArray[i]->findLine(address))->setFlags(SHARED_CLEAN);
}
}
}
else
{
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
}
return;
}
}
// for EXCLUSIVE state
if ((cacheArray[proc_num]->findLine(address))->getFlags() == EXCLUSIVE)
{ //PrRd --- For Read : EXCLUSIVE ---> EXCLUSIVE | FOR Write : EXCLUSIVE ---> MODIFIED
if(op=='r')
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(EXCLUSIVE);
return;
}
else
{ //EXCLUSIVE ---> MODIFIED
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
return;
}
}
// for MODIFIED state, no state change and no bus transaction
if ((cacheArray[proc_num]->findLine(address))->getFlags() == MODIFIED)
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
return;
}
// for SHARED_CLEAN state
if ((cacheArray[proc_num]->findLine(address))->getFlags() == SHARED_CLEAN)
{
if(op=='r')
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(SHARED_CLEAN);
}
else
{
cacheArray[proc_num]->Access(address, op);
//cacheArray[proc_num]->num_of_flushes++;
if(C==true)
{
(cacheArray[proc_num]->findLine(address))->setFlags(SHARED_MODIFIED);
}
else
{
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
}
for (int i = 0; i<num_proc; i++)
{
if (i != proc_num && cacheArray[i]->findLine(address) != NULL)
{
// change SHARED_MODIFIED state to SHARED_CLEAN if any
if((cacheArray[i]->findLine(address))->getFlags() == SHARED_MODIFIED)
{
(cacheArray[i]->findLine(address))->setFlags(SHARED_CLEAN);
//cacheArray[proc_num]->num_of_flushes++;
//cacheArray[i]->writeBack(address); // write backs
}
}
}
}
return;
}
// for SHARED_MODIFIED state
if ((cacheArray[proc_num]->findLine(address))->getFlags() == SHARED_MODIFIED)
{
if(op=='r')
{
cacheArray[proc_num]->Access(address, op);
(cacheArray[proc_num]->findLine(address))->setFlags(SHARED_MODIFIED);
}
else
{
cacheArray[proc_num]->Access(address, op);
if(C==true)
{
// when write to it and there are other copies, stay the state unchanged
(cacheArray[proc_num]->findLine(address))->setFlags(SHARED_MODIFIED);
}
else
{
// otherwise, change to MODIFIED
(cacheArray[proc_num]->findLine(address))->setFlags(MODIFIED);
}
//cacheArray[proc_num]->writeBack(address); // write back
}
}
return;
}
int main(int argc, char *argv[])
{
ifstream fin;
FILE * pFile;
int pro;
uchar op;
uint addr;
if(argv[1] == NULL){
printf("input format: ");
printf("./smp_cache <cache_size> <assoc> <block_size> <num_processors> <protocol> <trace_file> \n");
exit(0);
}
/*****uncomment the next five lines****/
int cache_size = atoi(argv[1]);
int cache_assoc= atoi(argv[2]);
int blk_size = atoi(argv[3]);
int num_processors = atoi(argv[4]);/*1, 2, 4, 8*/
int protocol = atoi(argv[5]); /*0:MSI, 1:MESI, 2:Dragon*/
char *fname = (char *)malloc(20);
fname = argv[6];
vector <Cache*> cacheArray;
for (int i = 0; i< num_processors; i++)
{
Cache* c = new Cache(cache_size, cache_assoc, blk_size);
cacheArray.push_back(c);
}
//****************************************************//
//**printf("===== Simulator configuration =====\n");**//
//*******print out simulator configuration here*******//
//****************************************************//
//*********************************************//
//*****create an array of caches here**********//
//*********************************************//
pFile = fopen(fname,"r");
if(pFile == 0)
{
printf("Trace file problem\n");
exit(0);
}
if(protocol==0)
{
goto MSI;
}
if(protocol==1)
{
goto MESI;
}
if(protocol==2)
{
goto DRAGON;
}
MSI:
while(!feof(pFile))
{
fscanf(pFile,"%d %c %x\n",&pro,&op,&addr);
MSI(cacheArray, pro, addr, op, num_processors);
}
///******************************************************************//
//**read trace file,line by line,each(processor#,operation,address)**//
//*****propagate each request down through memory hierarchy**********//
//*****by calling cacheArray[processor#]->Access(...)***************//
///******************************************************************//
fclose(pFile);
//********************************//
//print out all caches' statistics //
//********************************//
goto RESULT;
MESI:
while(!feof(pFile))
{
fscanf(pFile,"%d %c %x\n",&pro,&op,&addr);
MESI(cacheArray, pro, addr, op, num_processors);
}
fclose(pFile);
goto RESULT1;
DRAGON:
while(!feof(pFile))
{
fscanf(pFile,"%d %c %x\n",&pro,&op,&addr);
DRAGON(cacheArray, pro, addr, op, num_processors);
}
fclose(pFile);
goto RESULT2;
RESULT: // give the final output of MSI
for (int i = 0; i<num_processors; i++)
{
cout << "============ Simulation results (Cache " << i << ") ============" << endl;
cout << "01. number of reads: " << cacheArray[i]->getReads() << endl;
cout << "02. number of read misses: " << cacheArray[i]->getRM() << endl;
cout << "03. number of writes: " << cacheArray[i]->getWrites() << endl;
cout << "04. number of write misses: " << cacheArray[i]->getWM() << endl;
cout << "05. total miss rate: " << fixed << setprecision(2)<< (cacheArray[i]->getWM()+cacheArray[i]->getRM()) * 100.0 / (cacheArray[i]->getReads()+cacheArray[i]->getWrites())<< '%' << endl;
cout << "06. number of write backs: " << cacheArray[i]->getWB() << endl;
cout << "07. number of cache to cache transfers: " << cacheArray[i]->num_of_cache_to_cache_transfer << endl;
cout << "08. number of memory transactions: " << cacheArray[i]->num_of_mem_trans+cacheArray[i]->getRM()+cacheArray[i]->getWM()+cacheArray[i]->getWB()<< endl;
cout << "09. number of interventions: " << cacheArray[i]->num_of_interventions << endl;
cout << "10. number of invalidations: " << cacheArray[i]->num_of_invalidations << endl;
cout << "11. number of flushes: " << cacheArray[i]->num_of_flushes << endl;
}
return 0;
RESULT1: // give the final result of MESI
for (int i = 0; i<num_processors; i++)
{
cout << "============ Simulation results (Cache " << i << ") ============" << endl;
cout << "01. number of reads: " << cacheArray[i]->getReads() << endl;
cout << "02. number of read misses: " << cacheArray[i]->getRM() << endl;
cout << "03. number of writes: " << cacheArray[i]->getWrites() << endl;
cout << "04. number of write misses: " << cacheArray[i]->getWM() << endl;
cout << "05. total miss rate: " << fixed << setprecision(2)<< (cacheArray[i]->getWM()+cacheArray[i]->getRM()) * 100.0 / (cacheArray[i]->getReads()+cacheArray[i]->getWrites())<< '%' << endl;
cout << "06. number of write backs: " << cacheArray[i]->getWB() << endl;
cout << "07. number of cache to cache transfers: " << cacheArray[i]->num_of_cache_to_cache_transfer << endl;
cout << "08. number of memory transactions: " << cacheArray[i]->getWM() + cacheArray[i]->getRM() + cacheArray[i]->getWB() - cacheArray[i]->num_of_cache_to_cache_transfer << endl;
cout << "09. number of interventions: " << cacheArray[i]->num_of_interventions << endl;
cout << "10. number of invalidations: " << cacheArray[i]->num_of_invalidations << endl;
cout << "11. number of flushes: " << cacheArray[i]->num_of_flushes << endl;
}
return 0;
RESULT2: // give the final result of DRAGON
for (int i = 0; i<num_processors; i++)
{
cout << "============ Simulation results (Cache " << i << ") ============" << endl;
cout << "01. number of reads: " << cacheArray[i]->getReads() << endl;
cout << "02. number of read misses: " << cacheArray[i]->getRM() << endl;
cout << "03. number of writes: " << cacheArray[i]->getWrites() << endl;
cout << "04. number of write misses: " << cacheArray[i]->getWM() << endl;
cout << "05. total miss rate: " << fixed << setprecision(2)<< (cacheArray[i]->getWM()+cacheArray[i]->getRM()) * 100.0 / (cacheArray[i]->getReads()+cacheArray[i]->getWrites())<< '%' << endl;
cout << "06. number of write backs: " << cacheArray[i]->getWB() << endl;
cout << "07. number of cache to cache transfers: " << cacheArray[i]->num_of_cache_to_cache_transfer << endl;
cout << "08. number of memory transactions: " << cacheArray[i]->getWM() + cacheArray[i]->getRM() + cacheArray[i]->getWB()+cacheArray[i]->num_of_flushes<< endl;
cout << "09. number of interventions: " << cacheArray[i]->num_of_interventions << endl;
cout << "10. number of invalidations: " << cacheArray[i]->num_of_invalidations << endl;
cout << "11. number of flushes: " << cacheArray[i]->num_of_flushes << endl;
}
return 0;
}
Note: If you have any related doubts, queries, feel free to ask by commenting down below.
And if my answer suffice your requirements, then kindly upvote.
Happy Learning
venereology answered 5 months agoRelated Solutions
(20 pts) Using your programming language of choice (from C++, Java, or Python) , also drawing...
(20 pts) Using your programming language of choice (from C++,
Java, or Python) , also drawing on your experience from program 1,
read an integer, n from keyboard
(standard input). This integer represents the number of integers
under consideration. After reading that initial integer in, read
n integers in, and print the minimum and maximum
of all the integers that are read in.
Example:
Input
Output
7
1 5 3 6 9 22 2
Min: 1
Max: 22
C++ preferred
How would you design a cache coherence with only MS, not MSI. How do you manage...
How would you design a cache coherence with only MS, not MSI.
How do you manage the new protocol?
Draw the new MS protocol. For each state, show all the relevant
transitions.
In the new MSI protocol, when does a memory read occur? Specify
the bus transaction, the requestor's start and end states, and the
states of the other caches if relevant.
In the new MSI protocol, when does a memory write occur? Specify
the bus transaction and the requestor's...
In the C programming language, implement the translation from regular English to Euroglish. If the letters...
In the C programming language, implement the translation
from regular English to Euroglish. If the letters were uppercase,
keep them uppercase in the replacement.
1. Remove one“e”from the end of words that are more than three
characters long, if they happen to end in “e”.
2. Change all double letters to a single letter (including
double spaces). Do not remove double line spacing (i.e. “\n”).
3. When a word ends in “ed”, change that to just “d”.
Text:
The cat...
Java, Python, and C++ are three of the most useful programming languages to learn. Compare the...
Java, Python, and C++ are three of the most useful programming
languages to learn. Compare the functionalities of all three
programming languages. Why would you choose one language over
another? Provide code examples demonstrating their usefulness in a
real-world scenario.
Description: In this assignment, you will implement a deterministic finite automata (DFA) using C++ programming language...
Description:
In this assignment, you will implement a deterministic finite
automata (DFA) using C++ programming language to extract all
matching patterns (substrings) from a given input DNA sequence
string.
The alphabet for generating DNA sequences is {A, T, G, C}.
Write a regular expression that represents all DNA strings
that begin with ‘A’ and end with ‘T’. Note: assume empty
string is not a valid string.
Design a deterministic finite automaton to recognize the
regular expression.
Write a program which...
Kindly Do the program in C++ language Object Oriented Programming. Objectives Implement a simple class...
Kindly Do the program in C++ language Object Oriented
Programming.
Objectives
Implement a simple class with public and private members and
multiple
constructors.
Gain a better understanding of the building and using of classes
and objects.
Practice problem solving using OOP.
Overview
You will implement a date and day of week calculator for the
SELECTED calendar year.
The calculator repeatedly reads in three numbers from the standard
input that are
interpreted as month, day of month, days...
Programming language: JAVA First, implement a recursive, Divide&Conquer-based algorithm to identify both the Minimum and Maximum...
Programming language: JAVA
First, implement a recursive, Divide&Conquer-based algorithm
to identify both the Minimum and Maximum element in an unsorted
list.
Second, convert your recursive algorithm to a non-recursive (or
iterative) implementation. For your input, populate an "unsorted
list" with random elements between 1 and 1,000,000.
C Programming Language (Code With C Programming Language) Problem Title : Which Pawn? Jojo is playing...
C Programming Language (Code With C Programming
Language)
Problem Title : Which Pawn?
Jojo is playing chess himself to practice his abilities. The
chess that Jojo played was N × N. When Jojo was practicing, Jojo
suddenly saw a position on his chessboard that was so interesting
that Jojo tried to put the pieces of Rook, Bishop and Knight in
that position. Every time he put a piece, Jojo counts how
many other pieces on the chessboard can be captured...
Answer the following in Java programming language Create a Java Program that will import a file...
Answer the following in Java programming language
Create a Java Program that will import a file of contacts
(contacts.txt) into a database (Just their first name and 10-digit
phone number). The database should use the following class to
represent each entry:
public class contact {
String firstName;
String phoneNum;
}
Furthermore, your program should have two classes.
(1) DatabaseDirectory.java:
This class should declare ArrayList as a private
datafield to store objects into the database (theDatabase) with the...
The programming language is Python Instructions: Create a function that will delete a node in a...
The programming language is Python
Instructions:
Create a function that will delete a node in a Linked List based
on position number. On below example, if you want to delete
position #2, it will remove the Banana
(arrangement of nodes below is Apple, Banana, Cherry, Grapes,
Orange).
myLinkedList = LinkedList()
myLinkedList.append("Banana")
myLinkedList.append("Cherry")
myLinkedList.append("Grapes")
myLinkedList.append("Orange")
myLinkedList.prepend("Apple")
myLinkedList.deleteByPositionNum(2)
node = myLinkedList.head
while node:
print(node.value, " ")
node = node.next_node
You may start with the function head:
def deleteByPositionNum(self, positionNum):
ADVERTISEMENT
ADVERTISEMENT
Latest Questions
- Is offering GED classes or English as a second language classes to parent a good idea?
- In his Treatise on Money (1930) John Maynard Keynes adopted definitions of saving and investment which...
- The current overnight loans rate is 3 percent, with the Bank of Canada's operating band set...
- Two methanol–water mixtures are contained in separate flasks. The first mixture contains 40.0 wt% methanol, and...
- Had Geely done enough to improve the long-term prospects of Volvo?
- Contrast formal and informal communication.
- Use Statistical Tables to test for serial correlation given the following Durbin-Watson d statistics for serial...
ADVERTISEMENT