University of LeedsSchool of Computing
Procedural Programming XJCO1711
Semester 1, 2019-2020
Coursework 3
80 Marks
(40% of the total module marks)
Submission Deadline
This coursework must be uploaded to Minerva before 10am on Friday 20/12/2019
Late Penalties
5% will be deducted from your overall mark for every late day.
Skills Tested
This coursework tests your ability to use character strings, structures, and pointers. It also tests your ability to implement functions, process arrays, declare and use local variables, use assignment, conditional execution, and iteration statements.
The Brief
You will write a program to help a social network company understand how fake news can spread across the network and find ways to restrict the dissemination of fake news.
The Details
Social networks
A social network is a group of users connected to each other with friendship relations as shown in Figure 1. To join a social network a person must first create an account then add some friends to this account.
Instant messaging and fake news
Many social networks allow users to send instant messages to their friends. The recipient of a message can in turn forward it to their friends.Because of the interconnected nature of the network, a story can quickly spread across the entire network and become viral. A viral story can be received multiple times from different sources and can even return to the originator of the story. This powerful feature of social networks is sometimes exploited by malicious entities to spread fake news. Many social network companies are trying to implement measures to restrict the propagation of fake news such as:
Employing human or automated agents to detect and block fake stories.
Restricting the number of accounts to which a message can be forwarded in one go. For example, WhatsApp has limited message forwarding to five contacts only [1].
Allow anyone to report fake or offensive stories to the social network company.
Figure 1. A social network is a group of users connected to each other with friendship relations.
The task
You will write a program to simulate the dissemination of news, both real and fake, across a social network. The data structures required for the solution, as well as all the function prototypes have been defined for you in the provided header and template files.
Account types
We will assume that there are five types of accounts in a social network:
Real news publishers. These accounts publish real news stories. To spread the news, real news publishers send the genuine story to all of their friends, who in turn may forward the story to other people. For simplicity, we assume that real news publishers do not forward any stories they receive even if they are genuine ones.
Fake news fabricators. These are the evil guys who fabricate fake news stories and set them off across the network.To spread fake news, fabricators send the fake story to all of their friends, who in turn may forward the story to other people. For simplicity, we assume that fake news fabricators do not forward the stories they receive even if they are fake stories including their own fabrications if it ever comes back to them.
Nave forwarders. These guys are the nave people who forward any stories they receive from anyone to all of their friends without trying to verify if the story is genuine or not. We assume that nave forwarders do not originate any new stories.
Fake news sinks. These are the good guys who verify any story they receive. If the story turns out to be fake, they simply ignore it and refrain from forwarding it to anyone (hence the name sink). If the story is genuine, they forward it to all of their friends. We assume that fake news sinks do not originate any stories.
Fake news reporters. These are the angels of the social network. They dont only verify the stories they receive and refrain from forwarding fake ones, but they also report fake stories to the social network company. The social network company would then be able to block these stories and stop them from being transmitted across the network.
The news.h file contains a #define directive for each of the above types:
#define RealNewsPublisher1
#define FakeNewsFabricator 2
#define NaiveForwarder 3
#define FakeNewsSink 4
#define FakeNewsReporter 5
Accounts
An account in the social network is defined by the following structure:
typedef struct AccountStruct
{
int accId;// a unique id for this account
char accName [MaxNameSize];// the name of this account
int accType;// the type of this account (an integer from 1-5)
struct AccountStruct* Friends [MaxFriends]; // array of pointers to the friends of this account
int numFriends;// the number of friends of this account
Message receivedM [MaxMessageArraySize]; // an array for storing received messages (an inbox)
int numberReceivedM;// the number of messages in the receivedM array
Message sentM [MaxMessageBuffer];// an array for storing sent messages
int numberSentM;// the number of messages in the sentM array
} Account;
The purpose of each field in the Account structure is as follows:
accId: A unique integer id for this account. This is required because account names are not necessarily unique.
accName: The name of the account. We will assume that an account name is comprised of 4 letters and has the following pattern CVCV, where C is any consonant and V is any vowel, examples of valid account names include NINA, DALA, TITO, KARI etc
accType: The type of the account. This can take an integer value from 1-5 as explained above.
Friends: An array of pointers to the friends of this account. Each time a new friend is added to this account, a pointer to the friend account is added to the array. Figure 2 shows an example in which account A is friend with Accounts B and C, and Account C is friend with Account D. Notice that friendship is mutual, hence if A is friend with B then B is also friend with A.
numFriends: The number of friends of this account.
receivedM: An array for storing received messages. You can think of this array as the inbox of the account. The Message structure is explained below.
numberReceivedM: The number of messages in the receivedM array.
sentM: An array for storing sent messages (the outbox).
numberSentM: The number of messages in the sentM array.
Figure 2 Friendship relations between accounts are implemented with pointers. In this example, Account A is friend with Accounts B and C, and Account C is friend with Account D only.
The network
We will implement the social network as a collection of accounts dynamically created in the heap. To get a handle on any account in the network we will use the global array of pointers defined below:
Account* AllAccounts [MaxNumberAccounts];// the array of all accounts in the network
Each time a new account is created in the heap a pointer to this account is added to the AllAccounts array. Figure 3 shows an example of a network with four accounts.
Figure 3 Each element in the AllAccounts array points to an account in the heap.
WHAT YOU ARE REQUIRED TO DO NOW
In the template.c file, I have defined the following two arrays which contain subsets of the English consonants and vowels respectively:
char Consonants [NumberConsonants] = {B,C,D,F,G,J,K,L,M,N,P,R,S, T,V,Z};
char Vowels [NumberVowels] = {A,I,O,U};
I have also implemented the initAll and newAccountId functions. Your task now is to implement the following functions:
char aConsonant (); // returns a random consonant from the Consonants array
char aVowel (); // returns a random vowel from the Vowels array
int isConsonant (char letter); // returns 1 if letter is a consonant, otherwise returns 0
int isVowel (char letter); // returns 1 if letter is a vowel, otherwise returns 0
char* newAccountName (); // creates a new account name with the following pattern CVCV
Account* newAccount (int account_number, char accout_name [], int account_type); // creates a new account in the heap and returns a pointer to it
int addAccount (Account* an_account); // adds an account (more precisely a pointer to the account) to the AllAccounts array
int addFriend (Account* a, Account* b) // Makes account a friend with account b
int isFriend (Account *a, Account *b); //returns 1 if a is friend with b otherwise returns 0
int createSocialNetwork (int num_publishers, int num_fabricators, int num_forwarders, int num_sinks, int num_reporters, int num_friends); // creates a social network with a given number of each account type then connect all the accounts with random friendship relations so that each account will have at least num_friends friends
Stories
To distinguish fake stories from genuine ones, we will assume that all fake stories have a common and funny pattern. A fake story is comprised of two 3-letter words separated by single white space (ASCII code 32) and has the following pattern CVC CVC, where C is any consonant and V is any vowel. Examples of fake stories include RIS PUZ, DAR MUC, and PAV RAD.
On the other hand, we will assume that real stories are comprised of two different words randomly picked from this array of words:
char* TrueStoryWords [NumberTrueStoryWords] = {ELECTIONS, BREXIT, UK, MINISTER, DATE, EDUCATION, RESIGN, MAYOR, NEWS, WIN};
Examples of real stories include ELECTIONS UK, DATE BREXIT, UK RESIGN, and WIN DATE.
Messages
A story is just a string of characters. In order to send a story from one account (the sender) to another (the recipient), the story must be encapsulated within the Message structure defined in news.h as follows:
typedef struct
{
char theStory [MaxStoryLength];// the story (payload) carried by this message
struct AccountStruct* theSender;// the sender of the message
struct AccountStruct* theRecipient;// the recipient of the message
int isRead;// a flag, initially 0, set to 1 when the message is read
} Message;
Encapsulating a story within a Message is necessary to allow the story to be sent to the correct recipient. This is quite similar to enclosing a letter in an envelope when sending it through the post. The Message structure contains the following fields:
theStory:the story string.
theSender: the address of (i.e. a pointer to) the sender of the message.
theRecipient: the address of (i.e. a pointer to) the recipient of the message.
isRead: a flag that is initially zero and is set to one when the recipient reads the message.
WHAT YOU ARE REQUIRED TO DO NOW
Your task now is to implement the following functions:
char* aFakeStory (); // creates a new fake story (string) and returns a pointer to it
int isFakeStory (char* story); // returns 1 if story is a fake one
char* aRealStory ();// creates a new real story (string) and returns a pointer to it
Message createMessage (char* a_story, Account* sender, Account* recipient); // creates a new message that encapsulates a story sent from sender to recipient
The server
Messages cannot be directly sent from senders to recipients. Instead they must go through a central server, see Figure 4.Messages are uploaded from senders to the server which will then forward the messages to their respective recipients. The server does not immediately forward messages to recipients, instead incoming messages are temporarily stored in an array of pending messages.
Figure 4 Messages are sent from senders to recipients through the server.
The server is represented by the following structure:
typedef struct
{
Message pendingMessages [MaxNumberPendingMessages];// messages to be forwarded to recipients
int numberPendingMessages; // number of messages in the pendingMessages array
char* reportedFakeStories [MaxReportedFakeStroies]; // stories which are reported as fake
int numberReportedFakeSt; // the number stories in the reportedFakeStories array
} Server;
The purpose of each field in this structure is as follows:
pendingMessages: an array to store messages waiting to be forwarded to recipients.
numberPendingMessages: the number of messages in the pendingMessages array.
reportedFakeStories: an array to store reported fake stories
numberReportedFakeSt: the number of stories in the reportedFakeStories array
Sending messages
Sending a message from one account to another is implemented as follows:
The senders upload messages to the server. This simply means adding the messages to the servers pendingMessages array. As a result, uploaded messages from all senders accumulate in the servers pendingMessages array.
At regular intervals (see below), the server will go through the array of pending messages and push each message to the inbox of the proper recipient. Pushing a message to the inbox of the recipient simply means adding the message to the recipients receivedM array. Before pushing a message to the inbox of the recipient however, the server must inspect the story carried by the message to determine if it has been reported as a fake story. This is simply done by searching for the story in the reportedFakeStories array.If the story is found in this array, the message is discarded.
WHAT YOU ARE REQUIRED TO DO NOW
In the template.c file, I have defined the following variable:
Server theServer; // the server that receives messages from senders and forward them to recipients
I have also initialised the fields of this variable within the initAll function. Your task now is to implement the following functions:
int uploadMessage (Message a_message); // upload a message to the server, i.e. add the message to the servers pendingMessages array
int pushMessage (Message a_message); // push a message to the recipients inbox, i.e. add the message to the recipients receivedM array
int sendStory (char* a_story, Account* sender, Account* receiver);// send a story from a sender to a receiver (see details in template.c)
int isReported (char * story); // returns 1 if story has been reported as fake, otherwise 0
int ReportFakeStory (char* story); // report a fake story, i.e. add it to the servers ReportedFakeStories array
int transmitAllMessages ();// transmit all the messages in the servers pendingMessages array to their respective recipients
int isSent (Account* account, char* story); // returns 1 if story has been sent, i.e. it exists in the accounts sentM array
Disseminating stories
We are now ready to implement the functions that will create and disseminate news stories across the social network. These two functions are:
int originateOrforwardNews (Account* account); // allow an account to either originate a new story or forward newly received (unread) stories to all friends.
int simulate (); // simulate the propagation of news across the network;
The originateOrforwardNews function allows an account to either originate a new story if the account type is RealNewsPublisher or FakeNewsFabricator or forward newly received messages to friends. Forwarding stories should be in accordance with the expected behaviour of different account types as explained earlier. The function returns the number of sent messages.
The simulate function allows all accounts to participate in originating or disseminating news. The pseudocode for this function is as follows:
while at least one account has sent a message
{
For each account acc in the network
Allow acc to originate or forward messages
Allow the server to transmit all pending messages
}
In order for the simulation to converge (terminate), we will set a limit on the number of real and fake stories that a RealNewsPublisher or FakeNewsFabricator can originate during the simulation process. A news originator will stop creating new stories when the number of created stories reaches the limit. These limits are defined in template.c and initialised in the initAll function to a default value of 5:
int MaxNewFakeStory;// the maximum number of times fabricators can create new fake stories
int MaxNewRealStory;// the maximum number of times real news publishers can create new real stories
int numberNewFakeStories;// the number of fake news stories fabricated so far
int numberNewRealStories;// the number of new real stories published so far
General Implementation Guidelines
Write the program in standard C. If you write your code in any other language, it will NOT be marked, and you will score zero.
This is an individual project, and you are not supposed to work in groups or pairs with other students.
Be aware that plagiarising your code will earn you a zero mark and will have very serious consequences. It is much better to submit your own partially finished work, than to fall into the trap of plagiarism. We use a software to detect plagiarism automatically, so if you do work with someone else, or submit someone elses work it WILL be detected.
At the top of you program file please include the following information within a comment, and fill in your name, student id, email, and the date on which you commenced writing your program:
/*************************************************************************
SWJTU
Leeds joint school
XJCO1711- Procedural Programming
Coursework 3
I confirm that the following program has been developed and written by me and it is entirely the result of my own work. I also confirm that I have not copied any parts of this program from another person or any other source or facilitated someone to copy this program.
I confirm that I will not post this program online or share it with anyone before the end of the semester.
Student Name:
Student ID:
Email:
Date Work Commenced:
*************************************************************************/
If you do not include the above statement in your submitted file, your coursework may be rejected, and you will score 0 in this coursework.
Developing and testing your program
To simplify program development and facilitate automatic testing, I have provided you with C files containing declarations of the data structures and function prototypes that you will use to develop the program.
Please use these declarations as given and do not for any reason change them. Changing or deleting any of the declarations will stop the test harness (see below) from working and you will score zero in this coursework.
For this coursework, I have provided you with a test harness to automatically test and mark your program. You will run this harness on your code to make sure that you have implemented functions correctly, and to immediately see you mark on the screen.
Together with the file you are reading now, you will be able to find and download the following files:
news.h: This file contains declarations of the program data structures, as well as the prototype declarations of all the functions that you are required to implement. FOR YOU, THIS FILE IS READ ONLY AN SHOULD NEVER BE ALTERED. If you suspect that you have accidentally changed anything in this file, please download a fresh copy from Minerva.
template.c: This file contains all the functions that you are required to implement. They all return a value of type int. The body of each function initially contains just one statement: return -99. This special value tells the test harness that the function is not implemented. Replace this statement with your implementation code of the function. If you decide not to implement a function, then please do not delete the return -99 statement. In some cases, you will need to call some of the provided functions within other functions; in this case, you have to implement the called function first. You can also add other functions of your own if you think that you need them, but these will not be tested by the test harness.
test.o:This is the precompiled test harness file. You will use it to test your functions, and to see your mark. You cannot open this file with a text editor because it contains object code (machine language). If you suspect that you have accidentally changed this file, please download a fresh copy from Minerva.
To compile your program with the provided test harness, type:
gcc -std=c99 news.h template.c test.o -o test
then test your program by typing:
./test
Submission Instructions
Before submitting your coursework, you must make sure that you can compile your program on our schools Linux machines (e.g. DEC-10 Lab machines). You must also thoroughly test your program on these machines. Submissions that do not compile and run on our Linux machines will score zero even if they work perfectly well on another platform. Hence, if you have developed your program on a Windows or Mac PC or laptop, you must not submit your project until you have made sure that it does compile and run on our Linux computers without any problems.
You should test your program using the provided test harness on one of our Linux machines to make sure that the functions you have implemented will pass the tests, and to know your mark.
You should only upload to Minerva the template.c file that you have written. Do not upload the provided header file (news.h) or the test harness file (test.o).
Please make sure that you have uploaded the correct file by downloading it from Minerva and checking that it is indeed what you intended to submit. If you submit non-plain text or a corrupt file, your coursework may be rejected, and you will score 0.
Do not upload executable or binary files.
Marking Scheme
This coursework is automatically marked by a test harness and the marks assigned to each function can be seen in the provided news.h header file. These are reproduced below:
char aConsonant ();// 2 marks
char aVowel ();// 2 marks
int isConsonant (char letter);// 2 marks
int isVowel (char letter);// 2 marks
char* newAccountName ();// 3 marks
Account* newAccount (int account_number, char accout_name[], int account_type);// 3 marks
int addAccount (Account* an_account);// 3 marks
int addFriend (Account* an_account, Account* a_friend);// 3 marks
int isFriend (Account *a , Account *b);// 3 marks
char* aFakeStory ();// 3 marks
int isFakeStory (char* story);// 3 marks
char* aRealStory ();// 3 marks
Message createMessage (char* a_story, Account* sender, Account* receiver);// 3 marks
int uploadMessage (Message a_message);// 3 marks
int pushMessage (Message a_message);// 3 marks
int sendStory (char* a_story, Account* sender, Account* receiver);// 4 marks
int isReported (char * story);// 2 marks
int ReportFakeStory(char* story);// 3 marks
int transmitAllMessages ();// 5 marks
int isSent (Account* account, char* story);// 3 marks
int createSocialNetwork (int num_publishers, int num_fabricators,
int num_forwarders, int num_sinks,
int num_reporters, int num_friends);// 8 marks
int originateOrforwardNews (Account* account);// 8 marks
int simulate ();// 6 marks
Total80 marks
References
[1] https://www.theguardian.com/technology/2019/jan/21/whatsapp-limits-message-forwarding-fight-fake-news
Reviews
There are no reviews yet.