Monthly Archives: June 2019

Homework | Assignment | data mining| python – CSCI 1100 Computer Science 1

Homework | Assignment | data mining| python – 这是一个比较典型的数据挖掘的题目任务

CSCI 1100 Computer Science 1 homework 8

CS1 Multiverse: Classes

Overview

The goal of this assignment is to work with classes. You will be asked to write a simulation engine and use classes to encapsulate data and functionality. You will have a lot of design choices to make.

While we have done simulations before, this one will be more complex. It is especially important that you start slowly, build a program that works for simple cases, test it and then add more complexity. We will give lots of partial credit even if you do not get all the answers right. We will provide test cases of increasing difficulty. Make sure you develop slowly and test throughly.

Submission Instructions

In this homework, for the first time, you will be submitting multiple files to Submitty that together comprise a single program.

Please follow these instructions carefully.

You must submit three files. A file calledPerson.py that contains your Person class, a file called Universe.pythat contains your Universe class and a file calledhw8.py that contains your main program.

As always, make sure you follow the program structure guidelines. You will be graded on good program structure as well as program correctness.

Remember as well that we will be continuing to test homeworks for similarity. So, follow our guidelines for the acceptable levels of collaboration. You can download the guidelines from the resources section in Piazza if you need a refresher. Remember also that we can and will test for similarity againt programs from previous semesters as well.

Enter the multiverse: Universes

Many TV shows and movies make use of the theory of a multiverse. According to this theory many universes very similar to ours exist at the same time. In fact, different versions of us may exist in these universes as well. These alternate versions are very similar to us but may differ in very

fundamental ways. For example see regular and evil Spock from the original Star Trek (left), the Council of Ricks from Rick and Morty (middle) and the recent Council of Wells from Flash (right). Other examples include evil Willow and Xander. We can go on and on, but you get the point. Same individual but with a few fundamental differences that arise because they are from a different universe.

In this homework, you will have multiple universes each identified by their name. Assume each universe has the same dimensions, a rectangle between coordinates(0,0)at the upper left corner and(1000,1000)at the lower right corner. Each universe has some attributes:

  • Thenameof the universe given by a string.
  • A list of rewards in that universe. Each reward has the following information:x,y,points,name wherex,yis the location the reward is located in this universe, it has the point value (points) and the (name) which describes the reward.
  • A list of portals, each can transport you to a different universe. Each portal has the following information: from_x,from_y,to_name,to_x,to_y which means that the portal is at locationfrom_x,from_y in the current universe and it transports you to locationto_x,to_yin universe with nameto_name.

In the early tests for the homework, we will assume that there is a single universe with rewards, but no portals. As the plot thickens, we will add the portals and other universes.

You must implement a universe class to hold the above information and store it in a file called Universe.py. At a minimum, your Universe class must have a constructor (init) function and a string representation (str) function.

As you implement the main program, you may find other useful methods for this class that will simplify your program.

Here is an example universe from a test case:

Universe: EasyCS1 (4 rewards and 0 portals) Rewards: at (40,60) for 10 points: instant set knowledge at (100,200) for 40 points: bonus 5 points on one homework at (200,400) for 30 points: instant knowledge of list comprehension at (600,800) for 50 points: good variable name generation ability Portals: None

Multiverse: Individuals

In your simulation, you will track individuals moving along the universe. Each individual will have the following attributes:

name,radius,home_universe,x,y,dx,dy,current_universe,rewards

Each individual is from a specific universe (though we only use this to print where they are from). They are represented as a circle with a givenradius. Their current location is given byx,yand

thecurrent_universethey are on. Individuals have a speed given by their movement along x and y axis, stored in(dx,dy). Eventually individuals may stop or slow down, we will see how later.

You will be given an initial location and speed for each individual. They will all start moving in their current universe, but may move to other universes through portals. They may also pick up rewards over time, which you want to store. Initially, rewards will be empty. We will be interested in the awards the individual picked up as well as their total point value.

Implement a person class to hold the necessary data for each person. Store this in a file called Person.py.

As in universes, you may find that implementing some methods for each person class may signifi- cantly simplify your main code.

Here are some example individuals from one of our test cases.

Scientist of EasyCS1 in universe EasyCS at (20,30) speed (20,30) with 0 rewards and 0 points Engineer of EasyCS1 in universe EasyCS at (600,800) speed (-40,-10) with 0 rewards and 0 points

Cs1 Multiverse: The Main Idea

Here is the main idea of the simulation: In this simulation, you have (potentially) many universes and many individuals. Each individual is initially in their own universe at a specified location.

At each step of the simulation, each individual moves one time (i.e. x += dx, y += dy). Then, we check a number of conditions. Each condition is checked in the same order the individuals are given from the input file:

  1. If an individual passes near a location with treasure, she picks it up. As she carries more items, her speed goes down under the weight. The speed change will impact eitherdxordy as they shift left to right. If the magnitude (absolute value) of a persons speed drops below 10 in either thexory directions, she stops moving. Stopped individuals will no longer move in later steps.
  2. If an individual reaches the edge of the board, then she stops moving. Check for the center of the individual being passed or at the border.
  3. If two individuals hit each other while moving, they each drop the first reward they picked up (if they have any). The reward returns to its original location. Note that dropping a reward increases a persons speed. After a collision, both individuals begin moving in the opposite direction with their new speed.
  4. If an individual comes near the location of a portal, then she moves to a different universe that this portal points to. In the next simulation step, she will continue her journey in that new universe.

The simulation ends either at 100 steps or when there is no individual left moving. At the end of the simulation, the individual with the largest amount of collected treasure wins the game.

Whenever we are testing whether an individual is close to a reward, we check if the distance between the individuals location (x1,y1) and the rewards location (rx,ry) is less than or equal to the individuals radius (radius1):sqrt((x1-rx)2+(y1-ry)2)<= radius

To check whether two individual collide, we will look at the distance between their location (x1,y1andx2,y2) being less than or equal to the sum of their radiusradius1andradius2: sqrt((x1-x2)2+(y1-y2)2)<= radius1+radius

Note that, you will be given multiple test cases that only include steps (1) and (2) above. First implement these and test them. Then we will include test cases with collisions but no portals. Finally, we will have test cases with portals with or without collisions as universe expands.

For simplicity, we will give you all the relevant information about the program in a single JSON file. The file contains a single list, each item in the list is a universe.

Each universe is a dictionary with keys:universe_name,rewards,portals, andindividualsas shown below:

Universe Dictionary Field Data Type universe_name String rewards List of tuples with 4 values:x,y,points,description portals List of tuples with 5 values:fromx,fromy,to_universe,to_x,to_y individuals List of tuples with 6 values:name,radius,x,y,dx,dy Individuals are listed for a specific universe only. This is their home universe. When the simulation starts, the individual is also located in this universe in the initialx,ycoordinates.

The details of the simulation are given below. We recommend you implement slowly, reading each step and implementing it first. Think where the implementation should fall? A member function for universe or person classes, a function in your main program or simple code? Give yourself plenty of time to make changes to your program as needed.

Happy implementation!

Cs1 Multiverse: Detailed Problem Description

Create the class filesUniverse.pyandPerson.pycontaining class descriptions as described above. Write a program stored in filehw8.pyand import both classes into this file:

from Person import *
from Universe import *

Then, ask the user a single file name to read all universe and individual information:

Input file => file1.txt file1.txt

You can read the whole info using a single line of code as before:

data=json.loads(open(fname).read())

Using the data provided, create and store people and universe information in your program. Print out the main information for each universe and each individual first.

All universes


Universe: EasyCS1 (4 rewards and 0 portals) Rewards: at (40,60) for 10 points: instant set knowledge at (100,200) for 40 points: bonus 5 points on one homework at (200,400) for 30 points: instant knowledge of list comprehension at (600,800) for 50 points: good variable name generation ability Portals: None

All individuals

Scientist of EasyCS1 in universe EasyCS at (20,30) speed (20,30) with 0 rewards and 0 points Engineer of EasyCS1 in universe EasyCS at (600,800) speed (-40,-10) with 0 rewards and 0 points

Note: There are 40 dashes in the underline and a 4 space indent when printing individuals.

Now, start simulation and repeat each step below until 100 steps are reached, or no individuals are moving. At each step:

  1. Increment the simulation counter.
  2. Move all individuals in the order they are given in the input file by adding theirdx,dyto their current location.
  3. If an individual stops because their center is at or past the edge of the board, print a message. Archie stopped at simulation step 33 at location (1005.0,340.0)
  4. For each individual, check if they are able to reach a reward (i.e. the distance between their current location and the location of a reward in their current universe is less than or equal to the radius of the individual). If so, individual picks up the reward and the reward is no longer available to anyone else. Furthermore, the speed of the individual decreases according to the formula: dx = dx – (n%2)* (n/6)dx dy = dy – ((n+1)%2) (n/6)*dy wherenis the current number of rewards the individual has. Finally, print a message to show the reward that is picked and the individuals current info.
Scientist picked up "good variable name generation ability" at simulation step 33
Scientist of EasyCS1 in universe EasyCS
at (596.7,563.3) speed (8.3,13.3) with 3 rewards and 90 points
Remember that if the magnitude (absolute value) of a persons speed drops below 10 in either
thexorydirections, she stops moving.
  1. If the distance between two individuals is less than or equal to the sum of their radii, then they crash. In this case:
Each individual drops the first reward in their list (if they have any rewards). The reward
goes back to its original location in the universe in which it originated.
The speed of the individual dropping a reward increases because their load is reversed and
reverses direction, given by:
dx = -(dx + (n%2)* (n/6)*dx)
dy = -(dy + ((n+1)%2)* (n/6)*dy)
where n is the total number of current rewards for the individual after dropping the reward.
Print a message indicating the event.
Scientist and Archie crashed at simulation step 5 in universe IntersectionalCS
Scientist dropped "instant set knowledge", reward returned to IntersectionalCS1 at
(80,80)
Scientist of IntersectionalCS1 in universe IntersectionalCS
at (126.7,180.0) speed (-16.7,-30.0) with 0 rewards and 0 points
Archie of IntersectionalCS1 in universe IntersectionalCS
at (120.0,225.0) speed (-20.0,-15.0) with 0 rewards and 0 points
  1. Finally, if an individual is able to reach a portal (i.e. the distance between the individuals current location and the location of a portal is less than or equal to their radius), then the individual passes through the portal and moves to the universe pointed by the portal. Print an appropriate message. Scientist passed through a portal at simulation step 9 Scientist of MediumCS1 in universe EvilCS at (200.0,200.0) speed (16.7,30.0) with 1 rewards and 10 points

When the simulation ends, print the step the simulation ended, the number of individuals still moving at the end of the simulation and the individual(s) with the highest number of points and the rewards that they have.

Simulation stopped at step 48 0 individuals still moving Winners: Scientist of MediumCS1 in universe EvilCS at (850.0,1000.0) speed (16.7,20.0) with 2 rewards and 40 points Rewards: instant set knowledge ability to create black hole in Python

When you have fully tested your program, submit it as described above.

For this homework, we will be giving you both input files and the output created by them (instead of posting in PDF) so that you can test your code. Happy hunting for rewards!

To match the output: any indentation is 4 spaces. The line of hyphens is 40 characters long. Note that you must print your input file name as always.

代写Data Structures | 算法代做 | Algorithms | C代写 – Data Structures and Algorithms

代写Data Structures | 算法代做 | Algorithms | C代写 – 这是一个利用C语言进行BST搜索算法的任务,对时间复杂度有要求,属于比较典型的数据结构题目

Data Structures and Algorithms

######## LECTURE 26

Motivation

######## Organization and retrieval of information is at the heart of most computer

######## applications, and searching is the most frequently performed task

Searching
 If the array is not sorted, the search requires O( n ) time
If the value isnt there, we need to search all n elements
If the value is there, we search n /2 elements on average
 If the array is sorted, we can do a binary search
A binary search requires O(log n ) time
About equally fast whether the element is found or not
It doesnt seem like we could do much better
How about constant time search, O(1)?
We can do it if the array is organized in a particular way
Consider the problem of searching an array for a given value

######## Hashing is a technique used for performing insertions, deletions, and

######## searches in constant average time

######## Tree operations that require any ordering information among the elements

######## are not supported efficiently

######## The Data structure used is the hash table(a generalization of ordinary arrays)

oSeveral method of implementing the hash table
oCompare these methods
Hashing
Hash table

######## Given a table T and a record x (a record has a keyand an entry), we want to

######## support only the dictionary operations:

oInsert(T, x)
oDelete(T, x)
oSearch(T, x)

######## Goal

Fast operations without sorting the records beforehand
What is a table?

######## A table is simply another term for an array

It has several fields (i.e. types of information)
e.g., a telephone book has field name, field address, field phonenumber ,etc.
Smith 124 Moody St. 967 - 583 - 3322
White 1 South St. 781 - 222 - 1111
...
...

######## To find an entry in the table, you only need to know the content of one of

######## the fields (not all of them)

o This field is called key

######## Ideally, a key uniquely identifies an entry

Hash table big idea

######## Banking application

Imagine we have a file Account Info, and we want to be able to use a customers account
number to quickly (constant time) bring up their info
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier
We could use an array , of length 10,000, and simply use the account

######## numbers to index directly into the array

Direct-address table

######## Direct-address tables are ordinary arrays

######## Facilitate direct addressing

o Element whose key is k is obtained by indexing into the k thposition of the array

######## It is applicable when we can afford to allocate an array with one position for

######## every possible key

######## Insert/Delete/Search can be implemented to take O(1)time

####### 11/9/

Direct-address table

######## We have n elements that need to be stored

######## Universe U = {0, 1, …, m 1} of keys

 m >= n

######## Direct-address table

 T [0 ... m  1]
Each slot has a key k from K (actual keys used) in U
Empty slots contain NIL
254 Chapter 11 Hash Tables
11.1 Direct-address tables
Direct addressing is a simple technique that works well when the universeUof
keys is reasonably small. Suppose that an application needs a dynamic set in which

each element has a key drawn from the universeUDf0; 1; : : : ; m! (^1) g, wherem is not too large. We shall assume that no two elements have the same key. To represent the dynamic set, we use an array, or direct-address table ,denoted byT0::m! 1 , in which each position, or slot ,correspondstoakeyintheuni- verseU.Figure11.1illustratestheapproach;slotkpoints to an element in the set with keyk. If the set contains no element with keyk, thenTkDNIL. The dictionary operations are trivial to implement: DIRECT-ADDRESS-SEARCH.T; k/ 1 return Tk DIRECT-ADDRESS-INSERT.T; x/ 1 Tx: key Dx DIRECT-ADDRESS-DELETE.T; x/ 1 Tx: key DNIL Each of these operations takes onlyO.1/time. T (universe of keys) U K (actualkeys) 2 3 (^58) 1 9 4 0 7 6 2 3 5 8 key satellite data 2 0 1 3 4 5 6 7 8 9 Figure 11.1 How to implement a dynamic set by a direct-address tableT. Each key in the universe UDf0; 1; : : : ; 9gcorresponds to an index in the table. The setKDf2;3;5;8gof actual keys determines the slots in the table that contain pointers to elements. The other slots, heavily shaded, containNIL. Note: data does not have to be stored in an external object referenced from the slot in T. It can be just stored in the actual slot in T UUniverse of all possible keys KSet of keys actually stored in the table Account # Name 1345 Anderson 5076 Baker 0014 Cooper 2015 Dunhill 8428 Erickson 1007 Fourier

######## The disadvantageis that we could end up with a big array that has a lot of

######## empty space. This wastes lots of memory.

o The bigger we scale, the worse this problem gets (imagine if we used 9-digit account
numbers, and had only 10,000 customers
Direct-address table
Cons direct-address table

######## If U is large then a direct-address table T of size | U | is impractical or impossible

######## (considering memory)

oThe range of keys determines the size of T

######## The set K could be so small relative to U that most of the allocated space is

######## wasted

Direct-address table vs. Hash table
Direct-address table
o Element with key k is stored in slot k
Hash table
o Use hash function h ( k ) to compute the slot
Hash table big idea
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier

######## We can make the array smaller, and use the hash function to select which slot

######## we put our values into. For example the hash function = modulus function

######## Basically, we are compressing the domain of our keys so that they fit into the

######## array

0 1 2 3 4 5 6 7 8 9 10
Hash table big idea
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier
0 1 2 3 4 5 6 7 8 9 10
1345 mod 11 = 3
Anderson
h (k) = k mod m, where m is the size of your hash table
Hash table big idea
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier
0 1 2 3 4 5 6 7 8 9 10

5076 mod 11 = 5

Anderson Baker
Hash table big idea
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier
0 1 2 3 4 5 6 7 8 9 10

0014 mod 11 = 3

Anderson Baker
Cooper

Hash Tables

######## The size of the hash table is proportional to | K |

oWe lose the direct-addressing ability
oWe need to define functions that map keys to slots of the hash table
Hash function definition

######## A hash function h transforms a key k into a number that is used as an index in

######## an array to locate the desired location (bucket or slot)

oAn element with key k hashes to slot h ( k )
o h ( k ) is the hash value of key k
o h maps all keys in K from universe U into the slots of the hash table T[0 ... m  1]

######## Hash function

oSimple to compute
oAny two distinct keys get different cells
oThis is impossible, thus we seek a hash function that distributes the keys evenly among the
cells

########

######## h : U { 0 , 1 ,…, m 1 }

####### 11/9/

Hash function
256 Chapter 11 Hash Tables
11.2 Hash tables
The downside of direct addressing is obvious: if the universeUis large, storing
a tableTof sizejUjmay be impractical, or even impossible, given the memory
available on a typical computer. Furthermore, the setKof keys actually stored
may be so small relative toUthat most of the space allocated forTwould be
wasted.
When the setKof keys stored in a dictionary is much smaller than the uni-
verseUof all possible keys, a hash table requires much less storage than a direct-
address table. Specifically, we can reduce the storage requirement to.jKj/while
we maintain the benefit that searching for an element in the hash table still requires
onlyO.1/time. The catch is that this bound is for the average-case time ,whereas
for direct addressing it holds for the worst-case time.
With direct addressing, an element with keykis stored in slotk.Withhashing,
this element is stored in sloth.k/; that is, we use a hash function hto compute the
slot from the keyk.Here,hmaps the universeUof keys into the slots of a hash
table T0::m! 1 :
hWU!f0; 1; : : : ; m! 1 g;
where the sizemof the hash table is typically much less thanjUj.Wesaythatan
element with keyk hashes to sloth.k/;wealsosaythath.k/is the hash value of
keyk.Figure11.2illustratesthebasicidea.Thehashfunctionreducestherange
of array indices and hence the size of the array. Instead of a size ofjUj, the array
can have sizem.
T
U
(universe of keys)
K
(actual
keys)
0
m 
k 1
k 2
k 3

k (^4) k 5 h ( k 1 ) h ( k 4 ) h ( k 3 ) h ( k 2 ) = h ( k 5 ) Figure 11.2 Using a hash functionhto map keys to hash-table slots. Because keysk 2 andk 5 map to the same slot, they collide.

######## The ideal hash table is an array of some fixed size m , containing items (keyand

######## additional entry)

######## Each key k is mapped (using a hash function) into some number in the range 0

######## to m 1 and places in the appropriate cell

######## Insertion of a new entry is O(1)

######## Lookup for data is O(1) on average

oStatistically unlikely that O( n ) will occur

######## Decide what to do when two keys hash to the same value ( collision )

######## Choose a good hash function

######## Choose the size of the table

Issues with Hashing
Division method
Maps key k into one of m slots by taking the remainder of k divided by m
o h ( k ) = k % m
oFor example, hash table size m = 12 and key k = 100 h ( k ) = 4

######## Reasonable strategy, unless the key happens to have some undesirable

######## properties

oFor example, if the table size is 10 and all of the keys end in 0
Hash Function

######## Finding a perfect hashing function is not always possible

######## A hash function maps most of the keys onto unique integers, but maps some

######## other keys onto the same integer

######## This is called collision

Hash Function

######## Multiple keys can hash to the same slot: collisions are unavoidable

######## Design a good hash function will minimizethe number of collisions that

######## occur, but they will still happen, so we need to be able to deal with them

######## Design collision-resolution techniques

Collisions

######## There are two basic policies to handle collisions:

o Chaining
Store all elements that hash to the same slot in a linked list
Store a pointer to the head of the linked list in the hash table slot
 Open addressing
All elements stored in hash table itself
When collision occur, use a systematic procedure to store elements in free slots of the table
Handling Collision

Assignment | Lab代写 | C++代写 – LAB C++

Assignment | Lab代写 | C++代写 – 这是一个简单的C++的lab代做任务,属于基础训练题目

LAB

Add the necessary code to the source file Payroll5.cpp , that reads and processes each line of input in the sequential input file payroll.txt. The lines of the file begin with a string with an embedded blank that should be interpreted as an employee name. After the name, the input line contains a single pound (#) character followed by 3 double values. These should be interpreted as an employees hourly salary, the number of hours that the employee has worked and the taxrate as a percentage that is used for that employee. After inputing the remaining data on the input line, your program should display formatted values of the input values followed by the employees gross salary (hours hourly, with time and one-half for the number of hours beyond 40) and the net salary (the gross salary minus the gross salary the taxrate/100). Upon reaching the end of the file, your program should display the total of all of the gross salaries and the total of all of the net salaries. All monetary amounts should be right justified and formatted to display 2 digits to the right of the decimal point. All output for this program should be displayed on the monitor and should be embedded within functions. The file Payroll5.cpp contains functions instructions() and reportTitle() that display a descriptive message and the column headings, respectively. In addition, the file should use functions calculateGross() to calculate the gross pay for each employee, calculateNet() to calculate the net pay for each employee, displayEmployeeInfo() to display the salary information for each employee and totalAmounts() to display the total gross and total net. Keep in mind that three of the six aforementioned functions have already been written for you.

You should compile, execute and examine the code in Payroll5.cpp to try and understand the use of the functions instructions() and reportTitle(). For this assignment and the next, well take advantage of the make command. This command uses a file named makefile that automates the compilation process of our program. It is especially useful for large programs that consist of multiple files and well be using it from here on in with our laboratories. Issue the following commands to compile your source code. make payroll5. This command will create an executable called payroll5 . To run your program enter the command payroll

A Sample run using the data in the file payroll.txt is shown below. To gain full credit for this lab, the output must be formatted as shown below

Make sure to upload your source file to directory labs/ Once your lab is uploaded and while logged into the server via a terminal session, traverse to the directory labs/ 5 . YOU MUST BE IN DIRECTORY 5 , TO SUBMIT YOUR LAB. Once you are ready to submit your lab issue the command _submit csc155abc 5 _ where abc is the course section number.

Web | Math代做 | Ai代做 | Lab代写 – CISC 108: Introduction to Computer Science

Web | Math代做 | Ai代做 | Lab代写 – 这是一个典型的人工智能的代写任务

CISC 108: Introduction to Computer Science

lab 1

  1. Goals

Relevant sections of text:HtDP/2e Prologue and Chapters 1

This weeks lab will help you to practice:

  • usingDrRacket: interactions vs. definitions; stepper; error messages; indentation
  • simple image functions; using the Help Desk
  • function composition: write more complex functions by combining simpler functions.

Note: Exchange email addresses and phone numbers with your partner. Decide on your next meeting time this week in case you dont finish. Make surebothnames are at the top of your lab submission!

  1. Using DrRacket

Problem 1.

You may remember from math class that the distance from the origin point (0,0) to any point (x, y) in the cartesian plane is

distance(x, y) =

x^2 +y^2 ,

which is a function composed from other, more basic math functions (addition, squaring, and square root).

This function can be written in BSL as follows:

;; distance: Number Number -> Number[This is the SIGNATURE] ;; Consumes:[PURPOSE STATEMENT incl. parameter descriptions] ;; Number x : x-coordinate of a point in 2d-plane ;; Number y : y-coordinate of the point ;; Produces: the distance from origin to point (x,y).

(define (distance x y) (sqrt (+ (* x x) (* y y))))

Follow the step-by-step instructions below.

  • Copy this definition to theDrRacketdefinitionswindow (the top window).
  • PressRun. Notice which parts of the code are still in black/orangethose have not yet beentested.
  • Callthe function (i.e., run the program) by typing(distance 3 4)at the prompt in theinteractionswindow (lower window). Notice that the entire function definition is now tested. (Whether the answer is correct is a different issue 🙂
  • Now call the function to find the distance from the origin to the point (5,5). (Note: you can hitescapefollowed bypto haveDrRacketscroll backwards through the previous expressions that you typed at the interactions prompt.) Do you recall that#iindicates that the result is aninexactnumber? 1
  • Testing: to properly test a function, there should be at least one test per function. (Well be even more specific about this next week.) The black/orange coloring when you press Runindicates that that part of your code has not been tested. Tests on individual functions like this are calledunit tests. We will typically write the tests (as examples)BEFORE writing the function. (After all, if you dont know what the function is supposed to do, how can you possibly write the body?! Review Section 3.5On Testing.) The most common unit testing function ischeck-expect. For example, in the definitions pane add: (check-expect (distance 0 0) 0) ; the distance from (0,0) to (0,0) ; should be 0 However,check-expectcan only be used for checking exact equality of things. It will not work for inexact numbers. Try it: to the definitions pane add the following and pressRun: (check-expect (distance 5 5) 7.071) Note the error, note what is highlighted. The Unit Test Results window may be closed, or docked to the definitions and interactions panes. (When docked there will be three panes, not two). To test functions that return inexact numbers, use check-within. This unit testing function lets you say how close the answer must be to pass the test. Is within 0.1 close enough? 0.000001? For example, (check-within (distance 5 5) 7.071 0.0001) ; result must be between [7.0709 and 7.0711], inclusive Write two unit tests for the distance function, one withcheck-expectand one with check-within.
  • Call the function in the interactions window on incorrect arguments:(distance 4 "red"). Read and understand the error message!! What is highlighted in the definitions window? What if you type(distance true 10)in the interactions pane?
  • Using the Stepper: Put(distance 3 4)in thedefinitionswindow at the bottom. Press theStep button. This will bring up a separate window which lets you see how DrRacketis evaluating your program. Step through the program, making sure that you can correctly predict what the next step will be each time. Note that this is just simple algebraic substitution that you have used since middle school. Use the stepper anytime you are confused about what your function is doing.
  • Save your program and tests aslab1.rktusing theSave Definitionsoption in the file menu. There is nothing else to turn in for problem 1.

Problem 2.

Reread HtDP/2e Section 2.3,Composing Functions. Included are two solutions to the following sample problem:

Sample ProblemThe owner of a monopolistic movie theater in a small town has
complete freedom in setting ticket prices. The more he charges, the fewer people
can afford tickets. The less he charges, the more it costs to run a show because
attendance goes up. In a recent experiment the owner determined a relationship
between the price of a ticket and average attendance.
At a price of $5.00 per ticket, 120 people attend a performance. For each 10-cent
change in the ticket price, the average attendance changes by 15 people. That is, if
the owner charges $5.10, some 105 people attend on the average; if the price goes
down to $4.90, average attendance increases to 135. Let us translate this idea into
a mathematical formula:
avg. attendance= 120people
$(change in price)
$0. 10
 15 people
Stop! Explain the minus sign before you proceed.
Unfortunately, the increased attendance also comes at an increased cost. Every
performance comes at a fixed costs of $180 to the owner plus a variable cost of $0.
per attendee.
The owner would like to know the exact relationship between profit and ticket
price so that he can maximize his profit.

The first solution follows the correct design philosophy of defining one function per task:

;; attendees: Number -> Number ;; Consumes: ;; Number ticket-price : the price of one ticket in dollars ;; Produces: the number of people who will attend at that price (define (attendees ticket-price) (+ 120 (* (/ 15 0.1) (- 5.0 ticket-price))))

;; revenue: Number -> Number ;; Consumes: ;; Number ticket-price : the price of one ticket in dollars ;; Produces: the revenue generated, i.e. ticket price times ;; the number of attendees. (define (revenue ticket-price) (* (attendees ticket-price) ticket-price))

;; cost: Number -> Number ;; Consumes: ;; Number ticket-price : the price of one ticket in dollars ;; Produces: the costs incurred; costs have both a fixed [$180] and ;; variable [$.04 per attendee] part. (define (cost ticket-price) (+ 180 (* 0.04 (attendees ticket-price))))

;; profit: Number -> Number ;; Consumes: ;; Number ticket-price : the price of one ticket in dollars ;; Produces: the profit: revenues minus costs. (define (profit ticket-price) (- (revenue ticket-price) (cost ticket-price)))

Problem 2.1: Determine the potential profit for the following ticket prices: $1, $2, $3, $4, and $5. Which price should the owner of the movie theater choose to maximize his profits? Determine the best ticket price down to a dime. Place the answers as a comment in yourlab1.rktfile.

The alternative, poorly-thought-out definition is as follows:

;; No signature and purpose statement? ;; Lose most points for this function! (define (profit.bad price)

(- (* (+ 120

(* (/ 15 0.1)

(- 5.0 price)))
price)
(+ 180
(* 0.
(+ 120
(* (/ 15 0.1)
(- 5.0 price)))))))

Problem 2.2: After studying the cost structure of a show, the owner discovered several ways of lowering the cost. As a result of his improvements, he no longer has a fixed cost. He now simply pays $1.50 per attendee. Modify both programs to reflect this change. (You do not have to keep the originals). When the programs are modified, test them again with ticket prices of $3, $4, and $5 and compare the results. Add at least one unit test example for each function. Notice that DrRacketdoes not register your definition window edits in the interactions window until you pressRun. (You may wish to try running the program before and after you pressRunto see what happens.)

  1. String Arithmetic and the Help Desk

You may want to re-read HtDP/2e sections 1.2 and 1.3. Just as we can compose+, -,sqrt, sin, etc. for numbers, computation as the algebra of things allows us to compose functions on strings, images, boolean truth values, and any combination. Although you (I hope) have spent 12 years learning the common arithmetic number operations, computer languages tend to define their own operations on strings and images. (Even if your high school didnt teach them to you, mathematicians also named all the boolean operations, e.g.,and,or, andnot; these will come into play more next week). The book describes several string operations:

  • string-appendconcatenates two given strings into one. Think ofstring-appendas an operation that is just like+. While+consumes two (or more) numbers and produces a new number,string-appendconsumes two (or more) strings and produces a new string;
  • string-lengthconsumes a string and produces a (natural) number;
  • string-ithconsumes a stringsand extracts the one-character substring located at theith position (counting from 0);
  • number->stringconsumes a number and produces a string;
  • substring.. .hmmm, I wonder what this does? Look this up in theHelp Deskand find out what it does. If the documentation appears confusing, experiment with the function in the interaction area.

The Help Desk: Access the help desk from the menuHelpHelp Desk. This will bring up your web browser. Look underTeachingHow to Design Programs Languages. This will bring up all the teaching languages, and we are currently using BSL (Beginning Student Language). Click on the appropriate topic, e.g., Strings, and scroll down until you find an entry for the function you are interested in (substring). Alternatively, you can typesubstringinto the search box[.. .search manuals.. .]; make sure to only click on the result that is provided fromlang/htdp-beginnerfor now!

Problem 3. Define the functionstring-first, which extracts the first character from a non- empty string. Dont worry about empty strings. The signature for this function is

;; string-first: String -> String

From now on we assume that without being reminded, you will have a contract, purpose statement, and at least one example/unit test for each function that you write.We will discuss testing in more detail next week.

Problem 4. Define the function string-last, which extracts the last character (as a string) from a non-empty string. Dont worry about empty strings.

Problem 5. Define the functionstring-join, which consumes two strings and appends them with _ in the middle.

Problem 6. Define the functionstring-insert, which consumes a string and a numberiand which inserts at theithposition of the string (counting from the left, starting at 0). Assume iis a number between 0 and the length of the given string (inclusive). Also ponder the question whetherstring-insertshould deal with empty strings. If we insert at position 5 in the string helloworld, we expect the resulthello_world. We can write this example explicitly as a unit test:

(check-expect (string-insert "helloworld" 5) "hello_world")

Make sure that all of these functions and unit tests are included in your filelab1.rkt.

  1. Images and More Function Composition

See HtDP/2e section 1.4,.. ..

In class we will play with some built-in image-processing functions. To use them, you will load a library of previously defined functions by starting your definitions file with the line

(require 2htdp/image)

From the Help menu, choose Help Desk. UnderTeachingyou will seeHow to Design Programs Teachpacksclick on it. Then click onHTDP/2e Teachpacksin the upper left menu. In Sections 2.2 (Image Guide) and 2.3 (Images: image.rkt) you will find a complete description of all the functions in theimagelibrary. Yes, some of the concepts there have not been covered yet in class, but at this point the examples should be mostly clear and you should feel free to experiment in the DrRacketInteractions pane. Make it a habit to try to answer your own questions using the Help Desk before asking the TA or LA.

Here is an expression that will display a solid red circle of radius 10:

(circle 10 "solid" "red")

Notice that this conforms to the definition of a compound expression. (The operator/function name iscircle. The three arguments supplied to thecircleoperator are a number, 10, and two strings, solidandred.)

Problem 7. Use multiple image primitives, composed together, to create an image of a simple boat of your own design (have fun). Since the boat is always the same, define it as a constant:

;; a very unimaginative boat image using only one primitive (define MY-BOAT (ellipse 60 20 "solid" "Chartreuse"))

Problem 8. Define the functionimage-area, which computes the area of a given image.Note: The area is also the number of pixels in the picture.

DrRacketcan import images (e.g., from the web), either by cut-and-paste or theInsertImage… menu item. Consider an image like this:

This can be inserted inDrRacketby copying and pasting into a definition:

(define PALM )

Problem 9. Define the functionpinwheelthat consumes an image and produces a new image con- sisting of four copies of the image, each rotated around the center. For example,(pinwheel PALM) should produce something like:

Your function should work onPALM,MY-BOAT, or any image you pass in as an argument. For your unit tests, use any images you think appropriate.

Problem 10. Define an imageBACKGROUND, starting with a 500200 empty-scene, and adding some water (e.g., aLightSeaGreenrectangle) and an island with a palm tree.

Problem 11. Define a functiondraw-boatthat consumes a natural number (interpreted as the number of clock ticks that have gone by) and produces an image ofMY-BOATon top of the BACKGROUND, where the boat moves 3 pixels every clock tick, and when the boat leaves the right side it simply reappears on the left and continues. (Hint:look up the definition of the arithmetic operationmoduloin the Help Desk; consider(modulo 501 500),(modulo 502 500), etc.)

Make sure the line(require 2htdp/universe) occurs in your definitions area. Then add this as the final line in your definitions: (animate draw-boat). When you clickRun, an animation window should pop up with your background and boat, and the boat should begin moving across the background, wrapping around forever. Close the animation window and your unit tests will complete as usual.

Turn in your single filelab1.rktfile with all of your definitions, documentation, and tests from this lab using Sakai.MAKE SURE THAT SAK AI PROVIDES YOU WITH A RECIEPT!!! No receipt, no grade!

代写Operating System | Data Structure代做 | 作业Algorithm | C/C++代写 – Class CSCI-GA 2250- 001

代写Operating System | Data Structure代做 | 作业Algorithm | Assignment代写 | Lab代写 | C/C++代写 – 这是一个综合性的操作系统题目,使用C语言C++实现,是一个难度比较大的相关科目题目

Class CSCI-GA 2250- 001

In this lab/programming assignment you will implement/simulate the operation of an Operating Systems Virtual Memory Manager that maps the virtual address spaces of multiple processes onto physical frames using page table translation. The assignment will assume multiple processes, each with its own virtual address space of 64 virtual pages. As the sum of all virtual pages in all virtual address space may exceed the number of physical pages of the simulated system, paging needs to be implemented. The number of physical page frames varies and is specified by a program option, you have to support up to 128 frames, tests will only use 128 or less. Implementation is to be done in C/C++. Please submit your source only including a Makefile as a single compressed file via NYU classes.

INPUT SPECIFICATION:

The input to your program will be a comprised of:

  1. the number of processes (processes are numbered starting from 0)
  2. a specification for each process address space is comprised of i. the number of virtual memory areas / segments (aka VMAs) ii. specification for each said VMA comprises of 4 numbers: starting_virtual_page ending_virtual_page write_protected[0/1] filemapped[0/1]

Following is a sample input with two processes. First line not starting with a # is the number of processes. Each process in this sample has two VMAs. Note: ALL lines starting with # must be ignored and are provided simply for documentation and readability. In particular, the first few lines are references that document how the input was created, though they are

irrelevant to you. The input always follows the format below, though number and location of lines with # might vary.

#process/vma/page reference generator
# procs=2 #vmas=2 #inst=100 pages=64 %read=75.000000 lambda=1.
# holes=1 wprot=1 mmap= 1 seed=
2
#### process 0
#
2
0 42 0 0
43 63 1 0
#### process 1
#
2
0 17 0 1
20 63 1 0

Since it is required that the VMAs of a single address space to not overlap, this property is guaranteed for all provided input files. However, there can potentially be holes between VMAs, which means that not all virtual pages of an address space are valid (i.e. assigned to a VMA). Each VMA is comprised of 4 numbers. start_vpage: end_vpage: (note the VMA has (end_vpage start_vpage + 1) virtual pages write_protected: binary whether the VMA is write protected or not file_mapped: binary to indicated whether the VMA is mapped to a file or not

The process specification is followed by a sequence of instructions and optional comment lines (see following example). An instruction line is comprised of a character (c, r, w or e) followed by a number. c : specifies that a context switch to process # is to be performed. It is guaranteed that the first instruction will always be a context switch instruction, since you must have an active pagetable in the MMU (in real systems). r : implies that a load/read operation is performed on virtual page of the currently running process. w : implies that a store/write operation is performed on virtual page of the currently running process. e : current process exits, we guarantee that is the current running proc, so you can ignore.

# #### instruction simulation

c 0
r 32
w 9
r 0
r 20
r 12

Class CSCI-GA.2250- 001 Fall 2018

You can assume that the input files are well formed as shown above, so fancy parsing is not required. Just make sure you take care of the # comment lines. E.g. you can use sscanf(buf, %d %d %d %d,…) or stream >> var1 >> var2 >> var3.

DATA STRUCTURES:

To approach this assignment, read in the specification and create processes, each with its list of vmas and a page_table that represents the translations from virtual pages to physical frames for that process.

A page table naturally must contain exactly 64 page table entries (PTE). Please use constants rather than hardcoding 64. A PTE is comprised of the PRESENT/VALID, WRITE_PROTECT, MODIFIED, REFERENCED and PAGEDOUT bits and an index to the physical frame (in case the pte is present). This information can and should be implemented as a single 32-bit value or as a bit structures (easier). It cannot be a structure of multiple integer values that collectively are larger than 32-bits. (see http://www.cs.cf.ac.uk/Dave/C/node13.html (BitFields) or http://www.catonmat.net/blog/bit-hacks-header-file/ as an example, I highly encourage you to use this technique, let the compiler do the hard work for you). Assuming that the maximum number of frames is 128, which equals 7 bits and the mentioned 5 bits above, you effectively have 32-12 = 20 bits for your own usage in the pagetable. You can use these bits at will (e.g. remembering whether a PTE is file mapped or not). What you can NOT do is run at the beginning of the program through the page table and mark each PTE with bits based on filemap or writeprotect. This is NOT how OSes do that due to hierarchical page stable structures (not implemented in this lab though). You can only set those bits on the first page fault to that virtual page.

You must define a global frame_table that each Operating System maintains to describe the usage of each of its physical frames and where you maintain reverse mappings to the process and the vpage that maps a particular frame (In this assignment a frame can only be mapped by at most one PTE at a time).

SIMULATION and IMPLEMENTATION:

During each instruction you simulate the behavior of the hardware and hence you must check that the page is present. A special case is the c (context switch) instruction which simply changes the current process and current page table pointer.

Structure of the simulation

The structure of the simulation should be something like the following:

typedef struct { … } pte_t; // can only be total of 32-bit size !!!! typedef struct { … } frame_t;

class Pager { virtual frame_t* select_victim_frame() = 0; // virtual base class };

frame_t *get_frame() { frame_t *frame = allocate_frame_from_free_list(); if (frame == NULL) frame = THE_PAGER->select_victim_frame(); return frame; }

while (get_next_instruction(&operation, &vpage)) { // handle special case of c and e instruction // now the real instructions for read and write pte_t *pte = &current_process.page_table[vpage];// in reality this is done by hardware if (! pte->present) { // this in reality will generate the page fault exception and now you // execute frame_t *newframe = get_frame(); //-> figure out if/what to do with old frame if it was mapped // see general outline in MM-slides under Lab3 header // see whether and how to bring in the content of the access page. } // simulate instruction execution by hardware by updating the R/M PTE bits update_pte(read/modify/write) bits based on operations. }

Class CSCI-GA.2250- 001 Fall 2018

Classes for every paging Algorithm should derive from a base Pager class and there should be no replication of the simulation code. This will allow adding new classes.

If the page is not present, as indicated by the associated PTEs valid/reference bit, the hardware would raise a page fault exception. Here you just simulate this by calling your (operating systems) pagefault handler. In the pgfault handler you first determine that the vpage can be accessed, i.e. it is part of one of the VMAs, maybe you can find a faster way then searching each time the VMA list as long as it does not involve doing that before the instruction simulation (see above). If not, a SEGV output line must be created and you move on to the next instruction. If it is part of a VMA then the page must be instantiated, i.e. a frame must be allocated, assigned to the PTE belonging to the vpage of this instruction (i.e. currentproc-

pagetable[vpage].frame = allocated_frame ) and then populated with the proper content. The population depends whether this page was previously paged out (in which case the page must be brought back from the swap space (IN) or (FIN in case it is a memory mapped file). If the vpage was never swapped out and is not file mapped, then by definition it still has a zero filled content and you issue the ZERO output.

That leaves the allocation of frames. All frames initially are in a free list (you can choose a different FIFO Data structure of course). Once you run out of free frames, you must implement paging. We explore the implementation of several page replacement algorithms. Page replacement implies the identification of a victim frame according to the algorithms policy. This should be implemented as a subclass of a general Pager class with one virtual function frame_t* select_victim_frame(); that returns a victim frame. Once a victim frame has been determined, the victim frame must be unmapped from its user (

), i.e. its entry in the owning processs page_table must be removed (UNMAP), however you must remember the state of the bits. If the page was modified, then the page frame must be paged out to the swap device (OUT) or in case it was file mapped written back to the file (FOUT). Now the frame can be reused for the faulting instruction. First the PTE must be reset (note once the PAGEDOUT flag is set it will never be reset as it indicates there is content on the swap device) and then the PTEs frame must be set.

At this point it is guaranteed, that the vpage is backed by a frame and the instruction can proceed in hardware (with the exception of the SEGV case above) and you have to set the REFERENCED and MODIFIED bits based on the operation. In case the instruction is a write operation and the PTEs write protect bit is set (which it inherited from the VMA it belongs to) then a SEGPROT output line is to be generated. The page is considered referenced but not modified in this case.

Your code must actively maintain the PRESENT (aka valid), MODIFIED, REFERENCED, and PAGEDOUT bits and the frame index in the pagetables pte. The frame table is NOT updated by the simulated hardware as hardware has no access to the frame table. Only the pagetable entry (pte) is updated just as in real operating systems and hardware. The frame table can only be accessed as part of the simulated page fault handler ( see code above ).

The following page replacement algorithms are to be implemented (letter indicates option (see below)):

Algorithm Based on
Physical Frames
FIFO f
Random r
Clock c
Enhanced Second Chance / NRU e
Aging a
Working Set w

The page replacement should be generic and the algorithms should be special instances of the page replacement class to avoid switch/case statements in the simulation of instructions. Use object oriented programming and inheritance.

When a virtual page is replaced, it must be first unmapped and then optionally paged out or written back to file. While you are not effectively implementing these operations you still need to track them and create entries in the output (see below).

Since all replacement algorithms are based on frames, i.e. you are looping through the entire or parts of the frame table, and the reference and modified bits are only maintained in the page tables of processes, you need access to the PTEs. To be able to do that you should keep track of the reverse mapping from frame to PTE that is using it. Provide this reverse mapping (frame <proc-id,vpage>) inside each frames frame table entry.

Class CSCI-GA.2250- 001 Fall 2018

Note (again): you MUST NOT set any bits in the PTE before instruction simulation start, i.e. the pte (i.e. all bits) should be initialized to 0 before the instruction simulation starts. This is also true for assigning FILE or WRITEPROTECT bits from the VMA. This is to ensure that in real OSs the full page table (hierarchical) is created on demand. Instead, on the first page fault on a particular pte, you have to search the vaddr in the VMA list. At that point you can store bits in the pte based on what you found in the VMA and what bits are not occupied by the mandatory bits.

You are to create the following output if requested by an option (see at options description):

78: ==> r 2
UNMAP 1: 42
OUT
IN
MAP 26
Output 1
69: ==> r 37
UNMAP 0: 35
FIN
MAP 18
Output 2
75: ==> w 57
UNMAP 2: 58
ZERO
MAP 17
Output 3

For instance in Output 1 Instruction 78 is a read operation on virtual page 2 of the current process. The replacement algorithms selected physical frame 26 that was used by virtual page 42 of process 1 (1:42) and hence first has to UNMAP the virtual page 42 of process 1 to avoid further access, then because the page was dirty (modified) (this would have been tracked in the PTE) it pages the page OUT to a swap device with the (1:26) tag so the Operating system can find it later when process 1 references vpage 42 again (note you dont implement the lookup). Then it pages IN the previously swapped out content of virtual page 2 of the current process (note this is where the OS would use tag to find the swapped out page) into the physical frame 2 6 , and finally maps it which makes the PTE_2 a valid/present entry and allows the access. Similarly, in output 2 a read operation is performed on virtual page 37. The replacement selects frame 1 8 that was mapped by process_0s vpage=35. The page is not paged out, which indicates that it was not dirty/modified since the last mapping. The virtual page 37 is read from file (FIN) in to physical frame 18 (implies it is file mapped) and finally mapped (MAP). In output 3 you see that frame 17 was selected forcing the unmapping of its current user process_2, page 58, the frame is zeroed, which indicates that the page was never paged out or written back to file (though it might have been unmapped previously see output 2). An operating system must zero pages on first access (unless filemapped) to guarantee consistent behavior. For filemapped virtual pages (i.e. part of filemapped VMA) even the initial content must be loaded from file.

In addition your program needs to compute and print the summary statistics related to the VMM if requested by an option. This means it needs to track the number of instructions, segv, segprot, unmap, map, pageins (IN, FIN), pageouts (OUT, FOUT), and zero operations for each process. In addition you should compute the overall execution time in cycles, where maps and unmaps each cost 400 cycles, page-in/outs each cost 3000 cycles, file in/outs cost 2500 cycles, zeroing a page costs 150 cycles, a segv costs 240 cycles, a segprot costs 300 cycles and each access (read or write) costs 1 cycles and a context switch costs 121 cycles and process exit costs 175 cycles.

Per process: printf("PROC[%d]: U=%lu M=%lu I=%lu O=%lu FI=%lu FO=%lu Z=%lu SV=%lu SP=%lu
", proc->pid, pstats->unmaps, pstats->maps, pstats->ins, pstats->outs, pstats->fins, pstats->fouts, pstats->zeros, pstats->segv, pstats->segprot); All: printf("TOTALCOST %lu %lu %lu %llu
", inst_count, ctx_switches, process_exits, cost);

If requested by an option you have to print the relevant content of the page table of each process and the frame table.

PT[0]: * 1:RM- * * * 5:-M- * * 8:— * * # * * * * * * * * # * * * 24:— * * * # * * * * * *

      • * * * * * * * * * # * * # * * * # * * * * * * * *

FT: 0:1 0:5 0:24 0: PROC[0]: U=25 M=29 I=1 O=8 FI=0 FO=0 Z=28 SV=0 SP= TOTALCOST 31 1 0 52951

Note, the cost calculation can overrun 2^32 and you must account for that, so use at least a 64 – bit counters (unsigned long long). We will test your program with 1 Million instructions. Also the end calculations are tricky, so do them incrementally. Dont add up 32-bit numbers and then assign to 64-bit. Add 32-bit numbers incrementally to the 64-bit counters, if you use 32-bit.

Class CSCI-GA.2250- 001 Fall 2018

Execution and Invocation Format:

Your program must follow the following invocation: ./mmu [-a] [-o] [f<num_frames>] inputfile randomfile (optional arguments in any order). e.g. ./mmu ac o[OPFS] infile rfile selects the Clock Algorithm and creates output for operations, final page table content and final frame table content and summary line (see above). The outputs should be generated in that order if specified in the option string regardless how the order appears in the option string. We will grade the program with oOPFS options (see below), change the page frame numbers and diff compare it to the expected output.

The test input files and the sample file with random numbers are supplied. The random file is required for the Random algorithm. Please reuse the code you have written for lab2, but note the difference in the modulo function which now indexes into [ 0, size ) vs previously ( 0, size ]. In the Random replacement algorithm you compute the frame selected as with (size==num_frames) As in the lab2 case, you increase the rofs and wrap around from the input file.

 The O (ohhh) option shall generate the required output as shown in output-1/3.
 The P (pagetable option) should print after the execution of all instructions the state of the pagetable:
As a single line for each process, you print the content of the pagetable pte entries as follows:

PT[0]: 0:RMS 1:RMS 2:RMS 3:R-S 4:R-S 5:RMS 6:R-S 7:R-S 8:RMS 9:R-S 10:RMS

11:R-S 12:R– 13:RM- # # 16:R– 17:R-S # # 20:R– # 22:R-S 23:RM- 24:RMS #

27:R-S 28:RMS # # # # # 34:R-S 35:R-S # 37:RM- 38:R-S * # 41:R– # 43:RMS

44:RMS # 46:R-S * * # * * * # 54:R-S # * * 58:RM- * * # * *

R (referenced), M (modified), S (swapped out) (note we dont show the write protection bit as it is implied/inherited
from the specified VMA.
Pages that are not valid are represented by a # if they have been swapped out (note you dont have to swap out a
page if it was only referenced but not modified), or a * if it does not have a swap area associated with. Otherwise
(valid) indicates the virtual page index and RMS bits with - indicated that that bit is not set.
Note a virtual page, that was once referenced, but was not modified and then is selected by the replacement
algorithm, does not have to be paged out (by definition all content must still be ZERO) and can transition to *.
 The F (frame table option) should print after the execution and should show which frame is mapped at the end to
which <pid:virtual page> or * if not currently mapped by any virtual page.

FT: 0:32 0:42 0:4 1:8 * 0:39 0:3 0:44 1:19 0:29 1:61 * 1:58 0:6 0:27 1:

 The S option prints the summary line (SUM ...) described above.
 The x options prints the current page table after each instructions (see example outputs) and this should help you
significantly to track down bugs and transitions
 The y option is like x but prints the page table of all processes instead.
 The f option prints the frame table after each instruction.
 The a option prints additional aging information during victim_select and after each instruction for complex
algorithms (not all algorithms have detail
We will not test or use the -f ,-a or the -x,-y option during the grading. It is purely for your benefit to add these
and compare with the reference program under ~frankeh/Public/mmu on any assigned cims machines.
(Note only a max of 10 processes and 8 VMAs per process are supported in the reference program which means
that is the max we test with).

All scanning replacement algorithm typically continue with the frame_index + 1 of the last selected victim frame.

Please note you have to provide a modular design which separates the simulation (instruction by instruction) from the replacement policies. Use OO style of programming and think about what operations you need from a generic page replacement (which will define the API). A lack of doing a modular design with separated replacement policies and simulation will lead to a deduction of 5pts. Initializing the PTE before instruction simulation to anything but 0 will cost another 5 pts.

Class CSCI-GA.2250- 001 Fall 2018

FAQ: ( and lots of debugging help )

ESC/NRU requires that the REFERENCED-bit be periodically reset for all valid page table entries. The book suggests on every timer cycle which is way too often. Typically this is done at periodic times using a daemon. We simulate the periodic time inside the select_victim_frame function. If 50 or more instructions have passed since the last time the select function was called, then the reference bit of the ptes reached by the frame traversal should be cleared after you considered the class of that frame/page. Also in the algorithm you only have to remember the first frame that falls into each class as it would be the one picked for that class. Naturally, when a frame for class-0 (R=0,M=0) is encountered, you should stop the scan, unless the reference bits need to be reset, at which point you scan all frames. Once a victim frame is determined, the hand is set to the next position after the victim frame for the next select_victim_frame() invocation.

The -oa option will produce the following output: ( | scan ): ASELECT: 5 1 | 3 5 9 ^ hand at beginning of select function

^ Boolean whether reference bit has to be reset (>= 50 th instructions since last time) ^ Lowest class found [0-3]

^ Victim frame selected ^ Number of frames scanned

AGING requires to maintain the age-bit-vector. In this assignment please assume a 32-bit counter treated as a bit vector. Aging is implemented on every page replacement request. Since only active pages can have an age, it is fine (read recommended) to stick the age into the frame table entry. Once the victim frame is determined, the hand is set to the next position after the victim frame for the next select_victim invocation. Note the age has to be reset to 0 on each MAP operation.

The -oa option will produce the following output: ( | | scan ): ASELECT 2 – 1 | 2:40000000 3:10000000 0:20000000 1:80000000 | 3 ^ scan from frame 2 to 1 (so there is a wrap around )

^ frame# and age (hexadecimal) after shift and ref-bit merge (while scanning the frames) ^ frame selected (3)

WORKING-SET: In the case of working set we also need to deal with time (tau). Again we use the execution of a single instruction as a time unit. If more than 50 time units (instructions) have passed since the value of tau recorded in the frame and the reference bit is not set then this frame will be selected (see algo). Note when you map a frame, you must set its tau value to the current time (instruction count). The -oa option will produce the following output: ( | | scan ) ASELECT 3-2 | 3(0 3:7 5196) 0(0 3:31 5198) 1(0 0:34 5199) 2(1 0:10 0) | 3

^ scan from frame 3 to 2 (so there is a wrap around ) ^ frame# (refbit, proc:vpage, tau) (while scanning the frames) frame selected (3) ^

ASELECT 44-43 | 44(1 2:18 0) 45(0 1:33 5140) STOP(2) | 45 the scan stops if a frame with bigger tau is found ^ and that frame will be selected, (2) is number of frames scanned and 45 is the frame selected

What to do on process exit:

On process exit (instruction), you have to traverse the active processs page table starting from 0..63 and for each valid entry UNMAP the page, FOUT modified filemapped pages. Note that dirty non-fmapped (anonymous) pages are not written back (OUT) as the process exits. The used frame has to be returned to the free pool and made available to the get_frame() function again. The frames then should be used again in the order they were released.

OTHER STUFF

The pagetable and frametable output is generated AFTER the instruction is executed, so the output becomes the state seen prior to executing the next instruction. Optional arguments in arbitrary order? This was shown in the sample programs ~frankeh/Public/ProgExamples.tz Please read: http://www.gnu.org/software/libc/manual/html_node/Example-of-Getopt.html ( very useful and trivial to use)

Class CSCI-GA.2250- 001 Fall 2018

Provided Inputs

The submission comes with a few generated inputs that you can use to address the implementation in an incremental step. Each input is characterized by how many processes, how many maximum vmas per process, how many maximum write protected vmas per process, whether there is a filemapped vma and maximum numbers of vma holes might exist for a process.

Input
File
#inst #procs #vmas
(max)
Write-
protect
File-
mapped
Holes Proc
Exits
in1 30 1 1 0
in2 30 1 1 0
in3 100 1 4 0
in 4 100 1 5 2
in5 100 1 5 0 1
in6 100 1 5 2 2
in7 200 2 2
in8 200 2 3 1 1
in9 1000 3 4 1 1 2
in10 5000 4 6 2 1 2
in11 5000 4 5 1 1 2 2

It is suggested that you follow this approach: a) read the input creating your processes and their respective vmas and print them out again, to ensure you read properly. b) implement the features for a single process first (in1..in6) and implement one algorithm (e.g. fifo). c) add the basic features for context switching (in7..in8) and then expand to other algorithms d) Finally, try the more complex input files (in9..in10).

Sample output files are provided as a *.tar.Z for each input and each algorithm for two frame number scenar ios f16 and f 32 11 * 2 * 6 132 files. If you need more you can generate your own outputs using the reference program on the cims account (under ~frankeh/Public/mmu) for different frame numbers.

I also provide a ./runit.sh and a ./gradeit.sh. (change INPUTS and ALGOS in both to limit what you want to test) ./runit.sh <inputs_dir> <output_dir> ./gradeit.sh <refout_dir> <output_dir> # will generate a summary statement and <output_dir>/LOG file for more details. Look at the LOG file and it shows the diff command for those files that failed and even if the TOTALCOST are the same there are differences elsewhere. Remove the -q flag in the diff command of the LOG and run manually. If you runit and then gradeit you will get a matrix as follows .. any failing test will be marked as x.

$ ./gradeit.sh ../refout ../studentout/ input frames f r c e a w 1 16…… 1 32…… 2 16…… 2 32…… 3 16…… 3 32…… 4 16…… 4 32…… 5 16…… 5 32…… 6 16…… 6 32…… 7 16…… 7 32…… 8 16…… 8 32…… 9 16…… 9 32…… 10 16…… 10 32…… SUM 2 0 20 20 20 20 20

  • Class CSCI-GA.2250- 001 Fall

Project代写 | Swift代做 | IOS 代做- Mobile Application Development

Project代写 | Swift代做 | Ios – 这是一个IOS移动开发的任务,使用的技术是swift

Mobile Application Development lab 3: Drawing App

Overview

In this lab, you will be exploring UIKit and Core Graphics through the creation of a simple drawing app. This will be the first complete app you create, and will show how to use the ios swift代写 移动开发 苹果代写”> Swift language to get the most out of the built-in Cocoa Touch frameworks.

Please read this entire PDF prior to starting work on your lab. Every section contains information relevant to how you will be graded, not just the Requirements section.

Description

This lab requires you to create your own app from scratch. Although many of the implementation details are left to you, there are some helpful guidelines and code snippets to get you started in the Helpful Advice and Code Snippets section below. Many of the topics covered in this lab have been discussed in lecture as well. Additional resources are available online in the Swift documentation and UIKit documentation that Apple provides.

Requirements

[40 points] Users can draw continuous lines by tapping and dragging. [10 points] Lines drawn must be smooth (no jagged edges).

[5 points] Users can undo to erase the previous line drawn. They should be able to undo repeatedly until there are no lines on the screen. [5 points] Users can selected from multiple (at least 5) color options. [5 points] There is a slider to adjust the line thickness.

Requirements (continued)

[10 points] Single taps result in dots. [5 points] Users can easily erase all lines on the page.

[20 points] Creative portion: Add 2 other small features. Be creative!

Helpful Advice and Code Snippets

The first challenge will most likely be getting data from the users input. The way to do this is by overriding the touchesBegan, touchesMoved, and touchesEnded functions in your view controller. After these are in place, use the following code to get the location of a users touch.

guard let touchPoint = touches.first?.location(in: view) else { return }

This function takes the first touch from a set of UITouch objects provided by the system, and finds its location in the current view. This limits the user to only inputting a single touch at a time, but it should suffice for the purposes of this lab.

An easy way to implement custom drawing is to override the drawRect function of a custom UIView. Create a new class which subclasses UIView, and override the drawRect function. This is where the custom drawing will take place, and is called automatically. If you need to refresh what is displayed in the view, the setNeedsDisplay function will call drawRect for you. Do not call drawRect directly. This allows the graphics system to optimize how often the screen is redrawn, and it will only execute drawRect if the display needs to be updated for the next frame to be displayed.

As for the lines themselves, I recommend using a UIBezierPath object, which has a lot of convenient methods to incrementally build and store complex paths. It is a higher-level wrapper object for the underlying CGPath object, and integrates with UIKit easily. It is quite straightforward to draw a UIBezierPath in a UIView (search for the UIBezierPath class reference online to find out how). If you are digging into the depths of Core Graphics, you have probably missed an easier solution.

The UIBezierPath class also comes in handy for smoothing out your lines (which otherwise may look jagged and unpolished). There are many path smoothing algorithms, but one of the simplest is given below. It uses the original points as control points for the bezier curve, and the midpoints between each pair of points as the actual points. (If you have worked with the pen tool in any vector drawing application the concept of anchor points and control points might be familiar to you.) In any case, below is a function which takes in an array of CGPoints, and returns a smooth UIBezierPath. It requires the use of a midpoint helper function, which I will leave as an exercise for the reader.

private func midpoint(first: CGPoint, second: CGPoint) -> CGPoint { // implement this function here }

func createQuadPath(points: [CGPoint]) -> UIBezierPath { let path = UIBezierPath() if points.count < 2 { return path } let firstPoint = points[0] let secondPoint = points[1] let firstMidpoint = midpoint(first: firstPoint, second: secondPoint) path.move(to: firstPoint) path.addLine(to: firstMidpoint) for index in 1 ..< points.count-1 { let currentPoint = points[index] let nextPoint = points[index + 1] let midPoint = midpoint(first: currentPoint, second: nextPoint) path.addQuadCurve(to: midPoint, controlPoint: currentPoint) } guard let lastLocation = points.last else { return path } path.addLine(to: lastLocation) return path }

Lastly, this application provides a great opport unity to leverage object-oriented programming principles to make your code easier to read and maintain, as well as save you time. If you are going to make a button for seven different colors, consider creating a UIButton subclass so you only have to write your button styling code once. Or, if you need to store additional information along with a UIBezierPath (like its color or thickness, for example), consider creating your own custom class/struct to keep all that relevant data together.

Think about structuring your app according to the model-view-controller paradigm. What is the model? What is the view? How do we connect those pieces in a reusable way? Which object should be responsible for the createQuadPath function? Contemplating these questions may seem trivial for a simple app, but becomes critical as your codebase scales.

Good luck!

An example of a working drawing app. Notice that the lines are smooth (not just connected line segments) and the user can tap to draw dots.

代做Homework| 代写haskhell | Assignment – CS 457 Functional Languages

代做Homework| 代写haskhell | Assignment – 这是一个常规的haskhell的练习题目

CS 457/557 Functional Languages

Description

This course provides a gentle introduction to the ideas and techniques of functional programming, using the Haskell programming language. Functional languages are great for both rapid prototyping and serious software engineer- ing. The key idea is to program declaratively using functiondefinitions rather than operationally using assignments. Haskells features include higher-order functions, strong typing, polymorphism, user-defined algebraic data types,au- tomatic storage management, lazy evaluation, and powerfulabstraction and modularization facilities. The course will concentrate on developing practical programming skills in Haskell, with a brief look at the theoretical underpinnings.

Textbooks

The required text is by Paul Hudak,The Haskell School of Expression, Cambridge University Press, 2000.

An excellent auxiliary reference is Simon Thompson, Haskell: The Craft of Functional Programming, 2nd. ed., Addison-Wesley, 1999.

Two additional short readings are listed in the schedule below; more may be assigned from time to time.

Lecture notes will be available electronically in postscript format via the course home page.

Lots of on-line resources are available athttp://www.haskell.org.

Requirements

Weekly graded  homework assignments (8 in all) 40%
Midterm exam 30%
Final exam 30%

The weekly assignments are intended to help you master the basic material of the course. Each homework assignment is to be handed in (on paper) at the beginning of class on the Tuesday on which it is due.

Th midterm and final exams are intended to check that you have mastered the fundamentals of the language. They will be open-book, open-notes.

Computing Facilities

To do the homework, you will need to use the Haskell interpreter called HUGS 98. In particular, youll want the Nov2002 release; some of the graphics code in the Hudak book doesnotwork properly with more recent releases. A copy of this Hugs release is available on the Solaris networkin the CS department in thehugspackage. Alternatively, you can download it for use on your own machine (either Windows or linux) fromhttp://haskell.org/hugs. (Make sure to get the Nov2002 release.) It is easy to install and its resource demands are modest. Any supporting materials (program files, etc.) will be made available on thecourse web page.

1

Mailing List

Important information will be distributed throughout the term via a mailing list calledcs457list. You can subscribe to this list via the course home page.

Tentative Schedule

Reading Whats due Topics (Example Applications)
Sep 27 1,2 Introduction; Using Hugs; Lists
29 Data Types (Shapes); Modules
Oct 4 3,4 HW1 IO Actions; Graphics (Drawing Shapes)
6
11 5,6 HW2 Polymorphism; Higher-order functions; Maps and folds (Perimeters of shapes)
13
18 7,8,HJ HW3 Algebraic data types; Trees (Regions)
20
25 9,10 HW4 More higher-order functions: Currying, sections, composition; (Drawing Regions)
27
Nov 1 11 Midterm Exam (2-3:50pm)
3 Proving Program Properties
8 12,13 HW5 Qualified types and type classes (Animations)
10
15 14,H HW6 Streams; Laziness; Infinite data structures
17
22 18,19 HW7 Higher-order types; Monads (Robot Control Language)
24 Thanksgiving Holiday  no class
29 HW
Dec 1 Pragmatics
5 Final Exam (Monday 10:15am-12:05pm)

Class will normally meet from 2-3:30pm.

Schedule is subject to change.

Numbers in the readings column are chapter numbers from the Hudak textbook.

Letters in the readings column are keyed as follows:

HJ = P. Hudak and M. Jones,Haskell vs. Ada vs. c++ vs. Awk vs. …, An Experiment in Software Prototyping Productivity, July 1994,http://haskell.org/papers/NSWC/jfp.ps.

H = J. Hughes,Why Functional Programming Matters, 1984,http://www.math.chalmers.se/ rjmh/ Papers/whyfp.html.

Additional readings may be assigned from time to time.

Plagiarism

Unless specifically indicated otherwise, all homework assignments and exams must represent your own, individual work. It is permissible to discuss the assignment with otherstudents, but you must program and write up the solution by yourself.Do not, under any circumstances, copy another persons program and submit it as your own.Writing code for use by another or using anothers code in any form (even with their permission) will be considered cheating. In particular, cheating will result in an automatic F for theassignment in question, and the initiation of disciplinary action at the University level.

Disabilities

If you are a student with a disability in need of academic accommodations, you should register with Disability Services for Students and notify the instructor immediately to arrange for support services.

2

Assignment | Lab作业 | Java代写 | oop – 48024 Applications Programming

Assignment | Lab作业 | Java代写 | oop – 这是一个利用java进行软件设计训练的题目,对软件开发设计的流程进行训练解析

48024 Applications Programming

Assignment Lab作业 Java代写 oop CS作业代写 代写CS

assignment 1

1. Individual work

All work is individual. You may discuss ideas, approaches and problems, but you should write every line of code yourself except for code copied from the lecture notes, lecture code or lab code. You MUST NOT let another student see your solution code, and you MUST NOT look at another students solution code. More information about Academic Misconduct can be found at: http://www.gsu.uts.edu.au/rules/student/section-16.html

2. Specifcation

A friend of yours is setting up a computer building business, and to help customers decide on what components they want in their system, your friend has cajoled you, with the promise of cold pizza and fat coke, into writing some software to help this process.

The system should keep a catalogue of available parts, which can be displayed to the user, updated and fltered by type or price (or both).

The system should also allow the user to build a computer (more accurately a parts list) from parts in the catalogue, add and remove parts from the build, clear the build, see the build (including the total cost).

The interface for the prototype will be a simple text interface, where parts are identifed by their position in the catalogue/build.

As an advanced feature, your friend would like the user to be able to add several parts in one go.

Your friend has provided you with a nicely typed out text demonstration of how the system should work, along with some tests (… yet didnt just code it…) to help.

An aside…

While reading the the frrt part of the rpecifcationn you will notice there ir a lot going on.

 How many functionr did you identify?
 How many clarrer did you identify?
 What are the feldr in each clarr?
 How many goalr did you identify?
 How many patternr did you think of that might be applicable?

Thir arrignment will be challenging and you will probably want to manage your time well.

 How long do you think it will take you to code the functionr?
 How long do you think it will take you to code each goal?

A good rule of thumb ir to think of an ertimaten and then multiply that number by 3 or 4!

To manage your time welln you may need to fgure out which partr of the arrignment you can rtart early.

If you complete partr in the rame week that you learn the topicr (while they are frerh in your mind)n they will take lerr time to complete.

The User Interface

Below is a sample I/O trace. The green text indicates user input (you are not expected to print colour text). Not every conceivable scenario is shown below and you should submit your code to PLATE to see what specifc scenar ios are tested. You should also implement your solution in the same order as PLATEs test cases so that you can receive incremental feedback and marks as you progress.

Welcome to Jaime’s Computer Store Quality Parts at the Best Prices

=================================

  1. Catalogue Menu
  2. Build Menu
  3. Exit

Select option: 1

Welcome to the parts catalogue.

Enter choice (a/r/s/f/x): s

  1. STORAGE: evo 860 @ $155.
  2. KEYBOARD: daskeyboard @ $239.
  3. CPU: i5 @ $365.
  4. MEMORY: corsair 16G @ $299.
  5. MOTHERBOARD: ASUS ROG @ $159.
  6. CASE: sheetmetal box @ $39.
  7. CPU: Ryzen 7 @ $299.

Enter choice (a/r/s/f/x): f

Enter type of part to view (‘all’ for no filtering): cpu

Enter minimum price (‘-1’ for no filtering): –

  1. CPU: i5 @ $365.
  2. CPU: Ryzen 7 @ $299.

Enter choice (a/r/s/f/x): a

Enter part name: coolermaster junk

Enter part type: case

Enter part price: 50.

Enter choice (a/r/s/f/x): s

  1. STORAGE: evo 860 @ $155.
  2. KEYBOARD: daskeyboard @ $239.
  3. CPU: i5 @ $365.
  4. MEMORY: corsair 16G @ $299.
  5. MOTHERBOARD: ASUS ROG @ $159.
  6. CASE: sheetmetal box @ $39.
  7. CPU: Ryzen 7 @ $299.
  8. CASE: coolermaster junk @ $50.

Enter choice (a/r/s/f/x): x

  1. Catalogue Menu
  2. Build Menu
  3. Exit

Select option: 2

Let’s build a 1337 box!

Enter choice (n/a/r/v/c/x): a

Enter catalogue number of the part: 3

Enter choice (n/a/r/v/c/x): a

Enter catalogue number of the part: 1

Enter choice (n/a/r/v/c/x): a

Enter catalogue number of the part: 2

Enter choice (n/a/r/v/c/x): a

Enter catalogue number of the part: 4

Enter choice (n/a/r/v/c/x): a

Enter catalogue number of the part: 5

Enter choice (n/a/r/v/c/x): a

Enter catalogue number of the part: 6

Enter choice (n/a/r/v/c/x): c

The build is functional.

Enter choice (n/a/r/v/c/x): v

  1. CPU: i5 @ $365.
  2. STORAGE: evo 860 @ $155.
  3. KEYBOARD: daskeyboard @ $239.
  4. MEMORY: corsair 16G @ $299.
  5. MOTHERBOARD: ASUS ROG @ $159.
  6. CASE: sheetmetal box @ $39.

Total Price: $1256.

Enter choice (n/a/r/v/c/x): r

Enter number of part to remove: 1

Enter choice (n/a/r/v/c/x): a

Enter catalogue number of the part: 7

Enter choice (n/a/r/v/c/x): v

  1. STORAGE: evo 860 @ $155.
  2. KEYBOARD: daskeyboard @ $239.
  3. MEMORY: corsair 16G @ $299.
  4. MOTHERBOARD: ASUS ROG @ $159.
  5. CASE: sheetmetal box @ $39.
  6. CPU: Ryzen 7 @ $299.

Total Price: $1190.

Enter choice (n/a/r/v/c/x): c

The build is functional.

Enter choice (n/a/r/v/c/x): x

  1. Catalogue Menu
  2. Build Menu
  3. Exit

Select option: 3

Requirements

 Your design will consist of exactly the following classes with the listed
felds, declared as indicated. You may not add or remove classes or felds,
however you may add constructors, functions and procedures to complete
your design (in fact, you will have to!). You should pay careful attention to
the tests on PLATE, as these will help guide you with some (but not all) of
these methods.
 Classes  your design will consist of these 5 classes:
  1. ComputerBuilder
  2. Build
  1. Catalogue
  2. Part
  3. In (this is just the class youve been using throughout the labs to facilitate simpler I/O just copy it over) Fields the classes will have the following felds:
public class ComputerBuilder {
private Catalogue catalogue;
private Build currentBuild;
}
public class Build {
private List<Part> parts;
}
public class Catalogue {
private List<Part> parts;
}
public class Part {
private String name;
private String type;
private double price;
}

The felds also have some additional requirements and strictures:

  1. Lists all have the abstract type of List<>, but must be instantiated with a concrete type that implements the List<> behaviour (you will see two of these in week 6, you can choose either you may also want to think about why you might do things this way).
  2. The type String in Part is stored in lowercase.

Constructors the constructors of the class have the following requirements:

  1. All constructors initialise the felds of their class.
  2. The ComputerBuilder constructor takes no parameters.
  3. The Catalogue constructor takes no parameters, but will add some initial Parts to the catalogue:
Name Type Price
evo 860 storage 155.
daskeyboard keyboard 239.
i5 cpu 365.
Corsair 16G memory 299.
ASUS ROG motherboard 159.
sheetmetal box case 39.
Ryzen 7 cpu 299.
  1. The Build constructor takes no parameters.
  2. The Part constructor takes three parameters, corresponding to the name, type and price, with the same types as the respective felds. toString() Catalogue, Build and Part will each have a toString() function, see the I/O trace and tests for the formats. The main method of the program will be in the ComputerBuilder class.

3. Expected workload

The time to do the assignment to a credit/distinction level has been estimated at 25 hours for a student of average ability who has completed all the tutorial and lab exercises.

4. Online support

The Assignment 1 discussion board has been set up on UTSOnline so that students can ask questions, and other students can reply. The course coordinator will only post a reply only if the student response was wrong, or in the case of correcting a mistake in the assignment specifcation.

You must not post or share java code to the discussion board. The board is there to help you, not to provide the solution. Posting your code is academic misconduct and will reported. Each time this rule is violated, the code will be removed and replaced with a comment of the form: Strike 1: Posting code. After 3 strikes, the discussion board will be deleted because it did not work.

FAQs (Frequently Asked Questions) and their answers will be posted on PLATE alongside the assignment specifcation. If you have a question, check the FAQ frst; it may already be answered there. You should read the FAQ at least once before you hand in your solution, but to be safe check it every couple of days. Anything posted on the FAQ is considered to be part of the assignment specifcation. The FAQ will be frozen (no new entries) two days before the due date; no questions will be answered after it is frozen.

If anything about the specifcation is unclear or inconsistent, contact the subject coordinator who will try to make it clearer by replying to you directly and posting the common questions and answers to the FAQ. This is similar to working on the job, where you ask your client if you are unsure what has to be done, but then you write all the code to do the task. Email [email protected] to ask for any clarifcations or corrections to the assignment.

5. PLATE marking

Your solution is marked for correctness by PLATE (https://plate.it.uts.edu.au/) by comparing the output of your system to the output of the benchmark system. You can submit a solution to PLATE many times; I urge you to do this, so you

receive credit for your work. Submission takes the same form as for the labs, you must package your assignment in a JAR fle, including the source code.

PLATE will test the features of your program in a certain order: Classes and felds, then constructors, then goals from basic to advanced. PLATE cannot test the more advanced goals until the basic goals are working. To receive marks, you must pass PLATEs test cases in the order in which PLATE tests them.

Your code is marked by software, so you can get a good mark by fooling or spoofng the software. If you spoof a task worth N marks, you receive a penalty of 2*N marks.

6. Submission and return

Your solution is to be submitted to PLATE at https://plate.it.uts.edu.au/ under Applications Programming / Assessments / Assignment 1, in the same manner as your labs package in a JAR fle including the source code. Your provisional mark and feedback is generated immediately each time you submit to PLATE. However, analysis of spoofng, plagiarism, collusion and general cheating is done in the two weeks following the due date. If you are suspected of Academic Misconduct, I will forward your case to the Misconduct Committee and will notify you by email.

There is no scheduled late submission period. An extension of up to one week may be given by the subject coordinator before the due date; you have to supply documentary evidence of your claim. An extension CANNOT be given after the due date.

You may also apply for special consideration for reasons including unexpected health, family or work problems. More information about how to apply for special consideration can be found at http://www.sau.uts.edu.au/assessment/consideration.html.

7. Marking scheme

The marks for the assignment are divided into the following functionality components (note that individual tests may test several functionality components, and a functionality component may be tested by several tests):

Functionality
Component
Mark
Allocation
Fields 7
Constructors 7
Main Menu 5
Catalogue Menu 5
Build Menu 5
Add Part to
Catalogue 5
Remove Part from
Catalogue 8
Filter by Type/Price/
Both 21
Add Part to Build 6
Remove Part from
Build 6
Check Validity of
Build 10
Clear Build/Start
New Build 5
Add Several Parts to
Build at Once 10

This adds to a mark out of 100, at makes up 30% of your fnal assessment mark.

代写Data Structures | 算法代做 | Algorithms | C代写 – Data Structures and Algorithms

代写Data Structures | 算法代做 | Algorithms | C代写 – 这是一个利用C语言进行BST搜索算法的任务,对时间复杂度有要求,属于比较典型的数据结构题目

Data Structures and Algorithms

######## LECTURE 26

Motivation

######## Organization and retrieval of information is at the heart of most computer

######## applications, and searching is the most frequently performed task

Searching
 If the array is not sorted, the search requires O( n ) time
If the value isnt there, we need to search all n elements
If the value is there, we search n /2 elements on average
 If the array is sorted, we can do a binary search
A binary search requires O(log n ) time
About equally fast whether the element is found or not
It doesnt seem like we could do much better
How about constant time search, O(1)?
We can do it if the array is organized in a particular way
Consider the problem of searching an array for a given value

######## Hashing is a technique used for performing insertions, deletions, and

######## searches in constant average time

######## Tree operations that require any ordering information among the elements

######## are not supported efficiently

######## The Data structure used is the hash table(a generalization of ordinary arrays)

oSeveral method of implementing the hash table
oCompare these methods
Hashing
Hash table

######## Given a table T and a record x (a record has a keyand an entry), we want to

######## support only the dictionary operations:

oInsert(T, x)
oDelete(T, x)
oSearch(T, x)

######## Goal

Fast operations without sorting the records beforehand
What is a table?

######## A table is simply another term for an array

It has several fields (i.e. types of information)
e.g., a telephone book has field name, field address, field phonenumber ,etc.
Smith 124 Moody St. 967 - 583 - 3322
White 1 South St. 781 - 222 - 1111
...
...

######## To find an entry in the table, you only need to know the content of one of

######## the fields (not all of them)

o This field is called key

######## Ideally, a key uniquely identifies an entry

Hash table big idea

######## Banking application

Imagine we have a file Account Info, and we want to be able to use a customers account
number to quickly (constant time) bring up their info
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier
We could use an array , of length 10,000, and simply use the account

######## numbers to index directly into the array

Direct-address table

######## Direct-address tables are ordinary arrays

######## Facilitate direct addressing

o Element whose key is k is obtained by indexing into the k thposition of the array

######## It is applicable when we can afford to allocate an array with one position for

######## every possible key

######## Insert/Delete/Search can be implemented to take O(1)time

####### 11/9/

Direct-address table

######## We have n elements that need to be stored

######## Universe U = {0, 1, …, m 1} of keys

 m >= n

######## Direct-address table

 T [0 ... m  1]
Each slot has a key k from K (actual keys used) in U
Empty slots contain NIL
254 Chapter 11 Hash Tables
11.1 Direct-address tables
Direct addressing is a simple technique that works well when the universeUof
keys is reasonably small. Suppose that an application needs a dynamic set in which

each element has a key drawn from the universeUDf0; 1; : : : ; m! (^1) g, wherem is not too large. We shall assume that no two elements have the same key. To represent the dynamic set, we use an array, or direct-address table ,denoted byT0::m! 1 , in which each position, or slot ,correspondstoakeyintheuni- verseU.Figure11.1illustratestheapproach;slotkpoints to an element in the set with keyk. If the set contains no element with keyk, thenTkDNIL. The dictionary operations are trivial to implement: DIRECT-ADDRESS-SEARCH.T; k/ 1 return Tk DIRECT-ADDRESS-INSERT.T; x/ 1 Tx: key Dx DIRECT-ADDRESS-DELETE.T; x/ 1 Tx: key DNIL Each of these operations takes onlyO.1/time. T (universe of keys) U K (actualkeys) 2 3 (^58) 1 9 4 0 7 6 2 3 5 8 key satellite data 2 0 1 3 4 5 6 7 8 9 Figure 11.1 How to implement a dynamic set by a direct-address tableT. Each key in the universe UDf0; 1; : : : ; 9gcorresponds to an index in the table. The setKDf2;3;5;8gof actual keys determines the slots in the table that contain pointers to elements. The other slots, heavily shaded, containNIL. Note: data does not have to be stored in an external object referenced from the slot in T. It can be just stored in the actual slot in T UUniverse of all possible keys KSet of keys actually stored in the table Account # Name 1345 Anderson 5076 Baker 0014 Cooper 2015 Dunhill 8428 Erickson 1007 Fourier

######## The disadvantageis that we could end up with a big array that has a lot of

######## empty space. This wastes lots of memory.

o The bigger we scale, the worse this problem gets (imagine if we used 9-digit account
numbers, and had only 10,000 customers
Direct-address table
Cons direct-address table

######## If U is large then a direct-address table T of size | U | is impractical or impossible

######## (considering memory)

oThe range of keys determines the size of T

######## The set K could be so small relative to U that most of the allocated space is

######## wasted

Direct-address table vs. Hash table
Direct-address table
o Element with key k is stored in slot k
Hash table
o Use hash function h ( k ) to compute the slot
Hash table big idea
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier

######## We can make the array smaller, and use the hash function to select which slot

######## we put our values into. For example the hash function = modulus function

######## Basically, we are compressing the domain of our keys so that they fit into the

######## array

0 1 2 3 4 5 6 7 8 9 10
Hash table big idea
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier
0 1 2 3 4 5 6 7 8 9 10
1345 mod 11 = 3
Anderson
h (k) = k mod m, where m is the size of your hash table
Hash table big idea
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier
0 1 2 3 4 5 6 7 8 9 10

5076 mod 11 = 5

Anderson Baker
Hash table big idea
Account # Name
1345 Anderson
5076 Baker
0014 Cooper
2015 Dunhill
8428 Erickson
1007 Fourier
0 1 2 3 4 5 6 7 8 9 10

0014 mod 11 = 3

Anderson Baker
Cooper

Hash Tables

######## The size of the hash table is proportional to | K |

oWe lose the direct-addressing ability
oWe need to define functions that map keys to slots of the hash table
Hash function definition

######## A hash function h transforms a key k into a number that is used as an index in

######## an array to locate the desired location (bucket or slot)

oAn element with key k hashes to slot h ( k )
o h ( k ) is the hash value of key k
o h maps all keys in K from universe U into the slots of the hash table T[0 ... m  1]

######## Hash function

oSimple to compute
oAny two distinct keys get different cells
oThis is impossible, thus we seek a hash function that distributes the keys evenly among the
cells

########

######## h : U { 0 , 1 ,…, m 1 }

####### 11/9/

Hash function
256 Chapter 11 Hash Tables
11.2 Hash tables
The downside of direct addressing is obvious: if the universeUis large, storing
a tableTof sizejUjmay be impractical, or even impossible, given the memory
available on a typical computer. Furthermore, the setKof keys actually stored
may be so small relative toUthat most of the space allocated forTwould be
wasted.
When the setKof keys stored in a dictionary is much smaller than the uni-
verseUof all possible keys, a hash table requires much less storage than a direct-
address table. Specifically, we can reduce the storage requirement to.jKj/while
we maintain the benefit that searching for an element in the hash table still requires
onlyO.1/time. The catch is that this bound is for the average-case time ,whereas
for direct addressing it holds for the worst-case time.
With direct addressing, an element with keykis stored in slotk.Withhashing,
this element is stored in sloth.k/; that is, we use a hash function hto compute the
slot from the keyk.Here,hmaps the universeUof keys into the slots of a hash
table T0::m! 1 :
hWU!f0; 1; : : : ; m! 1 g;
where the sizemof the hash table is typically much less thanjUj.Wesaythatan
element with keyk hashes to sloth.k/;wealsosaythath.k/is the hash value of
keyk.Figure11.2illustratesthebasicidea.Thehashfunctionreducestherange
of array indices and hence the size of the array. Instead of a size ofjUj, the array
can have sizem.
T
U
(universe of keys)
K
(actual
keys)
0
m 
k 1
k 2
k 3

k (^4) k 5 h ( k 1 ) h ( k 4 ) h ( k 3 ) h ( k 2 ) = h ( k 5 ) Figure 11.2 Using a hash functionhto map keys to hash-table slots. Because keysk 2 andk 5 map to the same slot, they collide.

######## The ideal hash table is an array of some fixed size m , containing items (keyand

######## additional entry)

######## Each key k is mapped (using a hash function) into some number in the range 0

######## to m 1 and places in the appropriate cell

######## Insertion of a new entry is O(1)

######## Lookup for data is O(1) on average

oStatistically unlikely that O( n ) will occur

######## Decide what to do when two keys hash to the same value ( collision )

######## Choose a good hash function

######## Choose the size of the table

Issues with Hashing
Division method
Maps key k into one of m slots by taking the remainder of k divided by m
o h ( k ) = k % m
oFor example, hash table size m = 12 and key k = 100 h ( k ) = 4

######## Reasonable strategy, unless the key happens to have some undesirable

######## properties

oFor example, if the table size is 10 and all of the keys end in 0
Hash Function

######## Finding a perfect hashing function is not always possible

######## A hash function maps most of the keys onto unique integers, but maps some

######## other keys onto the same integer

######## This is called collision

Hash Function

######## Multiple keys can hash to the same slot: collisions are unavoidable

######## Design a good hash function will minimizethe number of collisions that

######## occur, but they will still happen, so we need to be able to deal with them

######## Design collision-resolution techniques

Collisions

######## There are two basic policies to handle collisions:

o Chaining
Store all elements that hash to the same slot in a linked list
Store a pointer to the head of the linked list in the hash table slot
 Open addressing
All elements stored in hash table itself
When collision occur, use a systematic procedure to store elements in free slots of the table
Handling Collision

Assignment | Lab代写 | C++代写 – LAB C++

Assignment | Lab代写 | C++代写 – 这是一个简单的C++的lab代做任务,属于基础训练题目

LAB

Add the necessary code to the source file Payroll5.cpp , that reads and processes each line of input in the sequential input file payroll.txt. The lines of the file begin with a string with an embedded blank that should be interpreted as an employee name. After the name, the input line contains a single pound (#) character followed by 3 double values. These should be interpreted as an employees hourly salary, the number of hours that the employee has worked and the taxrate as a percentage that is used for that employee. After inputing the remaining data on the input line, your program should display formatted values of the input values followed by the employees gross salary (hours hourly, with time and one-half for the number of hours beyond 40) and the net salary (the gross salary minus the gross salary the taxrate/100). Upon reaching the end of the file, your program should display the total of all of the gross salaries and the total of all of the net salaries. All monetary amounts should be right justified and formatted to display 2 digits to the right of the decimal point. All output for this program should be displayed on the monitor and should be embedded within functions. The file Payroll5.cpp contains functions instructions() and reportTitle() that display a descriptive message and the column headings, respectively. In addition, the file should use functions calculateGross() to calculate the gross pay for each employee, calculateNet() to calculate the net pay for each employee, displayEmployeeInfo() to display the salary information for each employee and totalAmounts() to display the total gross and total net. Keep in mind that three of the six aforementioned functions have already been written for you.

You should compile, execute and examine the code in Payroll5.cpp to try and understand the use of the functions instructions() and reportTitle(). For this assignment and the next, well take advantage of the make command. This command uses a file named makefile that automates the compilation process of our program. It is especially useful for large programs that consist of multiple files and well be using it from here on in with our laboratories. Issue the following commands to compile your source code. make payroll5. This command will create an executable called payroll5 . To run your program enter the command payroll

A Sample run using the data in the file payroll.txt is shown below. To gain full credit for this lab, the output must be formatted as shown below

Make sure to upload your source file to directory labs/ Once your lab is uploaded and while logged into the server via a terminal session, traverse to the directory labs/ 5 . YOU MUST BE IN DIRECTORY 5 , TO SUBMIT YOUR LAB. Once you are ready to submit your lab issue the command _submit csc155abc 5 _ where abc is the course section number.