# Exercises for Elementary Algorithmic Programming in Python

There are three ways to learn computer programming: *practicing,
practicing, and practicing.* So, get on with it! This document
contains a list of exercises intended to practice your basic,
algorithmic programming skills in Python.

The focus of these exercises is on the *algoritmic* aspects of
programming. However, some features of the Python language and its
libraries hide some of these fundamental aspects. Many
innocent-looking expressions hide linear complexities. For example,
you can check whether an array \(A\) contains an element \(x\) with a
simple expression `x in A`

, or you can get or splice values or entire
sequences in and out of arrays with expressions such as `A[1:]`

,
`A[2:3]`

, `A[1:1] = B`

. And of course, many algorithms are already
implemented in standard library functions (e.g., `min()`

, `max()`

,
`sort()`

). Here we deliberately avoid all that.

You must therefore solve all these exercises using only a limited subset of the Python language and libraries. In particular, You may only use the following built-in types:

- numeric types, such as
`int`

- sequence types, such as arrays, tuples, and strings (so, no sets or dictionaries)

With arrays or other sequence types, you may only use the following features:

- direct access to an element by index, as in
`print(A[7])`

or`A[i+1] = A[i]`

- append an element, as in
`A.append(10)`

- delete the last element, as in
`del A[-1]`

or`A.pop()`

; deleting any other element of a sequence is not permitted - read the length, as in
`n = len(A)`

- shrink to a given length, as in
`del A[length:]`

You may also use the `range`

function, typically in a for-loop, as in
`for i in range(10)`

.

You may not use any library or external function other than the ones listed above.

## Minimum

Write a function `minimum(A)`

that, given an array \(A\) of numbers,
returns the minimum value in \(A\). You may assume that the sequence
contains at least one element. Recall that you may not use the
built-in function `min()`

.

### Examples

>>> minimum([1,2,3]) 1 >>> minimum([3,2,1]) 1 >>> minimum([100,2,55,4,3,2,67,3]) 2 >>> minimum([7]) 7

## Position in Sequence

Write a function `position_in_sequence(A,x)`

that returns the first
position in which value \(x\) appears in \(A\). Positions start from \(0\).
Return \(-1\) if \(x\) does not appear in \(A\).

### Examples

>>> position_in_sequence([6, 7, 10, -2, 3], 7) 1 >>> position_in_sequence([3, 2, 1, 1, 3, 2, 2, 3, 1], 1) 2 >>> position_in_sequence([], 1) -1 >>> position_in_sequence([2, 3, 4, 5], 1) -1 >>> position_in_sequence([2, 3, 4, 5], 2) 0

## Count Lower

Write a function `count_lower(A,x)`

that returns the number of
elements in \(A\) whose value is less than \(x\).

### Examples

>>> count_lower([0,7,10,-2,3], 7) 3 >>> count_lower([3, 2, 1, 1, 3, 2, 2, 3, 1], 2) 3 >>> count_lower([3, 2, 1, 1, 3, 2, 2, 3, 1], 10) 9 >>> count_lower([], 1000000000000000) 0 >>> count_lower([2, 3, 4, 5], 1) 0

## Check Sorted

Write a function `check_sorted(A)`

that returns `True`

if the given
sequence \(A\) is sorted in non-decreasing order, or `False`

otherwise.

### Examples

>>> check_sorted([1,2,3]) True >>> check_sorted([1,3,2]) False >>> check_sorted([]) True >>> check_sorted([7]) True >>> check_sorted([50,50,50]) True >>> check_sorted([43,51,51]) True >>> check_sorted([43,51,50,51,70]) False

## Multiples of Three

Write a function `multiples_of_three(A)`

that takes an array \(A\) of
integers and prints the count of all the elements of \(A\) that are
multiples of three.

### Examples

>>> multiples_of_three([34, 31, 45, 5, 38, 19, 19, 26, 25, 19, 39, 40]) 2 >>> multiples_of_three([7, 2, 0]) 0

## Log Base Two

Write a function `log_base_two(n)`

that, given a positive integer \(n\),
returns the integer logarithm base-two of \(n\), that is, the maximal
integer \(k\) such that \(2^k\le n\).

### Examples

>>> log_base_two(1) 0 >>> log_base_two(2) 1 >>> log_base_two(5) 2 >>> log_base_two(1000) 9

## Maximal Difference

Write a function `maximal_difference(A)`

that returns the
maximal difference between any two elements of the given sequence \(A\).

### Examples

>>> maximal_difference([2, 1, 5, 9, 4, 10, 8]) 9 >>> maximal_difference([1]) 0 >>> maximal_difference([1, 1, 1]) 0 >>> maximal_difference([10,-3, 4, 11, 0, 9]) 14

## Minimal Sum

Write a function `minimal_sum(A, x)`

that returns `True`

if there are
some elements in \(A\) whose sum is greater or equal to \(x\), or `False`

otherwise.

### Examples

>>> minimal_sum([], 1) False >>> minimal_sum([1], 1) True >>> minimal_sum([3, 2], 4) True >>> minimal_sum([3, -2], 4) False >>> minimal_sum([2, 1, 5, -3, 9, 4], 20) True >>> minimal_sum([32,-3,10,7,-4,18,25], 50) True >>> minimal_sum([32,-3,10,7,-4,18,25], 94) False

## Isolated Elements

Write a function `isolated_elements(A)`

that prints, in order, all the
elements that are different from all their adjacent elements, that is,
each element that is different from the previous element (if that
exists) and the next element (if that exists).

### Examples

>>> isolated_elements([]) >>> isolated_elements([1]) 1 >>> isolated_elements([7,3]) 7 3 >>> isolated_elements([2, 2]) >>> isolated_elements([2, 2, 3, 2, 3]) 3 2 3 >>> isolated_elements([-2, 2, 2, 2, -2]) -2 -2 >>> isolated_elements([1,2,1,2,1,2,1,2]) 1 2 1 2 1 2 1 2

## Repeated Elements

Write a function `repeated_adjacent_elements(A)`

that prints, in
order, all the elements that are repeated in sub-sequences of two or
more elements. For every maximal subsequence of identical values,
`repeated_adjacent_elements(A)`

must print that value *only once.*

### Examples

>>> repeated_adjacent_elements([]) >>> repeated_adjacent_elements([1]) >>> repeated_adjacent_elements([1, 2]) >>> repeated_adjacent_elements([3, 3]) 3 >>> repeated_adjacent_elements([1,-1,7,7,-1,7,1,7,7,7,7,2,2]) 7 7 2

## Compression

Write a function `compress_sequence(A)`

that prints a “compressed”
version of the given sequence \(A\). Compression is obtained by
printing three or more consecutive elements with equal values with a
line containing \(x\) `*`

\(k\), where \(x\) is the value of those elements
and \(k\) is the number of consecutive equal elements.

### Examples

>>> compress_sequence([-1,1,1,1,7,7,7,7,5,5,1,1,4,1]) -1 1 * 3 7 * 4 5 5 1 1 4 1

## Maximal Increasing Subsequence

Write a function `maximal_increasing_subsequence(A)`

that returns the
maximal length of any strictly increasing sequence of contiguous
elements of \(A\). For \(A=-1,1,7,5,-2,1,2,7,7,5,0,1,3,4,1\), the result
is \(4\), since there is at least one increasing subsequence of length 4
(e.g., \(-2,1,2,7\)) but there is no increasing subsequence of length 5.

### Examples

>>> maximal_increasing_subsequence([-1,1,7,5,-2,1,2,7,7,5,5,1,1,4,1]) 4

## Partition Even/Odd

Write a function `partition_even_odd(A)`

that takes an array of
integers \(A\) and sorts the elements of \(A\) so that all the even
elements precede all the odd elements. The function must sort \(A\)
*in-place.* This means that it must operate directly on \(A\) just by
swapping elements, without using an additional array.

### Examples

>>> A = [-1,1,7,5,-2,1,2,7,7,5,5,1,1,4,1] >>> partition_even_odd(A) >>> print(A) [-2,2,4,-1,1,7,5,1,7,7,5,5,1,1,1]

Notice that in general the solution is not unique. For example, the following result would be equally correct:

>>> A = [-1,1,7,5,-2,1,2,7,7,5,5,1,1,4,1] >>> partition_even_odd(A) >>> print(A) [2,4,-2,5,1,5,1,7,7,7,-1,1,1,5,1]

## Like or dislike

Write a function `like_or_dislike(A)`

that takes a sequence of ratings
expressed with the strings `'like'`

and `'dislike'`

. The function
must print `'like'`

if the most prevalent rating is `'like'`

, or
`'dislike'`

if the most prevalent rating is `'dislike'`

, or
`'undecided'`

otherwise.

### Examples

>>> like_or_dislike(['like']) like >>> like_or_dislike(['dislike','like','dislike']) dislike >>> like_or_dislike(['like','dislike']) undecided >>> like_or_dislike([]) undecided

## Stops and Inversions

A car moves along a road. For simplicity you may assume that the road
is perfectly linear and that the position of the car is given as the
distance from a certain reference point on the road. Write a function
`stops_and_inversions(P)`

that, given an array \(P\) of time-ordered
positions of the car, prints the number of times the car stopped and
the the number of times that the car inverted the direction of motion.
\(P=p_1,p_2,p_3,\ldots\) is time ordered in the sense that the car is at
position \(p_1\) *before* it is at position \(p_2\), it is at \(p_2\) before
it is at \(p_3\), and so on.

### Examples

>>> stops_and_inversions([]) stops: 0 inversions: 0 >>> stops_and_inversions([5,5,5]) stops: 0 inversions: 0 >>> stops_and_inversions([5,5,5,6,7,8]) stops: 0 inversions: 0 >>> stops_and_inversions([5,5,5,6,7,8,8]) stops: 1 inversions: 0 >>> stops_and_inversions([1,5,10,12,12,12,15,20,24]) stops: 1 inversions: 0 >>> stops_and_inversions([1,5,10,12,12,11,8,7]) stops: 1 inversions: 1 >>> stops_and_inversions([1,5,10,12,12,11,8,7,9,11,20,30]) stops: 1 inversions: 2 >>> stops_and_inversions([1,5,10,12,12,11,8,7,9,11,20,30,30,30,30,35,35]) stops: 3 inversions: 2

## Minimal Bounding Rectangle

Consider a sequence of \(n\) points \(p_1,p_2,\ldots,p_n\) in a plane
identified by their Cartesian coordinates. The coordinates are given
in the form of two arrays \(X\) and \(Y\) both containing of \(n\) numbers,
such that point \(p_i\) has coordinates `X[i]`

and `Y[i]`

.

Write a function called `minimal_bounding_rectangle_area(X,Y)`

that,
given two arrays of coordinates \(X\) and \(Y\) representing \(n\) points,
returns the area of the smallest axis-aligned rectangle that covers
all the \(n\) points. An axis-aligned rectangle is such that its sides
are parallel to the \(X\) or \(Y\) axis.

### Examples

>>> minimal_bounding_rectangle_area([3,2,10,4],[5,5,3,2]) 24 >>> minimal_bounding_rectangle_area([2],[89]) 0 minimal_bounding_rectangle_area([-8,8,9,-9,4,-4,4,-9,7],[10,1,-1,-5,7,-7,-2,0,3]) 306

## Distance Between Points

Write a function called `distance_between_points(X,Y,d)`

that, given
two arrays of coordinates \(X\) and \(Y\) representing \(n\) points, and a
number \(d\), return `True`

if and only if two of the given points are
at a distance \(d\) from each other, or `False`

otherwise.

### Examples

>>> distance_between_points([3,2,1,10,5,4],[5,5,4,3,1,2],5) True >>> distance_between_points([3,2,1,10,5,4],[5,5,4,3,1,2],1) True >>> distance_between_points([3,2,1,10,5,4],[5,5,4,3,1,2],6) False >>> distance_between_points([3,2,1,10,5,4],[5,5,4,3,1,2],4) False

## Find a Square

Write a function called `find_a_square(X,Y)`

that, given two arrays of
coordinates \(X\) and \(Y\) representing \(n\) points, and a number \(d\),
return `True`

if and only if four of those points are the vertices of
a square, or `False`

otherwise.

### Examples

>>> find_a_square([0,1,2,3],[3,1,4,2]) True >>> find_a_square([0,1,2,1],[3,1,3,5]) False

## Most Common Digit

Write a function called `most_common_digit(n)`

that takes an integer
\(n\), and returns the most common digit in the decimal representation
of \(n\). If there are two or more most common digits, the function
must return the smallest one.

### Examples

>>> most_common_digit(1969) 9 >>> most_common_digit(44272) 2 >>> most_common_digit(36223771538825331723) 3 >>> most_common_digit(0) 0

## Sums of Squares

Write a function called `sums_of_squares(n)`

that prints all the pairs
of squares that sum to \(n\). That is, `sums_of_squares(n)`

prints a
line \(a^2\) `+`

\(b^2\) for all the distinct pairs \(a\le b\) such that
\(a^2+b^2=n\).

### Examples

>>> sums_of_squares(25) 9 + 16 >>> sums_of_squares(21) >>> sums_of_squares(125) 4 + 121 25 + 100 >>> sums_of_squares(178) 9 + 169 >>> sums_of_squares(179) >>> sums_of_squares(17993241) 176400 + 17816841