Simple Array Exercises

• Compute the sum of the elements of a given integer array.
• Simultaneously compute the sum of positive elements and the sum of negative elements of an array.
• Write a function taking a real-number array as input and finding the index of a maximum element.
• Write a function taking a non-empty array t as input and returning a pair (i,j) such that i >= j and |t_i - t_j| is maximum.
• Write a function taking a non-empty array t as input and returning true if the array has an element repeated at least twice, and false otherwise.
• Write a procedure taking a non-empty array t as input and displaying the (possibly empty) list of pairs (i,j) such that i < j and t_i = t_j.

Decimal to Binary Conversion

We want to automate the conversion from one base to another; for this we will use the example of translating a number in base 10 M = d_k d_(k-1) ... d_2 d_1 d_0 to its equivalent in base 2 a_l a_(l-1) ... a_2 a_1 a_0:

• We note that a_0 is the remainder of the Euclidean division of M by 2.
• If M_1 = (M - a_0)/2 (integer!), then a_1 is the remainder of the Euclidean division of M' by 2.
• …
• If M_i < 2, then n = i and a_n equals M_i.

Questions

• Design a procedure that prints the digits of the base 2 decomposition of an integer x passed as a parameter, printing the least significant bit on the left (since we compute the least significant bits first).
• Design a procedure that stores in an array the digits of the base 2 decomposition of an integer x passed as a parameter, then prints them with the least significant bits on the right.

Polynomial Evaluation

The polynomial P = 4 - 3X + X² + 5X³ can be stored in an array of the form [4, -3, 1, 5]. In general, the polynomial p_0 + p_1*X + ... + p_n*X^n is stored in an array of length n+1: [p_0, p_1, ..., p_n].

• Write a function that evaluates P(t) for a given t
• What is the complexity of your function for evaluating a polynomial of degree d? Try to propose an optimal version of polynomial evaluation… by noticing that P can be written as P = 4 + X × (-3 + X × (1 + X × 5))

Array Containment

Consider two arrays A and B of N integers. We say that A is contained in B when all elements of A appear at least once in B.

• Write a function that, given an integer x, determines whether it appears in an array B.
• Write a function that, without sorting the arrays, determines whether A is contained in B. You may use the previous function.
• Count the number of comparisons your algorithm performs.
• If the array B is sorted, can the algorithm be improved?

Maxima in an Array

We want to find the second largest element of an array t of fixed size N. We assume all elements of t are distinct.

• Write an algorithm that first finds the maximum, then makes another pass to find the second maximum.
• Write an algorithm that finds the result in a single pass.
• Compare the two algorithms in terms of the number of comparisons performed.

Dot Product of Two Vectors

Write an algorithm that computes the dot product of two vectors of the same size passed as parameters. Recall:

u · v = Σ(i) v_i * u_i

The common size of the two vectors can be passed as a parameter.

Factorial Again!

Write an algorithm that computes and stores in an array (vector) of size N the integers 0!, 1! … (N-1)!, using a minimum number of multiplications. What is the complexity of your algorithm?

Recall that i! = 1 × 2 × 3 × ... × i.

Sieve of Eratosthenes

Implement the sieve method whose principle is as follows. (Source: wikipedia) The algorithm proceeds by elimination: the goal is to remove from a table of integers from 2 to N all multiples of an integer. By removing all multiples, in the end only integers that are multiples of no integer will remain, which are therefore the prime numbers. We start by crossing out multiples of 2, then each time we cross out multiples of the smallest remaining integer. We can stop when the square of the smallest remaining integer is greater than the largest remaining integer, because in this case all non-primes have already been crossed out. At the end of the process, all integers that have not been crossed out are the prime numbers less than N.

Word Arrays

Words will be assumed to be encoded as a character array of size N (fixed, large) whose last element is \0 (special end-of-string character).

• Write an algorithm to compute the length of a word.
• Write an algorithm to reverse a word in place. The word to reverse and its size will be passed as parameters.
• Write an algorithm to determine whether a given word is a palindrome. The size of the word will be passed as a parameter.
• Let M1 and M2 be two words of respective sizes l_1 and l_2. Write an algorithm to determine whether the second word is an anagram of the first.

Word Arrays (bis)

Write the following programs:

• Determine and display the number of occurrences of a letter given by the user in an array.
• Determine the first index of occurrence of each letter and display in the form:

'a' never appears
'b' first appears at position 0
'c' first appears at position 35
...

Do not use an array, and for each letter use a while loop.

• Declare and initialize an array occurrences that will be used to count the number of occurrences of each letter. What size should it be?
• Fill the array occurrences with the number of occurrences of each letter in the array tab, and then display the result in the form:

'a' appears 0 times
'b' appears 1 time
'c' appears 4 times
...

• Display the content of the array tab in alphabetical order. Use the array occurrences, and if the character 'a' does not appear, do not display 'a'.
• Use the array occurrences to modify the array tab so that it is sorted in alphabetical order, then display the array tab to verify that it is sorted. Hint: with the array occurrences, we know the number of occurrences of each character. We can therefore overwrite the content of tab without losing any data.

Word Arrays (ter)

• Write a program that writes a file in reverse. Hint: Think about how to store the characters of the file
• Write a program that determines whether a certain word (a “pattern”) is present in a file.
• Write a program that determines whether the parentheses of a file are properly nested. Ignore other characters. In (())() the parentheses are properly nested, but not in ((((()(.

Simple Matrix Exercise

• Declare a 100-row by 200-column array, and initialize the array with random integers between 0 and 50.
• Write a procedure display_2d that takes as parameters a CMAX-column by LMAX-row array and displays this array in rows and columns.

Simple Matrix Exercise (bis)

Write an algorithm somme_tab2dim that takes a two-dimensional array tab as a parameter and:

• adds, column by column, the rows of the array and places the result in an array ligne;
• same by row
• adds all cells.
• Determine the index of the column whose sum of coefficients is the largest.

Order Relation

Let n be an integer and M[n][n] a boolean matrix representing a relation R on integers in the following way: M[i][j] = true if and only if i R j. Write algorithms to determine whether R is reflexive, symmetric, transitive.