CMU 15-112: Fundamentals of Programming and Computer Science
Homework 6a (Due Friday 9-Oct at 8pm)

• This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
• To start:
  1. Create a folder named 'week6'
  2. Download these files into that folder:
     1. hw6a.py
     2. cs112_f20_week6_linter.py
  3. Edit hw6a.py using VSCode
  4. When you have completed and fully tested hw6a, submit hw6a.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
• Do not use recursion, sets, or dictionaries in this unit.
• Do not hardcode the test cases in your solutions.

• Hw6a (this part) is due Friday at 8pm and is worth 60 points. It contains 6 standard problems and 1 spicy problem.
• Hw6b is due Saturday at 8pm and is worth 40 points. It contains another two standard problems, and everyone has to do both of them, plus a bonus problem.

1. alternatingSum(L) [10 pts] [autograded]
   Write the function alternatingSum(L) that takes a list of numbers and returns the alternating sum (where the sign alternates from positive to negative or vice versa). For example, alternatingSum([5,3,8,4]) returns 6 (that is, 5-3+8-4). If the list is empty, return 0.


2. median(L) [10 pts] [autograded]
   Write the non-destructive function median(L) that takes a list of ints or floats and returns the median value, which is the value of the middle element (if the list was sorted), or the average of the two middle elements if there is no single middle element (as in an even-length list). If the list is empty, return None.


3. nondestructiveRemoveRepeats(L) [10 pts] [autograded]
   Important Note: to receive any credit for this problem, you may not simply create a copy of L and then call the destructiveRemoveRepeats function below. Instead, you must create the resulting list from scratch here. Also, note that the autograder has no way to check this, so our TA's will check this manually after the hw deadline.
   Write the function nondestructiveRemoveRepeats(L), which takes a list L and nondestructively returns a new list in which any repeating elements in L are removed. For example:

   assert(nondestructiveRemoveRepeats([1, 3, 5, 3, 3, 2, 1, 7, 5]) ==
                                      [1, 3, 5, 2, 7])
   

   Also:

   L = [1, 3, 5, 3, 3, 2, 1, 7, 5]
   assert(nondestructiveRemoveRepeats(L) == [1, 3, 5, 2, 7])
   assert(L == [1, 3, 5, 3, 3, 2, 1, 7, 5]) # nondestructive!
   

   Note that the values in the resulting list occur in the order they appear in the original list, but each occurs only once in the result. Also, since this is a nondestructive function, it returns the resulting list.


4. destructiveRemoveRepeats(L) [10 pts] [autograded]
   Important Note: this is the analog of the previous important note. Here, to receive any credit for this problem, you may not simply call nondestructiveRemoveRepeats(L) and then somehow remove all the elements in L and then append the elements from that call. Instead, you must destructively modify the list as you go. Also, again, note that the autograder has no way to check this, so our TA's will check this manually after the hw deadline.
   Write the function destructiveRemoveRepeats(L), which implements the same function destructively. Thus, this function should directly modify the provided list to not have any repeating elements. Since this is a destructive function, it should not return any value at all (so, implicitly, it should return None). For example:

   L = [1, 3, 5, 3, 3, 2, 1, 7, 5]
   assert(destructiveRemoveRepeats(L) == None)
   assert(L == [1, 3, 5, 2, 7]) # destructive!
   

   
   
5. evalPolynomial(coeffs, x) [10 pts] [autograded]
   Background: we can represent a polynomial as a list of its coefficients. For example, [2, 3, 0, 4] could represent the polynomial 2x**3 + 3x**2 + 4. With this in mind, write the function evalPolynomial(coeffs, x) that takes a list of coefficients and a value x and returns the value of that polynomial evaluated at that x value. For example, evalPolynomial([2,3,0,4], 4) returns 180 (2*4³ + 3*4² + 4 = 2*64 + 3*16 + 4 = 128 + 48 + 4 = 180).


6. areaOfPolygon(L) [10 pts] [autograded]
   Write the function areaOfPolygon(L) that takes a list of (x,y) points that are guaranteed to be in either clockwise or counter-clockwise order around a polygon, and returns the area of that polygon, as described here. For example (taken from that text), areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]) returns 45.5 (at least the result is almostEqual to 45.5). Here is a sample test function for you:

   def testAreaOfPolygon():
       print("Testing areaOfPolygon()...", end="")
       assert(almostEqual(areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]), 45.5))
       assert(almostEqual(areaOfPolygon([(9,7), (11,2), (2,2), (4, 10)]), 45.5))
       assert(almostEqual(areaOfPolygon([(0, 0), (0.5,1), (1,0)]), 0.5))
       assert(almostEqual(areaOfPolygon([(0, 10), (0.5,11), (1,10)]), 0.5))
       assert(almostEqual(areaOfPolygon([(-0.5, 10), (0,-11), (0.5,10)]), 10.5))
       print("Passed!")
   

   Hint: There are other more-complicated ways to find the area of a polygon. Do not use those ways. Use the simple way described in the web page linked above.

7. runSimpleProgram(program, args) [60 pts] [autograded]
   First, carefully watch this video that describes this problem:
   
   Then, write the function runSimpleProgram(program, args) that works as described in the video, taking a legal program (do not worry about syntax or runtime errors, as we will not test for those cases) and runs it with the given args, and returns the result.
   
   Here are the legal expressions in this language:
   
   
   • [Non-negative Integer]
     Any non-negative integer, such as 0 or 123, is a legal expression.
   
   
   • A[N]
     The letter A followed by a non-negative integer, such as A0 or A123, is a legal expression, and refers to the given argument. A0 is the value at index 0 of the supplied args list. It is an error to get or set arg values that are not supplied. And you may ignore these errors, as we will not test for them!
   
   
   • L[N]
     The letter L followed by a non-negative integer, such as L0 or L123, is a legal expression, and refers to the given local variable. It is ok to get an unassigned local variable, in which case its value should be 0.
   
   
   • [operator] [operand1] [operand2]
     This language allows so-called prefix expressions, where the operator precedes the operands. The operator can be either + or -, and the operands must each be one of the legal expression types listed above (non-negative integer, A[N] or L[N]).
   
   And here are the legal statements in this language (noting that statements occur one per line, and leading and trailing whitespace is ignored):
   
   
   • ! comment
     Lines that start with an exclamation (!), after the ignored whitespace, are comments and are ignored.
   
   
   • L[N] [expr]
     Lines that start with L[N] are assignment statements, and are followed by the expression (as described above) to be stored into the given local variable. For example: L5 - L2 42 This line assigns (L2 - 42) into L5.
   
   
   • [label]:
     Lines that contain only a lowercase word followed by a colon are labels, which are ignored except for when they are targets of jump statements.
   
   
   • JMP [label]
     This is a jump statement, and control is transferred to the line number where the given label is located. The given label will always exist in our test cases.
   
   
   • JMP+ [expr] [label]
     This is a conditional jump, and control is transferred to the line number where the given label is located only if the given expression is positive. Otherwise, the statement is ignored.
   
   
   • JMP0 [expr] [label]
     This is another kind of conditional jump, and control is transferred only if the given expression is 0.
   
   
   • RTN [expr]
     This is a return statement, and the given expression is returned.
   
   Hints:
   1. Do not try to translate the program into Python! Even if you could do so, it is not allowed here. Instead, you are going to write a so-called interpreter. Just keep track of the local variables, and move line-by-line through the program, simulating the execution of the line as appropriate.
   2. You will find it useful to keep track of the current line number.
   3. How long do you run the program? Until you hit a RTN statement! You may assume that will always eventually happen.
   4. We used strip, split, and splitlines in our sample solution, though you of course may solve this how you wish.
   
   Finally, here is a sample test function for you. You surely will want to add some addition test cases. In fact, a hint would be to build your function incrementally, starting with the simplest test cases you can think up, which use the fewest expression and statement syntax rules. Then add more test cases as you implement more of the language.
   def testRunSimpleProgram(): print("Testing runSimpleProgram()...", end="") largest = """! largest: Returns max(A0, A1) L0 - A0 A1 JMP+ L0 a0 RTN A1 a0: RTN A0""" assert(runSimpleProgram(largest, [5, 6]) == 6) assert(runSimpleProgram(largest, [6, 5]) == 6) sumToN = """! SumToN: Returns 1 + ... + A0 ! L0 is a counter, L1 is the result L0 0 L1 0 loop: L2 - L0 A0 JMP0 L2 done L0 + L0 1 L1 + L1 L0 JMP loop done: RTN L1""" assert(runSimpleProgram(sumToN, [5]) == 1+2+3+4+5) assert(runSimpleProgram(sumToN, [10]) == 10*11//2) print("Passed!")