CMSC 14200 4 Introduc!on to Computer
Due: Thursday, January 30th at 4pm CT
The goal of this homework is to help you prac!ce working with graphs, and to gain further experience with GUI programming in pygame.
Ge"ng started
To test and submit your solu!on, you will need to pull some files provided by the instructors to your homework repository, and then add your code to three of
those files. Please start by naviga!ng to your coursework directory:
$ cd ~/cmsc14200-win-2025/coursework-GITHUB_USERNAME
Use git status to make sure that your repository is in a clean state. The output should look like this:
$ git status .
On branch main
Your branch is up to date with 'origin/main'.
If the output does not match, please review the relevant parts of the Git Basics tutorial. If you run into trouble, please ask for help.
Once you have cleaned up and are in a good state, run the following command:
$ git pull upstream main
(This command will pull the materials for this assignment into your local copy of your repository and will create a commit.)
Navigate to the hw3 directory that you just pulled and complete your work for this assignment in the files wordgraphs.py , test_graphs.py , and task5.py .
Tes!ng
As in the previous homework, we have provided automated tests for parts of this assignment. See How to Test your Solu!ons for a refresher on how to test
your code.
We strongly encourage you to use ipython3 to test your code by hand and to test your func!ons as you go.
As far as manually tes!ng your code in this assignment, the examples we provide assume that you have set up ipython3 to use autoreload and have
imported wordgraphs .
In [1]: %load_ext autoreload
In [2]: %autoreload 2
In [3]: import wordgraphs
Your Tasks
Adding type annota!ons
As in the prior homeworks, we expect you to add type annota!ons to the func!ons and methods you implement. You should add type annota!ons and
docstrings to any func!ons or methods you add, including any helper func!ons you choose to implement and any class methods you add.
You can typecheck your code for Tasks 1 through 4 at any !me like this:
mypy wordgraphs.py
You will generally want to check types any !me you implement a new func!on or method to check that you have added annota!ons correctly.
There are also some automated tests that will typecheck your code. This is explained in the “Type Checking” sec!on below.
Summary
These are the tasks in this assignment:
Task 1: complete RealWordsGraph class in wordgraphs.py
Task 2A: implement variants func!on in wordgraphs.py
Task 2B: write tests for variants in test_graphs.py
Task 3: implement shortest_word_path func!on in wordgraphs.py
Task 4A: complete PseudoWordsGraph class in wordgraphs.py
Task 4B: write tests for PseudoWordsGraph in test_graphs.py
Task 4C: complete RealWordsLazyGraph class in wordgraphs.py
Task 5: implement graph-drawing GUI in task5.py
Word Graphs
As we saw in class, graphs are a model and a type of data structure that allow us to represent en!!es and their rela!onships. These en!!es are o#en physical:
ci!es, people, or similar; with readily-imagined rela!onships like having transporta!on links, friendships, or the like.
But, we can work with more abstract en!!es and somewhat ar!ficial rela!onships as well. For instance, we might have a graph whose ver!ces correspond to
correctly-spelled words in the English language. What rela!onships might these more-conceptual en!!es have? Words might be linked by having a common
root in La!n, being from the same part of speech, or myriad other possibili!es depending upon what we are interested in.
Here is one defini!on of a rela!onship between words: two words are connected by an edge if they are of the same length, and exactly one of their le$ers is
different. For instance, “graph” and “grape” would be linked, or “node” and “code”, or “node” and “note”.
With this more abstract graph, the applica!ons may also be more abstract. But one could imagine using this kind of graph in support of some type of word
game, or perhaps as part of a spelling checker.
Task 1
The file graph.py contains an abstract base class for an undirected, unweighted graph whose ver!ces are strings. Given a vertex, we can find the set of
adjacent ver!ces, or the size of this set (the word’s degree). We can also ask whether a string represents a word that is actually in the set of real words used to
build the graph.
To complete this task, make an implementa!on of the class RealWordsGraph that inherits from the Graph base class. The constructor takes in the filename for a
list of words on which to base the graph, presumably from an English-language dic!onary. You should then populate an internal representa!on within the
object that treats each of the words in the input file as a vertex, and any two words of the same length that are only different in one of their le$ers as being
adjacent.
We do not specify the precise design of the data structure that you must employ, so long as you implement each of the methods in the class to func!on as
expected, and compute all the edges within the constructor. That said, think about a simple approach that stores all the needed informa!on using basic Python
data structures within a$ributes of the RealWordsGraph class; it is not necessary, and overly complicated, to adopt the mul!-class approach we saw in lecture
that used Vertex objects separate from a Graph class.
The specified file will contain one word per line. Because it will be computa!onally intensive to determine all the words that should share an edge in the graph,
the constructor takes a parameter for the maximum word length; skip any word longer than it. Also, skip any word that contains any character beyond the
twenty-six le$ers in the English alphabet; and change any upper-case le$ers to their lower-case equivalents.
We have provided the file web2 that contains all the words from the 1934 edi!on of Webster’s dic!onary. Because of its age, the copyright has lapsed, and this
file is included in some open-source opera!ng systems. Given the comprehensiveness of this data, you will find that it takes several seconds to build a graph
with words of length up to four, and a few !mes longer (on the order of half a minute) to build a graph with words of length up to five; hence, we recommend
you test your code star!ng with maximum lengths of three, then try four and five once your code appears to be working. (Please note that !mes are highly
dependent upon your computer and implementa!on details, so !mes close to the ones noted above, even if somewhat different, are not in and of themselves
cause for concern.)
Here is sample use of this class:
In [2]: g = wordgraphs.RealWordsGraph("web2", 4)
In [3]: g.is_word("code")
Out[3]: True
In [4]: g.is_word("abcd")
Out[4]: False
In [5]: g.adjacent("code")
Out[5]:
{'bode',
'cade',
'cede',
'coda',
'codo',
'coke',
'cole',
'come',
'cone',
'cope',
'core',
'cote',
'coue',
'cove',
'coze',
'dode',
'gode',
'lode',
'mode',
'node',
'rode',
'tode',
'wode'}
In [6]: g.degree("code")
Out[6]: 23
Remember that one difference between sets and lists is that sets do not have a no!on of order, so if your code produces the same set of adjacent words, but
they are printed in a different order, this is not a meaningful or worrisome dis!nc!on.
You can run the tests for Task 1 by using:
pytest -xvk task1 test_hw3.py
Task 2A
We could perform various analyses on this graph using breadth-first search. For instance, we might ask, given a word, what are the words that are a distance
of n away from that word in the graph? This would correspond to words that take a total of n modifica!ons to generate when star!ng at the specified word.
(These will usually be changes to n different le$ers in the word, but sequences that involve one or more changes to the same loca!on in the string would also
count, provided that no word appears mul!ple !mes as intermediate stages in the series of modifica!ons.)
Write the func!on variants that takes in a graph, a star!ng word, and a distance, and, using breadth-first search, produces the set of words exactly that many
edges away from the star!ng word. For instance, all of the words in the adjacency example shown earlier for Task 1 would cons!tute the answer for a star!ng
word of “code” and a distance of 1; and, for “code” and a distance of 2, one of the words would be “note” (because we can go from “code” to “node” and from
“node” to “note”). Given any word, only the word itself will be a distance of zero away from itself, and given a non-word, the set will be empty.
Here is sample use of this func!on:
In [7]: g = wordgraphs.RealWordsGraph("web2", 5)
In [8]: wordgraphs.variants(g, "abcde", 2)
Out[8]: set()
In [9]: wordgraphs.variants(g, "quake", 0)
Out[9]: {'quake'}
In [10]: wordgraphs.variants(g, "quake", 1)
Out[10]: {'quaky', 'quale', 'quare', 'quave'}
In [11]: wordgraphs.variants(g, "quake", 2)
Out[11]: {'huave', 'qualm', 'quark', 'quarl', 'quart', 'quire', 'suave'}
Again recall that set ordering is not meaningful.
Task 2B
Similarly to the prior assignment, we have only provided tests for some of the tasks in this homework, and you will write some of your own tests. We have
provided a test_graphs.py file in which you should write your tests for this task. Compared to Homework 2, we have given less detail about the tests you
should write. In par!cular, there are not empty func!ons in the test file, with specific descrip!ons for each test.
In the file test_graphs.py , write a series of func!ons whose names begin with test_task2_ and that test the variants func!on on a RealWordsGraph . For
reasons of performance, limit the maximum word length to three or four in your tests.
Here is a list of things you should test:
T0: that variants returns an empty set when given a word not in the dic!onary and a distance of at least one
T1: that variants yields a set consis!ng only of the given word when given a real word and a distance of zero
T2: that variants gives back the same set as adjacent would give, when given a real word and a distance of one
T3 and T4: tests for variants with real words and distances of two and three, respec!vely
In a comment for each of your test func!ons, write which requirement (T0, T1, T2, etc.) is fulfilled by a given test func!on.
To get the full benefit of tes!ng, you should determine the correct results of these tests manually, not merely by running your func!on and then se"ng its
answer as the expected result. How can you independently arrive at the correct answers for longer distances? You could for instance, use adjacent on a
star!ng word to get all the words one change away, then use adjacent on each of them, etc., in ipython3 , to work through the traversal by hand. You may also
be able to keep this task manageable by using unusually-spelled words that you expect will not have too many neighbors in the graph. If you adopt this kind of
approach, do be sure that your implementa!on of adjacent passes all the Task 1 tests first, so that you don’t base your test data here on incomplete or
incorrect adjacency informa!on.
Once you have implemented your test func!ons, you can type-check them like this:
mypy test_graphs.py
And run them like this:
pytest -xvk test_graphs.py
Please remember that there is no automated mechanism to check whether your tests are correct (i.e., there are no “tests for the tests”). The above command
will simply report whether or not your tests passed, not whether your tests were well-chosen or expected the correct output.
Task 3
A related ques!on to the above is, given two words, what is a path that, one le$er change at a !me, transforms the first word into the second, via other words?
In par!cular, what is the shortest path that does so, if any exists? When we think of shortest paths, we will o#en use Dijkstra’s shortest-paths algorithm, which
you have or will soon see in lecture; but, for unweighted graphs, breadth-first search is adequate and simpler.
Write the func!on shortest_word_path that takes in a graph, and source and des!na!on words, and using BFS, provides one of the shortest paths in the graph
between them, or None if no path exists. This path should be in order from the source to des!na!on, and include those words at its ends.
Here is sample use of this func!on:
In [9]: g = wordgraphs.RealWordsGraph("web2", 5)
In [10]: wordgraphs.shortest_word_path(g, "long", "path")
Out[10]: ['long', 'lone', 'lote', 'pote', 'pate', 'path']
Note that there are other legi!mate paths that your code might find instead. It would be acceptable if your code arbitrarily chose a different path among this list
of correct ones:
['long', 'lone', 'lote', 'pote', 'pate', 'path']
['long', 'lone', 'lote', 'late', 'lath', 'path']
['long', 'lone', 'lote', 'late', 'pate', 'path']
['long', 'lone', 'lane', 'pane', 'pate', 'path']
['long', 'lone', 'lane', 'late', 'lath', 'path']
['long', 'lone', 'lane', 'late', 'pate', 'path']
['long', 'lone', 'pone', 'pote', 'pate', 'path']
['long', 'lone', 'pone', 'pane', 'pate', 'path']
['long', 'pong', 'pone', 'pote', 'pate', 'path']
['long', 'pong', 'pone', 'pane', 'pate', 'path']
['long', 'pong', 'pang', 'pane', 'pate', 'path']
['long', 'tong', 'tang', 'tanh', 'tath', 'path']
You can run the tests for Task 3 by using:
pytest -xvk task3 test_hw3.py
Task 4A
The type of graph used in the previous tasks would be helpful for a word game, but not so much for a spelling checker: a#er all, the graph only contains
correctly-spelled words. We could instead consider a graph with all strings that contain only le$ers (real words or not), but with the same no!on of which
ver!ces are and are not linked by edges.
This graph could be problema!c in terms of memory use and performance, since there are exponen!ally-many “pseudo-words” (strings containing only le$ers)
of longer-and-longer lengths. But, we can employ a trick to manage this situa!on. Review the interface for graphs, embodied in the abstract base class. We are
only obligated to produce correct answers for each of the methods when asked to do so for a given vertex. In Task 1, we analyzed the set of words from an
English-language dic!onary and produced actual ver!ces and edges for later use. But, we could adopt a different approach en!rely: we could simply generate
answers on demand for a given string without actually having a durable internal representa!on of ver!ces and edges.
Implement the class PseudoWordsGraph as follows. Its constructor should take in the filename of a list of words, as with the earlier class. Read in these words and
store them internally (again filtering out words not consis!ng en!rely of le$ers, and conver!ng them to lower-case), but do not actually determine their
connec!ons or perform any other analysis in advance.
When asked for strings adjacent to a given string, produce all possible changes to the input string involving a single le$er. For instance, for the vertex “aaaa”,
one adjacent vertex would be “zaaa” and another would be “aama”. None of these are real words, but this graph conceptually consists of all strings that are
made only of le$ers, so each of these strings meets that defini!on. And, even though we have not constructed ver!ces and edges, so long as we have a way of
systema!cally producing all the other strings that are one change away from a given string, we have fulfilled the obliga!ons of the adjacent method. We
should also be able to compute the degree of a given vertex with a simple calcula!on.
For this class, the only reference to the dic!onary file is through the is_word method. Although any string consis!ng only of le$ers is a vertex in this graph, we
will only consider ver!ces that are actual words according to the provided file to be words for this par!cular method.
Having implemented this graph, we could use it in a spelling checker to suggest correctly-spelled words based on a misspelled word. If we have detected that a
string is not an actual word, we could use this graph to find all the variants one edge away from that string’s vertex that are actual words. If there are none, we
could next search for variants a distance of two away, and so on.
Modify your variants func!on to s!ll use any ver!ces returned by the adjacent method of the given graph in its traversal, but to only produce in its result set
ver!ces iden!fied as actual words by the is_word method. This modifica!on should not change results in any way when used with a RealWordsGraph , since all
ver!ces in such graphs are, in fact, real words. But, for PseudoWordsGraph objects, variants will now be able to explore through a path of intermediate nonwords before landing on a real one.
Here is sample use of this func!on with the new class:
In [11]: g = wordgraphs.PseudoWordsGraph("web2")
In [12]: wordgraphs.variants(g, "qbcde", 2)
Out[12]: {'abide', 'abode'}
Task 4B
You will also write tests for the PseudoWordsGraph class and its methods in the file test_graphs.py , in func!ons whose names start test_task4a_ .
Here is a list of things you should test:
T0, T1, and T2: that adjacent produces the correct set of strings when given an input string of length 1, 2, and 3, respec!vely, that is not an actual word
T3: that adjacent produces the correct results for a length-two input string that is an actual word
T4, T5, T6, and T7: that degree produces the correct number for the same scenarios as the corresponding test above numbered n-4 (i.e. T4 corresponds to
T0, T5 corresponds to T1, etc.)
T8 and T9: that is_word produces the correct result for a string that is (T8) and is not (T9) an actual word
Again write in a comment for each of your test func!ons which requirement is fulfilled by a given test func!on, and again independently write the correct
answers for comparison without merely copying the answers from your code. You can streamline the task of wri!ng a long list of adjacency answers by
genera!ng them within your test func!on via loops and making any needed modifica!ons to the results. To reduce the chances of making the same error in
your test logic as in your implementa!on, leading to a false sense of security, visually inspect any test data being generated by loops before relying on it.
Once you have implemented your test func!ons, you can type-check them like this:
mypy test_graphs.py
And run them like this:
pytest -xvk test_graphs.py
Task 4C
Recall that crea!ng an instance of a RealWordsGraph was slow. When it came !me to find all the edges between words of the same length, we had to do
something costly, like considering all pairs of words of the same length and whether an edge existed between them. This made working with a graph with
words of about length six or so unpleasantly slow, to say nothing of longer ones.
But, Task 4A contained an interes!ng and relevant insight: we do not necessarily need to precompute the en!re graph to be able to answer ques!ons about it.
In fact, a PseudoWordsGraph is arguably infinite, since we could ask ques!ons about the adjacent strings for strings of any length (100? 1,000? 10,000?). But, if
we only answer specific ques!ons about adjacency on demand rather than precompu!ng them, the infiniteness of the graph is immaterial.
Can we apply this same insight to the graph that consists only of real words? If we did, then we could avoid pre-genera!ng all the edges, which was costly.
Knowing all the edges in advance would only be beneficial if we expected to use this graph so much and for so long that we expected to eventually use most of
these edges at some point. But, if we only expect to use the graph for a few invoca!ons of variants and shortest_word_path , then it is not worth inves!ng the
!me in precompu!ng edges that we may never ul!mately touch.
For this task, implement a third graph class, RealWordsLazyGraph , which is, in some sense, a hybrid of the other two. Its constructor should only take in the name
of a word list file, but not a word length limit; the performance of this class will no longer make us want to impose such limita!ons. Con!nue to filter out words
that have non-le$er characters in them and con!nue to lower-case them. But, do not build an internal representa!on of the graph to the extent of actually
compu!ng the edges of the graph. It should be possible to implement RealWordsLazyGraph by making a copy of your code for PseudoWordsGraph and then
making a very small number of very small changes to this copy.
For the adjacent method, determine, on demand, which actual English words, based on the file loaded in the constructor, are one le$er modifica!on away
from the specified word. Because the informa!on has not been precomputed, as it was for RealWordsGraph objects, this determina!on will be slower than
calling adjacent on one of those graphs. But, since it only needs to consider the rela!onship between a single word and all others, rather than the rela!onships
between all pairs of words (as was needed to precompute a graph in a RealWordsGraph ), it will be faster to make the graph and then call adjacent a limited
number of !mes than it would be to precompute the en!re graph and call adjacent the same number of !mes.
Having implemented this graph correctly, you should be able to create an instance of the graph nearly instantaneously, but get the same results
from variants and shortest_word_path as you would for a RealWordsGraph . Further, you could get more ambi!ous with your tests, trying words of much longer
length:
In [2]: g = wordgraphs.RealWordsLazyGraph("web2")
In [3]: wordgraphs.shortest_word_path(g, "tricky", "normal")
Out[3]:
['tricky',
'bricky',
'bracky',
'cracky',
'cranky',
'craney',
'craner',
'crater',
'frater',
'framer',
'foamer',
'former',
'formel',
'formal',
'normal']
As before, either of these paths would be acceptable:
['tricky', 'pricky', 'prinky', 'pranky', 'cranky', 'craney', 'craner', 'crater', 'frater', 'framer', 'foamer', 'former', 'formel', 'formal', 'normal']
['tricky', 'bricky', 'bracky', 'cracky', 'cranky', 'craney', 'craner', 'crater', 'frater', 'framer', 'foamer', 'former', 'formel', 'formal', 'normal']
Your implementa!on is correct if it produces the same results as a RealWordsGraph would, but, instead of taking seconds to minutes to construct, calling the
constructor on a RealWordsLazyGraph returns effec!vely instantly. Although it is possible to use the timeit facility of ipython3 to evaluate run!mes precisely,
the difference should be so stark and the loading !me for a RealWordsLazyGraph no!ceably fast that precise !ming is not necessarily cri!cal.
You can run the tests for Task 4C by using:
pytest -xvk task4c test_hw3.py
Caching
You may have no!ced a downside of RealWordsLazyGraph and its approach to adjacent : if we call the adjacent method a second or subsequent !me with the
same vertex, it must compute the answer a second or subsequent !me from scratch. But, a RealWordsGraph would have computed this informa!on once, during
construc!on of the graph, and merely retrieve it each of the !mes it was asked. So, despite the long construc!on !mes, there are some possible benefits to that
design.
We could enhance our RealWordsLazyGraph to not perform repeated work unnecessarily. We could maintain an a$ribute in the object that tracks the answers
we have already computed, and check this a$ribute each !me we are asked for adjacency informa!on, before compu!ng it from scratch. For instance, the
a$ribute could be a Python dic!onary whose keys are strings and whose values are sets. The dic!onary would start out as empty. The adjacent method would
check the dic!onary and simply return the value for a given word, if present. If not present, it would compute the answer, and store it at that key in the
dic!onary before returning it. Should it be asked about the same vertex again, it will have the answer immediately the second and subsequent !mes.
It is possible to get even fancier with this idea to address concerns that might come up. For instance, if this dic!onary starts to take up too much memory, we
could selec!vely remove old or infrequently-accessed parts of it to save space, with the understanding that they could always be recomputed if need be.
You are not expected to add any of the op!miza!ons discussed in this subsec!on to your code, but we men!on it for your interest, especially since ideas like
this o#en come up when performing sophis!cated op!miza!ons for certain types of code. You will learn more about these topics in future courses.
Task 5
For this week’s GUI exercise, you will build a visualizer for complete graphs in task5.py . You can see a video demonstra!on here:
A complete graph K is an undirected graph of n ver!ces such that there is an edge connec!ng every pair of dis!nct ver!ces. The smallest complete graph with
a nonzero number of edges is K . Following the defini!on above, there are three edges in K , there are six edges in K , and so on. (A thought experiment: how
many edges are there in K for some integer i? It’s easily Google-able, but try to work out the answer on your own.) Note that K is the empty graph, and K is a
graph consis!ng of one vertex and zero edges (known as the singleton graph).
This week’s GUI task is to implement an applica!on that constructs an image of K for nonnega!ve integers $n$. The requirements of the GUI are minimal. It
must depict n ver!ces and the edges connec!ng every dis!nct pair of edges among them. It is not necessary to supply labels for the ver!ces; they can appear
on the screen as unlabeled dots or other shapes of your choosing. Also, the number of ver!ces must appear as a number somewhere in the GUI window. The
posi!on, size, color of this number is up to you. We have supplied four (open source) fonts in the assets/ directory for you to choose from.
When the applica!on opens, it must display K as well as the number 2. From there, your applica!on must support three keystrokes:
the up arrow must increase the number of ver!ces by one.
the down arrow must decrease the number of ver!ces by one, but never less than zero.
the q key must quit the applica!on.
While there is no upper limit on the hypothe!cal size of a complete graph, you may assume that we will not evaluate your work on any more than twenty
ver!ces (although once this tool is built, it is irresis!ble to mash the up arrow a million !mes and see what happens).
While we have chosen not to mandate exactly how your complete-graph figures should look, it is impera!ve not to arrange all of the ver!ces along one line
(except for a graph with only two ver!ces); this makes it impossible to see the edges connec!ng them. One way to arrange the ver!ces is equally spaced
around a circle; this is demonstrated in a video accompanying this task. The circular graph representa!on is not the only interes!ng display. Please experiment
and find an arrangement of ver!ces and edges that you find appealing.
Type Checking
While you have been doing some type-checking along the way, we’ve only been checking the files you have modified. We also need to make sure that there are
no type mismatches between the test code and your code. To do this, you will need to typecheck the test files themselves:
mypy test_hw3.py test_graphs.py
Doing this before you have a complete implementa!on will result in many type errors, so you want to wait un!l you have completed all the tasks before
running the above command.
Careful: any error reported by mypy will be the result of something wrong in your wordgraphs.py or test_graphs.py code. Never edit the test_hw3.py file to
make it pass the tests.
Finally, pytest will also type-check your code (which will be part of your Completeness score). To run those tests, run the following:
pytest -xvk mypy test_hw3.py
Grading
You will receive two S/N/U scores for this assignment: one for completeness and one for code quality.
Your completeness score will be determined solely on the basis of the automated tests, which provide a measure of how many of the tasks you have completed:
Grade Percent tests passed
Sa!sfactory at least 85%
Needs Improvement at least 55%
Unsa!sfactory less than 55%
For example, if your implementa!on passes 87% of the tests, you will earn a S (Sa!sfactory) score for correctness.
Submissions that pass 100% of the tests and achieve an S in Code Quality will receive an Excellent (E) in Completeness.
To find your score on the tests, first make sure you’ve run all the tests as follows:
$ pytest -v test_hw3.py test_graphs.py
Next, you can run the grader script like this:
$ python3 grader.py
Because there are no automated tests for Tasks 2B, 4B, and 5, your code quality score will be affected by how much func!onality you implement in Task 5 and
whether you adhered to the test requirements for Tasks 2B and 4B. As usual, it will also be based, in part, on your adherence to our Style Guide. Please note
that not implemen!ng Task 2B, 4B, or 5 at all will result in an N in Code Quality.
For your Code Quality score, we will be paying special a$en!on to the issues below. Submi"ng code with several of these issues will result in a score of N in
Code Quality. Addi!onally, please note that anything labelled as a “Major issue” will result in an automa!c score of N in your Code Quality.
[Task 1 - Major issue]: Your code should build a data structure where ver!ces are represented and there is explicit informa!on about which ver!ces have
edges to which other ver!ces.
[Task 2A]: You must not use any global variables in your implementa!on. Your implementa!on should use sets rather than lists where you are tracking a set
of items that does not need to be kept in any par!cular order and does not have duplicates.
[Task 2B - Major issue]: Your tests must actually perform the checks described in the list of tes!ng requirements. Small mistakes are fine, but you must not
make your tests pass by rote (e.g., by simply including something like assert True ).
[Task 3]: You must not use any global variables in your implementa!on. Your implementa!on should use sets rather than lists where you are tracking a set of
items that does not need to be kept in any par!cular order and does not have duplicates.
[Task 4A - Major issue]: Your code should not build a data structure with ver!ces for every possible string or precompute informa!on about edges between
ver!ces.
[Task 4A]: Your implementa!on of degree should use a simple calcula!on rather than actually genera!ng other strings and coun!ng.
[Task 4B - Major issue]: Your tests must actually perform the checks described in the list of tes!ng requirements. Small mistakes are fine, but you must not
make your tests pass by rote (e.g., by simply including something like assert True ).
[Task 4C]: Same as for Task 4A.
[Task 5 - Major issue]: Submi"ng the task5.py file without any modifica!ons (i.e., not implemen!ng Task 5 at all) is considered a major issue.
[Task 5]: You must implement the visualiza!on and each of the required behaviors.
[Task 5]: Your complete-graph visualiza!on must clearly display all ver!ces and all edges up to K .
[Style]: Your code must generally adhere to our Style Guide.
[Style]: Any new func!on you write must have a clear purpose that can be described in a sentence or two. Every func!on you write should also have a
proper docstring.
While these are the main things we care about in this assignment, please remember that it is not possible for us to give you an exhaus!ve list of every single
thing that could affect your code quality score (and that thinking in those terms is generally counterproduc!ve to learning how to program).
Cleaning up
Before you make your final submission, you should remove
any print statements that you added for debugging purposes and
all in-line comments of the form: “TODO”…” (these direc!ves typically start with ###). Further remove any raise NotImplementedError() lines once you have
completed the methods in which they resided (but not from an abstract base class).
Also, check your code against the style guide. Did you use good variable names? Do you have any lines that are too long?
Do not remove header comments, that is, the triple-quote strings that describe the purpose, inputs, and return values of each func!on.
Important: as you clean up, you should periodically save your file and run your code through the tests to make sure that you have not broken your code in the
process.
Submission
Once you have completed the required updates to wordgraphs.py task5.py , and test_graphs.py , you must submit your work through Gradescope under
“Homework #3”. Gradescope will fetch your files directly from your GitHub repository, so it is important that you remember to commit and push your work!
Under “Repository”, make sure to select your uchicago-cmsc14200-win-2025/coursework-GITHUB_USERNAME repository. Under “Branch”, just select “main”.
Finally, click on “Upload”. The Gradescope autograder will run three tools:
pylint to check for style issues. While this tool reports a numerical score, this score is not used to compute your SNU score on the homework. It may simply
alert you to style issues in your code.
mypy to type-check your code.
pytest to run the tests, which will determine your Completeness score.
Make sure to look at the score that is reported on the right sidebar. If 100 is reported as the score, you are done!
If your score is not what you expect, check to make sure you pushed your work to the server
請(qǐng)加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
