程序代写｜MPCS 52060 – Parallel Programming documentation Homework #5

Getting started

For each assignment, a Git repository will be created for you on GitHub. However, before that repository can be created for you, you need to have a GitHub account. If you do not yet have one, you can get an account here: https://github.com/join (https://github.com/join).

To actually get your private repository, you will need this invitation URL:

`HW5 invitation is posted on ED`__

When you click on an invitation URL, you will have to complete the following steps:

Make sure you’ve set up SSH access (https://docs.github.com/en/github/authenticating-to-github/connecting-to-github-with-ssh) on your GitHub account.

For each repository, you will need to get the SSH URL of the repository. To get this URL, log into GitHub and navigate to your project repository (take into account that you will have a di”erent repository per project).

Then, click on the green “Code” button, and make sure the “SSH” tab is selected. Your repository URL should look something like this: git@github.com (mailto:git%40github.com):mpcs52060-spr22/hw5-GITHUB

USERNAME.git.

If you do not know how to use git clone to clone your repository then follow this guide that Github pro

vides: Cloning a Repository (https://docs.github.com/en/github/creating-cloning-and-archiving-reposito

ries/cloning-a-repository)

Short Answer Questions

You have no short answer questions for this homework assignment.

Programming Questions

For this assignment you are only allowed to use the following Go concurrent constructs:

go statement

sync.Mutex and its associated methods.

sync/atomic package. You may use any of the atomic operations.

If you are unsure about whether you are able to use a language feature then please ask on Ed before using it.

Individual Assignment

The challenging part of this assignment is that you are working alone without the help of Professor Samuels or the course sta”. You have enough practice and knowledge to be able to complete this speci!c assignment by yourselves. Professor

Samuels and the course sta! will not help debug or provide advice about your potential solution or “xes to it.

However, we will clarify anything about the speci!cation, tests cases, or conceptually about the algorithm that you will implement for the assignment. You may post those types of questions on Ed and/or come to o#ce hours to ask questions. Again we will not be looking at code or providing advice on possible solutions. You’ll need to do this on your own.

Concurrent Set

For this assignment, you will implement a concurrent hash set using linear probing. The implementation will implement the following Set interface:

type Set interface {

Add(item string) bool

Remove(item string) bool

Contains(item string) bool

Size() int

}

To keep the implementation simple, the set will only contain string values. The Add method adds values to the set. A set cannot contain duplicates so do not add an already existing item to the set. Add returns true if it was successful in adding the item; otherwise it returns false . Remove removes a string from the set if it exists. If Remove was able to remove the given string then it returns true ; otherwise it returns false . The Contains method returns true if the given string is in the set; otherwise it returns false . The Size method returns how many string values are inside the set.

You must use the following hash function that is de!ned inside the hw5/set/set.go :

//hash is an implementation of the djb2 algorithm by Dan Bernstein

func hash(str string) int {

hash := 5381

for _, char := range str {

hash = ((hash << 5) + hash) + int(char) /* hash * 33 + c */

}

return hash

}

To convert each string into its hash value. Make sure to still mod the hash value by the current table size.

Inside hw5/set/set.go !le, there is a constructor function for creating a set. The only argument is the initial capacity

for the set:

func NewSet(capacity int) Set {

//Return a pointer to a set value.

return nil

}

A hash set built on linear probing does not have unlimited capacity, since each bucket can only contain a single value and there are a !xed number of buckets. But, we do not want to have to anticipate how many buckets might be used for a given hash set in advance and hard-code that number in for the capacity of the hash set. Therefore, we will take the following approach: the bucket capacity passed into the constructor will represent the initial size of the table. If the fraction of occupied bucket grows beyond 75% (i.e., num_occupied_buckets/capacity > 0.75 ) after an update, then we will perform an operation called rehashing: We will expand the size of our hash set, and migrate all the data into their proper locations in the newly-expanded table (i.e., each item is hashed again, with the hash function now considering the new size of the table). We will grow the size of the table by 2 ; for instance, if the initial capacity is 2 , then the size of the hash set will double to a new capacity of 4 .

Recall from lecture, that each bucket has an h value that represents the range of items that were displaced from their original bucket location. For example, assume “a” , “b” , “c” , “d” all collide at bucket index 18 (i.e., they all hash to index 18 ) then the implementation must place 3 of them in adjacent cells and h represents the furthest item away from the original hash location of 18 . One thing to know is that linear probing is cyclic. This means that if the table has a capacity of 20 then once probing gets to the end of the table it wraps around to beginning of the table (i.e., index 0 ) and continues to linear probe from that location. Keep this in mind when thinking about your linear probing implementation.

Deleting an item in a hash set that uses linear probing is tricky. One way to handle this is to use a lazy deletion technique.

We will “logically” delete the items. This means that you should have a marker for each bucket that indicates whether or not it’s item has been deleted. If the marker is true then the item is still inside the table; otherwise a false marker says that the items was deleted at some point. You must only “physically” remove (i.e., actually delete from the data structure) the items that have been “logically” removed during rehashing. You are not required to implement remove using a logical deletion approach. You can decide how to handle deletion in your implementation. However, it may make concurrent implementations easier to logically implement.

I recommend that you de!ne your own bucket type:

type bucket struct {

// Define your fields

}

for your implementation and you can de!ne the table using a slice (e.g., []bucket ).

The next section explains how to implement the concurrent set.

Problem: Choose your own adventure

For this assignment, you can choose how to implement the concurrent set using linear probing based on choosing between two algorithms:

Implement your implementation inside hw5/set/set.go . You can test your implementation using the set_test.go!le.

Programming assignments will be graded according to a general rubric. Speci!cally, we will assign points for complete ness, correctness, design, and style. (For more details on the categories, see our Assignment Rubric page (../index.html).)

The exact weights for each category will vary from one assignment to another. For this assignment, the weights will be:

Completeness: 60%

Correctness: 30%

Design & Style: 10%

Obtaining your test score

The completeness part of your score will be determined using automated tests. To get your score for the automated tests, simply run the following from the Terminal. (Remember to leave out the $ prompt when you type the command.)

$ cd grader

$ go run hw5/grader hw5

This should print total score after running all test cases inside the individual problems. This printout will not show the tests you failed. You must run the problem’s individual test !le to see the failures.

Design, Style and Cleaning up

Before you submit your !nal solution, you should, remove any Printf statements that you added for debugging purposes and all in-line comments of the form: “YOUR CODE HERE” and “TODO …”

Think about your function decomposition. No code duplication. This homework assignment is relatively small so this shouldn’t be a major problem but could be in certain problems.

Go does not have a strict style guide. However, use your best judgment from prior programming experience about style.

Did you use good variable names? Do you have any lines that are too long, etc.

As you clean up, you should periodically save your !le and run your code through the tests to make sure that you have not broken it in the process.

Submission

Before submitting, make sure you’ve added, committed, and pushed all your code to GitHub. You must submit your !nal work through Gradescope (linked from our Canvas site) in the “Homework #5” assignment page via two ways,