# C Programming/Beginning exercises

## Variables

### Naming

1.  Can a variable name start with a number?
2.  Can a variable name start with a typographical symbol(e.g. #, \*,
    \_)?
3.  Give an example of a C variable name that would *not* work. Why
    doesn\'t it work?

### Data Types

1.  List at least three data types in C
    1.  On your computer, how much memory does each require?
    2.  Which ones can be used in place of another? Why?
        1.  Are there any limitations on these uses?
        2.  If so, what are they?
        3.  Is it necessary to do anything special to use the
            alternative?
2.  Can the name we use for a data type (e.g. \'int\', \'float\') be
    used as a variable?

### Assignment

1.  How would you assign the value 3.14 to a variable called pi?
2.  Is it possible to assign an *int* to a *double*?
    1.  Is the reverse possible?

### Referencing

1.  A common mistake for new students is reversing the assignment
    statement. Suppose you want to assign the value stored in the
    variable \"pi\" to another variable, say \"pi2\":
    1.  What is the correct statement?
    2.  What is the reverse? Is this a valid C statement (even if it
        gives incorrect results)?
    3.  What if you wanted to assign a constant value (like 3.1415) to
        \"pi2\":

        :   **a**. What would the correct statement look like?
        :   **b**. Would the reverse be a valid or invalid C statement?

## Simple I/O

### String manipulation

1\. Write a program that prompts the user for a string (pick a maximum
length), and prints its reverse.

2\. Write a program that prompts the user for a sentence (again, pick a
maximum length), and prints each word on its own line.

### Loops

1\. Write a function that outputs a right isosceles triangle of height
and width *n*, so *n = 3* would look like

    *
    **
    ***

2\. Write a function that outputs a sideways triangle of height *2n-1*
and width *n*, so the output for *n = 4* would be:

    *
    **
    ***
    ****
    ***
    **
    *

3\. Write a function that outputs a right-side-up triangle of height *n*
and width *2n-1*; the output for *n = 6* would be:

         *
        ***
       *****
      *******
     *********
    ***********

## Program Flow

1\. Build a program where control passes from main to four different
functions with 4 calls.

2\. Now make a while loop in main with the function calls inside it. Ask
for input at the beginning of the loop. End the while loop if the user
hits Q

3\. Next add conditionals to call the functions when the user enters
numbers, so 1 goes to function1, 2 goes to function 2, etc.

4\. Have function 1 call function a, which calls function b, which calls
function c

5\. Draw out a diagram of program flow, with arrows to indicate where
control goes

## Functions

1\. Write a function to check if an integer is negative; the declaration
should look like bool is_positive(int i);

2\. Write a function to raise a floating point number to an integer
power, so for example to when you use it

``` c
float a = raise_to_power(2, 3);    //a gets 8
float b = raise_to_power(9, 2);    //b gets 81
float raise_to_power(float f, int power);    //make this your declaration
```

## Math

1\. Write a function to calculate if a number is prime. Return 1 if it
is prime and 0 if it is not a prime.

2\. Write a function to determine the number of prime numbers below n.

3\. Write a function to find the square root by using Newton\'s
method.

4\. Write functions to evaluate the trigonometric functions.

5\. Try to write a random number generator.

6\. Write a function to determine the prime number(s) between 2 and 100.

## Recursion

#### Merge sort

1\. Write a C program to generate a random integer array with a given
length n , and sort it recursively using the Merge sort algorithm.

-   The merge sort algorithm is a recursive algorithm .

\- sorting a one element array is easy.

\- sorting two one-element arrays, requires the merge operation. The
merge operation looks at two sorted arrays as lists, and compares the
head of the list , and which ever head is smaller, this element is put
on the sorted list and the head of that list is ticked off, so the next
element becomes the head of that list. This is done until one of the
lists is exhausted, and the other list is then copied onto the end of
the sorted list.

\- the recursion occurs, because merging two one-element arrays produces
one two-element sorted array, which can be merged with another
two-element sorted array produced the same way. This produces a sorted 4
element array, and the same applies for another 4 element sorted array.

\- so the basic merge sort, is to check the size of list to be sorted,
and if it is greater than one, divide the array into two, and call merge
sort again on the two halves. After wards, merge the two halves in a
temporary space of equal size, and then copy back the final sorted array
onto the original array.

#### Binary heaps

2\. **Binary heaps** :

-   A binary max-heap or min-heap, is an ordered structure where some
    nodes are guaranteed greater than other nodes, e.g. the parent vs
    two children. A binary heap can be stored in an array , where ,

\- given a position **i** (the parent) , **i\*2** is the left child, and
**i\*2+1** is the right child.

\- ( C arrays begin at position 0, but 0 \* 2 = 0, and 0 \*2 + 1= 1,
which is incorrect , so start the heap at position 1, or add 1 for
parent-to-child calculations, and subtract 1 for child-to-parent
calculations ).

-   try to model this using with a pencil and paper, using 10 random
    unsorted numbers, and inserting each of them into a \"heapsort\"
    array of 10 elements.

```{=html}
<!-- -->
```
-   To insert into a heap, **end-add** and **swap-parent** if higher,
    until parent higher.

```{=html}
<!-- -->
```
-   To delete the top of a heap, move **end-to-top**, and
    **defer-higher-child** or **sift-down** , until no child is higher.

```{=html}
<!-- -->
```
-   try it on a pen and paper the numbers 10, 4, 6 ,3 ,5 , 11.

```{=html}
<!-- -->
```
-   the answer was 11, 5, 10, 3, 4 , 6.

```{=html}
<!-- -->
```
-   EXERCISE: Now try removing each top element of 11, 5, 10, 3, 4, 6 ,
    using end-to-top and sift-down ( or swap-higher-child) to get the
    numbers

in descending order.

-   a priority queue allows elements to be inserted with a priority ,
    and extracted according to priority. ( This can happen usefully, if
    the element has a paired structure, one part is the key, and the
    other part the data. Otherwise, it is just a mechanism for sorting
    ).

```{=html}
<!-- -->
```
-   EXERCISE: Using the above technique of insert-back/challenge-parent,
    and delete-front/last-to-front/defer-higher-child, implement either
    heap sort or a priority queue.

#### Dijkstra\'s algorithm

Dijkstra\'s algorithm is a searching algorithm using a priority queue.
It begins with inserting the start node with a priority value of 0. All
other nodes are inserted with priority values of large N. Each node has
an adjacency list of other nodes, a current distance to start node, and
previous pointer to previous node used to calculate current node.
Alternative to an adjacency list, is an adjacency matrix, which needs n
x n boolean adjacencies.

The algorithm basically iterates over the priority queue, removing the
front node, examining the adjacent nodes, and updating with a distance
equal to the sum of the front nodes distance for each adjacent node ,
and the distance given by the adjacency information for an adjacent
node.

After each node\'s update, the extra operation **\"update priority\"**
is used on that node :

*while* the node\'s distance is less than it\'s parents node ( for this
priority queue, parents have lesser distances than the children), the
node is swapped with the parent.

After this, *while* the node is greater distance than one or more of its
children, it is swapped with the least distant child, so the least
distant child becomes parent of its greater distant sibling, and parent
to the greater distant current node.

With updating the priority, the adjacent node to the current node has a
back pointer changed to the current node.

The algorithm ends when the target node becomes the current node
removed, and the path to the start node can be recorded in an array by
following back pointers, and then doing something like a quick sort
partition to reverse the order of the array , to give the shortest path
to target node from the start node.

#### Quick sort

3\. Write a C program to recursively sort using the Quick sort partition
exchange algorithm.

-   you can use the \"driver\", or the random number test data from Q1.
    on mergesort. This is \"re-use\", which is encouraged in general.

\- an advantage of reuse is less writing time, debugging time, testing
time.

-   the concept of partition exchange is that a partition element is
    (randomly) selected, and every thing that needs sorted is put into 3
    equivalence

classes : those elements less than the partition value, the partition
element, and everything above (and equal to ) the partition element.

-   this can be done without allocating more space than one temporary
    element space for swapping two elements. e.g a temporary integer for
    integer data.
-   However, where the partition element should be using the original
    array space is not known.
-   This is usually implemented with putting the partition on the end of
    the array to be sorted, and then putting two pointers , one at the
    start of the array,

and one at the element next to the partition element , and repeatedly
scanning the left pointer right, and the right pointer left.

-   the left scan stops when an element equal to or greater than the
    partition is found, and the right scan stops for a smaller element
    than the partition value,

and these are swapped, which uses the temporary extra space.

-   the left scan will always stop if it reaches the partition element ,
    which is the last element; this means the entire array is less than
    partition value.
-   the right scan could reach the first element, if the entire array is
    greater than the partition , and this needs to be tested for, else
    the scan doesn\'t stop.
-   the outer loop exits when then left and right pointers cross.
    Testing for pointer crossing and outer loop exit

should occur before swapping, otherwise the right pointer may be
swapping a less-than-partition element previously scanned by the left
pointer.

-   finally, the partition element needs to be put between the left and
    right partitions, once the pointers cross.
-   At pointer crossing, the left pointer may be stopped at the
    partition element\'s last position in the array, and the right
    pointer not progressed past the

element just before the last element. This happens when all the elements
are less than the partition.

\- if the right pointer is chosen to swap with the partition, then an
incorrect state results where the last element of the left array becomes
less than the partition element value.

\- if the left pointer is chosen to swap with the partition, then the
left array will be less than the partition, and partition will have
swapped with an element with value greater than the partition or the
partition itself.

-   The corner case of quicksorting a 2 element
    `<b>`{=html}out-of-order`</b>`{=html} array has to be examined.

\- The left pointer stops on the first **out of order** element. The
right pointer begins on the first `<b>`{=html}out-of-order`</b>`{=html}
element, but the outer loop exits because this is the leftmost element.
The partition element is then swapped with the left pointer\'s first
element, and the two elements are now **in order**.

\- In the case of a 2 element **in order** array, the leftmost pointer
skips the first element which is less than the partition, and stops on
the partition. The right pointer begins on the first element and exits
because it is the first position. The pointers have crossed so the outer
loop exits. The partition swaps with itself, so the in-ordering is
preserved.

-   After doing a swap, the left pointer should be incremented and right
    pointer decremented, so the same positions aren\'t scanned again,
    because an endless loop can result ( possibly when the left pointer
    exits when the element is equal to or greater than the partition,
    and the right element is equal to the partition value). One
    implementation, Sedgewick, starts the pointers with the left pointer
    minus one and right pointer

the plus one the intended initial scan positions, and use the
pre-increment and pre-decrement operators e.g. ( ++i, \--i) .

fr:Exercices en langage C
et:Programmeerimiskeel
C/Harjutused
pl:C/Ćwiczenia dla
początkujących
