CS6771 Assignment One to five solutions

CS6771 Assignment One to five solutions

$120.00

Original Work ?

Download Details:

  • Name: assignments-mufkxl.zip
  • Type: zip
  • Size: 2.05 MB
Category: You will Instantly receive a download link upon Payment||Click Original Work Button for Custom work
Share This

Description

5/5 - (1 vote)

CS6771 Assignment One Stack Based Calculator

Aims:
 Familiarity with C++ Containers
 File and string processing
Write a stack-based calculator program in C++. The calculator reads tokens (numbers and commands) from a
specified input file. In the input file each token is separated by a space or a new line. Each number is placed on a
stack and each command consumes one or more values from the stack. A command may result in a modification
of the stack, an additional number added to the stack, and/or output printed to the console (stdout / cout). The
calculator should support int and double values and only promote an int to a double when necessary. Your
program should be written in pure C++ (not C) and should make use of the C++ STL. When printing output your
double values should be formatted to three decimal places. Your calculator should act on the following tokens:
Token Description
Console
Output
x.y A double (where x and y are numbers). All doubles will have decimal places. e.g., 2.1
x An integer (where x is a number).
add
Removes two numbers from the stack and calculates their sum. The sum is pushed back
onto the stack.
x + y = z
sub
Removes two numbers from the stack and subtracts the second number removed from
the first. The result is pushed back onto the stack.
x – y = z
mult
Removes two numbers from the stack and multiplies their product. The result is pushed
back onto the stack.
x * y = z
div
Removes two numbers from the stack and divides the first by the second. The result is
pushed back onto the stack.
x / y = z
sqrt
Removes the top of the stack and calculates the sqrt of this number. Pushes the result
back onto the stack.
sqrt y = z
pop Removes the top of the stack.
reverse
Removes the top of the stack. The ordering of the next n (the number that was at the top
of the stack) elements are reversed on the stack.
repeat
Removes the top of the stack. Numbers and commands continue to be read from the file
but not acted on until an endrepeat command.
endrepeat
Processes the numbers and commands that were read from the input file but stored from
the start of the repeat command. These numbers and commands are repeated n times
(where n is the number that was at the top of the stack when the repeat command was
given).
Sample input:
10 20 sub
4 3 add
2 mult
16.0
2 repeat
sqrt
endrepeat
pop
2.0
mult
3 repeat
2
2 reverse
div
3 mult
endrepeat
Sample output:
20 – 10 = 10
3 + 4 = 7
2 * 7 = 14
sqrt 16.000 = 4.000
sqrt 4.000 = 2.000
2.000 * 14 = 28.000
28.000 / 2 = 14.000
3 * 14.000 = 42.000
42.000 / 2 = 21.000
3 * 21.000 = 63.000
63.000 / 2 = 31.500
3 * 31.500 = 94.500
Getting started:
The following program will allow you to read a file from the command line and sets up the formatting for
printing doubles to three decimal places.
#include
#include
#include
int main(int argc, char* argv[]) {
// setup the print out format for the precision required.
std::cout.setf(std::ios::fixed,std::ios::floatfield);
std::cout.precision(3);
// open the file for reading
std::ifstream in;
in.open(argv[1]);
// string to be read into
std::string s;
// read the file while we have input.
while (in >> s) {
}
in.close();
}
Tips:
 Use C++! Do not use C-style printfs, unions, macros or arrays.
 You shouldn’t need any pointers or dynamic memory to complete this assignment (but you may want to
use references and const).
 The lecture slides and tutorials have many code snippets that you may find helpful.
 You may need multiple containers (stack, queue, vector, etc).
 Use the C++ STL – you shouldn’t build your own container classes or use other libraries (e.g., boost).
 You shouldn’t need to create any classes (but you may if you like).
 To detect if a string is a double look for a ‘.’ in the token, e.g.,
s.find(‘.’) != std::string::npos
 To detect if a string is a number look for a number in the first position of the token, e.g.,
isdigit(s[0])
 To convert a string to an int or a double use
std::stoi(s) or std::stod(s).
 To calculate a square root you may need to
#include
 Carefully consider when you need to promote an int to a double. Any command that only uses ints
should return an int result, only commands that mix ints and doubles should result in a double.
 The reference solution is 250 lines including comments.
 All testing input will be valid and computable (e.g., no ‘-1 sqrt’) however you should be able to handle or
ignore bad input.
 This assignment should be relatively easy, mixing ints and doubles is the only difficult bit.
 All your code should be placed in one C++ source file, you don’t need header or makefiles.
 Make sure your code reads a file specified in argv[1] and outputs using std::cout
Testing
Place all your code in a file called calculator.cpp
Ensure it compiles on the CSE machines under the following command:
g++ -std=c++14 -Wall -Werror -O2 -o calculator calculator.cpp
To run your code type:
./calculator input.txt
You should create your own input files to test the full functionality of your code against the specifications.
Marking
Your submission will be given a mark out of 10 with 7 an automarked performance component for output
correctness and 3 manually marked component for code style and quality.
As this is a third-year course we expect that your code will be well formatted, documented and structured. We
also expect that you will use standard formatting and naming conventions.
Note, if you write in C or use C types (e.g. union) or #define macros you will lose performance marks as well as
style marks.
A number of test cases will be used to mark your solution. To pass a test case, your solution must produce
exactly the same output as the reference solution. The results from both will be compared by using the linux tool
diff.
Submission Instructions
Copy your code to your CSE account and make sure it compiles without any errors or warnings. Then run your
test cases. If all is well then submit using the command:
give cs6771 ass1 calculator.cpp
If you submit and later decide to submit an even better version, go ahead and submit a second (or third, or
seventh) time; we’ll only mark the last one. Be sure to give yourself more than enough time before the deadline
to submit.
Late submissions will be penalised unless you have legitimate reasons for an extension which is arranged before
the due date. Any submission after the due date will attract a reduction of 20% per day to your individual mark.
A day is defined as a 24-hour day and includes weekends and holidays. No submissions will be accepted more
than three days after the due date.
Plagiarism constitutes serious academic misconduct and will not be tolerated. CSE implements its own
plagiarism addendum to the UNSW plagiarism policy. You can find it
here: https://www.cse.unsw.edu.au/~chak/plagiarism/plagiarism-guide.html.
Further details about lateness and plagiarism can be found in the Course Introduction.
Acknowledgement
This assignment is based on a 2007 Massey University assignment written by Professor Ken Hawick and has been
modified with permission.

CS6771 Assignment Two Euclidean Vector Class Library

1. Aims:
• Familiarity with C++ Classes
• Constructors
• Destructor
• Uniform initialisation
• Copy Control
• Function Overloading
• Operator Overloading
• Friends
• (Simple) Dynamic Memory Management
• Seperation of Interface from Implementation
Write a Euclidean Vector Class Library in C++, with its interface given in EuclideanVector.h and its implementation
in EuclideanVector.cpp. For assessment purposes, your EuclideanVector.cpp will be compiled with a series of
assessment test cases that #include your EuclideanVector.h.
Euclidean Vectors are commonly used in physics to represent directed quantities. Your Euclidean Vector class should be
dimension-agnostic, that is, it should be able to be constructed and operate on data of arbitrary dimensionality. The
magnitude in each dimension will always be a double. For example:
evec::EuclideanVector a(1); // a Euclidean Vector in 1 dimension, with
default magnitude 0.0.
evec::EuclideanVector b(2,4.0); // a Euclidean Vector in 2 dimensions with
magnitude 4.0 in both dimensions
std::list l;
l.push_back(5.0);
l.push_back(6.5);
l.push_back(7.0);
evec::EuclideanVector c(l.begin(),l.end()); // a Euclidean Vector in 3
dimensions constructed from a list of magnitudes
2. International Representation
You absolutely must use dynamically allocated memory to store a Euclidean vector where appropriate. Use of an STL
container (except obviously in type conversion) will result in a zero. Please make sure you use new and delete Therefore,
the compiler-generated copy-control members will not provide the correct semantics. You must provide your own
implementations for these copy-control member functions.
3. Constructors
Your design should allow Euclidean vectors to be defined in the following ways:
Constructor Description and Hints Examples
Constructor
A constructor that takes the number of dimensions (as an
unsigned int) but no magnitudes, sets the magnitude in each
dimension as 0.0. Hint: you may want to make this a
delegating constructor to the next constructor below.
This is the default constructor, with the default value being
1.
(1) EuclideanVector a(1);
(2) unsigned int i {3};
EuclideanVector b(i);
(3) EuclidenVector c; // or c{}
// same as EuclidenVector
c(1);
Constructor
A constructor that takes the number of dimensions (as an
unsigned int) and initialises the magnitude in each
dimension as the second argument (a double)
(1) EuclideanVector a(2,4.0);
(2) unsigned int x {3};
double y {3.24};
EuclideanVector b(x,y);
Constructor
A constructor (or constructors) that takes the start and end
of an iterator and works out the required dimensions, and
sets the magnitude in each dimension according to the
iterated values. The iterators will be from std::vector or
(1) std::list l;
EuclideanVector
a{l.begin(),l.end()};
(2) std::vector v;
std::list. Hint: a function template may help. Hint 2: the
compiler prefers calling normal functions over templated
functions, even if it’s an exact match for the template
EuclideanVector
b{v.begin(),v.end()};
Constructor
An initialiser-list constructor that creates an Euclidean
vector from a list of double values. See Pages 220 — 224 of
the text.
EuclideanVector a {1,2,3,4};
Constructor A copy constructor EuclideanVector aCopy{a};
Constructor A move constructor EuclideanVector
aMove{std::move(a)};
For all constructors, you may assume that the arguments supplied by the user are correct (as is the case for the STL
containers).
Please make sure that your constructors work correctly. Otherwise, we have no way to construct any Eucliden vector to test
your solution.
3. Destructor
Due to the use of dynamic memory allocation in your constructors, you must provide a destructor that deallocates the
memory acquired by the constructors. You should ensure that your implementation does not leak memory. You will be
penalised for an improperly implemented destructor.
Please use the compiler flag “-fsanitize=address” to enable AddressSanitizer , a fast memory error detector. Memory access
instructions are instrumented to detect out-of-bounds and use-after-free bugs.
4. Operations
Your design must support the following public (member) operations performed on Euclidean vectors:
Operation Description and Hints Examples
Copy Assignment A copy assignment operator overload EuclideanVector a;
a = b;
Move Assignment A move assignment operator EuclideanVector a;
a = std::move(b);
getNumDimensions() Returns an unsigned int containing the number of
dimensions in a particular vector a.getNumDimensions();
get(unsigned int) Returns a double, the value of the magnitude in the
dimension given as the function parameter a.get(1);
getEuclideanNorm()
Returns the Euclidean norm of the vector as a double. The
Euclidean norm is the square root of the sum of the squares
of the magnitudes in each dimension. E.g, for the vector [1
2 3] the Euclidean norm is sqrt(1*1 + 2*2 + 3*3) = 3.74.
Hint: the Euclidean norm should only be calculated when
required and ideally should be cached if required again.
Hint 2: mutable data members from lecture 3.1 may come in
handy
a.getEuclideanNorm();
createUnitVector()
Returns an Euclidean vector that is the unit vector of *this
vector. The magnitude for each dimension in the unit vector
is the original vector’s magnitude divided by the Euclidean
norm.
a.createUnitVector();
operator[]
Allows to get and set the value in a given dimension of the
Euclidean Vector. Hint: you may need two overloaded
functions to achieve this requirement.
double a {b[1]};
b[2] = 3.0;
operator+= For adding vectors of the same dimension. a += b;
operator-= For subtracting vectors of the same dimension. a -= b;
operator*= For scalar multiplication, e.g. [1 2] * 3 = [3 6] a *= 3;
operator/= For scalar division, e.g. [3 6] / 2 = [1.5 3] a /= 4;
Type Conversion Operators for type casting to a std::vector and
a std::list
EucilideanVector a;
std::vector vf =
a;
std::list lf = a;
You should not modify or augment the public interface provided.
5. Nonmember functions
In addition to the operations indicated earlier, the following operations should be supported as nonmember functions. Note
that these operations don’t modify any of the given operands.
operator== True if the two vectors are equal in the number of dimensions and the magnitude in each
dimension is equal. a == b;
operator!= The opposite of == a != b;
operator+ For adding vectors of the same dimension. a = b + c;
operator- For substracting vectors of the same dimension. a = b – c;
operator* For dot-product multiplication, returns a double. E.g., [1 2] * [3 4] = 1 * 3 + 2 * 4 = 11 double c {a *
b};
operator* For scalar multiplication, e.g. [1 2] * 3 = 3 * [1 2] = [3 6]. Hint: you’ll obviously need two
methods, as the scalar can be either side of the vector.
(1) a = b * 3;
(2) a = 3 * b;
operator/ For scalar division, e.g. [3 6] / 2 = [1.5 3] a = b / 4;
operator<< Prints out the magnitude in each dimension of the Euclidean Vector (surrounded by
[ and ]), e.g. for a 3-dimensional vector: [1 2 3]
std::cout <<
a;
6. Private Members
Remember you are required to store an Euclidean vector in dynamically allocated memory. Otherwise you may introduce
whatever private members you feel are necessary for your implementation. This includes private member functions.
7. Move Semantics
An Euclidean vector, once moved (by your move constructor or move assignment operator), must be left in a valid state. In
principle, a moved-from object can be written into but not read from. For marking purposes, please put a moved-from
Euclidean vector in such a valid state that calling the output operator << on it will result in the output
[]
with nothing inside the brackets.
8. Getting Started
There is no starter code for this second assignment.
• Create EuclideanVector.h and EuclideanVector.cpp
• Place the class declaration and definition inside the namespace evec
• Ensure the name of your class is EuclideanVector
• Make sure you include Header Guards in EuclideanVector.h
• You will need to figure out the function prototypes from the above descriptions
• Your EuclideanVector.cpp should not include a main method (your class will be compiled against a series of test
files that include a main method)
• Your code should not read or write any files, or print anything to the screen unless called to do so through the
overloaded << overloaded from a test file which #include “EuclideanVector.h”
• It is vital that the << operator is overloaded correctly for printing out your euclidean vector. This function must be
a friend and the function prototype should look like this:std::ostream& operator<<(std::ostream
&os, const EuclideanVector &v);
Note: If you are unsure about vector mathematics look in the library for a text book on linear algebra. Additionally, the
book: Bourg, David M. Physics for Game Developers (2001) O’Reilly Media, provides a good overview (and was an
inspiration for this assignment).
9. Sample Test Case (EuclideanVectorTester.cpp)
Testing for this assignment will be done via a number of test cases written as C++ programs that compile against your
library. The following program is an example of what these test cases will look like.
#include
#include
#include #include “EuclideanVector.h”
int main() {
evec::EuclideanVector a(2);
std::list l {1,2,3};
evec::EuclideanVector b{l.begin(),l.end()};
std::vector v2 {4,5,6,7};
evec::EuclideanVector c{v2.begin(),v2.end()};
std::vector a1 {5,4,3,2,1};
evec::EuclideanVector d{a1.begin(),a1.end()};
std::list a2 {9,0,8,6,7};
evec::EuclideanVector e{a2.begin(),a2.end()};
// use the copy constructor
evec::EuclideanVector f{e};
std::cout << a.getNumDimensions() << “: ” << a << std::endl;
std::cout << “D1:” << b.get(1) << ” ” << b << std::endl;
std::cout << c << ” Euclidean Norm = ” << c.getEuclideanNorm() << std::endl;
std::cout << d << ” Unit Vector: ” << d.createUnitVector() << ” L = ” <<
d.createUnitVector().getEuclideanNorm() << std::endl;
std::cout << e << std::endl;
std::cout << f << std::endl;
// test the move constructor
evec::EuclideanVector g = std::move(f);
std::cout << g << std::endl;
std::cout << f << std::endl;
// try operator overloading
e += d;
std::cout << e << std::endl;
evec::EuclideanVector h = e – g;
std::cout << h << std::endl;
// test scalar multiplication
h *= 2;
std::cout << h << std::endl;
evec::EuclideanVector j = b / 2;
std::cout << j << std::endl;
std::cout << “dot product = ” << j * b << std::endl;
if (g == (e – d)) std::cout << “true” << std::endl;
if (j != b ) std::cout << “false” << std::endl;
j[0] = 1;
std::cout << j << std::endl;
// type cast from EuclideanVector to a std::vector
std::vector vj = j;
// type cast from EuclideanVector to a std::vector
std::list lj = j;
for (auto d : lj) {
std::cout << d << std::endl;
}
// list initialisation
evec::EuclideanVector k {1, 2, 3};
std::cout << k << std::endl;
}
The correct output is:
2: [0 0]
D1:2 [1 2 3]
[4 5 6 7] Euclidean Norm = 11.225
[5 4 3 2 1] Unit Vector: [0.6742 0.53936 0.40452 0.26968 0.13484] L = 1
[9 0 8 6 7]
[9 0 8 6 7]
[9 0 8 6 7]
[]
[14 4 11 8 8]
[5 4 3 2 1]
[10 8 6 4 2]
[0.5 1 1.5]
dot product = 7
true
false
[1 1 1.5]
1
1
1.5
[1 2 3]
As illustrated in this example, the first element in a Euclidean vector has a position of 0 not 1, just like in the case
of std::vector.
10. Tips:
• Your code should be const correct.
• Use C++14 style and methods as much as possible.
• The lecture slides and tutorials have many code snippets that you may find helpful.
• Your code should be well documented, clearly describing how each function operates.
• To calculate a square root you may need to #include
• Do not use other libraries (e.g., boost).
• The reference solution is around 400 lines including generous comments.
11. Testing
Place all your code in files called EuclideanVector.h and EuclideanVector.cpp
Ensure it compiles on the CSE machines using the following sample makefile
all: EuclideanVectorTester
EuclideanVectorTester: EuclideanVectorTester.o EuclideanVector.o
g++ -fsanitize=address EuclideanVectorTester.o EuclideanVector.o -o
EuclideanVectorTester
EuclideanVectorTester.o: EuclideanVectorTester.cpp EuclideanVector.h
g++ -std=c++14 -Wall -Werror -O2 -fsanitize=address -c
EuclideanVectorTester.cpp
EuclideanVector.o: EuclideanVector.cpp EuclideanVector.h
g++ -std=c++14 -Wall -Werror -O2 -fsanitize=address -c EuclideanVector.cpp
clean:
rm *o EuclideanVectorTester
To compile your code type:
make
To run your code type:
./EuclideanVectorTester
You should create your own test cases to check the full functionality of your code against the specifications.
12. Marking
Your submission will be given a mark out of 100 with 70% an automarked performance component for output correctness
and 30% a manually marked component for code style and quality.
As this is a third-year course we expect that your code will be well formatted, documented and structured. We also expect
that you will use standard formatting and naming conventions.
Note, if you write in C or use C types (e.g. union) or #define macros you will lose performance marks as well as style
marks.
A number of test cases will be used to mark your solution. To pass a test case, your solution must produce exactly the same
output as the reference solution. The results from both will be compared by using the linux tool diff.
13. Submission Instructions
Copy your code to your CSE account and make sure it compiles without any errors or warnings. Then run your test cases. If
all is well then submit using the command:
give cs6771 ass2 EuclideanVector.cpp EuclideanVector.h
Note you do not need to submit a makefile or other test files, we will supply a makefile and test cases for each test.
Late submissions will be penalised unless you have legitimate reasons for an extension which is arranged before the due
date. Any submission after the due date will attract a reduction of 20% per day to your individual mark. A day is
defined as a 24-hour day and includes weekends and holidays. No submissions will be accepted more than three days after
the due date.
Plagiarism constitutes serious academic misconduct and will not be tolerated.
Further details about lateness and plagiarism can be found in the Course Introduction.

CS6771 Assignment Three Generic Directed Weighted Graph (GDWG)

1. Aims
• Function and Class Templates
• Smart Pointers
• Exception Handling
• Lambda Functions
In this assignment, you will write a Generic Directed Weighted Graph (GDWG) with value-like semantics in C++. Both the
data stored at a node and the weight stored at an edge will be of generic types. Both generic types may be different. For
example, here is a graph with nodes storing std::string and edges weighted by int:
gdwg::Graph<std::string,int> g;
Formally, this directed weighted graph G=(N,E) will consist of a set of nodes N and a set of weighted edges E. Give a node,
an edge directed into it is called an incoming edge and an edge directed out of it is called an outgoing edge. The in-degree of
a node is the number of its incoming edges. Similarly, the out-degree of a node is the number of its outgoing edges. Given a
directed edge from src to dst, src  dst, src is the source node and dst is known as the destination node. G is a multi-edged
graph, as there may be two edges from the same source node to the same destination node with two different weights.
However, all nodes are distinct, as they contain different data values.
2. Internal Representation
You must use smart pointers to represent the nodes and edges in your implementation.
3. Operations
There are many ways to implement a generic directed weighted graph. For our purposes, a node can contain the data stored
at that node and a set of its outgoing edges and an edge may be a tuple containing its source node, its destination node and
the weight associated with this edge. However, your solution does not have to follow strictly this suggestion, except that it
must adhere to the public interface defined below.
In what follows, we assume the graph template class is declared as:
template class Graph;
where N is the Node value data type and E is the Edge weight data type.
You may assume that both N and E are copy constructible, and <, <=, ==, !=, >=, and > are defined on N and E.
Member Description and Hints Examples
Constructor A user-defined or compiler-synthesised default
constructor for an empty graph.
gdwg::Graph<std::string,int>
g;
Copy and Move
Constructors
User-defined or compiler-synthesised copy and move
constructors as required.
Copy and Move
Assignment
operators
User-defined or compiler-synthesised copy and move
assignment operators as required.
bool addNode(const
N& val)
Adds a new node with value val to the graph. This
function returns true if the node is added to the graph and
false if there is already a node containing val in the graph
(with the graph unchanged).
std::string s = “a”;
g.addNode(s);
a.addNode(“b”);
bool addEdge(const
N& src, const N&
dst, const E& w);
Adds a new edge src  dst with weight w. This function
returns true if the edge is added and false if the edge
src  dst with weight w already exists in the graph. A
std::runtime_error is thrown if either src or dst is not in
the graph.
std::string u = “c”;
g.addEdge(“a”,u,1);
bool replace(const
N& oldData, const
N& newData);
Replaces the original data, oldData, stored at this
particular node by the replacement data, newData. If no
node that contains value oldData can be found, then a
g.replace(“a”,”e”);
std::runtime_error is thrown. This function returns false if
a node that contains value newData already exists in the
graph (with the graph unchanged) and true otherwise.
void
mergeReplace(const
N& oldData, const
N& newData);
Replaces the data, oldData, stored at one node, denoted
OldNode, with the data, newData, stored at another node,
denoted NewNode, in the graph. If either node cannot be
found in the graph, then a std::runtime_error is thrown.
After the operation has been performed successfully,
every incoming (outgoing) edge of OldNode becomes an
incoming (outgoing) edge of newNode, except that
duplicate edges must be removed. Note that the edges that
connect OldNode and NewNode are handled identically
by this edge merging rule. See test6.cpp for an example.
g.mergeReplace(“c”,”e”);
// node “c” is destroyed
void
deleteNode(const
N&) noexcept;
Deletes a given node and all its associated incoming and
outgoing edges. This function does nothing if the node
that is to be deleted does not exist in the graph. Hint: if
you are using weak ptrs for edges you may be able to do
this quite simply. This function should not throw any
exceptions.
g.deleteNode(“b”);
void
deleteEdge(const
N& src, const N&
dst, const E& w)
noexcept;
Deletes an edge from src to dst with weight w, only if the
edge exists in the graph. No exceptions are thrown. g.deleteEdge(“b”,”c”,1);
void clear()
noexcept;
Remove all nodes and edges from the graph. New nodes
or edges can be added to the graph afterwards. g.clear();
bool isNode(const
N& val) const;
Returns true if a node with value val exists in the graph
and false otherwise. g.isNode(“a”)
bool
isConnected(const
N& src, const N&
dst) const;
Returns true if the edge src  dst exists in the graph and
false otherwise. This function throws a std::runtime_error
if either src or dst is not in the graph.
g.isConnected(“e”,”b”)
void printNodes()
const;
Prints the data stored in all the nodes in the graph, with
one node per line, starting from the node with the smallest
outdgree to the node with the largest. If two nodes have
the same edge count, then the one with the smaller node
value determined by the < operator is printed first. See
test11.cpp for an example.
g.printNodes();
void
printEdges(const
N& val) const;
Prints the outgoing edges of a given node, SrcNode,
containing value val. The first line must be “Edges
attached to Node X”, where X is the data stored at
SrcNode. Then, the outgoing edges of SrcNode are
printed in increasing order of their weights, with one edge
per line adhering to the following format:
[the data at the destination node
DstNode] [the cost of the edge]
For example, if SrcNode  DstNode has a weight 3 (of
type int), where the data at DstNode is “abc” (of type
std::string), then the print out is “abc 3”. If SrcNode does
not exist in the graph, then a std::runtime_error is thrown
with no output printed. If the outdegree of SrcNode is 0,
then the first line of the print should work and the second
line should be “(null)”. If two edges have the same
weight, then the edge whose destination node has a
smaller node value, again determined by the < operator, is
printed first. See test12.cpp for an example.
g.printEdges(s);
In addition to these operations, you should also implement the following four operations, which provide a fake iterator for
enumerating all the node values in a graph. You can abstract a graph in any sequence, as long as the sequence consists
of all and only the nodes in the graph.
Member Description
void begin() const Sets an internal iterator, i.e., “pointer” to the first element of a sequence.
bool end() const Returns true if the iterator goes past the last element of the sequence and false
otherwise.
void next() const Moves the iterator to the next element of the sequence.
const N& value()
const Returns the value of the node pointed to by the iterator.
You can use the four member functions as follows:
gdwg::Graph<std::string,int>> g
for (g.begin(); !g.end(); g.next())
std::cout << g.value() << std::endl;
This `iterator’ is not nearly as powerful as a proper iterator (e.g., the one to be implemented in Assignment 4), but it should
suffice to give you an idea of what iterators are all about. You must make sure that these member functions can be invoked
correctly on both const and non-const graphs.
Hint: These four functions have short implementations. Review the mutable qualifier. In the reference solution, there are
altogether 4 lines in the bodies of these four functions, with 1 line per function.
Note: Your Graph class should not expose any other public members other than those listed above, although you can add
whatever private member functions and classes as you see fit. This implies that your Node and Edge classes should be
private nested classes.
4. Getting started:
• Name your class as Graph, with its interface in Graph.h and implementation in Graph.tem.
• Include your implementation inside your interface file as follows: Graph.h:
•
• namespace gdwg {
•
• Your class interface
•
• #include “Graph.tem”
•
• }
•
• Place the class declaration and definition inside the namespace gdwg
• Make sure you include Header Guards in Graph.h
• Your Graph.h and Graph.tem should not include main().
• Your class will be compiled against a series of test files that include main().
• Your code should not read or write any files or print anything to the screen unless called to do so through a test file
that contains #include “Graph.h”.
5. Sample test files:
Here are some test cases for testing some functionalities required:
• test1.cpp result1.txt – Graph default construction and Node insertion
• test2.cpp result2.txt – Edge insertion and print ordering (more in test11.cpp and test12.cpp)
• test3.cpp result3.txt – Exception and error handling
• test4.cpp result4.txt – Checks data integrity
• test5.cpp result5.txt – Replace Node data
• test6.cpp result6.txt – Merges two nodes
• test7.cpp result7.txt – Deleting data
• test8c.cpp result8c.txt – Copy construction
• test8m.cpp result8m.txt – Copy construction
• test9c.cpp result9c.txt – Copy assignment
• test9m.cpp result9m.txt – Copy assignment
• test10.cpp result10.txt – constness
• test11.cpp result11.txt – printing nodes
• test12.cpp result12.txt – printing edges
• test13.cpp result13.txt – fake iterators
In C++, a moved-from object is always in a valid but unspecified state. In this assignment, a moved-from graph is assumed
to be an empty graph.
6. Tips:
• Your code should be const correct.
• Use C++14 style as much as possible – especially smart pointers.
• The lecture slides and tutorials have many code snippets that you may find helpful.
• Your code should be well documented, clearly describing how each function operates.
• For a value-like class, you should look at Week 4’s lecture slides.
• Do not use other libraries (e.g., boost).
• You should use exceptions for error handling, as required, instead of using C-style asserts. In the other parts of this
assignment, you are free to use asserts as you see fit.
• The reference solution is around 500 lines including comments.
7. Testing
You need to make sure that your solution compiles on the CSE machines using the command:.
g++ -std=c++14 -Wall -Werror -O2 -o testX testX.cpp
The dry run for give will be the first test case.
To run your code, type:
./testX
You should create your own test cases to check all the functionalities of your code against the specifications.
8. Marking
Your submission will be given a mark out of 100 with 70% an automarked performance component for output correctness
and 30% a manually marked component for code style and quality.
As this is a third-year course, your code is expected to be well formatted, documented and structured. We also expect that
you will use standard formatting and naming conventions.
If you write in C or use C types (e.g. union) or #define macros, you will lose performance marks and style marks.
A number of test cases will be used to mark your solution. To pass a test case, your solution must produce exactly the same
output as the reference solution. The results from both will be compared by using the linux tool diff.
9. Submission Instructions
Copy your code to your CSE account and make sure it compiles without any errors or warnings. Then run your test cases. If
all is well, then submit using the command:
give cs6771 ass3 Graph.h Graph.tem
You do not need to submit a makefile or other test files. We will supply a makefile and test cases for each test.
Late submissions will be penalised unless you have legitimate reasons for an extension which is arranged before the due
date. Any submission after the due date will attract a reduction of 20% per day to your individual mark. A day is defined as a
24-hour day and includes weekends and holidays. No submissions will be accepted more than three days after the due date.
Plagiarism constitutes serious academic misconduct and will not be tolerated.
Further details about lateness and plagiarism can be found in the Course Introduction.

COMP6771 Assignment 4: The B-Tree

1. Aims
In this assignment you will get a chance to implement a reasonably complex, generic
C++ container, together with proper iterators. You will practice working with template
classes and everything this entails. You will write a bi-directional iterator from scratch,
use iterator adaptors to provide reverse iterators. You will also employ lots of the C++
features you have learnt about in this course. You will also have a second chance to
practice working move semantics if you didn’t get it right in Assignment 3.
2. The B-Tree Container
B-Trees are generalised binary search trees, in that a binary-search-tree-like property is
maintained throughout the entire structure. The primary difference—and it’s a big
one—is that each node of the tree has many children, from a handful to thousands.
Actually, it’s the number of client elements stored within the node that determines the
number of children. In the same way that a single element partitions a binary search tree
into two sub-trees, a
B-Tree node storing four
clients elements
partitions the B-Tree into
five sub-B-Trees. If the
four elements are stored
in sorted order, it’s very
easy to constrain what
type of elements can
reside in each of the five
sub-B-Trees.
Check out the B-Tree node
we’ve drawn on the next
page. Note that C, J, S, and W
split the rest of the B-Tree
into sub-B-Trees that store elements A through B, D through I, K through R, T through
V, and X through Z. This B-Tree property is maintained throughout the entire structure.
Think of each node as a mother with quintuplets instead of twins.
The above picture implies that the stored elements are characters, but any element
capable of comparing itself to others can be stored in a B-Tree. And the decision to store
four keys per node was really arbitrary. While all nodes will store the same number of
elements (except along the fringe—sometimes there just aren’t enough elements to fill up
the fringe of the B-Tree), the actual node size can be tweaked to maximise performance.
In practice, the number is typically even, and is chosen so that the total amount of
memory devoted to one node is as close to a memory page size as possible. That way, all
of your elements are likely to be right next to each other in memory, and the operating
system maximises the number of elements in the cache at any one time.
We’re not going to burden you with those optimisations though. Your task is to
implement a generic B-Tree template capable of storing any type whatsoever. Here’s a
very brief look at the template interface. You’ll need to provide implementations for the
constructor and destructor, the insert operation, the two versions of find (which are
precisely the same, save the const versus non-const business), and the output
operator <<. You will also need to provide full, explicit copy control using value
semantics, i.e., no shared pointees.
template
class btree {
public:
btree(size_t maxNodeElems = 40);
btree(const btree&);
btree(btree&&);
btree& operator=(const btree&);
btree& operator=(btree&&);
friend ostream& operator<< <> (ostream&, const btree&);
// typedef’s for iterators and declarations
// for begin(), end(), rbegin(), rend() and
// cbegin(), cend(), crbegin() and crend() go here
iterator find(const T&);
const_iterator find(const T&) const;
pair<iterator, bool> insert(const T&);
// make sure your destructor does not leak memory
// (if raw pointers are used)
~btree();
private:
// your internal representation goes here
};
The btree.h header file tells you everything you need to know about what you’re
implementing and what you aren’t. You must implement what’s outlined above, and in
doing so, you should write clean, compact C++ code that you’d be proud to show mum
and dad.
3. Implementation Details
3.1 Internal Representation
You are free to choose whatever suitable STL container to to represent a b-tree node. As
for the pointers linking a node with its child nodes and parent node, you can either use
raw pointers or smart pointers. This is completely up to you. However, either raw
pointers or smarter pointers must be used. failure to do so will result in a final mark of 0 for
this deliverable.
3.2 Insertion
Remember that you are not required to balance the B-Tree.
We’re leaving the details of the concrete representation up to you, but the details of
insertion are complicated enough that you deserve a few illustrations. Once you have
insertion down, search is more or less straightforward.
For the purposes of illustration assume that nodes are engineered to store up to four
characters. Initially, a B-Tree is empty, but after inserting two elements, the state of the
tree would look as follows:
Because there are only two elements in the tree, we needn’t give birth to any child nodes.
In fact, it won’t be until we saturate the root node above with two more elements before
the addition of new elements will mandate the allocation of a child.
To insert the letter P at this point would require that the X be shifted over to make room.
The node is designed to store a total of four elements, so the P really belongs in between
the M and the X:
Throw in a G for good measure, and voilà, you have a saturated node of size four:
At this point, the node is structured this way for the lifetime of the B-Tree. But now that
it’s completely full, it will need to give birth to child nodes as needed.
Consider now the insertion of the letter T. Since five’s a crowd, a new node—one capable
of storing all types of characters ranging from Q through W—is allocated, and a pointer
to this node is recorded as being ‘in between’ elements P and X of the root:
Curious how the tree grows after we insert a B, a Z, an N, and then an R? Check out the
following film in slow motion:
Note that each of the new nodes was allocated because the first element inserted into it
was required to reside there. T had to go in the node stemming between P and X because
anything alphabetically in between P and X needs to be placed there. B is inserted before
G, Z after X and N between M and P. Finally R is T’s sibling.
As more and more characters are inserted, it’s likely that even the child nodes will
saturate, and when that happens, each of the children starts its own family. Consider the
insertion of S and W into the Frame-5 B-Tree above. R and T will allow S and W to join
them:
The insertion of Q and V at this point would require the introduction of third-level
nodes, as with:
In theory, there’s no limit whatsoever to how deep the tree can get. At the risk of
repea-ting ourselves and seeming monotonous, let us say some important things again:
The tree above stored four elements per node, but B-Trees can store up to any
prede-fined maximum. The default value of the constructor argument implies that you
should store a default of 40 elements per node. Of course, the code you write should
work for any value greater than 0.
The tree above stored characters, but the B-Tree is templated, so we could have just as
readily used a B-Tree of strings or doubles or records. Of course, the code you write
shouldn’t be character-specific, but general enough to store any type whatsoever. That’s
where templates come in.
The underlying implementation of the B-Tree is for you to decide, but the
implemen-tation certainly must make use of a multiply-linked structure in line with the
drawings above. Failure to do so is likely to result in a nice, round mark for this
deliverable (0!). How do you store the client elements and the child nodes? That’s your
job.
The insert function returns a pair that is a class template provided in the C++ STL. The
first element in the pair is an iterator positioned at the element inserted. The second
element is a Boolean value indicating whether the insertion is successful or not. The
second element is false if the element to be inserted is found already in the B-Tree and
true otherwise.
3.3 Searching
The find function returns an iterator positioned at the element found in the B-Tree. If
the element being searched is not found in the B-Tree, an iterator that is equal to the
return value of end() is returned.
3.4 Copy Control
All copy-control members must be implemented correctly. The move constructor and
move-assignment operators are implemented in a few lines each. For a moved-from
btree object, you should know by now how to put it in a state correctly according to the
C++14 requirement. For this assignment, a moved-fromm b-tree should be empty.
3.5 Iterators
You are required to implement a bonafide bi-directional iterator type capable of doing
an inorder walk of the B-Tree. An inoder traversal will allow all values in a B-Tree to be
printed in the increasing order of their values, where the comparison operator is defined
by the type of the elements in the B-Tree. Since the iterators are bi-directional they will
also support the reverse inorder traversal. You MUST implement your iterators as an
external class (btree_iterator), failure to do so will result in a final mark of 0 for this
deliverable.
The iterators will come in const and non-const forms, just like they would for any
built-in STL container. The iterators should respond to the *, ->, ++, –, == and !=
operators and be able to march over and access all of the sorted elements in sequence,
from 1 to 32767, from “aadvark” to “zygote”, etc., as well as support backward
move-ment. The challenge is working out how ++/– behave when a neighboring
element resides in another part of the B-Tree.
Your iterators should be appropriately declared as bi-directional. You should implement
and test the complete bi-directional iterator functionality. This includes pre/post
incre-ment and decrement. The post-increment/decrement operations should return a
copy of the value pointed to before the increment/decrement is performed.
It can be argued that the non-const iterators to a B-Tree are dangerous, since changing
the values of elements is likely to break the B-Tree invariant. This is indeed the case, but
you still have to implement this feature to develop some practical experience and we
will assume the responsibility. Your non-const iterator will be tested, e.g., increment
every value in the B-Tree by one. It is important that you get to practice writing a
non-const iterator.
In addition, you are to implement const and non-const forms of reverse iterators.
These reverse iterators should be returned by the rbegin() and rend() B-Tree
mem-ber functions. You should use iterator adaptors to implement your reverse
iterators. Once you have managed to make the const and non-const forms of the “forward”
iterators work for you, it takes usually a few extra minutes to implement the reverse iterators by
using iterator adaptors.
You can now implement the C++14 begin and end member functions, cbegin(), cend(),
crbegin() and crend(). This can be done in a few minutes by implementing them in terms of the
member functions that you have already implemented for the “forward” and reverse iterator.
3.6 Output Operator
You are to implement the output operator for the B-Tree class. This operator should just
print the values of the nodes in the B-Tree in breadth-first (level) order. The values
should be separated by spaces. No newline is to be output. For example, the output
operator would print the following when called on the last version of the tree in 3.1:
G M P X B N R S T W Z Q V
You may assume that the types stored in your B-Tree themselves support the output
operator. Note that we will use the output operator in combination with the iterator
traversal to ensure that your B-Tree structure is above-board correct. This means that
you must construct your B-Tree exactly as indicated, any other approach, including any
balancing scheme, is likely to lead to failed tests.
4. Testing the B-Tree
We’ve provided a simple C++ program that’ll exercise your B-Tree just enough to start
believing in it when it passes. It’s hardly exhaustive, as it only builds B-Trees of integers.
It does, however, do a good job of confirming that find and insert do their jobs, and it
does an even better job of showing you how quickly B-Trees support the insertion of
roughly 5,000,000 random integers in less than 90 seconds. Try that with a hash table or a
binary search tree and you’ll see it flail in comparison. This is cool and you should think
so too! Exciting!
Apart from this test program, a couple of other simple tests are provided.
You are responsible for making sure your B-Tree is bullet proof, and if some bug in your
code isn’t flagged by our tests, that’s still your crisis and not ours. You should try
buil-ding your own test programs to make sure that everything checks out okay when
you store doubles, strings, and structures. This is a great opportunity to try some unit
testing, because the class you’re testing is very small and easily stressed.
Your code will be compiled together with a test file containing the main function and
with these compiler flags:
% g++ -Wall -Werror -O2 –std=c++14 -fsanitize=address…
No matter where you do your development work, when done, be sure your deliverable works on
the school machines.
5. Getting Started
You are provided with a stub that contains the files you need to get started on this
deliverable. The stub is available on the subject account. Login to CSE and then type
something like this:
% mkdir -p cs6771/btree
% cp ~cs6771/soft/17s2/btree.zip .
% unzip btree.zip
% ls
% more README
In the stub, you should find a fully documented btree.h file, a btree_iterator.h
stub file, and some test files designed to exercise the B-Tree and make sure it’s working.
You’ll see a Makefile in the mix as well.
You are free to introduce any new classes you like, e.g., a node class. To make marking
easier please place any new classes in the submission files. Take the time to do this thing right,
since it’s really at the heart of what C++ generics are all about. You should want to do
these things the right way.
You are not allowed to change the names of the btree/btree_iterator classes.
Neither can you change the public interface of the btree class template as defined in
btree.h, of course, you will agument it with the appropriate iterator related types and
operations.
Please note that the supplied files don’t yet compile since there is no definition for some
of the files.
Our implementation with generous comments consists of about 400 lines of C++ code.
6. Marking
This deliverable is worth 10% of your final mark.
Your submission will be given a mark out of 100 with a 80/100 automarked component
for output correctness and a 20/100 manually marked component for code style and
quality.
As always, failure to implement a proper B-Tree representation and/or an external,
iterator class, will earn you a total mark of 0 for this deliverable.
As this is a third-year course we expect that your code will be well formatted,
docu-mented and structured. We also expect that you will use standard formatting and
naming conventions. However, the style marks will be awarded for writing C++ code
rather than C code.
As for the performance of your solution, we are lenient. When compared to a
straightforward implementation, your solution is expected not to run >20X slower.
7. Submission
Copy your code to your CSE account and make sure it compiles without any errors or
warnings. Then run your test cases. If all is well then submit using the command (from
within your del4 directory):
% give cs6771 ass4 btree.h btree_iterator.h
Note that you are to submit specific files only, this means that these are the only files you
should modify. You should also ensure they work within the supplied infrastructure.
If you submit and later decide to submit an even better version, go ahead and submit a
second (or third, or seventh) time; we’ll only mark the last one. Be sure to give yourself
more than enough time before the deadline to submit.
Late submissions will be penalised unless you have legitimate reasons to convince the
LIC otherwise. Any submission after the due date will attract a reduction of 20% per day
to the maximum mark. A day is defined as a 24-hour day and includes weekends and
holidays. Precisely, a submission x hours after the due date is considered to be ceil(x/24)
days late. No submissions will be accepted more than five days after the due date.
Plagiarism constitutes serious academic misconduct and will not be tolerated.
Further details about lateness and plagiarism can be found in the Course Outline.

CS6771 Assignment Five Parallel Bucket Sort

Aims:
• To learn how to write multithreaded programs in C++
• To learn how to use mutex locks to avoid race conditions in multiple threads
• To learn about potential performance bottlenecks and performance evaluation of parallel programs
Your task is to take a slow single threaded sort algorithm and redesign it into a parallel radix sort algorithm that sorts a vector of
numbers as quickly as possible.
The sorting algorithm takes a vector of unsigned ints and sorts them by using a MSD (Most Significant Digit) radix sort, which uses
lexicographic order.
For example, given a vector [ 32, 53, 3, 134, 643, 3, 5, 12, 52, 501, 98 ], the sorted output would be [ 12, 134, 3, 3, 32, 5, 501, 52, 53,
643, 98 ] (as if a shorter number were conceptually left-justified and padded on the right with “-1” to make it as long as the longest
number for the purposes of determining sorted order).
A MSD radix sort can be done easily through a parallel bucket sort. A bucket sort takes the most significant digit of each number and
groups the list of numbers with the same digit into one bucket. For example, the vector given above may be split into the following
buckets according their most significant digits:
Bucket 1: [ 134, 12 ]
Bucket 3: [ 32, 3, 3 ]
Bucket 5: [ 53, 5, 52, 501]
Bucket 6: [ 643 ]
Bucket 9: [ 98 ]
Afterwards, each bucket is sorted recursively, starting with the next most significant digit:
Bucket 1: [ 12, 134 ]
Bucket 3: [ 3, 3, 32 ]
Bucket 5: [ 5, 501, 52, 53]
Bucket 6: [ 643 ]
Bucket 9: [ 98 ]
Finally, all the buckets are concatenated together in order: [ 12, 134, 3, 3, 32, 5, 501, 52, 53, 643, 98 ]
Requirements:
In this assignment, you will need to create two files: BucketSort.cpp and BucketSort.h. These files can contain as many
classes, functions and structs as you require. However, because this assignment is about speed, there is no requirement that any
structure must strictly adhere to object oriented design principles (e.g., structure member fields do not need to be private). For any
single-threaded solution without using multiple threads, a mark of 0 will be awarded.
BucketSort.h must contain the following struct (which can be added to):
#ifndef BUCKET_SORT_H
#define BUCKET_SORT_H
#include
struct BucketSort {
// vector of numbers
std::vector numbersToSort;
void sort(unsigned int numCores);
};
#endif /* BUCKET_SORT_H */
The member field numbersToSort will be modified by user code to add numbers to be sorted to a BucketSort object. The same
member field will then be read from after the sort method has been called to confirm that the numbers have been sorted correctly. Your
main task is to write a multithreaded definition of the sort member function in your BucketSort.cpp file.
The sort method will be passed an unsigned int containing the number of CPU cores that are available to be used. You do not need to
adhere to this number when creating threads, however, it can be useful as it is not sensible to create more threads than there are CPU
cores available. Secondly, in some test cases, the number of cores available may be less than the true number of CPU cores available.
This is to ensure that the system running the application is able to keep other operating system tasks running. If at any point during
execution the number of threads your application is using exceeds the numCores limit for a given test case (used
in pbs.sort(numCores)) you program may be terminated by the marking system and you will score 0 for that test case.
Single Threaded Starter Code
The following definition of the sort member function is the reference solution for the correct sort output. Your multithreaded
implementation should produce the same output as this function, and should be much faster.
#include “BucketSort.h”
#include
#include
bool aLessB(const unsigned int& x, const unsigned int& y, unsigned int pow) {
if (x == y) return false; // if the two numbers are the same then one is not less
than the other
unsigned int a = x;
unsigned int b = y;
// work out the digit we are currently comparing on.
if (pow == 0) {
while (a / 10 > 0) {
a = a / 10;
}
while (b / 10 > 0) {
b = b / 10;
}
} else {
while (a / 10 >= (unsigned int) std::round(std::pow(10,pow))) {
a = a / 10;
}
while (b / 10 >= (unsigned int) std::round(std::pow(10,pow))) {
b = b / 10;
}
}
if (a == b)
return aLessB(x,y,pow + 1); // recurse if this digit is the same
else
return a < b;
}
// TODO: replace this with a parallel version.
void BucketSort::sort(unsigned int numCores) {
std::sort(numbersToSort.begin(),numbersToSort.end(), [](const unsigned int& x,
const unsigned int& y){
return aLessB(x,y,0);
} );
}
Sample User Code
Test cases for this assignment will involve user code creating large vectors of random numbers and calling the sort method. Your code
will be limited by time and memory with tests increasing in difficultly through decreasing time and memory limits and increasing
vector sizes.
The following sample test case shows how this is done. For the given single threaded code, this sort takes around about 23 seconds to
run on the CSE server williams (with 8 cores). In comparison the model multithreaded solution runs for about 6 seconds (without any
optimisation being applied).
#include
#include
#include #include “BucketSort.h”
int main() {
unsigned int totalNumbers = 500000;
unsigned int printIndex = 259000;
// use totalNumbers required as the seed for the random
// number generator.
std::mt19937 mt(totalNumbers);
std::uniform_int_distribution dist(1, std::numeric_limits::max());
// create a sort object
BucketSort pbs;
// insert random numbers into the sort object
for (unsigned int i=0; i < totalNumbers; ++i) {
pbs.numbersToSort.push_back(dist(mt));
}
// call sort giving the number of cores available.
const unsigned int numCores = std::thread::hardware_concurrency();
pbs.sort(numCores);
std::cout << “number of cores used: ” << numCores << std::endl;
// print certain values from the buckets
std::cout << “Demonstrating that all the numbers that start with 1 come first” <<
std::endl;
std::cout << pbs.numbersToSort[0] << ” ” << pbs.numbersToSort[printIndex – 10000]
<< ” ” << pbs.numbersToSort[printIndex] << ” ” <<
pbs.numbersToSort[pbs.numbersToSort.size() – 1]
<< std::endl;
}
Tips:
• Consider carefully when you need shared and local memory.
• Consider carefully when you need to use mutexes around shared memory.
• Consider carefully when you need to use multithreaded code and when you need to use single threaded code.
• You may need to split the sort into multiple sections where threads are created, destroyed and later additional threads are
created.
• You shouldn’t need to use condition variables, futures or thread pools in this assignment, but you can use these if they help
you.
• You shouldn’t need any pointers or dynamic memory to complete this assignment.
• The lecture slides and tutorials have many code snippets that you may find helpful.
• You shouldn’t need to create any additional classes or structs (but you may if you like).
• The reference solution is 220 lines including comments.
• Do not use other libraries (e.g., boost).
• The textbook: Wilkinson, B. and Allen, M., Parallel Programming, 2nd Edition (2005), Pearson Prentice Hall., provides
further details and ideas on how to implement the parallel bucket sort.
A six page pdf photocopied extract covering the relevant section is available here. Figure 4.10 is the best diagram of what
you should be working your code towards.
Testing
Place all your code in a files called BucketSort.h and BucketSort.cpp
Ensure it compiles on the CSE machines using the following sample makefile
all: sortTester
sortTester : sortTester.o BucketSort.o
g++ -std=c++14 -Wall -Werror -O2 -pthread -o sortTester sortTester.o BucketSort.o
sortTester.o: sortTester.cpp BucketSort.h
g++ -std=c++14 -Wall -Werror -O2 -pthread -c sortTester.cpp
BucketSort.o : BucketSort.h BucketSort.cpp
g++ -std=c++14 -Wall -Werror -O2 -pthread -c BucketSort.cpp
clean:
rm *.o sortTester
To compile your code type:
make
To run your code type:
./sortTester
You should create your own test cases to check the full functionality of your code against the specifications.
If you like, you may use the benchmarking suite provided to compare performance with your previous result, or with other students
(though if comparing with other students, run it on wagner)
Marking
Your submission will be given a mark out of 100 with 80% an automarked performance component for output correctness and 20%
manually marked component for code style and quality.
As this is a third-year course we expect that your code will be well formatted, documented and structured. We also expect that you will
use standard formatting and naming conventions.
A number of test cases will be used to mark your solution. To pass a test case, your solution must produce exactly the same output as
the reference solution. The results from both will be compared by using the linux tool diff.
In a number of test cases, your solution will be tested under a time limit, which is set according to the reference solution that
was quickly written with no optimisations being applied.
Submission Instructions
Copy your code to your CSE account and make sure it compiles without any errors or warnings. Then run your test cases. If all is well
then submit using the command:
give cs6771 ass5 BucketSort.h BucketSort.cpp
If you submit and later decide to submit an even better version, go ahead and submit a second (or third, or seventh) time; we’ll only
mark the last one. Be sure to give yourself more than enough time before the deadline to submit.
Late submissions will be penalised unless you have legitimate reasons for an extension which is arranged before the due date. Any
submission after the due date will attract a reduction of 20% per day to your individual mark. A day is defined as a 24-hour day and
includes weekends and holidays. No submissions will be accepted more than three days after the due date.
Plagiarism constitutes serious academic misconduct and will not be tolerated.
Further details about lateness and plagiarism can be found in the Course Introduction.
Acknowledgement
Inspiration for this assignment is based on a 2009 Massey University assignment written by Dr Martin Johnson.

Related products