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])
orA[i+1] = A[i]
- append an element, as in
A.append(10)
- delete the last element, as in
del A[-1]
orA.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