辅导案例-FALL 2020

欢迎使用51辅导，51作业君孵化低价透明的学长辅导平台，服务保持优质，平均费用压低50%以上！ 51fudao.top

ASSIGNMENT #5: ADVANCED C++ AND DESIGN PATTERNS CS246, FALL 2020
Assignment #5: Advanced C++ and Design Patterns
Due Date: Wednesday, November 25, 2020, 5:00 pm
Online Quiz: Wednesday, December 2, 2020, 5:00 pm
Topics that must have been completed before starting:
1. Advanced C++: Unique and shared pointers (smart pointers)
2. Advanced C++: RAII: Resource Acquisition Is Initialization
3. Advanced C++: Exception Safety
4. Advanced C++: STL Algorithms
Learning objectives:
• Advanced C++: Smart pointers and RAII
• Advanced C++: Exception Safety
• Advanced C++: STL Algorithms
• This assignment has only one due date. All questions are due on the same due date. You must submit
the online quiz on Learn by the Quiz date.
• You must use the C++ I/O streaming and memory management facilities on this assignment. Marmoset will
be programmed to reject submissions that use C-style I/O or memory management.
• You may include the headers , , , , ,
, , , , , , and .
• You are not allowed to use delete. You must manage memory with smart pointers only.
• Each question on this assignment asks you to write a C++ program, and the programs you write on this
assignment each span multiple files. For this reason, we strongly recommend that you develop your solution
for each question in a separate directory. Just remember that, for each question, you should be in that
directory when you create your ZIP file, so that it does not contain any extra directory structure.
• You are required to submit a Makefile along with every code submission. Marmoset will use this
Makefile to build your submission.
Page 1 of 6
ASSIGNMENT #5: ADVANCED C++ AND DESIGN PATTERNS CS246, FALL 2020
Question 1
(40%) Historically, Google used an algorithm called “pagerank” in its search engine. Pages’ ranks were adjusted by their
popularity, as measured by the number of incoming links. In this question, you will write a simplified search-ranking system
based on the same concept. You must use smart pointers and RAII principles throughout your code. You should never directly
use new or delete, and, of course, must not leak memory.
Our “search engine” consists of an internal “web” of pages. Each page is a URL (which is just a string), a set of words that
appear on that page, and a set of links to other pages. This web is exposed through a class Web, which provides addPage,
addLink, and search methods. Two additional classes, Page and Result, are also provided, which just contain data.
void addPage(std::string url, std::set words) adds a page to the Web with the
given URL and words, and no links. Note that we haven’t introduced std::set, though it is in many ways similar to
std::map; you must learn its interface on your own. If the page already exists, then the old page and all links to and from it
are discarded and replaced with the new page.
void addLink(std::string from, std::string to) adds a link from the URL from to the URL to. If
either URL has not been added as a page, then this function should do nothing. Note that there is no interface to query what
links exist, only to add them.
std::vector search(std::string word) performs a search. The search result is a vector of
Results. Each Result consists of a Page and a rank, which is an unsigned long. The Page contains the URL and
words associated with the page. The returned vector must be in decreasing order by rank. If two pages have the same
rank, they should be in increasing order by URL (you can use < and > to compare strings!). You will probably want to use
to help you sort this vector.
Of course, the complexity of this problem is in the actual search algorithm. The search result should include every page
which either includes the word or is linked to by at least one page which includes the word. The ranking for each page x is a
sum of:
• 25 if the page x includes the word directly
• 5 for each page other than x which includes the word and links to x
• 1 for each page other than x which links to x but does not include the word
Do not worry about overflow when computing this sum.
For example, consider the following web:
URL: example.com/1 example.com/2 example.com/3
Words: stravinsky, retort, perfume retort, exhibit, glamour boogie, perfume, unclouded
Links to: example.com/1, example.com/6 example.com/1, example.com/3 example.com/2, example.com/5
URL: example.com/4 example.com/5 example.com/6
Words: retort, forage, guava perfume, stravinsky, guava perfume, exhibit, boogie
Links to: example.com/2, example.com/5 example.com/1, example.com/3 example.com/3, example.com/5
Note that real webs are not limited to exactly three words or two links per page. If we search this web for the word
“boogie”, our result should be:
Page 2 of 6
ASSIGNMENT #5: ADVANCED C++ AND DESIGN PATTERNS CS246, FALL 2020
URL Rank Explanation
example.com/3 32 25 points because “boogie” appears in example.com/3
5 points because “boogie” appears in example.com/6, which links to example.com/3
2 points because example.com/2 and example.com/5 link to example.com/3 but don’t
include “boogie”
example.com/6 26 25 points because “boogie” appears in example.com/6
1 point because example.com/1 links to example.com/6 but does not include “boogie”
example.com/5 11 10 points because “boogie” appears in example.com/3 and example.com/6, which both
link to example.com/5
1 point because example.com/4 links to example.com/5 but does not include “boogie”
example.com/2 6 5 points because “boogie” appears in example.com/3, which links to example.com/2
1 point because example.com/4 links to example.com/2 but does not include “boogie”
Result does not include any explanation; explanations are shown here to describe the process.
You will almost certainly need to create other datatypes, but must not change the public interface of any existing class.
You are provided with Makefile, main.cc, and web.h. You must implement web.cc, as well as any files for any
other classes you need to implement the functionality. You may modify the Makefile, and modify web.h so long as
you don’t change the public interface of any existing class, but must not change main.cc. A main function is provided in
main.cc to act as a test harness, which uses simple console commands to build and search a web:
Command Behavior
addpage u w Adds a page with URL u and (whitespace-separated) words w
addlink u1 u2 Adds a link from u1 to u2
search w Searches for the word w and prints out the results
Due on the due date: Implement Web’s methods. Save your solution in a file named a5q1.zip. The Makefile must
create an executable named a5q1 when the command make is given.
Question 2
(45%) A heap is a tree in which every node has a numeric value, and the values of all of the children of any node must be less
than the value of the node itself. A sum heap restricts this further: In a sum heap, the value of a node must be greater than the
sum of all of its children, at any depth (that is, all of its children, grandchildren, etc). In this question, you will write a sum
heap data structure using unique_ptrs which is strongly exception safe: Operations which violate the sum heap property
must throw an exception, and leave the tree in the state it was in before the method was called. You may not store a node’s
children links in non-unique_ptrs.
A sum heap is represented as a class SumHeap, which has a vector of unique_ptrs of children, a simple SumHeap *
pointer back to its parent or nullptr if it is the root, and an unsigned int value. Children may be added, queried, or
swapped, and are always returned to the user of a SumHeap as SumHeap *s, not unique_ptrs, because
the unique pointer is within the tree. SumHeap’s only constructor takes an unsigned int value argument and sets the
SumHeap’s value to it, with no children. SumHeap provides several methods: addChild, getParent, numChildren,
getChild, getValue, and swap. Note that there is no interface to remove children from a SumHeap. There is also a class
InvalidValueException, which is thrown when an operation would invalidate the sum heap property, or when the sum
of the values of the children at any depth of a tree node overflows. To check if summing unsigned integers overflowed, simply
check if the resultant sum is less than either of the operands. Note that when checking if the sum heap property is violated,
you will need to check not just the node(s) being changed, but their parents, and their parents, etc. Adding or swapping nodes
may violate the sum heap property at a higher level while satisfying it at a lower level!
SumHeap *addChild(unsigned int value) creates a new node which is a child of this, with the given
value, and returns a bare pointer to that node. If adding this node would violate the sum heap property or overflow, an
InvalidValueException is thrown, the node is not added, and this’s number of children does not change.
SumHeap *getParent() returns this->parent. size_t numChildren() returns the number of children
Page 3 of 6
ASSIGNMENT #5: ADVANCED C++ AND DESIGN PATTERNS CS246, FALL 2020
this has. SumHeap *getChild(size_t idx) returns the child at index idx. unsigned int getValue() re-
turns this’s value. With the exception of getChild, these methods are trivial and cannot fail. The behaviour of getChild
when called with an index out of bounds is not defined.
void swap(SumHeap *other) swaps this for other. That is, if this is this->parent’s third child, and
other is other->parent’s first child, then this becomes other->parent’s first child, and other becomes this->parent’s
third child. If this operation is invalid, an InvalidValueException is thrown, and both SumHeap nodes stay in their
original locations. The operation may be invalid because doing so would invalidate the sum heap property, because doing so
would cause an overflow, or because either this or other are roots.
InvalidValueException has no properties and carries no additional information.
To demonstrate, consider these two trees:
188
33 37
18 10 13 7
1 7 8
170
40 45
9 8 22 23
10
4 5
The left tree is an invalid sum heap: Although 37 (labeled in red) is greater than the sum of its direct children (10+13+7 = 30),
it is not greater than the sum of its further children (10 + 13 + 7 + 8 = 38). The right tree is a valid sum heap. Consider
swapping its 22 and 10 subtrees:
170
40 45
9 8 10 23
4 5 22
In the resulting tree, 45 violates the sum heap rule. Note that it is not the immediate parent of either swapped node!
You are provided with Makefile, main.cc, and sumheap.h. You must implement sumheap.cc. You may not
modify the public interface of SumHeap or InvalidValueException. A main function is provided in main.cc to act
Page 4 of 6
ASSIGNMENT #5: ADVANCED C++ AND DESIGN PATTERNS CS246, FALL 2020
as a test harness, which uses simple console commands to build a SumHeap. It takes a single command line argument, which
is the value of the root of the SumHeap being created. The entire tree is printed after every command, except those that fail.
It also has a “cursor”, which is the node currently being manipulated. The commands are:
Command Behaviour
addchild v Adds a child to the current node with value v, and sets the cursor to that node
child i Sets the cursor to the ith child of the current node, if it exists
parent Sets the cursor to the parent of the current node, if it exists
swap path Swaps the current node with the node described by path, which is a sequence of numbers. For
instance, to swap the current node with the 3rd child of the 1st child of the 0th child of the root, use
swap 0 1 3.
Due on the due date: Implement SumHeap’s methods. Save your solution in a file named a5q2.zip. The Makefile
must create an executable named a5q2 when the command make is given.
Page 5 of 6
ASSIGNMENT #5: ADVANCED C++ AND DESIGN PATTERNS CS246, FALL 2020
Written Assessment
Questions 3, 4, and 5 are part of the written assessment, and may not be publicly discussed on Piazza (or anywhere else).
Question 3
(5%) How could a program which always uses shared_ptrs or unique_ptrs nonetheless fail to adhere to the principles
of RAII?
Question 4
(5%) Consider the following short method:
void transfer(Account *account1, Account *account2, int amount, int serviceFee) {
account1->decreaseBalance(amount);
account2->increaseBalance(amount);
account2->decreaseBalance(serviceFee);
}
Assume that decreaseBalance and increaseBalance are exception safe, decreaseBalance throws an ex-
ception when the balance is decreased below 0, and increaseBalance throws an exception when the balance overflows.
Describe, in English, what would need to be done to make transfer exception safe.
Question 5
(5%) You are writing code which uses a data structure written by someone else which is not exception safe, but which has a
correct deep copy constructor which never throws exceptions. How can you write exception-safe code which uses this data
structure?
Page 6 of 6

欢迎咨询51作业君