?‍? ?‍? Examples for teachers - Algorithms

Status
Not open for further replies.

Erel

B4X founder
Staff member
Licensed User
Longtime User
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:

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

Erel

B4X founder
Staff member
Licensed User
Longtime User
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:
B4X:
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).

V1L0INfG0B.gif


B4J project is attached.
 

Attachments

  • TowerOfHanoi.zip
    2.9 KB · Views: 724
Last edited:

Erel

B4X founder
Staff member
Licensed User
Longtime User
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.

2o3y7OjYKC.gif


B4J project is attached.
 

Attachments

  • MergeSort.zip
    2.7 KB · Views: 656
Last edited:

Erel

B4X founder
Staff member
Licensed User
Longtime User

Attachments

  • QuickSort.zip
    2.7 KB · Views: 631
Last edited:

Erel

B4X founder
Staff member
Licensed User
Longtime User
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:
B4X:
'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

B4X founder
Staff member
Licensed User
Longtime User
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

B4X:
'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
 
Last edited:

Erel

B4X founder
Staff member
Licensed User
Longtime User

Attachments

  • Stack.zip
    2.4 KB · Views: 548

Erel

B4X founder
Staff member
Licensed User
Longtime User
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

java_vdvDgaRCE5.png


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?
 

Attachments

  • HashTable.zip
    3.7 KB · Views: 578

Erel

B4X founder
Staff member
Licensed User
Longtime User
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

X438B3acdE.gif
 

Attachments

  • BinarySearchTree.zip
    4.1 KB · Views: 570
Status
Not open for further replies.
Top