CMU 15-112 Summer 2020: Fundamentals of Programming and Computer Science
Homework 10 (Due Thu 11-Jun, at 5:00pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. Create a folder named 'hw10'
  2. Create a file named hw10.go in that folder. You should look to hw9.go for guidance on setting up your starter file. We're also happy to help you set up in small groups!
  3. Edit hw10.go using VSCode
  4. When you are ready, submit hw10.go to Autolab. For this hw, you may submit up to 10 times, but only your last submission counts.
• Do not use recursion in this assignment.
• Do not hardcode the test cases in your solutions.
• NOTE: This homework may be graded for style. Make sure that you adhere to the style guide when you're working on this HW, and double check your file against the style guide before you submit to Autolab!
• NOTE: For the next few days, assignments in Go will be manually graded.

1. Mid-Summer Feedback [5 pts]
   Fill out this feedback form on how we're doing so far! At the end of the form, you'll be sent to another link to actually get credit, so that your feedback can stay anonymous. Do not forget to fill out the second form!.
   Also, please fill out this TA Feedback Form (once per TA)! This is not for any points, but your feedback is invaluable to us, and we would love to hear it so that we can continue to improve!
   
   
2. Big-O Calculation [27.5pts]
   In a multiline comment at the top of your file (just below your name), include solutions to this exercies. For each of the following functinos:
   1. State in less than 10 words what it does in general
   2. Write the Big-O time or number of loops for each line of the function, then state the resulting Big-O of the whole function.
   3. Provide an equivalent Go function that is more than a constant-factor faster (so its worst-case Big-O runtime is in a different function family). The better your solution's Big-O runtime, the more points you get!
   4. Write the Big-O or the number of loops for each line of the new function, then state the resulting Big-O of the whole function right above the function.
   
   
   # Hint: popping the 0th element of a list has to shift over EVERY element # in that list by 1 place. insert(0) is similar. What does this mean for # the Big-O? def slow1(lst): # N is the length of the list lst assert(len(lst) >= 2) a = lst.pop() b = lst.pop(0) lst.insert(0, a) lst.append(b) def slow2(lst): # N is the length of the list lst counter = 0 for i in range(len(lst)): if lst[i] not in lst[:i]: counter += 1 return counter import string def slow3(s): # N is the length of the string s maxLetter = "" maxCount = 0 for c in s: for letter in string.ascii_lowercase: if c == letter: if s.count(c) > maxCount or \ s.count(c) == maxCount and c < maxLetter: maxCount = s.count(c) maxLetter = c return maxLetter


3. invertMap [27.5pts]
   Write the function invertMap(m map[int]int) map[int]intSet that takes a map m that maps keys to values and returns a map of its inverse, that maps the original values back to their keys. One complication: there can be duplicate values in the original map. That is, there can be keys k1 and k2 such that (m[k1] == v) and (m[k2] == v) for the same value v. For this reason, we will in fact map values back to the set of keys that originally mapped to them. So, for example:
   
   fmt.Println(invertMap(map[int]int{1:2, 2:3, 3:4, 5:3})) // map[2:{1} 3:{2, 5} 4:{3}]