# Basic building blocks of C++
For these questions you will code using some of the basic building blocks of C++: vectors, functions, and classes.
Where you are to write functions, ensure you use constness and references where appropriate, to avoid needlessly copying objects, and to help ensure you have written correct code.
Make sure you don’t commit any compiled code to your GitHub repository; or if you choose to use an IDE, any large project directories created by your IDE.You can make these on your machine, but don’t `commit` or `add` them to your repository — this isn’t what git is designed for.
Remember — the Preliminary work is due in at the earlier deadline for Preliminary 1, the Core work is due in at the later deadline (after reading week).
—-
# Preliminary 1 — Items on a map [3 marks]
For this part of the coursework, you will write code to work with data about items that are placed at different places on a map, each of which is available at a certain time.
Items are described by four properties:
– Their latitude (a number in degrees, e.g. 51.75087595155126)
– Their longitude (a number in degrees, e.g. -0.33483137537806396)
– A string ID
– The time at which they become available: an integral number of seconds past the hour
In `Item.h`, make a class Item that contains these as private member variables.
Give the class an appropriate constructor that initialises these four variables to the arguments passed to the constructor (passed in the above order).
To compile your code, `BasicItemTest.cpp` provides a main function that makes two `Item` objects.You can compile this as follows:
`g++ -std=c++11 -o BasicItemTest BasicItemTest.cpp`
…and if it compiles then run:
`./BasicItemTest`
The code will not produce any output, as it’s just constructing objects but doing nothing with them.Let’s work on that.
In `Item.h`, implement an `operator<<` function for printing out Item objects, so that the following code will work:`Item strand(51.5115, -0.116, “StrandCampus”, 600);“cout << strand << endl;`…and will produce output of the form:`{latitude, longitude, “ID”, time}`…in this case:`{51.5115, -0.116, “StrandCampus”, 600}`To compile your code, `ItemPrintTest.cpp` provides a main function that makes two `Item` objects, prints them out, and checks the output is correct.You can compile this as follows:`g++ -std=c++11 -o ItemPrintTest ItemPrintTest.cpp`…and if it compiles then run:`./ItemPrintTest`All working well?One last thing — let’s actually do something interesting with the items.Create a class function `distanceTo` in Item, that will take another Item, and return the distance to it in metres.To compute this distance, use the [Haversine Formula](http://andrew.hedges.name/experiments/haversine/), which can be implemented using the following pseudo-code:`dlon = lon2 – lon1“dlat = lat2 – lat1“a = pow((sin(dlat/2)), 2) + cos(lat1) * cos(lat2) * pow((sin(dlon/2)), 2)“c = 2 * atan2( sqrt(a), sqrt(1-a) )“distance = R * c (where R is the radius of the Earth)`Note that this pseudo-code assumes the latitude and longitude are in *radians*, whereas your class stores them in degrees, so you will need to convert them to radians first.`cos`, `sin` and the other trignometric functions can be obtained by putting `#include
To test your code, you can use ItemDistanceTest.cpp.To compile to an executable `ItemDistanceTest`, run:
`g++ -std=c++11 -o ItemDistanceTest ItemDistanceTest.cpp`
Note that this will only work once you have implemented the constructor and functions discussed above.
—-
# Core — Circular buffer [3 marks]
### What is a circular buffer?
Circular buffers use a fixed-size block of memory to temporary buffer data.For instance, keypresses on the keyboard put characters in the buffer; and when the operating system is ready to process them, it reads characters from the buffer.
The buffer starts as being empty.For instance, if we had a buffer of size 5 it would look like:
`[ | | | | ]`
If we then write ‘a’ and ‘b’ into the buffer it would look like:
`[ a | b | | | ]`
…and then removing the next item in the buffer would give:
`[ | b | | | ]`
If we continue to write elements into the buffer, e.g. ‘c’, ‘d’, ‘e’, ‘f’ then when the end is reached, elements start being written into any spare space at the start:
`[ f | b | c | d | e ]`
At this point the buffer is full.We can’t write any more data to it — in the case of keyboard buffers, the computer would start beeping.We can though remove an element, which always removes the *oldest*, i.e. the letter ‘b’, which would leave the buffer:
`[ f | | c | d | e ]`
We could then remove the next element (c), or as there is now a space again, write another character into the buffer.
### Given Code — SimpleVector
Your implementation in this part of the coursework should be based on a `SimpleVector` of characters. A `SimpleVector` is a simplified version of `vector`, removing the functionality that you don’t need here.But, it can still do the operations you’d expect to be able to do with an array in Java: to create a `SimpleVector` of some size; to ask for its size; and to access elements.For instance:
`SimpleVector
`cout << someNumbers.size() << ”
“; // will print out 10“someNumbers[3] = 42;// set element 3 to 42“cout << someNumbers[3] << ”
“; // will print out element 3, i.e. 42`### Implement a circular bufferIn the file`CircularBuffer.h` complete the definition of the CircularBuffer class.In `CircularBuffer.h`, the constructor of the class should take the capacity of the buffer as an argument.It should have a `SimpleVector
It needs to have the functions:
1. `count()` which returns how many things are in the buffer
2. `full()` which returns true *iff* the buffer is full
3. `add()` which takes a character and adds it to the buffer (you can assume the buffer is not full — you do not need to implement error handling)
4. `remove()` which removes and returns the next character from the buffer (you can assume the buffer is not empty — you do not need to implement error handling)
Once you have provided the constructor and functions, you can test your code using `TestCircularBuffer.cpp`.To compile this, run:
`g++ -std=c++11 -o TestCircularBuffer TestCircularBuffer.cpp`
If it compiles, you can then run:
`./TestCircularBuffer`
As well as being confident your solution behaves correctly, and that you have used const appropriately, ensure you use the initialisation syntax with your constructor to appropriately initialise the vector to be the right size — `SimpleVector` does not have a default constructor, so this is the only way to give it its size.
Note: do not change the code in `SimpleVector.h` and do not add any extra `#include` statements to `CircularBuffer.h`.Otherwise you may get a mark of zero.If you have a case for adding an extra `#include` ask in the KEATS discussion forum.
# Core — Nearly Sorted [3 marks]
Your next task is to do with vectors of integers that are *nearly* sorted, in ascending order.For our purposes, the vector is nearly sorted if either:
– There is a pair of elements i and j, such that if these two elements are swapped, the vector becomes sorted; or,
– There is a pair of elements i and j, such that if the range of elements from i and j (inclusive) is reversed, the vector becomes sorted.
For instance, if our vector is:
`vector
…then it is nearly sorted as swapping the elements with index 1 and 3 gives a sorted vector.Or, if the vector is:
`vector
…then it is nearly sorted as reversing the elements from index 2 to index 5 gives a sorted vector.The vector:
`vector
…is not nearly sorted, though, as multiple swaps would be needed to make it sorted.
In the file NearlySorted.h, implement a function `nearlySorted` that takes a vector of integers, and returns a `HowToSort` object that describes how to sort the vector.`HowToSort` is a small class that has been written for you — you should not change this.For the examples above, the HowToSort objects that would be returned are:
`return HowToSort(1,3,true); // index 1 and 3, true because it’s a swap`
`return HowToSort(2,5,false); // index 2 and 5, false because it’s a range reversal`
`return HowToSort();// default constructor: it can’t be sorted`
Assumptions you can make:
* The input vector will not be empty
* The input vector will not have any duplicate numbers.
* If it’s possible to use a swap or a reverse, use a swap.
* If the vector is already sorted, return `HowToSort(0,0,true)`
To perform some basic testing on your code, once you have implemented the function (or at least declared it, and given it a return statement) `TestNearlySorted.cpp` defines a simple test harness.To compile this, run:
`g++ -std=c++11 -o TestNS TestNearlySorted.cpp`
If it compiles, you can then run:
`./TestNS`
When your work is marked, a wider range of test cases will be used, including input vectors that contain up to 10,000 numbers — your code should be able to handle these with modest resources (10 seconds of CPU on a desktop machine, and 0.5GB of RAM).
# Further C++ practice
These questions give you more practice working with the basic building blocks of C++: vectors, functions, and classes; and additionally, pointers.
Where you are to write functions, ensure you use constness and references where appropriate, to avoid needlessly copying objects, and to help ensure you have written correct code.
Make sure you don’t commit any compiled code to your GitHub repository; or if you choose to use an IDE, any large project directories created by your IDE.You can make these on your machine, but don’t `commit` or `add` them to your repository — this isn’t what git is designed for.
Remember — the Preliminary work is due in at the earlier deadline for Preliminary 2, the Core work is due in at the later deadline (after reading week).
—-
# Preliminary 2 — Using stacks [3 marks]
In `Stack.h`, implement a class `Stack` that is a Stack of `double`s.You should implement this using the `vector` class: Stack.h already contains the necessary `include` and `using` lines for this.
Your `Stack` class needs to provide three functions:
– `empty()` that returns true if the stack is empty
– `pop()` that removes and returns the top element off the stack
– `push()` that takes a double and pushes it onto the stack
Once you have written a Stack class, after it — but still in `Stack.h` — implement a function `evaluate` that takes a `string` containing a mathematical expression written in [Reverse Polish Notation](https://en.wikipedia.org/wiki/Reverse_Polish_notation), and returns the result of evaluating the expression, as a `double`.
In reverse polish notation (RPN), operators are written *after* rather than between what they act upon.For instance:
`3.0 4.0 +`
…is the same as the usual (infix) notation `(3.0 + 4.0)`.Or:
`3.0 4.0 + 2.0 *`
…is the same as `(3.0 + 4.0) * 2`.The advantage of RPN is that there is no need to worry about brackets and order of precedence.
To implement the `evaluate` function, use your Stack class.RPN expressions can be evaluated by splitting the input string by spaces into tokens, and working through it one token at a time:
* If the token is a `+`, pop two numbers a and b off the stack, and push (b + a) onto the stack
* If the token is a `-`, pop two numbers a and b off the stack, and push (b – a) onto the stack
* If the token is a `*`, pop two numbers a and b off the stack, and push (b * a) onto the stack
* If the token is a `/`, pop two numbers a and b off the stack, and push (b / a) onto the stack
* Otherwise, the token is a number: push it onto the stack
After going through all the tokens, the answer is then on the top of the stack: return it.
To test your code, compile and run `TestStack.cpp`.This will to evaluate three expressions, and check they give the right answer.As a reminder, to compile using g++ at the command line, with debugging turned on (`-g`):
`g++ -std=c++11 -g -o TestStack TestStack.cpp`
…then run `./TestStack`
Notes:
– `std::stod(s)` will convert the string `s` into a double, and return its value
—-
# Core — Treasure hunt, continued [3 marks]
*For this part, first, copy across your Item.h file from Part1, over the (basically empty) file provided in the Part2 directory.*
## A map of items
In MapOfItems.h, make a class `MapOfItems`. It needs to have:
– a private member variable that stores a vector of `Item`s
– a public function ‘addItem’ for adding an item to the end of this vector
– a public function ‘size()’ for returning the size of this vector
– a public function ‘getItems’ that returns a const reference to the vector of Items
## Taking a tour of the Map
For this part of the assignment, you will implement a greedy algorithm that finds an order in which to visit the Items, allowing for a walking speed between them, and during the times at which they are available (i.e. from a given number of seconds past the hour, until 15 minutes after).
It should be in a class function called `getTour`, implemented within the MapOfItems class.It should take a walking speed as an argument.The tour should take no longer than 3600 seconds; that is, the last item you visit, must be visited before 3600.It should return the tour as a `vector` of `Item*`s — each of these Item pointers should point to some item in the vector of Items inside the MapOfItems class.
The algorithm specification is as follows:
– The tour must finish before time 3600.
– The tour must start at the Item that is available first, at the time it becomes available.For instance, if there are five items on the map, available from times 3,10,14,16,18, the item at time 3 would be visited first, at time 3.(That is, the current time is 3.)
– Then, repeatedly:
– For each Item *I* that hasn’t been visited yet,
– Calculate the time that it would take to walk from the previous Item visited, to *I* (using the distance between them, and the walking speed).This time, plus the current time, is the time that *I* would be visited — if we went there next.This time is denoted *visit(I)*.
– If *visit(I)* is too late (more than fifteen minutes after the item appears), we can’t visit that Item
– If it’s too early (before the time at which the item appears), we would need to wait at *I* until it appeared.This is okay. but we would set *visit(I)* to the time at which *I* appears.
– The next item to visit is then the one with the smallest *visit(I)*: append a pointer to this Item to the tour, and set the current time to *visit(I)*..
– Or, if we are too late for all the remaining Items, the tour has finished.(Yes, it might not be able to visit all the items.)
– The function then returns the tour
To test your implementation, use MapOfItemsTest.cpp.
# Core — String construction [3 marks]
This part of the assignment considers a string construction problem defined as follows:
– You are given as input a target string
– Starting with an empty string, you add characters to it, until your new string is same as the target.You have two options to add characters to a string:
– You can append an arbitrary character to your new string, with cost x
– You can clone any substring of your new string so far, and append it to the end of your new string, with cost y
– For a given target, append cost x, and clone cost y, we want to know what the *cheapest cost* is of building the target string
For some simple examples:
– Target “aa”, append cost 1, clone cost 2: the cheapest cost is 2:
– Start with an empty string, “”
– Append ‘a’ (cost 1), giving the string “a”
– Append ‘a’ (cost 1), giving the string “aa”
– Target “aaaa”, append cost 2, clone cost 3: the cheapest cost is 7:
– Start with an empty string, “”
– Append ‘a’ (cost 2), giving the string “a”
– Append ‘a’ (cost 2), giving the string “aa”
– Clone “aa” (cost 3), giving the string “aaaa”
– Target “xzxpzxzxpq”, append cost 10, clone cost 11: the cheapest cost is 71:
– Start with an empty string, “”
– Append ‘x’ (cost 10): “x”
– Append ‘z’ (cost 10): “xz”
– Append ‘x’ (cost 10): “xzx”
– Append ‘p’ (cost 10): “xzxp”
– Append ‘z’ (cost 10): “xzxpz”
– Clone “xzxp” (cost 11): “xzxpzxzxp”
– Append ‘q’ (cost 10) : “xzxpzxzxpq”
In the file `StringConstruction.h` write a function `stringConstruction` that takes the target string, the append cost, and the clone cost (in that order), and returns the cheapest way of making the target string.It doesn’t need to return *how* to do it, just the cost.
To test your code, TestStringCons.cpp contains some test cases.To compile and run at the command line:
`g++ -std=c++11 -o TestSC TestStringCons.cpp`
`./TestSC`
Note: when your work is marked, it will be tested with target strings of a range of sizes.To get full marks, it will need to work for the largest of these target strings, which is 30,000 characters.Your code will be ran on a modest desktop PC, and allowed 2 seconds.
# Linked lists
For these questions you will be making a Linked List template class.The basics are Preliminary 3, the rest are part of the Core assignment.
Note that in answering these questions, **you should not add any `#include` or `using` statements**: you must implement the functionality yourself, without using any data structures from the standard library.I have added `#include
Make sure you don’t commit any compiled code to your GitHub repository; or if you choose to use an IDE, any large project directories created by your IDE.You can make these on your machine, but don’t `commit` or `add` them to your repository — this isn’t what git is designed for.
Remember — the Preliminary work is due in at the earlier deadline for Preliminary 3, the Core work is due in at the later deadline (after reading week).
—-
# Preliminary 3 — LinkedList basics [3 marks]
## a) Making a list node
In the file `node.h` implement a template class `Node` that represents a node in a doubly-linked list.It should have three `public` member variables:
– The `data` stored in that Node.The type of this should be a template argument.
– A pointer to the `next` Node in the list
– A pointer to the `previous` Node in the list
Make a constructor that takes an item of data, stores it in the node, and sets the two pointers to `nullptr`.
## b) Making an iterator for list nodes
The file `node.h` contains an incomplete `NodeIterator` class, that contains a pointer to a `Node`.It is a template class — a `NodeIterator
Complete the definition of the `NodeIterator` class, so that:
– We can increment the iterator, using ++, which makes it point to the next node in the list
– We can see if two iterators are the same, using the == operator.Two iterators are the same if they point to the same Node.
– We can see if two iterators are different, using the != operator
To test your code, compile and run TestNode.cpp.A Makefile has been provided, run:
`make TestNode`
…at the command line.This makes two Nodes, one linked to the other, then makes an iterator over these.
If you don’t have make, you can always open the Makefile and copy-paste the command that will be used to compile TestNode:
`g++ -Wall -g -std=c++11 -o TestNode TestNode.cpp`
—-
# Core — Making a LinkedList class [6 marks]
In the file `linkedlist.h` implement a template class LinkedList.This should use the `Node` class you have written so far.As member variables you should have:
– A pointer to the head of the list
– A pointer to the tail of the list
– A count of how many elements are in the list
The functions in LinkedList should be:
– A constructor, that creates an empty list (head and tail are `nullptr`, 0 elements in the list)
– A `push_front` function that takes an item and pushes it onto the front of the list, i.e. it becomes the head of the list.(Note this should *not* take a Node: for a LinkedList
– A `front()` function, that returns a reference to the data inside the head node
– A `push_back` function that takes an item and pushes it onto the back of the list, i.e. it becomes the tail
– A `back()` function, that returns a reference to the data inside the tail node
– A `size()` function that returns the count of how many elements are in the list
– A `begin()` function that returns an iterator pointing to the head of the list
– An `end()` function that returns an iterator pointing to `nullptr`(NB it doesn’t point to the tail: it points *off the end* of the list — and the Node after the tail is `nullptr`.)
– A destructor, that `delete`s every node in the list.
– A `reverse()`function that reverses the order of the nodes in the list (NB it doesn’t make new nodes, it should re-order the existing nodes.)
(It is recommended you implement them in roughly this order.)
To test your LinkedList at this point, compile and run TestList.cpp.You can do this using:
`make TestList`
It may help you to comment out tests that use code you haven’t written yet (as they won’t compile).Alternatively, if you push your code to github, the automated tests will be run individually and should work even if you have not completed all parts.
Note: when your work is marked, deductions will be made for memory leaks.Take care to ensure that you have deleted every object you created with new, exactly once.
Once you’re happy with your work so far, it’s time to make the class a bit more useful.
First, extend your class to have a constructor that takes a [std::initializer_list
`LinkedList
When we write this, the numbers in braces are put in the initializer_list and passed to the constructor.
Next, inserting and erasing elements from linked lists is a classic interview question.Add functionality as follows:
– `insert()`, taking as arguments a NodeIterator pointing to where to insert the new element in the list; and the element itself.The element should be inserted in this position, and an iterator to the new element returned.For instance for the list:
`[3,5,7]`
…if we have an iterator pointing to `5` and call insert with this and `4` the new list would be:
`[3,4,5,7]`
…and insert() would return an iterator pointing to 4.
Note you may edit your iterator class to provide a function to access the Node pointer from inside the iterator.
– `erase()`, taking as argument a NodeIterator pointing to an element to erase; and returning what is now in its place — after removing element *i*, it should return a NodeIterator to what is now element *i*.For instance, if the list was:
`[3,5,7]`
…and an iterator pointing to `5` was erased, that would update the list to be:
`[3,7]`
…and return an iterator pointing to 7.If you are deleting the last item off the list, it should return an iterator pointing to nullptr.
Again, as above, make sure your implementation avoids memory leaks.
To test your LinkedList now, compile and run TestListD.cpp.You can do this using:
`make TestListD`
# Binary Search Trees
In these questions you will be making a Binary Search Tree template class.The basics are Preliminary 4, the rest are part of the Core assignment.
Note that in answering these questions, you should not add any `#include` or `using` statements: you must implement the functionality yourself, without using any additional data structures from the standard library.I have added `#include
Make sure you don’t commit any compiled code to your GitHub repository; or if you choose to use an IDE, any large project directories created by your IDE.You can make these on your machine, but don’t `commit` or `add` them to your repository — this isn’t what git is designed for.
—-
# Preliminary 4 — Binary search tree nodes [3 marks]
In the file `treenode.h` implement a template class `TreeNode` that represents a node in a binary search tree.It should have four `public` member variables:
– The `data` stored in that node.The type of this should be a template argument.
– A unique_ptr
– A unique_ptr
– A pointer to the parent of the node (NB not a unique_ptr)
Make a constructor that takes an item of data, stores it in the node, and sets the parent pointer to nullptr.
Make a function `setLeftChild(TreeNode* child)` that:
– stores `child` in the left `unique_ptr`
– sets the `parent` pointer of the child to point to `this`
Write an analogous function `setRightChild` for setting the right child of the node.
Make a function `write` that takes an ostream reference, and prints to it:
– The result of calling write on the left child (if there is one)
– A space character
– The data from the node
– A space character
– The result of calling write on the right child (if there is one)
You should then be able to write, e.g:
`someNode->write(cout);`
…to be able to print the subtree starting at some node to screen.(NB `write` should be marked as const.)
To test your code, compile and run TestTreeNode.cpp.A Makefile has been provided, run:
`make TestTreeNode`
…at the command line.This makes four tree nodes, linked to each other, then prints out the tree.
—-
# Core — Making and working with binary search trees [6 marks]
## The Tree class
In the file `tree.h` implement a template class BinarySearchTree.This should use the `TreeNode` class you have written in Preliminary 4.
As a private member variable you should have a unique_ptr, `root`, containing a pointer to the root TreeNode.
### Default constructor
Implement an empty default constructor.
### write
Write a function `write` that takes an `ostream` reference, and calls `write` on the root of the tree.(NB write should be marked as const.)
### insert
Make a function `insert` that takes an item of data, and inserts it into the tree:
– If the data is not already in the tree, it should make a node and add this in the correct place
– If something equal to the data is already in the tree, it shouldn’t make any new nodes, and shouldn’t change any of the existing nodes.
In both cases, it should return a `TreeNode*`, pointing to the node containing the data.
Note, in your implementation, you should only compare the data inside nodes by using the `<` operator.Do not use `>` or `!=` or `==` or any other operator.For each node, if it has a left child, then `left->data < data`, and if it has a right child, then `data < right->data`.
As an example, if the binary search tree is:
`…4`
`./…`
`2…..7`
…and 3 is inserted, the tree should become:
`…4`
`./…`
`2…..7`
`.`
`..3`
..because, starting at the root:
– `3 < 4`, so we need to go to the left- `2 < 3`, so we need to go to the right- We’ve got to the bottom of the tree, so 3 is added as the right child of 2A pointer to the node containing 3 would then be returned.(Not a unique_ptr, a normal pointer.)If 7 is inserted into the tree above, the function should stop when it gets to the node containing 7, and return a pointer to that node.### findWrite a function `find` that takes an item of data and traverses the Binary Search Tree to see if the data is in the tree.If it is, it should return a `TreeNode*` pointing to the node containing the data.If it is not in the tree, it should return `nullptr`To test your code, compile and run TestTree.cpp.A Makefile has been provided, run:`make TestTree`### Copy constructorWrite a copy constructor for the BinarySearchTree class.The copy constructor should make the newly constructed tree be identical to the tree given as input.The following code should work once you have done this:`BinarySearchTree
`a.insert(2);`
`a.insert(1);`
`a.insert(3);`
`BinarySearchTree
`a.write(std::cout); cout << ”
“; // print out a“b.write(std::cout); cout << ”
“; // print out b — should be the same as a`(NB if you like, you can add code to the Node class to help with this.)### Assignment operatorWrite an assignment operator for the BinarySearchTree class.The assignment operator should make the tree assigned to, be identical to the tree given as input.The following code should work once you have done this:`BinarySearchTree
`a.insert(2);`
`a.insert(1);`
`a.insert(3);`
`BinarySearchTree
`b = a; // uses the assignment operator`
`a.write(std::cout); cout << ”
“; // print out a“b.write(std::cout); cout << ”
“; // print out b — should be the same as a`(NB if you like, you can add code to the Node class to help with this.)## The TreeMap class### KeyValuePairIn the file `treemap.h`, the incomplete class `KeyValuePair` defines a class that holds a key–value pair, that will be used to make a map.Complete the class by implementing:- a Constructor that takes a Key and a Value and stores them in the respective member variables.*(NB Use the initialisation syntax for this)*- a Constructor that takes just a Key, and stores this in the relevant member variable *(NB again, use the initialisation syntax)*- an `operator<` function that compares it to another `KeyValuePair` object, by comparing just the keys (using the < operator).Remember to use const here correctly.### TreeMapIn the file `treemap.h`, the incomplete class `TreeMap` defines a class that holds a tree of key–value pairs.Provided is a function `insert` that takes a Key and a Value, and inserts these into tree as a KeyValuePair.It then returns a pointer to the *data* inside the tree node returned by `tree->insert`.
Implement a function `find` that takes a Key, makes a KeyValuePair from it, and calls `find` on the tree to see if a match can be found.If it can be found, return a pointer to the *data* inside the tree node found by find (a `KeyValuePair
To test your code, compile and run TestTreeMap.cpp.A Makefile has been provided, run:
`make TestTreeMap`
## A tree iterator
In `treenode.h` implement a template class `TreeNodeIterator` that is an iterator over a binary search tree.As with the ListNodeIterator from the Part3 directory, it should have:
– A single member variable pointing to a TreeNode *and no other member variables*
– A constructor that sets this to point to a given TreeNode
– An `operator*` that dereferences this pointer, and returns it (by reference)
– `operator==` and `operator!=` that compare it to other iterators, by checking if they point to the same (or a different) node
– An increment operator, `operator++` that moves the iterator to point to the next node in the list.
For the tree:
`…4`
`./…`
`2…..7`
`.`
`..3`
– Incrementing an iterator pointing to 2 should make it point to 3;
– Incrementing an iterator pointing to 3 should make it point to 4;
– Incrementing an iterator pointing to 4 should make it point to 7
In other words, iterator steps through the tree in ascending order.
Extend your `BinarySearchTree` class with `begin()` and `end()` functions that return iterators to the left-most node in the tree (in the tree above — 2), and nullptr, respectively.
Note that your iterators should still work if additional items are inserted into the tree.For instance, if we have the tree:
`…5`
`./…`
`1…..9`
`.`
`..3`
…and have an iterator at the ‘3’ node, then insert 4 into the tree to get:
`…5`
`./…`
`1…..9`
`.`
`..3`
` `
`4`
…then increment our iterator, it should be at the ‘4’ node — it shouldn’t be at the ‘5’ node.
## maxDepth
In `TreeNode` implement a function maxDepth that returns the maximum depth of the subtree rooted at that node.If the TreeNode has no children, it has depth 1.Otherwise, its depth is 1 + the maximum of either the depth of its left child, or the depth of its right child.
In `BinarySearchTree` implement a function maxDepth that returns the maxDepth of the root (or 0 for an empty tree).
## AVL trees
In the worst case, when using a Binary Search Tree, the data is adding in ascending order, giving the following tree:
`A`
`.`
`..B`
`…`
`….C`
That is, the depth of the tree is the same as the number of elements.What we ideally want is a balanced tree, where the depth of the tree is *log(N)* in the number of elements, N.
AVL trees rebalance the tree every time a node is inserted.This is done by computing the *balance factor* of that node.It is computed as:
`balanceFactor(node) = maxDepth(left node) – maxDepth(right node)`
If this balance factor is ever 2, or -2, the tree beneath that node needs to be rebalanced: it is much deeper on one side than the other.For the following tree:
`A`
`.`
`..B`
`…`
`….C`
…the balance factors are:
`-2`
`.`
`..-1`
`…`
`….0`
…because looking at the root, the depth of the right subtree is 2; but the depth of the left subtree is 0.
To become rebalanced, an AVL tree performs one of four operations.Perform these where needed in your implementation of `insert` in the BinarySearchTree class.After inserting a node you will need to look at its parent, and its parent’s parent; compute the balance factor of its parent’s parent; and if the tree is then unbalanced, perform the appropriate operation.
(A full AVL tree implementation does a bit more than this, but implementing the cases described here is sufficient for this assignment.)
### Left rotation
If a node becomes unbalanced, when a node is inserted into the right subtree of its right child, then we perform a left rotation.This is best shown with an example.Suppose we had the subtree:
`A`
`.`
`..B`
…and added ‘C’, we would get:
`A`
`.`
`..B`
`…`
`….C`
*C* is what we have just inserted; *B* is its parent; *A* is its parent’s parent.
*A* now has a balance factor of -2, so we left rotate: we reorder the nodes so that B is the root of this subtree instead of A:
`..B`
`./.`
`A…C`
Each of these now has a balance factor of 0, so it is balanced again.
Note if A had a parent, B is attached to this, replacing A.
### Right rotation
If a node becomes unbalanced when a node is inserted into the left subtree of its left child, then we perform a right rotation.Suppose we had the tree:
`….C`
`…/ `
`..B`
…and added ‘A’, we would get:
`….C`
`…/ `
`..B`
`./`
`A`
C is now unbalanced: its balance factor is 2, because its left child has depth 2, but its right child is empty (depth 0).Thus, we right rotate: we reorder the nodes so that B is the root of this subtree instead of C:
`..B`
`./.`
`A…C`
Note if C had a parent, B is attached to this, replacing C.
### Left-Right rotation
If a node becomes unbalanced when a node is inserted into the right subtree of its left child, then we perform a left-right rotation.If we had the tree:
`….C`
`…/ `
`..A`
…and added B, we would get:
`….C`
`…/ `
`..A`
`..`
`…B`
C is now unbalanced.This scenario is fixed by performing a left–right rotation.First, we perform a left rotation on the subtree rooted at A, making B the root of this subtree:
`….C`
`…/ `
`..B`
`./`
`A`
Then, we perform a right rotation on C, making B the root of this subtree:
`..B`
`./.`
`A…C`
Note if C had a parent, B is attached to this, replacing C.
### Right-left rotation
One scenario left: a node becomes unbalanced when a node is inserted into the left subtree of its right child, then we perform a right-left rotation.If we had the tree:
`….A`
`….. `
`……C`
… and added B, we would get:
`….A`
`….. `
`……C`
`…../`
`….B`
A is now unbalanced.A right-left rotation fixes this in two stages.First, we perform a right rotation on the subtree rooted at C:
`….A`
`….. `
`……B`
`…….`
`……..C`
Then, we perform a left rotation on A, making B the root of this subtree:
`..B`
`./.`
`A…C`
Note if A had a parent, B is attached to this, replacing A.
To test your code, compile and run TestTreeD.cpp.A Makefile has been provided, run:
`make TestTreeD`
# Sudoku [9 marks]
In these questions you will be working on writing code that will solve Sudoku puzzles.
All these questions are part of the Core assignment, due in at the deadline after reading week.
For the avoidance of doubt — with the exception of the SudokuSquareSet question, you may add extra `#include` and `using` statements, if you need to.
Make sure you don’t commit any compiled code to your GitHub repository; or if you choose to use an IDE, any large project directories created by your IDE.You can make these on your machine, but don’t `commit` or `add` them to your repository — this isn’t what git is designed for.
# a) Making a Sudoku board class
In the file `Sudoku.h` make a class `Sudoku` that holds an *incomplete* [Sudoku](https://en.wikipedia.org/wiki/Sudoku) solution.
It should have a constructor that takes a single argument — the size of the board.For instance, for a 9×9 Sudoku, the constructor would be given the value 9.Or, for a 16×16 board, the constructor would be given the value 16.
You need to store the incomplete solution as a member variable. The *recommended* way to do this, to start with, is to have a vector of vectors (a square array), in which each square is represented as a `set
Write a function `getSquare(int row, int col)` that returns the value in the cell in the square at the given row and column:
– If there is only one value in the set for that square, return the number in that set.
– Otherwise, return -1 (a dummy value to indicate we don’t know what should be in that square yet)
# b) Setting the value of a Sudoku square
Write a function `setSquare(int row, int col, int value)` that sets the value in the cell in the square at the given row and column, then updates the sets of possible values in the rest of the grid to remove choices that have been eliminated.For instance, if we put a ‘3’ on a given row, then nothing else on that row can have the value 3.
The implementation of setSquare is split into two parts.
First, the easy part: the set of possible values for that cell is cleared, and `value` is inserted.This forces that cell to have that value.
Then, a loop begins that does the following:
– Loop over the entire grid
– For each square that has only one value in it, remove that value from the sets of possible values for:
– All the other squares on that row
– All the other squares in that column
– All the other squares in the same *box*.A 9×9 grid is divided into 9 boxes, each 3×3: no two values in the same box can have the same value.For larger grids (e.g. 16×16), the size of the box is always the square root of the size of the grid.
If at any point the set of values for a square becomes empty, the function should return false: it has been shown that there is no value that can go in a square.
The loop should continue whilst values are still being removed from the sets of possible values.The reason for this is that after setting the given square, we might end up with only one option being left for some other squares on the grid.For instance, if on a given row some of the squares had the sets:
`{3,4} {3,5}{4,5}`
…and we call setSquare to set the middle square to have the value 3, then before the loop:
`{3,4} {3}{4,5}`
On the first pass of the loop, we would find the square containing `3` and remove this from the other sets on the row (and the other sets in the same column and box).The row then looks like:
`{4} {3}{4,5}`
We then start the loop again, and find the square containing the value ‘4’.This is removed from the other sets on the row (and column and box) to give:
`{4} {3} {5}`
We then start the loop again, and find the square containing the value ‘5’.
This process stops when, having looped over the board, and updated the sets by removing values, our sets have stopped getting any smaller.At this point the function returns true.
For simple Sudodu puzzles, this process here is enough to solve the puzzle.No guesswork is needed: setting the squares of the board to hold the initial values specified in the puzzle, is enough to cause all the other squares of the board to have only one option left.
You can test this by compiling and running BasicSudoku.cpp:
`g++ -std=c++11 -g -o BasicSudoku BasicSudoku.cpp`
This calls `setSquare` for the values in a simple Sudoku puzzle; then uses `getSquare` to check your code has the right answer.
# c) Searching for a solution
For more complex puzzles, after putting in the initial values using setSquare, some of the squares on the board have more than one value left in their set of possible values — using logic alone, we cannot deduce what the value has to be; we have to make a guess and see what happens.
For this, we are going to use the Searchable class.This is an *abstract class* for puzzles, containing the following virtual functions:
– `isSolution()`: this returns true if the puzzle has been solved.For Sudoku, this means all the squares contain just one value.
– `write(ostream & o)`: a debugging function to print the board to screen.
– `heuristicValue()`: an estimate of how far the puzzle is from being solved.We will return to this in part (d)
– `successors()`: in a situation where a guess is needed, this returns several new puzzle objects, each of which corresponds to a different guess having been made.
Make your Sudoku class inherit from Searchable, by changing the opening of the class definition to `class Sudoku : public Searchable`
Implement isSolution() to only return true if the puzzle has been solved; i.e. every set in every square is of size 1.
Implement a write() function to print the board.You can display the board however you like.A reasonable implementation is to print out the board one row at a time:
– If the square has more than one value in its set, print a space character
– Otherwise, print the value from the set.
(I’m not marking write(), it is to help your debugging.If you want to print nothing at all, that’s fine.)
Implement successors() as follows:
– Make an empty vector of successors to return.This should be a `vector
– Find the first row containing a square that still has more than one option in its set
– Find the left-most square on that row
– For each value in the set for that square:
– Make a *copy* of the current Sudoku object (this) using new
– Use setSquare on the *copy* to set the value of the square
– If setSquare returns true, add the pointer to the back of the vector of successors to return.Otherwise, delete the pointer.(You can use a unique_ptr for this if you wish.)
– Once done, return the vector of successors
Once you have implemented these functions, you can test your code by using BreadthFSSudoku:
`g++ -std=c++11 -g -o BreadthFSSudoku BreadthFSSudoku.cpp`
# d) Other improvements
## SudokuSquareSet
Using a `set
`00000000 00000000 00000000 00001101`
`…………………………….^if bit 0 is 1, then 1 is in the set`
`…………………………..^..if bit 2 is 1, then 3 is in the set`
`………………………….^…if bit 3 is 1, then 4 is in the set`
Note that because 0 can never be in a Sudoku square, bit 0 is 1 if *1* is in the set, bit 1 is 1 if *2* is in the set, and so on.
Conceptually, it’s still a set — each value can only be stored once — but it’s much more efficient.
In the file `SudokuSquare.h` complete the definition of the SudokuSquareSet class.It should have exactly two member variables, and no others:
– An `unsigned int` whose bits denote what values are in the set
– An `int` that denotes how many values are in the set
…and provide similar functionality to `set
– A default constructor that creates an empty set (all bits set to 0)
– A size() function that returns how many values are in the set
– An empty() function that returns true iff there are no values in the set
– A clear() function that removes all values from the set
– operator==() that compares a SudokuSquareSet to another given SudokuSquareSet, and returns true if the values are the same
– operator!=() that compares a SudokuSquareSet to another given SudokuSquareSet, and returns true if the values are different
– begin() and end() that get iterators, allowing you to loop over the values in the set (you will need to implement an iterator class inside the SudokuSquareSet class for this)
– An `insert` function that adds a value to the set, and returns an iterator to it
– A `find` function that sees if a value is in the set — if it is, it returns an iterator to it, otherwise it returns end()
– An `erase` function that takes a value, and if it’s in the set, removes it
– An `erase` function that takes an iterator at a given value, and calls `erase()` with that value
To perform some basic tests on your SudokuSquareSet class you can compile and run TestSudokuSquare.cpp:
`g++ -std=c++11 -g -o TestSudokuSquare TestSudokuSquare.cpp`
Once you have done this, you can edit your Sudoku.h file to use `SudokuSquareSet` instead of `set
– Add `#include “SudokuSquare.h”` to the #include section at the top of `Sudoku.h`
– Replace `set
You should then be able to compile and run the tests you were using earlier, to test the overall Sudoku functionality.
## Other performance tweaks
We can improve on the basic sudoku solver in a few ways. Your mark for this part will be based on how quickly your solution works: the faster it runs, the higher the marks.As well as 9×9 boards, I will be testing your solution on larger (e.g. 16×16) Sudoku boards.
### A better setSquare
Suppose we had the following squares on a row:
`{3,4} {3,4,6} {3,4,6,7} {3,4}`
There are *2* cells that contain identical sets of size *2*.There are only two ways of satisfying this:
– 3 in the left-most cell; 4 in the right-most cell
– 4 in the left-most cell; 3 in the right-most cell
In either case, no other value on the row can have the value 3 or 4.We can thus remove 3 and 4 from the other sets:
`{3,4} {6} {6,7} {3,4}`
As before, this process loops and carries on until the sets stop getting any smaller — because there is a cell that contains just 6, we would then get:
`{3,4} {6} {7} {3,4}`
Extend the implementation of setSquare to include this sort of reasoning for duplicates sets of values in rows, columns and boxes: look for pairs of squares, with identical sets of size 2.
To test your code, compile and run BreadthFSSudoku again — it should explore fewer nodes than it did before you made these changes.
If you wish, you can then continue this work to add additional logic to setSquare.For instance, looking for 3 identical sets of size 3, 4 identical sets of size 4, etc.Or, any other deduction rule for Sudoku that you can find online, and implement in your work — add a comment to the website or paper you used as your source.
### Better search with a heuristic
Open up `BreadthFirstSearch.h`.It defines a search strategy known as breadth-first search.It has a queue of incomplete solutions (initially, the starting configuration of the board.Then, it repeatedly takes a board off the queue, and if it’s not a solution, gets its successors, and puts them on the queue.
The queue used follows a `first in, first out` (FIFO) strategy: the next board is always taken off the front of the queue; and new boards are always put on the back of the queue.
Breadth-first search can be improved by using a heuristic: an estimate of how close a board is to being finished.The `Searchable` class defines a `heuristicValue()` function that calculates an estimate of this.
Add a `heuristicValue()` function to your Sudoku class, that returns the number of squares on the board whose sets are of size greater than 1.On paper this corresponds to the number of squares we haven’t written a number into yet; and the fewer the squares, the closer it looks like that board is to being a solution.
Complete the `BestFirstSearch` class provided, so that instead of using a first-in first-out queue (as in breadth-first search) it uses a priority queue, sorted in ascending order of heuristic value.That is, when we get the successors to a board, these are inserted into the queue so that the board with the smallest heuristic value is always at the front.
To test your code, compile and run BestFSSudoku:
`g++ -std=c++11 -g -o BestFSSudoku BestFSSudoku.cpp`
This should expand fewer nodes than breadth-first search
NB: Your BestFirstSearch code should never assume `Searchable` objects are Sudoku objects.Only use functions defined in the Searchable base class.
### A better successors function
One last edit.In the successors function, we choose a square, and make successors corresponding to setting that square to have each of its possible values.We keep only the successors for which setSquare returned true.
If when we do this, we keep only one successor — and that successor isn’t a solution — then instead of returning a vector of just that one successor, recursively call `successors()` on that; and return what *it* returns.
The intuition for this is as follows.If setSquare only returned true for one of the possible successors, we have shown that, actually, having tried all the options, only one of the possible values for that square was acceptable.Thus, we can instead return the successors of that one valid option.We only need to return successors to search, to go on the queue, if there is more than one option to choose from.
As with before, implementing this should allow both breadth-first search and best-first search to expand fewer nodes.
# Warmup Exercises
For these exercises, you will write Java code to answer a number of coding interview style questions.The rest of the work on the module uses C++ and Scala, as you have done Java, this gives you the chance to get used to working with GitHub without also learning a new language at the same time.
Note that these exercises are the only ones in this GitHub repository that do not count towards your overall mark: _all other assignments count_.
Make sure you don’t commit any compiled code to your GitHub repository; or if you choose to use an IDE, any large project directories created by your IDE.You can make these on your machine, but don’t `commit` or `add` them to your repository — this isn’t what git is designed for.
# Single character edits
There are three sorts of single character edit that can be made to a string:
* Replacing one character with another, at some position
* Removing a character, from some position
* Inserting a character at some position, before what was previously there
Implement the method in the `SingleCharacterEdit` class (provided) that takes two strings, `a` and `b`, and returns a String that prescribes what single-character edit will turn a into b; or returns `null` if no such single-character edit exists.The format of the string returned should be as follows:
* If the character at position *n* was replaced with the character *c*, return the string `replace,n,c`.For instance, if character 1 was replaced with an x, return `replace,1,x`
* If the character at position *n* was removed, return `remove,n`.For instance, if the first character was removed, return `remove,0`.
* If a new character *c* was inserted at position *n*, return the string `insert,n,c`.For instance, for input strings `cat` and `chat`, return `insert,1,h`
Note the string returned should be exactly as prescribed here.Do not add additional spacing, and replace, remove and insert should be in lowercase.
To test your code, run the given class `TestSingleCharacterEdit`.This will perform some basic testing of your code, by calling it and checking it gives the right outputs.
# A screen as bytes
Each pixel on a monochrome (black and white) screen can be represented as a bit — either off (0) or on (1).The whole screen can in turn be represented as an array of bytes, with each byte storing eight pixels (eight bits).The first bytes in the array are the pixels at the left of the top row of the image; and the last bytes in the array are the pixels at the right of last row of the image.For instance, the following image, 16 pixels wide and 3 pixels tall:
`1111….1111….`
`….1111…….1`
`1111….1111…1`
..becomes the bytes (in binary):
`{11110000,11110000,00001111,00000001,11110000,11110001}`
…or in decimal:
`{240,240,15,1,240,241}`
When you are ready to test the code you will write for this question, run the given class `TestScreenAsBytes`.This will perform some basic testing of your code, by calling it and checking it gives the right outputs.
## Drawing a single pixel
Complete the method `setPixel` in the given class `ScreenAsBytes`.This takes as input:
* The bytes representing the screen, as described above
* The width of the image.You can assume this is a multiple of 8. *Hint: you can work out the height of the image from the length of the array, and the width.*
* The x and y positions of the pixel
The method should modify `screen’ so the given pixel has a value of 1.For instance, for a screen 16 pixels wide and 3 pixels tall that is entirely blank (all pixels set to zero), screen would be
`00000000,00000000,`
`00000000,00000000,`
`00000000,00000000`
…or in decimal `{0,0,0,0,0,0}`.After calling `setPixel(screen,16,0,1)` to set the first pixel on the second row to 1, screen should be:
`00000000,00000000,`
`10000000,00000000,`
`00000000,00000000`
…or in decimal `{0,0,128,0,0,0}`
To perform a basic test of your code, run TestScreenAsBytes, which as the first test will set a single pixel of the image to 1 and check the correct one has been set.
## Drawing a horizontal line
Complete the method `drawHorizontalLine`.This takes as input:
* The bytes representing the image, and its width (like `setPixel`)
* The start and end X positions of the horizontal line.These should be *inclusive* — that is, drawing a line from pixels 0 to 2 on row 1, should set the first *three* pixels on the row to 1
* The y position at which to draw the line (0 for the first 1, 1 for the next row, and so on)
The method should modify `screen` to contain a horizontal line drawn at the correct position.
To perform a basic test of your code, run TestScreenAsBytes, which as the second test will draw a horizontal line on the image and check the correct pixels have the value 1.
## Drawing a vertical line
Complete the method `drawVerticalLine`. This is the vertical equivalent of `drawHorizontalLine` line, and takes as input:
* The bytes representing the image, and its width
* The X position at which to draw the vertical line
* The start and end Y positions for the line.As with the horizontal line, these should be *inclusive*.
Reviews
There are no reviews yet.