哈佛注释体系（Harvard System），也称为“作者－日期法”(Author-date method)。根据哈佛体系，每一个引文无论直接还是间接，都有两种引用方式需要注明：在文中引用处注明；在全书或全文最后的参考书目（bibliography）处注明。
1.当作者姓名在句子中自然出现时，给出作者的姓和出版年份，并将出版年份放在小括号内。比如，In a recent study Harvey （1993） argued that …。
2.当作者姓名不在句子中自然出现时，姓和出版年份都放在括号中，比如，A recent study (Harvey,1993） shows that…。
3.被引用的作者在同一年中出版了两部以上著作，或者发表了两篇以上的论文，用小写字母a、b、c等予以区别，并放在年份后面，如Johnson （1989a) discussed the subject…。
4.如果被引用的著作有两位作者，要将两位作者的姓同时给出，如Matthews and Jones （1992） have proposed that…。
5.如果有三位以上的作者，只需给出第一位作者的姓，再用斜体写上et al.（等人），如Wilson et al.（1993） conclude that…。
6.如果在文中直接引用其他作者(即原话照抄)，并且引文不超过两行，则直接插入文本中，并用引号将文本隔开。另外，英文文稿可用单引号也可用双引号，只要全文一致即可。最后，记得要在恰当的位置给出作者的姓和出版年份以及页码，比如，Aitchison （1981）,for example,points out that language is subject to change,and is not caused by “unnecessary sloppiness,laziness or ignorance” (p 16）.
Paine et al.（1983）added that good praise follows the “if-then” rule:
The “if-then rule” states that if the student is doing something you want
to encourage—something you want to see the student do again or do
more often in the future (and if you are sure that that is what the student
is doing）—then (and only then) you should praise the student for it(p.46）. 
比如，White,R.（1988）. Advertising: What it is and How to do it. 2nd ed. London: McGrawhill.
作者姓、名的首字母大写，（出版年份），章节标题，In: 主编名首字母大写，姓，ed. 或者eds. 书名，再版著作注明版次，丛书注明卷次，出版地：出版商，出版年份，论文所在页码。
如，Wright,P.（1986）. Reactions to an Ads contents versus judgments of Ads impact. In: J. Olsen,& K. Sentis,eds. Advertising and consumer psychology. Vol.3. New York: Praeger,1986,108-117.
如，Greco,A.J.,& Swayne,L.D. （1992）. Sales response of elderly customers to point-of-purchase advertising. Journal of Advertising Research,32 ⑸，43-63.
作者姓、名首字母大写，（年份），论文题目，In: 会议文集主编名首字母大写，姓，ed. 或eds. 文集名，会议地点，时间，出版地：出版商，论文所在页码。
如，Silver,K.（1989）. Electronic mail: the new way to communicate. In: D.I. Raitt,ed. 9th international online information meeting,London 3-5 December 1988. Oxford: Learned Information,323-330.
如，Independent Television Commission.（1991）. The ITC code of advertising standards and practice. London: ITC.
作者姓、名首字母大写，（日期），题目，[在线]，（编辑、版次），出版地： 出版商，网站名： [下载时间]。
如，Holland,M. （1996）. Harvard system [online]. Poole,BournemouthUniversity.Available from：
参考文献的注释规范是学术研究人员应共同遵守的行为准则，目前全球各种语言的注释规范不尽统一，仅英文的注释规范就有哈佛体系（Harvard system）、英国标准（British Standard BS 5605）、APA（The American Psychological Association）方式、MHRA（The Modern Humanities Research Association）方式、MLA（The Modern Language Association）方式等。无论我们使用哪种注释，重要的是在一篇文献里前后应保持一致，即使是哈佛体系，在使用时也有些许的变化，比如在参考书目处作者姓和名的首字母缩写之后的出版日期，有的用小括号，而有的却不用；对于期刊和论文集中收集的论文题目，有的用单引号，有的却用双引号；当一本书有多位作者时，有的给出最多两位作者的姓，有的却给出最多三位作者的姓。另外，有些学术刊物也有自己的注释规范，当我们要想投稿时，需要特别注意这类特定刊物的具体要求。不过，无论怎么注释，最基本的一条是必须有注释，否则，这就不仅仅是学术规范的问题，而是学术道德层面的问题了。
Clearing为最终补录阶段，从8月份开始，到8月末结束。在此期间，如果小伙伴们没有获得任何offer，或者拒绝了所有offer，可以向学校clearing部分打电话询问是否专业有空缺，如果学校对此学生感兴趣，则会提供给学生clearing number，之后学生可凭借clearing number进行申请。但是每次只能添加一所，如被拒绝，则可无限重复添加，直至8月末。
In this homework, you’ll be building a shell, similar to the Bash shell you use on your CS 162 Virtual Machine. The purpose of a shell is to allow users to run and manage programs. The operating system kernel provides well-documented interfaces for building shells. By building your own shell, you’ll become more familiar with these interfaces and you’ll probably learn more about other shells as well.
Log in to your Vagrant Virtual Machine and run:
$ cd ~/code/personal/
$ git pull staff master
$ cd hw1
We have added starter code for your shell and a simple Makefile in the hw1 directory. It includes a string tokenizer, which splits a string into words. In order to run the shell:
In order to terminate the shell after it starts, either type exit or press CTRL-D.
Add support for cd and pwd
The skeleton code for your shell has a dispatcher for “built-in” commands. Every shell needs to support a number of built-in commands, which are functions in the shell itself, not external programs. For example, the exit command needs to be implemented as a built-in command, because it exits the shell itself. So far, the only two built-ins supported are ?, which brings up the help menu, and exit, which exits the shell.
Add a new built-in pwd that prints the current working directory to standard output. Then, add a new built-in cd that takes one argument, a directory path, and changes the current working directory to that directory.
Once you’re done, push your code to the autograder. In your VM:
$ git add shell.c
$ git commit -m "Finished adding basic functionality into the shell."
$ git push personal master
You should commit your code periodically and often so you can go back to a previous version of your code if you want to.
If you try to type something into your shell that isn’t a built-in command, you’ll get a message that the shell doesn’t know how to execute programs. Modify your shell so that it can execute programs when they are entered into the shell. The first word of the command is the name of the program. The rest of the words are the command-line arguments to the program.
For this step, you can assume that the first word of the command will be the full path to the program. So instead of running wc, you would have to run /usr/bin/wc. In the next section, you will implement support for simple program names like wc. But you can pass some autograder tests by only supporting full paths.
You should use the functions defined in tokenizer.c for separating the input text into words. You do not need to support any parsing features that are not supported by tokenizer.c. Once you implement this step, you should be able to execute programs like this:
0: /usr/bin/wc shell.c
77 262 1843 shell.c
When your shell needs to execute a program, it should fork a child process, which calls one of the exec functions to run the new program. The parent process should wait until the child process completes and then continue listening for more commands.
You probably found that it was a pain to test your shell in the previous part because you had to type the full path of every program. Luckily, every program (including your shell program) has access to a set of “environment variables”, which is structured as a hashtable of string keys to string values. One of these environment variables is the PATH variable. You can print the PATH variable of your current environment on your Vagrant VM: (use bash for this, not your homemade shell!)
$ echo $PATH
When bash or any other shell executes a program like wc, it looks for a program called “wc” in each directory on the PATH environment variable and runs the first one that it finds. The directories on the path are separated with a colon.
Modify your shell so that it uses the PATH variable from the environment to resolve program names. Typing in the full pathname of the executable should still be supported. Do not use “execvp”. The autograder looks for “execvp”, and you won’t receive a grade if that word is found. Use execv instead and implement your own PATH resolution.
When running programs, it is sometimes useful to provide input from a file or to direct output to a file. The syntax “[process] > [file]” tells your shell to redirect the process’s standard output to a file. Similarly, the syntax “[process] < [file]” tells your shell to feed the contents of a file to the process’s standard input.
Modfiy your shell so that it supports redirecting stdin and stdout to files. You do not need to support redirection for shell built-in commands. You do not need to support stderr redirection or appending to files (e.g. “[process] >> [file]”). You can assume that there will always be spaces around special characters < and >. Be aware that the “< [file]” or “> [file]” are NOT passed as arguments to the program.
Signal Handling and Terminal Control
Most shells let you stop or pause processes with special key strokes. These special keystrokes, such as Ctrl-C or Ctrl-Z, work by sending signals to the shell’s subprocesses. For example, pressing CTRL-C sends the SIGINT signal which usually stops the current program, and pressing CTRL-Z sends the SIGTSTP signal which usually sends the current program to the background. If you try these keystrokes in your shell, the signals are sent directly to the shell process itself. This is not what we want since, for example, attempting to CTRL-Z a subprocess of your shell will also stop the shell itself. We want to have the signals affect only the subprocesses that our shell creates.
Before we explain how you can achieve this effect, let’s discuss some more operating system concepts.
We have already established that every process has a unique process ID (pid). Every process also has a (possibly non-unique) process group ID (pgid) which, by default, is the same as the pgid of its parent process. Processes can get and set their process group ID with getpgid(), setpgid(), getpgrp(), or setpgrp().
Keep in mind that, when your shell starts a new program, that program might require multiple processes to function correctly. All of these processes will inherit the same process group ID of the original process. So, it may be a good idea to put each shell subprocess in its own process group, to simplify your bookkeeping. When you move each subprocess into its own process group, the pgid should be equal to the pid.
Every terminal has an associated “foreground” process group ID. When you type CTRL-C, your terminal sends a signal to every process inside the foreground process group. You can change which process group is in the foreground of a terminal with “tcsetpgrp(int fd, pid_t pgrp)”. The fd should be 0 for “standard input”.
Overview of signals
Signals are asynchronous messages that are delivered to processes. They are identified by their signal number, but they also have somewhat human-friendly names that all start with SIG. Some common ones include:
1.SIGINT - Delivered when you type CTRL-C. By default, this stops the program.
2.SIGQUIT - Delivered when you type CTRL-. By default, this also stops the program, but programs treat this signal more seriously than SIGINT. This signal also attempts to produce a core dump of the program before exiting.
3.SIGKILL - There is no keyboard shortcut for this. This signal stops the program forcibly and cannot be overridden by the program. (Most other signals can be ignored by the program.)
4.SIGTERM - There is no keyboard shortcut for this either. It behaves the same way as SIGQUIT.
5.SIGTSTP - Delivered when you type CTRL-Z. By default, this pauses the program. In bash, if you type CTRL-Z, the current program will be paused and bash (which can detect that you paused the current program) will start accepting more commands.
6.SIGCONT - Delivered when you run fg or fg %NUMBER in bash. This signal resumes a paused program.
7.SIGTTIN - Delivered to a background process that is trying to read input from the keyboard. By default, this pauses the program, since background processes cannot read input from the keyboard. When you resume the background process with SIGCONT and put it in the foreground, it can try to read input from the keyboard again.
8.SIGTTOU - Delivered to a background process that is trying to write output to the terminal console, but there is another foreground process that is using the terminal. Behaves the same as SIGTTIN by default.
In your shell, you can use kill -XXX PID, where XXX is the human-friendly suffix of the desired signal, to send any signal to the process with process id PID. For example, kill -TERM PID sends a SIGTERM to the process with process id PID.
In C, you can use the signal function to change how signals are handled by the current process. The shell should basically ignore most of these signals, whereas the shell’s subprocesses should respond with the default action. Beware: forked processes will inherit the signal handlers of the original process. Reading man 2 signal and man 7 signal will provide more information. Be sure to check out the SIG_DFL and SIG_IGN constants. For more information about how signals work, please work through the tutorial here.
Your task is to ensure that each program you start is in its own process group. When you start a process, its process group should be placed in the foreground. Stopping signals should only affect the foregrounded program, not the backgrounded shell.
So far, your shell waits for each program to finish before starting the next one. Many shells allow you run a command in the background by putting an “&” at the end of the command line. After the background program is started, the shell allows you to start more processes without waiting for background process to finish.
Modify your shell so that it runs commands that end in an “&” in the background. You only need to support background processing for programs, not built-in commands. Once you’ve implemented this feature, you should be able to run programs in the background with a command such as “/bin/ls &”.
You should also add a new built-in command wait, which waits until all background jobs have terminated before returning to the prompt.
You can assume that there will always be spaces around the & character. You can assume that, if there is a & character, it will be the last token on that line.
Optional: Foreground/Background Switching
Most shells allow for running processes to be toggled between running in the foreground versus in background. You can optionally add two built-in commands to support this:
1.“fg [pid]” – Move the process with id pid to the foreground. The process should resume if it was paused. If pid is not specified, then move the most recently launched process to the foreground.
2.“bg [pid]” – Resume a paused background process. If pid is not specified, then resume the most recently launched process.
You should keep a list of all programs you’ve started, whether they are in the foreground or background. Inside this list, you should also keep a “struct termios” to store the terminal settings of each program.
1.Be sure your code follows the coding style for CSE214.
2.You are not allowed to use LinkedList, ArrayList, Vector or any other Java API Data Structure classes to implement this assignment except where noted.
3.You may use Scanner, InputStreamReader, or any other class that you wish for keyboard input.
In this homework assignment you will be building a trip planner for road trips. You will be modelling a road trip as a linked list of stops, with each stop having a distance to travel, a location, and an activity. There are two itineraries (so that you can plan two trips, or make two versions of the same trip), and they should be completely independent (ie: modifying one should not cause the other to change). This means that a deep copy must be made each time the itinerary is copied from one itinerary to the other.
NOTE: All exceptions explicitly thrown in Required Classes except for IllegalArgumentException are custom exceptions that need to be made by you.
TripPlanner (Driver Class)
1.public static void main(String args)
2.Runs the User interface menu as shown in Required Functions
3.Can be changed as necessary for GUI/Android App
4.This method will contain two Itinerary objects for cloning.
1.private TripStopNode head
2.private TripStopNode tail
3.private TripStopNode cursor
The above variables will hold links into a doubly linked list of TripStopNodes where each node links to the previous and next ones, or nulls if there are none.
Constructor: initializes an empty itinerary with no elements – head, tail, and cursor are set to null.
2.public int getStopsCount()
Returns the total number of TripStopNodes in the Itinerary.
This method must run in O(1) time.
3.public int getTotalDistance()
Returns the sum of distances over all TripStopNodes.
This method must run in O(1) time.
4.public TripStop getCursorStop()
Returns a reference to the TripStop wrapped by the TripStopNode that cursor points to.
If cursor is null, this returns null.
5.public void resetCursorToHead()
Returns the cursor to the start of the list.
If head is not null, the cursor now references the first TripStopNode in this list.
If head is null, the cursor is set to null as well (there are no TripStop objects in this list).
6.public void cursorForward()
Moves the cursor to select the next TripStopNode in this list. If cursor == tail, throw an exception.
EndOfItineraryException - Thrown if cursor is at the tail of the list.
7.public void cursorBackward()
Moves the cursor to select the previous TripStopNode in this list. If cursor == head, throw an exception (this includes the case where cursor and head are both null).
EndOfItineraryException- Thrown if cursor is at the head of the list.
8.public void insertBeforeCursor(TripStop newStop)
Inserts the indicated TripStop before the cursor.
The TripStop object to be wrapped and inserted into the list before the cursor.
newStop is not null.
newStop has been wrapped in a new TripStopNode object
If cursor was previously not null, the newly created TripStopNode has been inserted into the list before the cursor.
If cursor was previously null, the newly created TripStopNode has been set as the new head of the list (as well as the tail).
The cursor now references the newly created TripStopNode .
Thrown if newStop is null.
You should NOT move data references around between TripStopNodes to accomplish this method. Instead, you should wrap the TripStop object in a new TripStopNode object, and insert this object into the list before the cursor.
9.public void appendToTail(TripStop newStop)
Inserts the indicated TripStop after the tail of the list.
The TripStop object to be wrapped and inserted into the list after the tail of the list.
newStop is not null.
newStop has been wrapped in a new TripStopNode object
If tail was previously not null, the newly created TripStopNode has been inserted into the list after the tail.
If tail was previously null, the newly created TripStopNode has been set as the new head of the list (as well as the tail).
The tail now references the newly created TripStopNode.
Thrown if newStop is null.
This insertion method does not affect the cursor, unless the list was previously empty. In that case, head, tail, and cursor should all reference the new TripStopNode.
10.public TripStop removeCursor()
Removes the TripStopNode referenced by cursor and returns the TripStop inside.
cursor != null
The TripStopNode referenced by cursor has been removed from the list.
All other TripStopNodes in the list exist in the same order as before.
The cursor now references the previous TripStopNode
Exceptions: If the cursor was originally the head, the cursor will now reference the current head.
The TripStop that was removed
EndOfListException if cursor is null.
1.private TripStop data
2.private TripStopNode next
3.private TripStopNode prev
4.public TripStopNode(TripStop initData)
initData - The data to be wrapped by this TripStopNode. This parameter should not be null, since we should never have a TripStopNode with null data (remember, this class serves only as a wrapper for the TripStop class).
initData is not null.
This TripStopNode has been initialized to wrap the indicated TripStop, and prev and next have been set to null.
Thrown if initData is null.
5.public TripStop getData()
Returns the reference to the data member variable of the list node.
6.public void setData(TripStop newData)
Sets the data private field to the one passed as a parameter.
newData - Reference to a new TripStop object to update the data member variable. This parameter must not be null, since we should never have a TripStopNode with null data (remember, this class serves only as a wrapper for the TripStop class).
newData is not null.
IllegalArgumentException - Thrown if newData is null.
7.public TripStopNode getNext()
Returns the reference to the next member variable of the list node. Can be null, means there’s no next TripStopNode.
8.public void setNext(TripStopNode newNext)
Updates the next member variable with a new TripStopNode reference.
newNext - Reference to a new TripStopNode object to update the next member variable. This parameter may be null, since it is okay to have no next TripStopNode (this means we’ve reached the tail of the list!).
9.public TripStopNode getPrev()
Gets the reference to the prev member variable of the list node.
The reference of the prev member variable. Note that this return value can be null, meaning that there is no previous TripStopNode in the list. (this means we’ve reached the head of the list!).
10.public void setPrev(TripStopNode newPrev)
Updates the prev member variable with a new TripStopNode reference.
newPrev - Reference to a new TripStopNode object to update the prev member variable. This parameter may be null, since it is okay to have no previousTripStopNode (this means we’ve reached the head of the list!).
This class contains private data fields for Location (String), Distance (int), and Activity (String). This class is mutable, so there are getters and setters for all private data fields.
If distance is less than 0, throw an IllegalArgumentException
While you must have a default constructor, you are encouraged to make an overloaded constructor taking all 3 fields as parameters (this is not required).
You might want to implement a toString() method for TripStop, TripStopNode, and Itinerary to make debugging and printing easier. You do not have to do this, but it will help you.
You can feel free to add extra private methods if you need, but if you want to add a public method, check on the discussion board first.
UI Required Functions
The menu should have options similar to these, and NOT be case sensitive.
I-Insert before cursor
Secondary menu asking for Location, Distance, Activity (in that order)
A-Append to tail
Secondary menu asking for Location, Distance, Activity (in that order)
D-Delete and move cursor forward
H-Cursor to Head
T-Cursor to Tail
Secondary menu asking for edits to Location, Distance, Activity (in that order, see sample)
O-Insert cursor from other itinerary before cursor from this itinerary (via cloning)
R-Replace this itinerary with a copy of the other itinerary
P-Print current itinerary, including summary (see sample)
C-Clear current itinerary
All lists must be printed in a nice and tabular form as shown in the sample output. You may use Java style formatting as shown in the following example. The example below shows two different ways of displaying the name and address at pre-specified positions 21, 26, 19, and 6 spaces wide. If the ‘-’ flag is given, then it will be left-justified (padding will be on the right), else the region is right-justified. The ‘s’ identifier is for strings, the ‘d’ identifier is for integers. Giving the additional ‘0’ flag pads an integer with additional zeroes in front. See here for more details.
String name = "Doe Jane";
String address = "32 Bayview Dr.";
String city = "Fishers Island, NY";
int zip = 6390;
System.out.println(String.format("%-21s%-26s%19s%06d", name, address, city, zip));
System.out.printf("%-21s%-26s%19s%06d", name, address, city, zip);
All labs and assignments for this course will be done on A Unix environment. You will need to log in and access your account there. If you do not have an account in the Lab, you must go see ITSS. If you do not have an account, please send me an email with your full name and student number so that I can create an account for you (or have one created). You may use any software you like to access the OS machine (E.g., putty, x2go, cygwin).
To continue developing your skills in C programming you are to write a program called glue that does exactly the same thing as the Unix join command. The utility join combines the lines of two files based on the presence of a common word. For details on join you can use the man command:
tami@os:~$ man join
You do not need to implement any of the command line options, but you should perform suitable error checking (e.g., 3 command line arguments, both files exist and are readable). For additional explanation and some examples of operation, please see:
However, because there is a working join command on OS, you can learn how it works by creating data files and then trying to join them. For testing purposes, you can verify your program’s correctness by using both glue and join and then checking that they produce identical results. All source code must be written from scratch. You are not permitted to download any code and use it as a part of your solution, though you may reuse code you have written for lab 0.
To submit your work you do not have to do anything. The marker will have access to your directories on OS and will simply enter them, check the timestamps, and mark work that is timestamped BEFORE the submission deadline. Your assignment must be in your home directory in a sub-directory named lab1 (all lower case). The OS machine is explicitly for performing assignments in the operating systems course. You have no privacy on this machine as the marker, administrator, and instructor can enter your directories, view your running programs, and examine your files.
Space on the machine is minimal, so do not store any files that are not directly related to your operating systems assignments.
Marking will ONLY be performed on code that executes. Your code will be marked with regard to format, clarity, readability, and efficiency. Please prioritise simplicity ahead of efficiency. That is, I want to see clean, easy-to-read code, more than efficient but complicated and confusing code. However, do not sacrifice efficiency when a clear, easy-to-understand improvement is possible.
英国it课程补习范文精选：“分布式计算”，这篇论文主要介绍了如何通过分布式计算来解决出现的Fake code等一系列问题。文章通过假设数据，编写了一系列的Map和Reduce函数，接着进行了多次的chain MapReduce，最终得出了与之相对应的结果。
Today, almost all professional sports teams (e.g., NFL, NBA, MLB, NHL, MLS, etc.) use distributed computing to analyze games, give feedback to players (sometimes in real time), and to decide whom to trade and when.
This homework uses fictitious stories and characters from sports teams to frame the homework problems. Any resemblance to persons, places, things, or events, living or dead, past, present, or future, is purely coincidental. These stories and this homework is aimed neither at endorsing, nor criticizing, any league, any sports team or persons associated with these teams or leagues.
1.The Chicago Bears would like to increase their Twitter presence. As a warm up exercise they wish to find pairs of interested users on social media. They would like to use MapReduce for this. In MapReduce, one writes a program for Map that processes one input line at a time and outputs a (key, value) or nothing; and one writes a program for Reduce that processes an input of (key, all values for key). The iteration over input lines is done automatically by the MapReduce framework. You are given an input file containing information from an asymmetrical social network (e.g., twitter) about which users “follow” which other users. If user a follows b, the entry line is (a, b). Write a MapReduce program (Map and Reduce separately) that outputs all pairs of users (a,b) who follow each other. You don’t need to write code - pseudocode is fine as long as it is understandable. Hint: Think about the “key” in Map output.
2.The Green Bay Packers laugh at the Chicago Bears and decide to one-up them by finding triples (instead of pairs). You are given an input file containing information from an asymmetrical social network (e.g., twitter) about which users “follow” which other users. If user a follows b, the entry line is (a, b). Write a MapReduce program (Map and Reduce separately) that outputs all “triples”, i.e., sets of users (a,b,c) such that a follows b, b follows c, and c follows a (there might be other follows-relationships among the triple). You can chain Mapreduces if you want (but only if you must, and even then, only the least number). Be sure to output each triple at most once (e.g., in sorted order). You don’t need to write code – pseudocode is fine as long as it is understandable. Hint: Think about the “key” in Map output.
3.But LeBron James snickers at both the above teams and says he by himself is more popular than either of those teams (it’s true! @KingJames has 32 M Twitter followers!). King James would like to know who are the Twitter users most similar to him, and would like to use Hadoop for this. There is an input file containing information from Twitter (which is an asymmetrical social network) about which users “follow” which other users. If user a follows b, the entry line is (a, b) – you can assume this data is already sharded HDFS and can be loaded from there. Write a MapReduce program (Map and Reduce separately) that outputs the list of all users U who satisfy the following three conditions simultaneously: U has at least a million followers, and U herself/himself follows at least 10 users, and U follows at least one user V who in turn has at least a million followers (e.g., @KingJames satisfies this). You can chain Mapreduces if you want (but only if you must, and even then, only the least number). Your program must be as highly parallelizable as possible.
4.The NE Patriots team has had too many injuries, so they decide to design a failure detector. A cornerback has designed a failure detection protocol that is a modified ring failure detection protocol. It works as follows: each process i selects k other processes at random and asks these k processes to send it (i) heartbeats directly. Heartbeats are not relayed (so this is not gossip, but more like ring failure detection), and process i times out if it doesn’t receive heartbeats.
a. The quarterback (Tom Brady himself) claims that this algorithm provides completeness up to (k-1) failures. Is he right? If yes, argue why (informal proof). If no, give a counter-example, and also state what completeness the algorithm does provide.
b. The running back (of the day) in the team claims this algorithm satisfies accuracy. Are they right? If yes, argue why (informal proof). If no, give a counter-example, and also state what kind of accuracy the algorithm does provide.
5.The Chicago White Sox have N players (processes) where you are guaranteed to not to have more than N/3 failures (no new processes join; processes just fail). What is the least amount of memory a heartbeat-based membership protocol can use so that it satisfies completeness? Prove that your algorithm has completeness.
6.The Chicago Bulls decide that like they don’t need Derrick Rose, gossip protocols don’t need all processes either in their membership lists. So they decide to build a membership protocol (for a system of N processes) where each process has a membership list of size k. The membership list at each process is selected uniformly at random across the entire group (somehow, the messages take care of it – don’t worry about the protocol part). Each message is gossiped to m randomly selected neighbors (from the membership list), where m < k, and m = O(log(N)), with the latter needed to ensure spread of gossip. The new Bulls’ point guard argues that due to random selection, the overall “behavior” of this protocol (in terms of dissemination time of gossips, etc.) is the same as in the case where all processes might have had full membership lists (known everyone in the group), and each gossip was sent to m neighbors. Is he right? If yes, then give a proof. If no, show why.
7.The new manager and coach of the LA Lakers team feel the rest of country is too disconnected from their team (after Kobe’s retirement). He wants to connect all Lakers fans together using a P2P system, and have it be topologically aware. Design a variant of Chord that is topology-aware and yet preserves the O(log(N)) lookup cost and O(log(N)) memory cost. Use examples or pseudocode - whatever you chose, be clear! Make the least changes possible. Hint: Try to change only the finger selection algorithm, but not the routing. Show that (formal proof or informal argument):
a. Lookup cost is O(log(N)) hops.
b. Memory cost is O(log(N)).
c. The algorithm is significantly more topologically aware than Chord, and almost as topology aware as Pastry.
8.Someone smart on the Pittsburgh Penguins NHL team (after all, they won the Stanley Cup in 2016!) designs a new P2P DHT called “AHDHT” (A Hop DHT) where all peers know the addresses of all peers.
a. How would you build this design so that any file can be fetched from any peer in just 1 hop.
b. Someone proposes sending all join/leave/fail requests immediately to all other processes in the DHT, in order to keep all membership lists always fresh (thus all lookups would be correct). Given your design from (a), and a churn rate of 100% per hour, what is the amount of bandwidth necessary to keep all membership lists up to date in a system containing 1 million peers? (That is, we want each membership change to be instantly reflected in all membership lists). Is this bandwidth tenable in a Wide Area Network today?
c. You decide to use gossip-based membership, where each entry has an IPv6 address, a port number, a gossip count (int with 4 bytes), and a last updated time (UTC time). You have only 2 GB to store the membership list. How large can the P2P system be in size?
9.In order to have their players share team videos with each other (but not during the game, because that would be illegal!), the Indianapolis Colts decide to use a peer to peer system. They use the Gnutella system. At one point of time, the Gnutella topology looks like a virtual ring with 12 processes, with each process connected to its immediate three clockwise neighbors and immediate three anticlockwise neighbors (thus each process has six neighbors). All links are bidirectional. Answer three parts:
a. A process sends a Query message with TTL=3. How many of the processes receive this Query message?
b. What is the minimum TTL in a Query message to ensure all nodes in the system receive the Query?
c. If we add a 13 th process (the coach) that is connected to all the 12 processes, what is the minimum TTL in a Query message to ensure all nodes in the system receive the Query?
10.In order to win their next championship (after the century-plus drought) the Chicago Cubs realize they need to stop losing fans. They decide that they need to get their fans excited. They decide to use a Chord-like peer to peer system to connect the mobile phones of their fans with each other. The players also start using this system - after a particular game, the players’ mobile phones are in a Chord ring using m = 12, nodes with the following peer ids (or node ids) join the system: 1908, 1910, 1920, 1930, 1940, 2000, 2014, 2015, 2016. Then, answer the following questions:
a. Show or list all finger table entries for node 1910.
b. When all finger tables and successors have converged, show the path taken by a search (or query) message originating from node 1908 intended for the key 2015.
c. Node 2015 fails. List all the nodes whose finger tables need to be updated.
Server – S
Clients – C1, C2, C3, C4, C5
Initial setup: pwd.txt must contain C1, C2, C3 and C5’s password information. C4 is a first time user.
Assume no groups or clients are stored on server at this point.
Log in and Sign up
C1, C2, C3 and C5 log in. This will happen from 4 different chat windows.
C4 must sign up and create a new account (i.e., its host name/pwd pair must be added to pwd.txt file)
Visibility and dropdown lists
C2 and C3 set themselves to be invisible.
Available clients list is populated with C1, C4 and C5 (as C2 and C3 are invisible). This means that only C1, C4 or C5 can receive unicast messages.
Group creation and joining
C1 creates a group called G1. G1 must become visible to all logged in clients. When G1 is selected, all members of G1 must be listed somewhere on the side. At this point, it must only list C1.
C2 and C4 join group G1. Now if G1 is selected, all members of G1 must be listed somewhere on the side. At this point, it must list C1, C2 and C4.
Note: C2 set itself to be invisible. This means it will not be listed in the available clients list. However, it will be listed when its group is selected. The only way to send messages to C2 is by joining the group G1. You cannot send unicast or broadcast messages to C2.
C5 creates a group called G2.
C1 and C3 join group G2.
The list of available groups must now show G1 and G2.
Unicast, multicast and broadcast
C1, C2 and C4 can receive multicast messages but only from one another.
C1, C3 and C5 can receive multicast messages but only from one another.
Any client (even the invisible clients) can send a broadcast message but it will be received by C1, C4 and C5 (the visible clients).
Unicast messages can be sent to the listed available clients: C1, C4 or C5.
Leaving groups/Logging out
C2 leaves the group G1. It will no longer be listed as a client in the group G1.
C1 logs out. It will no longer be listed as a client in the group G1. Also, it will be removed from the available clients list.
Note: A group is not dissolved when the creator of the group leaves it or logs out. A group is dissolved if the last member of the group leaves it or logs out.
C4 logs out. C4 was the last member of group G1. G1 will be dissolved at this point.
Server will have to maintain separate lists in order to determine who to send unicast, multicast or broadcast messages.
英国代写code范文精选：“Computational Geometry基础算法”，这篇论文主要介绍了Computational Geometry的基础算法。文章指出，关于Computational Geometry基础算法Convex Hull的Lab作业，可按照书上的Fake code，再用任意语言编写即可。
1.Your solution must be electronically submitted.
2.This programming assignment must be solved individually.
3.You can code your solution in Matlab, C/C++, or Java. The choice is up to you. But you have to properly document your submission to explain how your program can be compiled and run. Important: if you solve your assignment in C/C++, it must compile with gcc. Other languages will not be accepted. Do not include solutions depending on the availability of IDEs (e.g., Eclipse or similar). If you use C/C++ or java, please provide instructions to compile your code from the command line.
4.Submissions that do not compile will receive 0 points without further consideration.
5.Your code will be closely inspected to see whether you followed the algorithm presented in class. Solutions not following the algorithm presented in class will receive 0 points.
Implement the algorithm to compute the convex hull of n points in the plane. Your code should print to the screen the points in the convex hull in clockwise order, starting from the leftmost point (one point per line). The input to the algorithm is a text file called input.txt where the input points are given one per line. For example, if the file input.txt is as follows:
your solution should print to the screen the following:
1.your solution must be able to handle inputs of arbitrary size (i.e., you do not know beforehand how many rows are in input.txt);
2.your code must be able to handle special cases, including collinear points, empty inputs, and possible repetitions on the input (i.e., the same point appearing more than once);
3.your code will be tested against various test cases and must work correctly on all of them.