## Description

**Homework # 3
**

__Question 1 : __

Consider the following two implementations of a function that if given a list, lst, create and return a new list containing the elements of lst in reverse order.

def reverse1(lst):

rev_lst = []

i = 0

while(i < len(lst)):

rev_lst.insert(0, lst[i]) i += 1

return rev _lst

def reverse2(lst):

rev_lst = []

i = len(lst) – 1

while (i >= 0):

rev_lst.append(lst[i]) i -= 1

return rev _lst

If lst is a list of *n *integers,

- What is the worst case running time of reverse1(lst)? Explain of your
- What is the worst case running time of reverse2 (lst)? Explain of your

__Question 2: __

Consider the implementation we made in class for ArrayList, and its extensions you did in the lab.

In this question, we will add two more methods to this class: the insert method and the pop method. For this question, please submit the modified ArrayList class.

- a) Implement the method insert(self, index, val) that inserts val before index (shifting the elements to make room for v a l ) .

For example, your implementation should follow the behavior below:

> > > arr_ lst = ArrayList() >>> **for **i **in **range(1, 4+1): …Â arr_ lst.append(i)

>>> arr_ lst.insert(2, 30) >>> arr_ lst

[1, 2, 30, 3, 4]

__Notes:__

1 . Make sure to double the capacity of the array, if there is no room for an additional element.

2 . Your function should raise an IndexError exception in any case the index (positive or negative) is out of range.

- b) Implement the method pop(self) , that removes the last element from the list. The pop method should return the element removed from the list, and put None in its place in the array. If pop was called on an empty list, an IndexError exception should b e raised.

In order to maintain the linear memory usage of the list data structure, and its efficient amortized performance, we use the following shrinking strategy: When the number of elements in the list goes strictly below a quarter of the arrayâ€™s capacity, we shrink its capacity by half.

For example, your implementation should follow the behavior below:

> > > arr_ lst = ArrayList()

>>> **for **i **in **range(1, 5+1):

…Â Â Â Â Â arr_ lst.append(i)

>>> arr_ lst.pop() 5

>>> arr lst.pop()

4

>>> arr lst.pop()

3

>>> arr lst.pop() 2

>>> arr _ lst

[1]

__Note:__ After the executing the code above, the capacity of the array in ArrayList will b e 4.

- c)
*Extra Credit (You donâ€™t need to submit)*: The extending and shrinking strategies we use in our ArrayList implementation (doubling the capacity of the array each time there is no room to add an element, and shrinking the capacity of the array by a factor of 2 each time the number of elements is less than a quarter of the arrayâ€™s capacity), guarantees two important things:

i . In any given time, the memory used to store the elements is linear. That is, if

there are *n *elements in the array, then: Â â‰¤(Â â„Ž ) â‰¤ 4.

ii . Any sequence of *n *append and/or pop operations on an initially empty ArrayList object, takes *O(n) *time.

Proving these properties is out of the scope of this assignment, but we will show two supporting insights:

1 . Show that the following series of *2n *operations takes *O(n) *time: *n *append operations on an initially empty array, followed by *n *pop operations.

2 . Consider a variant to our shrinking strategy, in which an array of capacity *N*, is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below *N/2*.

Show that there exists a sequence of *n *append and/or pop operations on an

initially empty ArrayList object, that requires Î©(^{2}) time to execute.

- d) Modify the pop method, so it could optionally get an index as a parameter. This

index indicates the position of the element that is to be removed from the list.

__Notes:__

1 . Make sure to use the same shrinking strategy described above in section (b).

2 . Your function should raise an IndexError exception in any case the index (positive or negative) is out of range.

__Question 3 : __

- a) Give a
**linear implementation**of the following function:**de f**find_duplicates (lst)

The function is given a list lst of *n *integers. All the elements of lst are from the domain: *{1, 2, Ã‰, n-1}*. Note that this restricted domain implies that there are element/s appearing in lst more than once.

The function should return a list containing all the elements that appear in l s t more than once.

For example, if lst=[2, 4, 4, 1, 2], the call find_duplicates( l s t ) could return [2, 4 ] .

- b) Analyze the worst-case running time of your implementation in (a).

__Question 4: __

The remove(value) method of the list class, removes the **first **occurrence of

value from the list it was called on, or raises a ValueError exception, if value is not present.

__Note:__ Since remove needs to shift elements, its worst-case running time is linear. In this question we will look into the function remove_all(lst, value) , that removes **all **occurrences of value from l s t .

- Consider the following implementation of remove_all:

**def** remove_all(lst, value): end = False

**while **(end == False):

**try**:

lst.remove(value) **except** ValueError: end = True

Analyze the worst-case running time of the implementation above.

- Give an implementation to remove_all that runs in worst-case linear time.
__Notes:__

1 . Your implementation should **mutate the given list object **(in-place), without using an additional data structure.

2 . Your implementation **should keep the relative order **of the elements that remain in the list

- c) Analyze the worst-case running time of your implementation in (b).