Exercises for Elementary Algorithmic Programming in Python

Write a function median_value(a,b,c) that, given three numbers \(a,b,c\) returns their median value.

Write a function leap_year(y) that, given a year number \(y\) in the Gregorian calendar, return True if \(y\) is a leap year, or False otherwise. Recall that a leap year is one whose number is divisible by 4, excluding the year numbers divisible by 100, but including the year numbers divisible by 400.

Write a function classify_triangle(a,b,c) that, given three positive numbers representing the lengths of three segments, respectively, output a classification of the triangle obtained by connecting the three segments. The output consists of one or two words printed on a single line and separated by a single space. The first word is one of acute, right, obtuse, or impossible. impossible indicates that it is impossible to form a triangle with the given segment lengths, in which case the output ends there. acute, right, and obtuse indicate that the resulting triangle has all acute angles, one right angle, or one obtuse angle. In these cases, the output must contain a second word that can be either scalene, isosceles, or equilateral, indicating the type of triangle.

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().

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\).

Write a function count_lower(A,x) that returns the number of elements in \(A\) whose value is less than \(x\).

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.

Write a function check_sorted(A) that returns True if the given sequence \(A\) is sorted in non-decreasing order, or False otherwise.

Write a function is_monotonic(A, i, j) that, given an array of numbers, \(A\), returns True if \(A\) contains a monotonic sub-sequence starting at position \(i\) and ending at position \(j\), or False otherwise. A monotonic sequence is one that is either in non-decreasing or non-increasing order.

Consider the following algorithm:

def algorithm_x (A):
    x = 0
    for i in range(len(A)):
        for j in range(i+1, len(A)):
            if is_monotonic (A, i, j):
                if x < j - i:
                    x = j - i
    return x

Write an algorithm find_peak(A) that, given a “peak” sequence \(A\), finds the maximal value \(x\) in \(A\). A “peak” sequence \(A\) consists of an increasing sequence \(A_{1,\ldots,i}\) attached to a decreasing sequence \(A_{i,\ldots,n}\), for some index \(i\). These two sequences share exactly one element, namely \(A_i\).

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\).

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

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.

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).

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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\).