Programming with Python (lab classes)

Vedran Šego, vsego.org

Content:

  1. Analysis of algorithms

Problem 1. Write a function sum_dif(L) that returns the sum of absolute differences of all the unordered pairs (subsets with exactly two elements) of the elements in the ascendinly sorted list L. In other words, if we denote the elements of L as $a_1, a_2, \dots, a_n$, then the function returns $$\operatorname{sum\_dif}(L) = \sum_{i=1}^{n-1} \sum_{j=i+1}^n | a_i - a_j |.$$

In your function's docstring explain what is the complexity of your algorithm.

Note: For a hint on how to make an algorithm of a linear complexity, see here. This is a nice example of a mathematical "trickery" used to improve the complexity, but it will not be a part of any examination. Also, notice that this algorithm can improve the computation even if the list is not sorted, since the sorting itself can be done in $O(n\log n)$ time, which is faster that $O(n^2)$ required by the naive "by the definition" algorithm.

Problem 2. We define the "Look and Say" sequence of numbers: $$L_1 := 1, \quad L_2 := 11, \quad L_3 := 21, \quad L_4 := 1211, \quad L_5 := 111221, \quad L_6 := 312211, \quad L_7 := 13112221, \dots$$ in the following way:

  1. The first number is $L_1 := 1$.
  2. If the $i$-th number is $L_i =\underbrace{a_1a_1\dots{}a_1}_{k_1}\underbrace{a_2a_2\dots{}a_2}_{k_2}\dots\underbrace{a_ma_m\dots{}a_m}_{k_m}$, where $a_j \ne a_{j+1}$ for all $j=1,2,\dots,m-1$, then the $(i+1)$-st number is $L_{i+1} := k_1a_1k_2a_2\dots{}k_ma_m$.

The first five numbers are constructed as follows:

  • The first number is $L_1 = 1$, which has only $\color{red}{1}$ digit $\color{blue}{1}$. Hence, the second number is $L_2 = \color{red}{1}\color{blue}{1}$.
  • The second number, $L_2 = 11$, has $\color{red}{2}$ digits $\color{blue}{1}$, so the third number is $L_3 = \color{red}{2}\color{blue}{1}$.
  • The third number, $L_3 = 21$, has $\color{red}{1}$ digit $\color{blue}{2}$ and $\color{orange}{1}$ digit $\color{green}{1}$, so the fourth number is $L_4 = \color{red}{1}\color{blue}{2}\color{orange}{1}\color{green}{1}$.
  • The fourth number, $L_4 = 1211$, has $\color{red}{1}$ digit $\color{blue}{1}$, $\color{orange}{1}$ digit $\color{green}{2}$, and $\color{purple}{2}$ digits $\color{navy}{1}$, so the fifth number is $L_5 = \color{red}{1}\color{blue}{1}\color{orange}{1}\color{green}{2}\color{purple}{2}\color{navy}{1}$.

Write a function look_and_say(a, b) that returns the list of numbers $L_a, L_{a+1}, \dots, L_{b-1}$. If $a \ge b$, the returned list should be empty. If $a \le 0$, the function should raise a ValueError exception.

Note: Instead of a list, it is prefered to make look_and_say a generator, but this is beyond what will be asked for in the examinations and is hence left as an exercise for the students that are interested in doing it that way.

Hints:

  1. Creating the $(i+1)$-st number is easier done if the $i$-th number is first converted to a string or, better yet, if one works with strings all the time and then converts them to integers just before returning them or adding them to a list.

  2. To find out how many consecutive digits are equal to each other, start with the first and increase index while they are. Be careful not to increase the index beyond the last one (len(s)-1).

Side-problem: Try to prove that:

  • none of the elements in the "Look and Say" sequence have digits other than $1$, $2$, and $3$, and
  • every $L_n$ for $n \ge 6$ has digits $1$, $2$, and $3$ (all three of them, and none other).

Problem 3. Write a function lists_intersection(L1, L2) that returns the list of all elements that appear in both of the lists L1 and L2 (all three represent ordered multisets). If an element x appears in L1 a total of r1 times and in L2 a total of r2 times, it has to appear in the resulting list min(r1, r2) times. The lists L1 and L2 must remain unchanged.

All the elements in all three lists are assumed to be strings. The result list should be sorted by the elements' values.

Hint: Converting these lists to sets and finding their intersection can help you find what elements belong to the intersection, but you still need to count how many instances go to the result list.