Session 6

Feedback

Recursion

Sorting

Help for exercises

Your feedback

Offline videos about basic things

Good idea.

I can try to choose topics/examples. Of course the best, if you can ask.

Link to forms on tofferi.fi/dsa

Other materials

Books (online or paper)

Youtube: Mark Lewis, Scala language

More sample problems / help towards course exercises

Main part of the Course, don't underestimate time required.

Don't underestimate how much that helps you to learn!

Use others to help you.

If you have 1h - 1,5h time to do exercise every second day, you can do well. You can do as follows:

1. Try to get something compiling and running (methods returning zeros etc...)
2. Read question multiple times
3. Try to solve problem about 50 minutes (think with small amount of data, with paper etc.)

1. Last 10 minutes, try to think what to ask about exercise: what you have thought and how to explain what you don't understand. You should have better than "I don't know how to solve this".
2. Ask that question/questions (from me: Centria email, other students, even AI).
3. Next time try again 20min. Start next exercise 40min.

Recursion

Loop is not always easy for repetitive tasks!

Recursion is not extremely difficult, it is only less used

Example 1

Let's print numbers factors with recursion

Idea:

1. start from 2, try to find first factor (num % i == 0)
2. print that factor
3. make recursive call where you use (num / first factor) as parameter
4. how do we "stop" recursion?

Recursive call stack

Now we try to learn how to follow a call stack

Example 2

We try to print numbers 1, 2 and 3 in two orders

1. We are doing "loop"
2. on first function, print number and then call recursively (1, 2, 3)
3. on second function, first call recursively and then print a number (3, 2, 1)
4. We can also try to combine those function

Example 3

We can try to follow recursion where is fibonacci numbers

Multiple recursive calls allows more powerful structures

Sorting

Bubble Sort - Selection Sort - Insertion Sort - Merge Sort - Quick Sort - Heap Sort - Radix Sort - Bucket Sort - Shell Sort - Counting Sort - Tim Sort - Comb Sort - Pigeonhole Sort - Cycle Sort - Cocktail Shaker Sort - Gnome Sort - Tree Sort - Bitonic Sort - Pancake Sort - Stooge Sort

Shell sort

We can try to understand code together

void ShellSort(int[] arr)
{
    int n = arr.Length;
    int gap = n / 2;
    while (gap > 0)
    {
        for (int i = gap; i < n; i++)
        {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp)
            {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }
}
    

General tips

Read/start exercises today, rest overnight, try again

Use pencil and paper

Try to learn follow a code