(I need help coding for problem B but posted part A because they use some of the same perimeters; an explanation would be appreciated. In Python, please, Thank you.)

### Part (A)

Given a list of pairs of integers, for example

~~~ List( (1, 5), (2, 7), (15, 14), (18, 19), (14, 28), (0,0), (35, 24) ) ~~~

Output a list consisting of just those pairs $(n_1, n_2)$ in the original list wherein $ | n_1 - n_2 | \leq 1 $. Ensure that the order of the elements in the output list is the same as that in the input list.

For the example above, the expected output is:

~~~ List( (15,14), (18,19), (0,0) ) ~~~

__Note__

- Your function must be called `outputConsecutivePairs` with just one argument that must be a list of pairs of integers. It must return a list of pairs of integers. - You can use for-loops and the following operators for concatenating elements to list. - `::` or cons appends an element to the front of a list. - `:+` appends an element to the back of a list. - `++` appends two lists together. - You can use list API functions: `reverse` and `length` - You should not use any other list API functions including `filter`, `map`, `foldLeft`, `foldRight` and so on. - Plenty of time to learn them properly later on. - Do not try to convert your list to an array or vector so that you can mutate it. - There are no restrictions on the use of vars.

__Hints__

- In Scala, pairs of integers have the type `(Int, Int)` - A list containing pairs of integers has the type : `List[ (Int, Int) ]`. - Here is how one iterates over the elements of a list in Scala ~~~ for (elt <- list) { // do stuff with elt } ~~~ - Appending an element to the end of a list (see below). ~~~ result_list = result_list :+ elt // result_list must be declared as a var ~~~ - Appending an element to the front of a list : ~~~ result_list = elt:: result_list // using cons ~~~ - Appending an element to the end of a list ~~~ result_list = result_list ++ List(elt) // use list concatenation ~~~ - Warning: The append at end of a list `:+` (or other operations like list concat `++`) operation takes $O(n)$ time, where $n$ is the size of the list. We will often try to avoid it. But OK to use it for this particular part of problem 1.

### Part (B)

If you followed the hint we provided in part (A), you would have used the :+ or ++ operation to append an element to the end of a list at each step.

for ... { // iterate over a loop ... new_list = new_list :+ new_element // this takes O( size of new_list ) } 

Each :+ or ++ operation requires a full list traversal to find the end of the list and append to the end. The overall algorithm thus requires O(n2)(2) where n is the size of the original list (also the number of loop iterations)

To illustrate: cut & paste/run this code in a new test cell. Just remember to delete that cell before you submit. It will take a long time to run.

//create a list of 1,000,000 pairs val longTestList = (1 to 1000000).map ( x => (x, x-1)).toList //run the function you wrote outputConsecutivePairs(longTestList) //This will take a long time to finish.

In this problem, we wish to implement a function `outputConsecutivePairsLinearTime` that solves the exact same problem as in __Part(A)__ but takes time linear in the size of the input list.

To do so, we would like you to use the `::` or Cons operator on a list that appends an element to the __front__ of a list.

~~~ val l1 = List(1, 2, 3) val l2 = 25 :: l1 // place 25 and then the contents of list l1. // list l2 is List(25, 1, 2, 3) ~~~

You may also want to use the list reverse function

~~~ val l = List(1, 2, 5, 6, 7, 8) val r = l.reverse println(r) // r is the reverse of list l, this works in linear time in the size of the list. ~~~

**Restrictions** remain the same as problem 1. But we would like you to focus on ensuring that your solution runs in linear time.

// YOUR CODE HERE ???

//BEGIN TEST

val lst1 = List((1,1), (-1, 1), (1, -1)) val out1 = outputConsecutivePairsLinearTime(lst1) testWithMessage( out1, List( (1,1)), "test1")

val lst2 = List((1, 2), (2, 1), (1,0), (0,1), (1,1)) val out2 = outputConsecutivePairsLinearTime(lst2) testWithMessage( out2, lst2, "test2")

val lst3 = List((1,5), (5,1)) val out3 = outputConsecutivePairsLinearTime(lst3) testWithMessage(out3, Nil, "test3")

val lst4 = List((2,5), (1,2), (-5, -4), (4,1)) val out4 = outputConsecutivePairsLinearTime(lst4) testWithMessage(out4, List((1,2), (-5,-4)), "test4")

passed(5) //END TEST

//BEGIN TEST //create a list of milion pairs val longTestList = (1 to 1000000).map ( x => (x, x-1)).toList //run the function you wrote outputConsecutivePairsLinearTime(longTestList) // this better finish in <= 15 seconds //END TEST