?‍? ?‍? Examples for teachers - Algorithms

[Erel]

We want to help teachers teach programming and/or computer science with B4X.
In this thread I will try to build a collection of classic algorithms that teachers can use as part of their lessons.

The first few examples are well explained in Jeff Erickson's Algorithms book: http://jeffe.cs.illinois.edu/teaching/algorithms/
The book material is quite advanced however the first chapters are not too complicated.
The book is free and licensed with a permissive license.

To keep this thread "clean", it is closed for discussions. You are welcome to post here: https://www.b4x.com/android/forum/threads/?‍?-?‍?-examples-for-teachers-discuss-here.115896/

Algorithms and data structures index:

• Tower of Hanoi
• Merge Sort
• Quick Sort
• SplitMultiply
• Insertion Sort
• N Queens
• ConstructSubset
• Linked List (data structure)
• Stack (data structure)
• Hash Table / Map (data structure)
• Binary Search Tree (data structure)

The examples in this thread are shared in the public domain. You can do whatever you like with them.

 

[Erel]

Tower of Hanoi - example that shows the magic and power of recursion.
The puzzle is explained here: https://www.b4x.com/guides/Algorithms-JeffE_Recursion/?page=42

The puzzle is solved in about three lines:

Sub Hanoi (n As Int, SrcPeg As Peg, DestPeg As Peg, TempPeg As Peg) As ResumableSub
    If n > 0 Then
        Wait For (Hanoi(n - 1, SrcPeg, TempPeg, DestPeg)) Complete (unused As Boolean)
        Wait For (MoveDisk(SrcPeg, DestPeg)) Complete (unused As Boolean)
        Wait For (Hanoi(n - 1, TempPeg, DestPeg, SrcPeg)) Complete (unused As Boolean)
    End If
    Return True
End Sub

The reason that I'm using Wait For to make the calls is that each step is animated. This way the code will wait for the called sub to complete (this is always the case when calling non-resumable subs).

B4J project is attached.

 

[Erel]

Merge Sort - recursive sorting based on merging sorted sub-arrays.
Explained here: https://www.b4x.com/guides/Algorithms-JeffE_Recursion/?page=44

The differences in the code compared to the pseudo code are:
- The "StartIndex" position is passed instead of creating sub-arrays.
- The arrays indices start from 0.
- The array holds a custom type with the numeric value and the label.
- The sub calls are done with Wait For to let the animations complete.

B4J project is attached.

 

[Erel]

Quick sort - Sorting based on partitioning. It works in the opposite way compared to merge sort.
The pivot is selected randomly. It works best when the pivot is close to the median number.

Explanation: https://www.b4x.com/guides/Algorithms-JeffE_Recursion/?page=47

B4J project is attached.

 

[Erel]

SplitMultiply - Fast multiplication algorithm for multiplying two n digits numbers.
The numbers are stored as strings.
We only use the addition operator and multiplication of one digit numbers.
Explanation: https://www.b4x.com/guides/Algorithms-JeffE_Recursion/?page=58

(this is of course millions of times slower than using the built in hardware based math features)

B4X code:

'Non-UI application (console / server application)
Sub AppStart (Args() As String)
    Log(SplitMultiply("1234", "0002", 4))
    Log(SplitMultiply("80001", "12341", 5))
End Sub

Sub SplitMultiply (x As String, y As String, n As Int) As String
    If n = 1 Then
        Return GetDigitFromString(x, 0) * GetDigitFromString(y, 0) 'one digit * one digit
    Else
        Dim m As Int = Ceil(n / 2)
        Dim a As String = DivideBy10M(x, m)
        Dim b As String = Modulo10M(x, m)
        Dim c As String = DivideBy10M(y, m)
        Dim d As String = Modulo10M(y, m)
        Dim e As String = SplitMultiply(a, c, m)
        Dim f As String = SplitMultiply(b, d, m)
        Dim g As String = SplitMultiply(b, c, m)
        Dim h As String = SplitMultiply(a, d, m)
    End If
    'the strings will be parsed here and later converted back to a string.
    'we use NumberFormat2 to control the formatting.
    Return NumberFormat2(ShiftByM(e, 2 * m) + ShiftByM(g + h, m) + f, 0, 0, 0, False)
End Sub

Sub GetDigitFromString(s As String, index As Int) As Int
    Return "" & s.CharAt(index)
End Sub

Sub DivideBy10M (s As String, m As Int) As String
    If s.Length <= m Then Return "0"
    Return s.SubString2(0, s.Length - m)
End Sub

Sub Modulo10M (s As String, m As Int) As String
    Return s.SubString(s.Length - m)
End Sub

Sub ShiftByM(s As String, m As Int) As String
    For i = 0 To m - 1
        s = s & "0"
    Next
    Return s
End Sub

 

[Erel]

Insertion Sort - Simple iterative algorithm. On each step we find the position of the next element in the previously sorted items.

Explanation: https://en.wikipedia.org/wiki/Insertion_sort

 

[Erel]

N Queens - Backtracking solution. Finds the possible placements where none of the chess queens can attack other queens.

Explanation: https://www.b4x.com/guides/Algorithms-JeffE_Backtracking/?page=1

 

[Erel]

ConstructSubset - Recursively finds a subset of values that add up to the target value.

Explanation: https://www.b4x.com/guides/Algorithms-JeffE_Backtracking/?page=6

The algorithm was adjusted to avoid making copies of the list.
Example:
X: {8, 6, 7, 5, 3, 10, 9}
Target: 33
Output: 6 + 5 + 3 + 10 + 9 = 33

'Non-UI application (console / server application)
Sub AppStart (Args() As String)
    Dim x As List
    x.Initialize
    x.AddAll(Array As Int(8, 6, 7, 5, 3, 10, 9)) 'we cannot use x = Array(..) as it will create a read-only list.
    Dim Target As Int = 33
    If ConstructSubset(x, Target) Then
        Dim sb As StringBuilder
        sb.Initialize
        For Each v As Int In x
            If sb.Length > 0 Then sb.Append(" + ")
            sb.Append(v)
        Next
        sb.Append(" = ").Append(Target)
        Log(sb.ToString)
    Else
        Log("No solution")
    End If
End Sub

'Finds a single subset that add up to Target.
'Modifies the input list.
Sub ConstructSubset (X As List, Target As Int) As Boolean
    If Target = 0 Then
        'remove all remaining values
        X.Clear
        Return True
    End If
    If Target < 0 Or X.Size = 0 Then
        Return False
    End If
    Dim CurrentValue As Int = X.Get(0)
    X.RemoveAt(0)
    'without current value
    Dim res As Boolean = ConstructSubset(X, Target)
    If res Then Return True
     'with current value
    res = ConstructSubset(X, Target - CurrentValue)
    'put the value back in the list
    X.InsertAt(0, CurrentValue)
    Return res
End Sub

 

[Erel]

LinkedList data structure.
Singly linked list implemented in a class.

Explanation: https://en.wikipedia.org/wiki/Linked_list

 

[Erel]

Stack data structure (LIFO = Last In First Out). I'm using the built-in List collection to store the elements for simplicity. The same code would have worked with the previously implemented LinkedList.

Explanation: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

 

[Erel]

Hash Table / Map / Dictionary / Associated Array data structure. Implementation of the beloved Map collection. It is a bit more complicated than the two previous data collections.

Explanation: https://en.wikipedia.org/wiki/Hash_table

The buckets are made of list of items. The bucket is chosen based on the string hash value.
Quiz: what will happen if we change CalcHash to always return 5 ? Will it work properly?

 

[Erel]

Binary Search Tree (BST) data structure - a binary tree where larger values are on the right side and smaller values are on the left side. This is an efficient structure that allows getting the values in sorted order.
It is also a good example of working with trees where almost all tasks are done recursively.
Explanation: https://en.wikipedia.org/wiki/Binary_search_tree