C# For Dummies

Chapter 7. Arrays

1. Write a program, which creates an array of 20 elements of type integer and initializes each of the elements with a value equals to the index of the element multiplied by 5. Print the elements to the console.

Guidelines: Use an `int[]` array and a`for` loop.

Solution:
2. Write a program, which reads two arrays from the console and checks whether they are equal (two arrays are equal when they are of equal length and all of their elements, which have the same index, are equal).

Guidelines: Two arrays are equal if they have the same value for the length and the values for their elements. You can check for the second condition using a for-loop

Solution:
3. Write a program, which compares two arrays of type char lexicographically (character by character) and checks, which one is first in the lexicographical order.

Guidelines: In lexicographic order the elements are compared one by one starting from the very left. If the elements are not the same, the array, whose element is smaller (comes earlier in the alphabet), comes first. If the elements are equal, the next character is compared. If the end of one of the arrays is reached, without finding different elements, the shorter array is the smaller (comes earlier lexicographically). If all elements are equal, the arrays are equal

Solution:
4. Write a program, which finds the maximal sequence of consecutive equal elements in an array.
E.g.: {2, 1, 1, 2, 3, 3, 2, 2, 2, 1} à {2, 2, 2}.
à {2, 2, 2}.

Guidelines: Scan the array from left to right. Every time when the current number is different from the one before it, a new sequence starts. If the current element is equal to the one before it, it is a continuation of the same sequence. So, if we keep the index of the start position of the current sequence (in the beginning it is 0) in `start` and the length of the current sequence (in the beginning it is 1) in `len`, we can find all sequences of equal elements and their lengths. We can easily keep the shortest one in two additional variables – `bestStart` and `bestLen`.

Solution:
5. Write a program, which finds the maximal sequence of consecutively placed increasing integers.
Example: {3, 2, 3, 4, 2, 2, 4} à {2, 3, 4}.

Guidelines: This exercise is very similar to the previous one, but we have a continuation of the current sequence when the next element is bigger.

Solution:
6. Write a program, which finds the maximal sequence of increasing elements in an array `arr[n]`. It is not necessary the elements to be consecutively placed.
Example: {9, 6, 2, 7, 4, 7, 6, 5, 8, 4} à {2, 4, 6, 8}.

Упътване: Guidelines: We can solve the problem with two nested loops and one more array `len[0…n-1]`. In the array `len[i]` we can keep the length of the longest consecutively increasing sequence, which starts somewhere in the array (it does not matter where exactly) and ends with the element `arr[i]`. Therefore `len[0]=1, len[x]` is the maximal sum `max(1 + len[prev])`, where `prev < x ` and `arr[prev] < arr[x]`. Following the definition, we can calculate `len[0…n-1]` with two nested loops: the outer loop will iterate through the array from left to right with the loop variable `x`. The inner loop will iterate through the array from the start to position `x-1` and searches for the element `prev` with maximal value of `len[prev]`, where `arr[prev] < arr[x] `. After the search, we initialize `len[x]` with 1 + the biggest found value of `len[prev]` or with 1, if such a value is not found.
The described algorithm finds the lengths of all maximal ascending sequences, which end at each of the elements. The biggest one of these values is the length of the longest increasing sequence. If we need to find the elements themselves, which compose that longest sequence, we can start from the element, where the sequence ends (at index `x`), we can print it and we can search for a previous element (`prev`). By definition `prev < x ` and `len[x] = 1 + len[prev]` so we can find `prev` with a `for`-loop from 1 to `x-1`. After that we can repeat the same for `x=prev`. By finding and printing the previous element (`prev`) many times until it exists, we can find the elements, which compose the longest sequence in reversed order (from the last to the first).

Solution:
7. Write a program, which reads from the console two integer numbers N and K (K < N) and array of N integers. Find those K consecutive elements in the array, which have maximal sum.

Guidelines: Find in Internet information about "Selection sort" and its C# implementations. Briefly the idea is to find the smallest element and to place it at position 0 (through swapping) then to find the smallest number excluding the first and place it at position 1 and so on, until the entire array is arranged in ascending order.

Solution:
8. Sorting an array means to arrange its elements in an increasing (or decreasing) order. Write a program, which sorts an array using the algorithm "`selection sort`".

Guidelines: Find in Internet information about "Selection sort" and its C# implementations. Briefly the idea is to find the smallest element and to place it at position 0 (through swapping) then to find the smallest number excluding the first and place it at position 1 and so on, until the entire array is arranged in ascending order.

Solution:
9. Write a program, which finds a subsequence of numbers with maximal sum. E.g.: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8} à 11

Guidelines: There are two ways to solve this problem. The first way is to use brute force method, which in this case means that using two nested loops we check every possible start and end and its corresponding sum.
The second way is to use one loop through the array to scan it from left to right and sum the elements. Once we get a negative sum, we can restart summing from the next element. Think why this is correct! At each step we check if the current sum is greater than the current max.

Solution:
10. Write a program, which finds the most frequently occurring element in an array. Example: {4, 1, 1, 4, 2, 3, 4, 4, 1, 2, 4, 9, 3} à 4 (5 times).

Guidelines: This exercise can be solved in a couple of ways. One of them is the following: get the first number and check how many times it is repeated in the array and store this number in a variable. After a repeated number is found we change its value to `int.MinValue`. Then pass to the next number and do the same with it. The current number is remembered if its occurrences are maximal. As you may guess, when a number equal to `int.MinValue` is found (already processed number) we should skip it.
Another solution is to sort the numbers in ascending order and then the elements with same value will be placed next to each other. So, basically we then find the longest sequence of neighbor equal elements.

Solution:
11. Write a program to find a sequence of neighbor numbers in an array, which has a sum of certain number S. Example: {4, 3, 1, 4, 2, 5, 8}, S=11 à {4, 2, 5}.

Guidelines: This exercise can be solved with two nested loops. The first loop assigns a starting index. The second loop sums the elements from the starting index to the right until this partial sum reaches or is greater than S. If the sum is equal to S, we will remember the starting index (from the first loop) and the ending index (from the second loop).
If all numbers are positive, there is a much faster algorithm. We sum all numbers from left to the right, starting from zero. If the current sum becomes greater than S during the summation, we remove the leftmost number in the sequence and we subtract it from the sum. If the current sum is still greater than S, we remove the next leftmost number and do that until the current sum becomes smaller than S. When the sum becomes smaller than S we add the next number on right. If we find a sum equal to S, we print the sum and the sequence to the console. So this solution uses just with one scan through the elements in the array.

Solution:
12. Напишете програма, която създава следните квадратни матрици и ги извежда на конзолата във форматиран вид. Размерът на матриците се въвежда от конзолата.
Example for `(4,4)`:

Guidelines: a), b), c) Think about appropriate ways for iterating through the matrices with two nested loops.
d) We can start from (0, 0) and go down N times. Therefore, go to the right N-1 times, after that up N-1 times, after that left N-2 times, after that down N-2 times and etc. At each iteration we place the next number in a sequence 1, 2, 3, …, N in the cell, which we are leaving.

Solution:
13. Write a program, which creates a rectangular array with size of `n` by `m` elements. The dimensions and the elements should be read from the console. Find a platform with size of (3, 3) with a maximal sum.

Guidelines: Look at the previous solution.

Solution:
14. Write a program, which finds the longest sequence of equal string elements in a matrix. A sequence in a matrix we define as a set of neighbor elements on the same row, column or diagonal.

Guidelines: Check every element in a diagonal line, a row and a column until you get a sequence. If you get a sequence, check whether this sequence is longer than the currently longest sequence.

Solution:
15. Write a program, which creates an array containing all Latin letters. The user inputs a word from the console and as result the program prints to the console the indices of the letters from the word.

Guidelines: We can solve this problem with two nested loops (one for the words and one for the letters of the current word). There is a solution without using an array: we can calculate the index of a given uppercase Latin letter ch using the expression: `(int) ch – (int) 'A'`.

Solution:
16. Write a program, which uses a binary search in a sorted array of integer numbers to find a certain element.

Guidelines: Find on the Internet information about the algorithm "binary search". Note that binary search works only on sorted arrays.

Solution:
17. Write a program, which sorts an array of integer elements using a "merge sort" algorithm.

Guidelines: Find on the Internet information about the algorithm "merge sort" and its implementations in C#. It is a bit complicated to write merge sort efficiently. You can have 3 preallocated arrays when merging arrays: two arrays for keeping the numbers for merging and а result array. Thus you will never allocate new arrays during the algorithm’s execution. The arrays will be allocated just once at the start and you will just change their purpose (swap them) during the algorithm execution.

Solution:
18. Write a program, which sorts an array of integer elements using a "quick sort" algorithm.

Guidelines: Find information about the "quick sort" algorithm in Internet and its C# implementations. It can be best implemented by using recursion. Generally at each step you choose an element called pivot and reorder the array into two sections: at the left side move all elements ≤ pivot and at the right side move all elements > pivot. Finally run the quicksort algorithm recursively over the left and the right sides.

Solution:
19. Write a program, which finds all prime numbers in the range [1…10,000,000].

Guidelines: Find on the Internet information about "The sieve of Erathostenes" (you have probably heard about it in math classes in high-school).

Solution:
20. Write a program, which checks whether there is a subset of given array of N elements, which has a sum S. The numbers `N, S` and the array values are read from the console. Same number can be used many times.
Example: {2, 1, 2, 4, 3, 5, 2, 6}, S = 14 à yes (1 + 2 + 5 + 6 = 14)

Guidelines: Generate all possible sums this way: take all the numbers and mark them as "possible sum". Then take every number `ko, k2, …, kn-1` and for each already marked "possible sum" `p`, mark as possible the sum `p+ki`. If at some step you get `S`, a solution is found. You can keep track of the "possible sums" either in a `bool[]` array `possible[]`, where each index is a possible sum, or in a more complex data structure like `Set`. Once you have `possible[S] == true`, you can find a number `ki` such that possible`[S-ki] == true`, print `ki` and subtract it from `S`. Repeat the same to find the next `ki` and print and subtract is again, until `S` reaches 0.
Another algorithm: generate all possible subsets of the numbers by a `for`-loop from 0 to `2N-1`. If we have a number `p`, take its binary representation (which consists of exactly N bits) and sum the numbers that correspond to 1 in the binary representation of `p` (with a nested loop from 0 to `N-1`). Thus all possible sums will be generated and if some of them is `S`, it can be printed. Note that this algorithm is slow (needs exponential time and cannot run for 100 or 1000 elements). It also does not allow using the same array element twice in the sum.

Solution:
21. Write a program which by given N numbers, K and S, finds K elements out of the N numbers, the sum of which is exactly S or says it is not possible.
Example: {3, 1, 2, 4, 9, 6}, S = 14, K = 3 à yes (1 + 2 + 4 = 14)

Solution:
22. Write a program, which reads an array of integer numbers from the console and removes a minimal number of elements in such a way that the remaining array is sorted in an increasing order.
Example: {6, 1, 4, 3, 0, 3, 6, 4, 5} à {1, 3, 3, 4, 5}
Guidelines: Use dynamic programming to find the longest increasing sub-sequence in the input sequence `arr[]`. The elements not included in the maximal increasing sequence should be removed in order the array to become sorted.

Solution:
23. Write a program, which reads the integer numbers `N` and `K` from the console and prints all variations of K elements of the numbers in the interval [1…N].