Category Archives: Määratlemata

Määratlemata

Homework: age grouping

Your task is to create a program that will analyze the ages of guests for an event. As input, you will get an unknown number of age values until the user enters 0 as the age. At that point the input will stop and the output statistics will be printed.

Grouping requirements:

  • Everyone below 18 is a minor
  • Ages 18 and beyond will be put grouped with a step of 5 years (e.g. 18 – 22, 23 – 27 etc.)
  • Everyone whose age is above the previously defined groups will be grouped as elders.

Data structure

The counters for each group will be created as an array, where each array member is for one of the predefined groups. The size of the array is defined with the macro GROUPS .

  • Index GROUPS - 1  is for elders
  • Index GROUPS - 2  is for minors
  • Indexes from 0 to GROUPS - 3  are used for the rest of the age groups.
    I.e. index 0 is for ages 18 – 22; index 1 is for 23 – 27 etc.

Program requirements:

  • Grouping settings must be easily configurable by only adjusting macros.
    • Group count
    • Group stepping
    • Upper bound for minor group
  • The rest of the code must automatically adjust itself if any of the macros were altered.

Required functions

For this task, you should create at least 3 functions

  • To validate that the user input is within allowed and reasonable bounds
  • To find the group index that the age belongs to. Group index must be returned by this function and stored into idx  variable
  • To print the results

You can also make a 4th function to make the program even nicer by moving the infinite loop from main into a separate function handling the processing.

Program structure

We are giving you the generic structure for the program with the macros already in place. You need to use them in the final code.

The places where you should call your functions (the ones listed by “required functions” section)  are highlighted as comments.

Algorithm

We have modeled most of the algorithm for you that you need to implement. Some of the calculations we have left for you to figure out – e.g. how to find the end points for age ranges in the output and a little bit of the array indexing as well.

Sample

Here is a sample of the program and how it behaves. You can also see a debugging output – it is useful to sanity check yourself. You can print out even more data just to be sure. In this case it helps to identify which counter (array slot) was increased. In the final version you do not need to include the counter, but for development it is highly recommended.

NB! When testing that your code works, try to also change the GROUPS and GROUP_STEP macros and see if everything still calculates correctly.

Määratlemata

7. lab: Sorting

Lab materials

Tasks

This lab has one task which can be extended by 2 extra tasks.

Lab task: Bubble sort

In this lab task you will implement a bubble sorting algorithm that will sort an array of numbers entered by the user.

Requirements
  • User is asked for 5 integers, they are stored in an array.
  • Array is to be sorted using the bubble sort algorithm.
  • You must optimize the loops in such a way that it skips the redundant comparison operations – just as was shown in the slide! Make sure to optimize both the inner and the outer loop lengths.
  • Count and show how many times the numbers were compared by the algorithm. If you count exactly 10, the optimizations are likely correct.
  • Display the sorted array in an ascending order.
  • Display the sorted array in the descending order.
  • You are allowed to sort the array only once during the program! Displaying the numbers in the opposite order does not require sorting!
  • You are to create 4 functions within the base task (listed below)
  • Reminders!
    • Variables lowerCamelCase
    • Functions  UpperCamelCase
    • Macros  SCREAMING_SNAKE_CASE
    • Magical numbers must be replaced with macros
    • Array length must always be passed to the function

Answer the question: You can observe both the count of comparisons and swaps. Which one will be reduced by our optimization and why?

Create the following functions

Implement a total of 4 functions in your code

  • For reading the numbers
  • For sorting the array
  • Two functions for displaying the array
Hints
  • You can already start reusing the functions from last week. Copy the ones that suit this program over and adjust them as needed for this task. Then just add the function call.
  • Bubble sort is another one of those functions that you should keep in handy for the future. Just make sure to remove the counting part from the code – we typically don’t want side effects for our functions.
Test 1: Reverse order

This is the worst case scenario for bubble sort. All numbers are sorted in the opposite order to what they need to be.

Test 2: Random order

The order is randomized here. The number of comparisons remains the same. This may also trigger an edge case in some computer systems when an array bound is exceeded. NB! You should not assume this to be reliable, there are more specialized tools for that, however it may bring out some errors in some systems.

Extra task 1: further loop optimization

The algorithm used initially can be improved upon even further. Initial design doesn’t detect if the array gets sorted earlier. This can however be detected easily and the sorting process can be stopped.

  • If the array gets sorted earlier than the last iteration of the outer loop, stop the sorting. Avoid doing unnecessary work!
  • Hint: think of what statements are being executed in a situation where the array is still being sorted, that will no longer be executed once it is sorted. Detect it and stop the sorting.
  • During defense: explain which kind of data order benefits from this algorithm. Demonstrate that your algorithm indeed works!

Extra task 2: matrix sort

In this part you will jump a little bit ahead and have to familiarize yourself with 2-dimensional arrays.

  • Solve this task as a separate program. Use the original code as a template to build upon. Keep the original, you will need the functions later on!
  • You are permitted to solve this task without using functions as we haven’t covered passing 2-d arrays to functions.
  • Instead of a 1-d array, you will need to sort a 5 x 5 matrix.
  • Sorting is performed line-by-line (independently)
  • Matrix must be initialized. Use the following matrix as your test data.
Sorted matrix
Hint

Wish to use the sorting function that you just did within the base task? In C, you can pass rows of a matrix to a function (in reality it it’s a bit more complex, but it serves our purpose). Pass it to the sort function as follows:
SortArray(numbers[rowIndex], rowLength); This way your code will look a lot cleaner.

After the class

  • You should understand what a number base (radix) is
  • You should recognize the most common numbering systems, including binary and hexadecimal.
  • You should understand what’s the difference between a positional and non-positional numbering system.
  • You should know what a bit, a byte and a nibble are, as well as how many bits are there in a byte or in a nibble
  • You should understand basic conversion between bases (10 -> 2, 10 -> 16, 10 -> 8, 2 > 10, 2 -> 16, 16 -> 10, 16 -> 2, 8 -> 10)
  • You should be able to convert between any system positional numbering system and base 10 using the generic conversion algorithm.
  • You should understand what an integer overflow is, when it happens and how dangerous it can be
  • You should know that there are a lot of sorting algorithms out there and for a practical application, you need to pick the right one
  • You should understand, that optimization and faster hardware are important, however they will only have a limited effect compared to a faster algorithm
  • You should understand what a bubble sort is and be able to write and apply it

Additional content

Generic references

Integer overflow in real life