Third Homework Assignment

Posted 10 Feb 2004 by hermanDue by 12:00 midnight, 16th February via Email.

This is the first programming assignment. You'll learn how to write simple programs in Python. The assignment is given in homework3.pdf, and to save you some typing, here are three files associated with the first three problems (use right-button click to download):

If you modify these downloaded files, the docstring will assist you with unit tests. For instance, once you have a workingelimcharsprogram, the commandwill run with no errors. During development, you should use the commandpython elimchars.pyto get interative prompts for development and debugging.python -i elimchars.py

Solutions, posted 17 Feb 2004 by hermanThere are many possible solutions to the problems; I think most everyone got the last problem (simulated birth) correctly solved, so I'll present solutions just for the first three problems.

- The best answer to the first problem is a function such as:
However, it is also possible to build the solution iteratively:def elimchars(ref,strin): for c in ref: strin = strin.replace(c,'') return strindef elimchars(ref,strin): newstring = '' for i in range(len(strin)): if strin[i] in ref: continue newstring = newstring + strin[i] return newstring

- The best answer to the second problem is the one line answer:
Most students gave an algorithmic solution, something like:list2dict = dictEither solution is acceptable.def list2dict(L): d = {} for i in L: a, b = i d[a] = b return d

- There were many solutions for the third problem. Most look rather complicated, such as:
(somewhat simpler versions of this are possible). Here's how a mathematically inclined python expert might write the function.def gunion(g,h): n = {} # first union h into g for i in g.keys(): b = g[i] if i in h.keys(): for j in h[i]: if j not in b: b += [j] b.sort() n[i] = b # now, for any of h that was missed ... for i in h.keys(): if i not in g.keys(): b = h[i] b.sort() n[i] = b return nAlthough this is a lengthy function definition, the logic is quite straightforward.def noDuplicateSort(L): # this function removes duplicates from # a list and sorts the list r = {} # enter items of L as keys in a dictionary for m in L: r[m] = 0 # now the keys have no duplicates r = r.keys() r.sort() return rdef gunion(g,h): r = {} # define union, intersection, and complement # of the intersection of vertices of (g,h) vUnion = g.keys() + h.keys() vIntersect = [ k for k in g.keys() if k in h.keys() ] vComplement = [ k for k in vUnion if k not in vIntersect ] # add intersection items to r for x in vIntersect: r[x] = g[x] + h[x] # add complement items to r for x in vComplement: if x in g.keys(): r[x] = g[x] else: r[x] = h[x] # finally, sort and remove duplicate edges for k in r.keys(): r[k] = noDuplicateSort(r[k]) return r