COMP2017 / COMP9017 Assignment 2
This assignment is worth 10% of your final assessment
Task Description
The given data has been collected from a social media platform. supergraph2048. You are tasked with
writing program using the C programming language that will handle different queries and compute
the correct result.
Some queries may require simple partitioning of data for each thread to operate on, while others may
require strategy of dynamically partitioning data, checking the distribution of the data and synchroni-
sation in order to efficiently process and eliminate redundant operations.
You can ask questions on Ed using the assignments category. Please ensure that your work is your
own and you do not share any code or solutions with other students.
Working on your assignment
You can work on this assignment using your own computers or the lab machines. Students can also
take advantage of the online code editor on Ed. You will need to navigate to the assessments or
workspaces page where you will be able to run, edit and submit your code from within your browser.
However we recommend you write this code using your own computer or the lab machines.
It is important that you continually back up your assignment files onto your own machine, flash drives,
external hard drives and cloud storage providers. You are encouraged to submit your assignment
while you are in the process of completing it to receive feedback and to check for correctness of your
solution.
COMP2017 / COMP9017
Program structure
The social media platform. is composed of two types of entities:
• Users
• Posts
Each user in the social network have a list of followers, other users they are following and posts.
These collections are represented as an array of indices that relate to a user* or post* array.
struct user {
uint64_t user_id; //User id, is unique
size_t* followers_idxs; //User indices within user* users graph
size_t n_followers; //Number of followers
size_t* following_idxs; //User indices within user* users graph
size_t n_following; //Number of users the user is following
size_t* posts_idxs; //Post indices within post* posts graph
size_t n_posts; // Number of posts a user has made.
};
typedef struct user user;
All user_id values within the users array will be unique. The lists: followers, following and posts
are arranged by ascending order. In order of insertion.
struct post {
uint64_t pst_id; //Post id, is unique
size_t* reposted_idxs; //Reposted indices within the graph
size_t n_reposted; // Number of reposted posts.
};
typedef struct post post;
All pst_id values within the posts array will be unique. The posts array will not contain any cycles
as for any reposts to exist depends on the existance of an original post.
For all queries you will need to return a heap allocated result structure: This structure stores all
elements retrieved from the query as a heap allocated contiguous block of pointers and the number of
elements. It will be used to determine if your result is correct.
struct result {
void** elements;
size_t n_elements;
};
typedef struct result resu oc_threshold
• Account reputation, You will need to acknowledge the user reputation, caluclating it based
on: n_followers
(n_followers+n_following) bot_net_threshold
Page 7 of 10
COMP2017 / COMP9017
Algorithms
Breadth First Search
Breadth first search will check its neighbours before moving onto its neighbour’s neighbours and so
on.
BFS(G, v)
Queue q;
for all vertices u in G
u.seen = false
q.enqueue(v)
while(!q.empty())
u = q.dequeue()
if u.seen is false
u.seen = true
for all neighbours w of u
q.enqueue(w)
You may apply a Breadth First Search or any other algorithms based on what you think is appropriate.
Error handling
For all four queries, you will need to ensure that your query returns heap allocated memory. If the
data set provided is NULL or the number of elements (count) is 0, your query must return an empty
result set ( n_elements is 0, elements is NULL).
Page 8 of 10
COMP2017 / COMP9017
Submission Details
You will be provided with benchmarking code for this assessment called supergraph2048_bench
and its source. It will time your query as well as load any expected results you have stored. Your pro-
gram must produce no errors on Ed and will be compiled with the command:
clang -O0 -std=gnu11 -march=native -lm -lpthread
You are to submit your assessment using Ed which will check for correctness of your queries. In the
event that your program does not produce the correct output, your program will not be checked for
performance.
• 4 Marks for the correctness of your program. This requires implementing all queries specified
in the assignment and ensuring that they will return the correct result. If it does not compile, it
will receive zero.
• 4 marks are assigned based on the performance of your code related to the benchmark. This
is tested on a separate machine. Submissions that are faster or equal to the benchmark set, will
receive full marks. Submissions faster than a basic implementation will receive a minimum of
2 marks.
• 2 marks are assigned for a manual marking component in your tutorial. This will be based on
your submission prior to the 4thofJune20188:00amAEST. This manual marking component
will assess your current progress of your assessment, styling (indentation and function layout)
and also explaining your code to your tutor.
Warning: Any attempts to deceive or disrupt the marking system will result in an immediate zero for
the entire assignment. Negative marks can be assigned if you do not follow the assignment specifica-
tion or if your code is unnecessarily or deliberately obfuscated.
Page 9 of 10
COMP2017 / COMP9017
Academic declaration
By submitting this assignment you declare the following:
I declare that I have read and understood the University of Sydney Student Plagiarism: Coursework Policy and
Procedure, and except where specifically acknowledged, the work contained in this assignment/project is my
own work, and has not been copied from other sources or been previously submitted for award or assessment.
I understand that failure to comply with the Student Plagiarism: Coursework Policy and Procedure can lead
to severe penalties as outlined under Chapter 8 of the University of Sydney By-Law 1999 (as amended). These
penalties may be imposed in cases where any significant portion of my submitted work has been copied without
proper acknowledgment from other sources, including published works, the Internet, existing programs, the
work of other students, or work previously submitted for other awards or assessments.
I realise that I may be asked to identify those portions of the work contributed by me and required to demonstrate
my knowledge of the relevant material by answering oral questions or by undertaking supplementary work,
either written or in the laboratory, in order to arrive at the final assessment mark.
I acknowledge that the School of Information Technologies, in assessing this assignment, may reproduce it
entirely, may provide a copy to another member of faculty, and/or communicate a copy of this assignment
to a plagiarism checking service or in-house computer program, and that a copy of the assignment may be
maintained by the service or the School of IT for the purpose of future plagiarism checking.