Uncategorized

String Comparison V

Learning Outcomes
Utilize Java syntax in fundamental programming algorithms (a)
Recognize and apply the various input and output devices in programming (c)
Recognize and apply the various control structures (b)
Recognize an apply the basic debugging strategies in programming (c)
Requirements
With this lab you gain further experience with fundamental Java constructs including variables,
assignment statements, comparing String objects, Scanner class, JOptionPane class.
Preliminaries
0. Create an Eclipse Java project. The name of the project must be lab05_<your
FirstNameLastName>. For example, my project would be named, lab05_PeterNg.
1. Create a class named Order3Strings added to the project
2. Make sure you have a comment block at the beginning of each Java class to containing the following
lines:
/*
* <your name>
* CS 160–02/03/04, Spring 2018 (Note: Write only your section nos.)
* Lab 5
*
*/
Exercise
In this exercise you
solve Programming Challenge 7, p 186 (189 in Edition 5) of your textbook
learn and practice the confirm dialog of the JOptionPane class
learn and practice and additional use of a Scanner object for the sake of splitting texts
Additional requirements are detailed as follows.
1. (2pt) Open a JOptionPane confirm dialog as shown on Figure 1 below. Follow the template
exactly. The syntax is similar to the other dialogs:

JOptionPane.showConfirmDialog(null, <ask for a choice here>,
<title line here>, JOptionPane.YES_NO_OPTION);
Note that by clicking one of the buttons this method returns an integer number which is one of
the two named constants
JOptionPane.YES_OPTION or JOptionPane.NO_OPTION

Tree

For this project, you will perform a series of searches for 1000+ objects stored in a Binary
Search Tree, an AVL Tree, and a Splay Tree. For each search, you will record how many objects
you had to visit to complete the search. You will analyze your results from the different data
structures.
Implement
You should have your 1000+ objects stored in a vector (I recommend you start with your
Project 2 code). Add at least three more dummy objects to the vector. That way, you only
need integer indexes to determine which objects you are searching for, and you will have at
least three objects in the vector that will not be in the tree structures.
Say you have N objects in your vector. You will need to create three les of integers: a sorted
list in range [0, N-1]; a random ordering of the same integers; and a list of integers [0, N/5]
that repeat each integer ve times in a row (i.e. 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 etc.)
Store the objects (excluding the dummy objects you added to the vector) in a Binary Search
Tree, an AVL Tree, and a Splay Tree. I recommend that you start with the textbook code
(http://users.cs.u.edu/~weiss/dsaa_c++4/code/ ). Note that you will need to overload the <,
>, ==, and << operators to compare two objects of your class. You should copy the entire
class from the textbook (don’t cherry pick parts or your program will have memory leaks). Any
code that is not original must be cited in your writeup (including textbook code).
Modify the code so that a search of the tree also stores the depth of the last node visited. I
recommend that you pass the address of an integer to the contains method and modify it
inside the method(s).
Read in from each of the three les, an integer at a time, searching for the object at that
integer index in the vector. Search the BST, the AVL tree, and the Splay tree. Store the depths
of each search.
Analyze the data. Plot graphs of the depths for the 1000+ searches in each of the three tree
structures. Look at maximums, minimums, averages, and patterns, compare and contrast the
different tree structures for each data le, and draw conclusions about when you would use
each tree structure. Discuss complexities and their effects. All of this will go in your writeup.
You must submit your .cpp le(s), your data le(s) (including the three integer les), and your
writeup. Please submit your writeup in PDF format.

RPS and Image Transformations

Rock, Paper, Scissors (30 points)

For the first part of this project, you will be implementing the game of Rock, Paper, Scissors. For those unfamiliar with the rules, typically the game is played with two people who use hand gestures to represent a rock (closed fist), paper (an open hand), or scissor (a vee made with your fingers.) Each person displays their choice at the same time and the winner is determined by (winner in bold):

Scissors cuts paper, paper covers rock, rock breaks scissors

Your job is to write a program where a human can play against the computer in a best-of-5 tournament. The first to win three games wins the match. Have the human player enter their choice, and then have the computer randomly pick its choice. If the two match, the game is a tie and doesn’t count. Otherwise you will add one to the score of the winner. After the match is over, you should ask the user if they would like to play again.

Example:

Welcome to Rock, Paper, Scissors

Would you like to play? yes

What is your choice? scissors
The computer chooses rock. You lose this game!

The score is now you: 0 computer: 1

Hints

  • Generating random numbers in C is a two-step part. First, we need to seed the random number generator onceper program. The idiom to do this is:
    srand((unsigned int)time(NULL));
  • When we need random numbers, we can use the rand() function. It returns an unsigned integer between 0 and RAND_MAX. We can use modulus to reduce it to the range we need:

int value = rand() % (high – low + 1) + low;

Image Transformations (70 points)

A Bitmap Image File (typical extension: .bmp) is a container format for a big array of pixels. There are a variety of ways that BMP files can encode image data, but we will focus on one particular form and write a program that performs two simple image transformations: Inverting the image and Converting a color image to grayscale.

Inverting an image means to take each pixel (a “picture element” – basically one discrete colored point in a larger image) and produce the “opposite” color, which we will define as being the bitwise-NOT of each pixel’s color value.

Converting a color image to grayscale is precisely what it says, we will take the various colors of the image and replace them by differing intensities of the color gray.

We will be assuming Windows Bitmap files whose contents are 24-bit RGB color. This means that each pixel is represented by a 24-bit number, split into three 8-bit parts. The first part is the intensity of the color blue, the second is the intensity of the color green, and the third is the intensity of the color red, each expressed as an integer value from 0-255. (Yes, that’d actually make it BGR and not RGB, but BMP is just weird that way…)

NLP

1
Task: Language Modeling of Different Datasets
Your task is to analyze the similarities and differences in different domains using your language model.
1.1
Data
The data archive (available on Canvas) contains corpus from three different domains, with a train, test, dev, and
readme le for each of them. The domains are summarized below, but feel free to uncompress and examine the
les themselves for more details (will be quite helpful to perform your analysis).
Brown Corpus: Objective of the corpus is to be the standard corpus to represent the present-day (i.e. 1979)
edited American English. More details are available at http://www.hit.uib.no/icame/brown/bcm.html.
Gutenberg Corpus: This corpus contains selection of text from public domain works by authors including Jane
Austen and William Shakespeare (see readme le for the full list). More details about Project Gutenberg is
Reuters Corpus: Collection of nancial news articles that appeared on the Reuters newswire in 1987. The cor-
pus is hosted on the UCI ML repository at https://archive.ics.uci.edu/ml/datasets/Reuters-21578+
1.2
Source Code
I have released some initial source code, available at https://github.com/sameersingh/uci-statnlp/tree/
. The interface and a simple implementation of a language model is available in lm.py , which you
can extend to implement your models. In generator.py , I provide a generic sentence sampler for a language
model. The le data.py contains the main function, that reads in all the train, test, and dev les from the archive,
trains all the unigram models, and computes the perplexity of all the models on each other’s data. The README
le provides a little bit more detail. Of course, feel free to ignore the code if you do not nd it useful.
2
What to Submit?
Prepare and submit a single write-up (PDF, maximum 5 pages) and relevant source code (compressed in a single
zip
or tar.gz le; we will not be compiling or executing it, nor will we be evaluating the quality of the code) to
Canvas. Do not include your student ID number, since we might share it with the class if it’s worth highlighting.
The write-up and code should contain the following.
2.1
Implement a Language Model (20 points)
The primary task of the homework is to implement a non-trivial language model. You are free to pick the type of
the model, such as discriminative
/neural or generative. If you decide to implement an n-gram language model, it
should at least use the previous two words, i.e. a trigram model (with appropriate ltering and smoothing). Your
language model should support “start of sentence”, i.e. when the context is empty or does not have enough tokens.
Use appropriate smoothing to ensure your language model outputs a non-zero and valid probability distribution  

for out-of-vocabulary words as well. In order to make things efcient for evaluation and analysis, it might be
worthwhile to implement serialization of the model to disk, perhaps using pickle .
In the write up, dene and describe the language model in detail (saying “trigram
+laplace smoothing” is not
sufcient). Include any implementation details you think are important (for example, if you implemented your
own sampler, or an efcient smoothing strategy). Also describe what the hyper-parameters of your model are and
how you set them (you should use the dev split of the data if you are going to tune it).
2.2
Analysis on In-Domain Text (40 points)
Here, you will train a model for each of the domains, and anayze only on the text from their respective domains.
Empirical Evaluation: Compute the perplexity of the test set for each of the three domains (the provided
code would do this for you), and compare it to the unigram model. If it is easy to include a baseline version
of your model, for example leaving out some features or using only bigrams, please do so. Provide further
empirical analysis of the performance of your model, such as the performance as hyper-parameters and
/or
amount of training data is varied, or implementing an additional metric.
Qualitative: Show examples of sampled sentences to highlight what your models represent for each domain.
It might be quite illustrative to start with the same prex, and show the different sentences each of them
results in. You may also hand-select, or construct, sentences for each domain, and show how usage of certain
words
/phrases is scored by all of your models (function lm.logprob_sentence() might be useful for this).
2.3
Analysis on Out-of-Domain Text (40 points)
In this part, you have to evaluate your models on text from a domain different from the one it was trained on. For
example, you will be analyzing how a model trained on the Brown corpus performs on the Gutenberg text.
Empirical Evaluation: Include the perplexity of all three of your models on all three domains (a 3 × 3 matrix,
as computed in data.py ). Compare these to the unigram models, and your baselines if any, and discuss
the results (e.g. if unigram outperforms one of your models, why might that happen?). Include additional
graphs
/plots/tables to support your analysis.
Qualitative Analysis: Provide an analysis of the above results. Why do you think certain models
/domains
generalize better to other domains? What might it say about the language used in the domains and their
similarity? Provide graphs, tables, charts, examples, or other summary evidence to support any claims you
make (you can reuse the same tools as the qualitative analysis in § 2.2, or introduce new ones).

GradeCalculator

The main objective in this assignment is to build a small prototype which would be useful in
simulating and testing a partial set of requirements of a fully-featured tool that an instructor
can use to maintain partial grades and compute final grades in a course. Secondly, to give you
practice designing and coding simple classes and methods using loops, conditionals and console
I/O in the Java language. Lastly, to give you an initial exposure to object-oriented techniques to
solve computational problems. To attain these goals, you will organize the programming of this
prototype around the following modular entities:
First, you will write a Java class named Student that allows the creation and maintenance of the
marks, as well as of the final mark, for each student in the course.
Second, you will write a Java class named GradeCalculator which will drive the operational
features of your tool and the text-based console I/O for receiving commands from and issuing
results to a user.
Description
I — User Interface and Program Flow
Upon starting, your tool will display on the console the following menu:
Grade Calculator (Version 0.1). Author: [Your first and last name]
1 – Simulate Course Marks
2 – View/Update Student Marks
3 – Run Mark Statistics
Select Option [1, 2 or 3] (9 to Quit):
Upon completing the processing of any of the operations 1, 2, or 3, your program will return to
display the previous menu and wait for the user to select a menu option. If the user enters 9,
the program terminates.
a) Simulate Course Marks – Selecting this option will run a simulation that creates all the
Student objects for a course of size N students, assigns to each student randomly-generated
marks for assignments 1 and 2, and the final exam. If Student objects from previous course
marks simulations exist when running this simulation, their status attribute will set to false
before creating the Student objects corresponding to the new simulation.
First, the program will prompt the user to enter the class size by displaying the message: Enter
course enrollment size:
Next, the program will issue in sequence the following prompts to the user, asking for weight
percentages within given ranges: Enter weight assignment 1 (20-30):, Enter weight assignment
2 (20-30):, Enter weight final exam (40-60):. If any of the weights is out of range, the program 

will repeat the prompt for the respective weight. If the entered weights do not add up to 100,
the program will display the message << Error: weights do not add up to 100% >>, and will
return to and display the selection menu.
b) View/Update Student Marks – Selecting this option will display the prompt Enter Student
Number:
If the user enters an invalid student number, or the number corresponds to an inactive Student
object (i.e., object’s status attribute is set to false), the program will display the message:
[entered student number] is invalid, and will return to and display the selection menu.
Otherwise, it will display the message: View or Update? (V/U):, and will wait for the user to
enter a selection. If the user enters V, the program will display all the course marks for the
selected student. If the user selects U, the program will display the prompt Mark Type? (A1, A2
or FE): and will wait for a selection from the user. Once the user has input one of the possible
options, the program will display the selected mark as: [Mark Type] is [mark], and will return
to and display the selection menu. If the user enters an invalid mark type, the program will
display the message: [Mark Type] is an invalid mark type, and will return to and display the
selection menu.

web site design

 The detailed functional requirements are listed as follows (basic
requirements):
1.
User can add favorite cat with pictures and description.
2.
User can list all the cats on the web page.
3.
User can search and sort the cats.
4.
User can browse the detailed information for the selected cat.
5.
User can give comments for any cat.
6.
User can give “like” for any cat.
7.
System should give each cat a score based on some kind of
algorithm combining comments and “like”s for each cat.
8.
Administrator can browse the “like” statistics for cats.
9.
Administrator can browse the score statistics for cats.
10.
Administrator have right to remove any cat item from website.
Additional requirements for the coursework:
°
Language: English
°
Use wordpress as opensource platform to build your web application
°
Naming your variables and functions with meaningful identification.
Please analyze above requirements and generate your team’s design
document. Such design document should include at least following
content:
1.
Corresponding Entity-Relationship diagram (including wordpress
original entities);
2.
SQL statements for basic requirements;
3.
Web page navigation diagram;
4.
The skin of your website application (wordpress theme)

C语言

Part 1: Why learn and use C? (25 points)

To start off this assignment, please look into the history of C, the influence it has had on other languages, and some examples of what the language is used for today and then answer the question “Why learn and use C?”. Your answer should be at least 1 paragraph.

There is no “correct” answer to this question. I think that it is an important question to reflect on though when learning any new programming language so that is why I have included it as part of this assignment.

Part 2: Defining the Problem and your Approach Towards Finding a Solution (75 points)

The following is very much a real-world example (though scaled down so that it will be possible for you to complete the assignment in the time that is left in this semester) of a problem that you could solve using C.

The Problem

Given a small database of person accounts (a sqllite3 database – which is written in C itself – that will be provided to you shortly), determine which set of accounts in that database are authorized to access a resource and should therefore be sent to the appropriate destination “system” based on the roles associated with those accounts.

The database will contain person records, roles, resources (i.e. and by resource I mean something that requires a person to have a specific role in order to access it), a mapping of the roles to people, and a mapping of the roles to resources. This should be all of the information that you need in order to programmatically make the determination about which accounts are authorized. I will post an ERD detailing this prior to lab on 11/16.

Each destination “system” that I mentioned will just be a location in local memory (again, for the sake of keeping the scale manageable). When writing to these locations (and I will post more details about the what and how of this piece soon), you will need to allocate memory, write to it, and have a way to maintain it. You should not need these specific implementation details to to come up with a preliminary solution design though.

Designing a Solution

For this part of the assignment, you should not be programming anything. Instead, you should make sure that you understand the functional details of this assignment.

It should also be an opportunity for you to examine your approach to problem solving. The number one reason that I’ve seen students (and even professionals) fail to complete an assignment or task is because they did not understand what the problem was asking and the steps they needed to take in order to solve the problem. If you take the time to document and think about your design and approach, I do not think that you will find yourself in a place where you are unable to complete this assignment.

For this part of the assignment, how you present your design is up to you. A couple of options are to create a process flow diagram or to create a specification document of some kind, such as a scaled down version of a software requirements specification (SRS) document (some things that normally go into an SRS document, just aren’t applicable or aren’t worth spending too much time on because of the limited scale of this assignment. I will post some examples of some documentation that I’ve done to solve problems similar to this one.

Part 3: Writing Pseudo-code (75 points)

Once you have your preliminary design, you should then start to think about specifics of your implementation. Rather than jumping right in and writing C code though, you should first take the intermediate step of writing pseudo-code. I will expect you to turn this in.

When you move on from part 3 to part 4, do not worry about going back and updating your pseudo-code if you find that you’ve deviated from it in your actual code. The pseudo-code is just a stepping stone to help you write the actual code, so I don’t think it is necessary or useful to update it once it is done unless you find that you need to do a massive overhaul of your code and once again use the pseudo-code as your stepping stone.

Part 4: Implementing the Solution (100 points)

I am purposefully holding off on writing anything here. I will post more details here over the weekend. I really strongly recommend that you do these parts in order (at least parts 2-5), so you should not need these details until you’ve completed parts 2 and 3.

Part 5: Testing your Solution (25 points)

spellchecker

This assignment requires you to create four files: SpellChecker.h, SpellChecker.cpp, WordCounts.h
and WordCounts.cpp
. The class definitions should be in the .h files and the implementation of the
methods in the .cpp files. Your main.cpp file should be used to test your implementation of your
classes. You can create a project in CodeBlocks to create the main.cpp file and add the two classes to
the project. CodeBlocks can create projects (use console application template) and will create the .h
and the .cpp files when you add classes to the project. Code Blocks will compile each file for you and
link them into the project executable for testing.
You should
NOT be using the #include
“SpellChecker.cpp”
and #include “WordCounts.cpp” in your main file to include your code
into
main.
1. Once you have your code running on your virtual machine (VM), submit a zip file with
main.cpp, SpellChecker.h, SpellChecker.cpp, WordCounts.h and WordCounts.cpp to the
autograder
COG .
2.
You must also submit your code to Moodle to get full credit for the assignment.
● 10 points: Comments at the top of your source files should include your name,
recitation
TA, and the assignment and problem number.
● 10 points: Algorithm descriptions comments in your code submission to describe
what
your code is doing.
● 10 points: Code in your
main() function that is testing the functions in
SpellChecker.cpp
and WordCounts.cpp. 10 points will be deducted if the
main.cpp you submit to moodle does not have code testing the functions you have
written in
SpellChecker.cpp and WordCounts.cpp. Remember that COG does
not run your
main(), it runs its own main. (Code you write in main() will not
impact
your COG runs).
● NEW starting with this assignment! 10 points: Proper and consistent indentation of
the code. You will have 10 points deducted if the indentation is missing or if the code
in
the files is using an inconsistent style.
Part
I
In this part of the assignment, you are to create a class,
SpellChecker
. You will define some class
data members, member methods and helper functions. The class methods will be used to check the
spelling of words and assess the word count across documents. Elements of this assignment are
intentionally vague; at this point in the semester, you should be able to make your own decisions
about appropriate data structures for storing and looking up data, as well as defining helper
functions. You can assume that your code will never be storing more than 10,000 valid or corrected
words.
SpellChecker
should have at least the following Public members:
● string language
: the name of the language this spell checker is using (i.e. “English”, “Spanish”,
“Italian”,
“Hindi”, …)
SpellChecker
should have at least the following Private members:
● char
start_marker: used for marking the beginning of an unknown word in a string
● char
end_marker: used for marking the end of an unknown word.
SpellChecker
should have three constructors:
● Default
Constructor, the one with no arguments.
● Second
constructor that takes a string for the object’s language
.
● Third constructor that takes a string for the object’s
language and two filenames as
parameters. The first filename specifies the file with correctly spelled words and the second
filename
specifies the misspelled words with their corrections.
You
will be dealing with two different files:
● The
data in the first filename supplies a list of correctly spelled words, one word per line:
● The data in the second filename contains a list of misspelled words and their correct
spellings.
The word and its correction are separated by a tab character (‘\t’):

It is
very important you understand the format of this file. The correctly spelled words may have
spaces
in them! For example a file that converts common texting abbreviations into words:

The constructor with the filename arguments should open the files and read them into an
appropriate data members of the class. To find if a
word is a valid spelling or is a misspelling, you
should
think about storing the words in the right structure so that it’s easy to search and access it.
SpellChecker
should also include the following public methods:
● bool readValidWords(string filename)
: this method should read in a file in exactly the
same way as detailed in the description of the constructor. This file will have the format
specified for correctly spelled words. This method should return a boolean of whether or not
the file was successfully read in. This method should add the words from the file to the list of
words
already contained in the object.
● bool readCorrectedWords(string filename)
:
this method should read in a file in exactly
the same way as detailed in the description of the constructor. The file will have the format
specified for the wrongly spelled words and their corrected spellings. This method should
return a boolean of whether or not the file was successfully read in. This method should add
the
words from the file to the list of words already contained in the object.
● Setters and Getters for the markers to be used for unknown words (see description of
marker
use below).
○ bool
setStartMarker(char begin)
○ bool
setEndMarker(char end)
○ char
getStartMarker()
○ char
getEndMarker()

string repair(string sentence)
: Repair will take in a string of multiple words, strip out all
the punctuation, ignore the case and return the sentence with all misspellings replaced or
marked.
For example: here are what the following calls would return:
If you cannot find a word in the list of valid words or in the list of misspelled words (for
instance, if the word is misspelled beyond recognition), you should just return the misspelled
words with the
start_marker in front and the end_marker at the end. For example: if
start_marker
and end_marker are both ‘~’, the call:
● (Challenge Problem) repairFile(string input_filename, string output_filename)
: Repair
will process all the lines in the input file and write the repaired lines to the output file. The
resulting file would still have all of the punctuation, but with individual words corrected.
One way to break this down into simpler tasks would be to first check each stripped word for
spelling. The second task would be to replace the corrected word within the sentence will all
its
punctuation.
Testing
Testing of your class and all of its methods is now in your hands. You must determine the test cases
that will test if your implementation returns the correct results in all conditions. For example, you
would need to write code that will declare SpellChecker objects with each of the possible
constructors, to verify that each of those methods will create and initialize the object correctly. The
same must be done for each of the other public methods to verify that your implementation works
correctly
in all possible conditions and ordering of calls to those methods.
Once
you are satisfied that your code works as intended, submit it to COG for its evaluation.

Part
II
In this part of the assignment, you are to create a class,
WordCounts
. You will define some class data
members, member methods and helper functions. The class methods will be used keep a running
count of the number of times each word is being used. You can assume that there will never be more
than 10,000 unique words being counted. Your class will provide the following public methods to
support
counting word usage:
● void tallyWords(string sentence):
This function will take in a string of multiple words,
remove the punctuation, and increment the counts for all words in the string. If a word is not
already in the list, add it to the list. This function is used to keep
a running count of each
unique word processed; that means multiple calls to the function should update the count of
the
words, not replace them. If we call the function three times:
The count for the words “the” and “fox” should be 2, the count for the words “brown”, ”red”,
”blue”,
“cat”, and “teh” should be 1.
int getTally (string word)
: return the current count of the given word. If the word is not
found
to be in the current list of words, return 0.
void
resetTally(): reset all word counts to zero.
int mostTimes(string words[], int counts[], int n)
: find the n most common words in
the text that has been counted and return those words and counts in via the arrays given as
parameters.
Assume the arrays are large enough to hold the number of elements requested.
Testing
Testing of your class and all of its methods is now in your hands. You must determine the test cases
that will test if your implementation returns the correct results in all conditions. For example, you
would need to write code that will declare
WordCounts objects with each of the possible
constructors, to verify that each of those methods will create and initialize the object correctly. The
same must be done for each of the other public methods to verify that your implementation works
correctly
in all possible conditions and ordering of calls to those methods.
Once
you are satisfied that your code works as intended, submit it to COG for its evaluation.

Implementation of Monitor

The goal of this problem is to solve an inter-thread communication problem called Sleeping Stylist using semaphores.
There are 40 customers but only 1 stylist in a hair salon. In the salon, there are 5 chairs that customers can sit and
wait for the stylist. Since there is only one stylist, only one customer can get a haircut at a time. If there are no
customers in the salon, the stylist sleeps. When a customer enters the salon, he/she wakes up the stylist and then
waits for the stylist to get ready. The stylist then takes the customer. If the stylist is busy with a customer and more
customers arrive, they sit and wait in the 5 waiting chairs. If a customer enters the salon and it is full (there are
already 5 waiting customers while a customer is getting a haircut), the customer leaves to go shopping and then
comes back later to try to get a haircut again. Every customer must eventually get a haircut (no starvation).
When the stylist nishes with a customer, it takes the next waiting customer. If there are no waiting customers,
the stylist goes back to sleep. The pseudocode is given in Figure 1. Note that the pseudocode only suggests a
guideline. Feel free to add more parameters, variables, and functions as you think necessary.
You will use the pthread package to create 40 customer threads and 1 stylist thread. The program will be
called “sleepingStylistSem.c”. Use a delay loop to slow down each thread (see the pseudocode) by adjusting the
loop bound so that you get a steady stream of customers to compete to get haircuts by the stylist. You want to
ensure that your program can demonstrate its operation when the salon is not full and when the salon is full. Also
make sure that we can see the gradual build up of customers waiting in the chairs. You must complete your
work in csce.unl.edu. Use POSIX semaphore (sem init, sem get, sem post, etc.). Also note that OS-X unlocks
semaphores differently.
3
Sleeping Stylist with Monitor (40 pts)
The goal of this problem is to create your own monitor to provide synchronization support for the sleeping stylist
problem. You will use the pthread package to create 40 customer threads and 1 stylist thread. There are 5 waiting
chairs in the salon. You then need to use a semaphore to create your entry queue.
You also need to create your own Condition Variables (CVs). That is, you CANNOT USE the CV type
provided by the pthread library (e.g., pthread cond init). Condition variables are used to suspend processes or
threads that cannot continue executing due to a specic monitor state (e.g. the stylist is busy). They are also used
to awaken suspended processes or threads when the conditions are satisable. To create your own CVs, follow the
following steps:
1. You will create a new variable type called CV. To do this, you will create a new structure called cond.
The structure consists of an integer variable that indicates the number of threads blocked on a condition
variable and a semaphore used to suspend threads. Your implementation must follow the signal-and-wait
discipline. If your implementation follows a signal-and-continue discipline, you would automatically
lose 20 points. There are three operations that your CV will support. They are:
(a) count(cv)—returns the number of threads blocked on the cv.
(b) wait(cv)— relinquishes exclusive access to the monitor and then suspends the executing threads.
/ ==== s l e e p i n g S t y l i s t S e m . c ====//
# d e f i n e CHAIRS 5
# d e f i n e DELAY 100000 / /
a d j u s t
t h i s
v a l u e
s e m a p h o r e mutex = 1 ,
s t y l i s t = 0 c u s t o m e r s = 0 ;
i n t
w a i t i n g = 0 ;
v o i d main ( v o i d )
{
/ /
c r e a t e 40 c u s t o m e r
t h r e a d s and 1
s t y l i s t
t h r e a d
/ /
don ’ t
f o r g e t
t o
j o i n
t h r e a d s
}
v o i d
s t y l i s t ( v o i d )
{
i n t
j ;
w h i l e ( 1 ) {
down(& c u s t o m e r s ) ;
down(& mutex ) ;
w a i t i n g = w a i t i n g 1 ;
up (& s t y l i s t ) ;
up (& mutex ) ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
c u t
h a i r
}
}
v o i d c u s t o m e r ( v o i d )
{
i n t
j ;
w h i l e ( 1 ) {
down(& mutex ) ;
i f
( w a i t i n g < CHAIRS) {
w a i t i n g = w a i t i n g + 1 ;
up (& c u s t o m e r s ) ;
up (& mutex ) ;
down(& s t y l i s t ) ;
break ;
}
e l s e {
up (& mutex ) ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
go s h o p p i n g
}
}
}
Figure 1: Pseudo-code for the sleeping stylist problem using semaphores
(c) signal(cv)—unblocks one thread suspended at the head of the cv blocking queue. The signaled thread
resumes execution where it was last suspended. The signaler exits the monitor and suspends itself at
the entry queue
.
You should pay special attention to the following questions during your implementation:
(a) How would you guarantee that only one thread is inside the monitor at one time?
(b) How would you make sure that a suspended thread (due to wait) resumes where it left off?
(c) How would you initialize the necessary data structures to support your monitor and make them visible
to all threads?
(d) How would you produce the necessary debugging information that you can use to verify the correctness
of your implementation? For example, what output will you need to show that your implementation
follows the signal-and-wait discipline and not signal-and-continue. How can you show that the num-
ber of waiting threads and the corresponding counter is consistent? How can you show how many
customers have already got their haircuts and how many are still trying? Remember, you’ll need to
convince the grader that your implementation follows our specication precisely.
2. You will create function mon checkCustomer that manages the waiting list and takes a customer to the
styling chair. It rst invokes signal on condition variable stylistAvailable to indicate that the stylist is not
busy. If the salon is empty, it then invokes wait on the condition variable customerAvailable to put the
stylist to sleep.
3. You will create function mon checkStylist that puts a customer on the waiting list if the salon is not
full. If the stylist is sleeping or busy, it rst invokes wait on the condition variable stylistAvailable. It also
invokes signal on condition variable customerAvailable to indicate that a customer is waiting.
4. You will create function customer, stylist, and salonState.
Note that the pseudocode given in Figure 2 provides a guideline on how to program your monitor. However,
this pseudo-code may have incorrect logics. It is part of your responsibility to identify faults and implement a
correctly working monitor.
These functions and your CVs will be implemented in a separate C le. Thus, you should at least have two C
source les, monitor.c and sleepingStylistMon.c. You can compile monitor.c using -c ag (e.g. gcc -c monitor.c).
This will give you the object le (monitor.o) that can be linked to your sleepingStylistMon.c (gcc sleepingStylist-
Mon.c monitor.o). You must complete this part in csce.unl.edu.
4
Submission (10 pts)
Create a zip le that has all your solutions and submit it through canvas. The step to create proper directory
structure is as follows:
1. Create a directory called lastname hw3 (replace lastname with the submitter’s lastname). If you are working
with your partner, only one submission is needed.
2. Create subdirectories: prob1 and prob2 under lastname hw3.
3. Place your solutions in the proper directory. Provide README.txt le for each problem. To earn 10 points,
each README le should:
Provide the name of every member on your team.
Specify the instruction on how to test your solution.
Document the amount of time you spent on each problem.
Quantify the level of challenge from 0 to 5 (5 is most difcult) for each problem.
4. Once all solutions are properly stored, zip the folder lastname hw3 and submit the zip le through canvas.
Note that canvas will only take .zip extension. If you use other means to compress your le, the system will
not accept it. You can use “zip -r” command in csce.unl.edu to zip your folder.
/ / ==== s l e e p i n g S t y l i s t M o n . c ====//
# d e f i n e DELAY 100000 / /
a d j u s t
t h i s
v a l u e
v o i d main ( v o i d )
{
/ /
c r e a t e 40 c u s t o m e r
t h r e a d s and a
s t y l i s t
t h r e a d
/ /
don ’ t
f o r g e t
t o
j o i n
t h r e a d s
}
v o i d s a l o n S t a t e ( v o i d )
/ /
p r i n t how many c u s t o m e r s a r e
w a i t i n g
{
/ /
p r i n t
t h e
s t a t e
o f
t h e
w a i t i n g
c h a i r
u s i n g
t h e
f o l l o w i n g
/ /
f o r m a t :
f i r s t
u s e d
c h a i r :
l a s t
u s e d
c h a i r :
c o u n t
\n .
}
v o i d
s t y l i s t
( v o i d )
{
/ /
add more v a r i a b l e s
a s n e e d e d
i n t
j ;
w h i l e ( 1 ) {
s a l o n S t a t e ( ) ;
m o n c h e c k C u s t o m e r ( ) ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
c u t
h a i r
}
}
v o i d c u s t o m e r ( v o i d )
{
/ /
add more v a r i a b l e s
a s n e e d e d
i n t
j ;
w h i l e ( 1 ) {
s a l o n S t a t e ( ) ;
i f
( m o n c h e c k S t y l i s t ( ) )
break ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
go s h o p p i n g
}
}
/ / ===== m o n i t o r . c ===== / /
# d e f i n e CHAIR 5
c o n d s t y l i s t A v a i l a b l e ,
c u s t o m e r A v a i l a b l e ;
i n t c u s t o m e r = 0 ;
i n t
s t y l i s t = 0 ;
/ /
add more v a r i a b l e s
a s n e c e s s a r y
( e . g . a s e m a p h o r e f o r
e n t r y q u e u e )
v o i d m o n c h e c k C u s t o m e r ( )
{
s t y l i s t = s t y l i s t + 1 ;
s i g n a l ( s t y l i s t A v a i l a b l e ) ;
/ /
s t y l i s t ’ s r e a d y t o
c u t
h a i r
i f
( c u s t o m e r == 0 )
/ /
do n o t u s e w h i l e
h e r e
w a i t ( c u s t o m e r A v a i l a b l e ) ;
c u s t o m e r = c u s t o m e r 1 ;
}
i n t
m o n c h e c k S t y l i s t ( )
/ /
T h i s
f u n c t i o n may h a v e
f a u l t s .
/ /
I f
y o u t h i n k
i t
d o e s ,
y o u ’ l l
n e e d t o
f i x
i t .
{
i n t
s t a t u s = 0 ;
i f
( c u s t o m e r < CHAIRS) {
c u s t o m e r = c u s t o m e r + 1 ;
s i g n a l ( c u s t o m e r A v a i l a b l e ) ;
i f
( s t y l i s t == 0 )
/ /
do n o t u s e w h i l e
h e r e
w a i t ( s t y l i s t A v a i l a b l e ) ;
s t y l i s t = s t y l i s t 1 ;
s t a t u s = 1 ;
}
r e t u r n
s t a t u s

Memory Management

Assignment Deliverables
The deliverables for this assignment are the following files:
proj07.makefile
– the makefile which produces “proj07”
proj07.student.c
– the source code file for your solution
Be sure to use the specified file names and to submit your files for grading via the CSE Handin system before the
project deadline.
Assignment Specifications
The program will simulate some of the steps that an operating system takes to manage a virtual memory system
which uses demand paging and a fixed allocation of page frames. The simulator will gather statistics about the
behavior of a single user process under a given page replacement algorithm.
The system to be simulated contains 1,048,576 bytes of RAM which is divided into 256 page frames. Logical
addresses are 16 bits in length.
1. Your program will process a file which contains the simulation parameters, as well as zero or more memory
references. The first line of the file will contain the page replacement algorithm to be studied (the character string
“FIFO”, “LRU” or “Clock”), and the second line will contain the number of page frames allocated to the process.
Each additional line of the file (if any) will contain the following information about a memory reference:
a) logical address being referenced (4 hexadecimal digits, with leading zeroes)
b) operation being performed (one character; R for read and W for write)
Items within a line will be separated by exactly one space, and each line will terminate with a newline.
2. For each memory reference in the file, your program will display one line with the following information:
a) logical address being referenced (4 hexadecimal digits, with leading zeroes)
b) page number (1 hexadecimal digit)
c) page offset (3 hexadecimal digits, with leading zeroes)
d) operation being performed (one character; R for read and W for write)
e) page fault flag (one character; F for page fault, blank otherwise)
f) write back flag (two characters; WB for write back, blanks otherwise)
g) physical address (5 hexadecimal digits, with leading zeroes)
Items within a line will be separated by exactly one space, and each line will terminate with a newline.
3. After the simulation is completed, your program will display the following:
a) simulation parameters (page replacement algorithm and number of frames allocated)
b) total number of memory references
c) total number of read operations
d) total number of write operations
The summary information will be appropriately labeled and formatted.
4. Your program will display the contents of the page table at the start of the simulation, after every N memory
references, and at the end of the simulation. The page table will not be displayed twice in succession (there must
be some intervening output related to memory references).
The display will contain one line for each page table entry:
a) index of the page table entry (one hexadecimal digit)
b) V bit (one character; 0 for not valid, 1 for valid)
c) R bit (one character; 0 for not referenced, 1 for referenced)
d) M bit (one character; 0 for not modified, 1 for modified)
e) frame number stored in that page table entry (2 hexadecimal digits, with leading zeroes)
Items within a line will be separated by exactly one space, and each line will terminate with a newline. The page
table display will begin and end with a blank line, and will include appropriate column headers.
The value of N will be a positive integer value; any other value (such as 0) will prevent the program from displaying
the contents of the page table.
5. Your program will accept two command-line arguments: an integer representing the value of N and the name
of the input file.
6. The three page replacement algorithms which your program will support are FIFO, LRU and Clock.
For FIFO page replacement, the page which has been in primary storage for the longest time will be selected as the
victim.
For LRU page replacement, the page which has been referenced least recently will be selected as the victim.
For Clock page replacement, your program will use the strategy described in the Stallings textbook.
For all of the page replacement algorithms, your program will use “less than” to break any ties. For example, if
frame 42 and frame 43 are both empty when a page fault occurs, your program will select frame 42.
7. The program will include appropriate error-handling.
Assignment Notes
1. You must use “g++” to translate your source code file in the CSE Linux environment.
2. The page frames allocated to the process being simulated will be consecutive and will begin with frame 20
hexadecimal.