Oldal 132 [132]
4.2 HOW CAN THE PRESENTED METHODS BE IMPROVED... 131
The merge sort (and guick sort) dance video offers an excellent opportunity
for introducing the concept of parallelization too, which is also included by ISTE/
CSTA (2020) among the CT-related key abilities. “Why boys stand idle while
girls...?” is an obvious question also suggesting the need for parallelization.
11.3.4 Exploring backtracking strategies from an algorithm
complexity perspective
Time complexity aspects of n-queens backtracking algorithms can be sug¬
gested by discussing the following questions (see Figures 11.4):
— How many possibilities are to arrange 4 pawns on a 4 x 4 chessboard if the
only restriction is: no pawns in the same row? How many pawn ballerinas
are needed for a four-pawn backtracking choreography?
— How many possibilities are to arrange 4 rooks on a 4 x 4 chessboard in
such a way that no rook is positioned to attack any other rook (no rook
pairs in the same row or column)? How many rook ballerinas are needed
for a four-rook backtracking choreography?
— How many possibilities are to arrange 4 queens on a 4 x 4 chessboard in
such a way that no queen is positioned to attack any other queen (no queen
pairs in the same row, column, or diagonal)? How many queen ballerinas
are needed for a four-queen backtracking choreography?
If students master the related mathematical apparatus (exponential function,
permutations), the teacher might continue as follows:
— How many possibilities are to arrange n pawns on an n x n chessboard if
the only restriction is: no pawns in the same row?
— How many possibilities are to arrange n rooks on an n x n chessboard in
such a way that no rook is positioned to attack any other rook?
— Although implementing the n-pawns backtracking algorithm is easier than
implementing the n-queens one, why is “the valid n-queens arrangements
are such valid n-pawns arrangements where no pawns are in the same
column or diagonal” approach inefficient?
— Usually, backtracking algorithms have exponential time complexity. Why?
11.3.5 Basic characteristics of algorithms: Generality
According to the ISTE definition, CT implies the skill of generalizing and
transferring the studied problem-solving process to a wide variety of problems
(skill 6). In line with this, the teacher should help students notice that the studied
algorithms/searching strategies are applicable to any sequence (or any sorted
sequence in the case of binary search).
— The protagonist of the performance is searching for a dancer sequence
wearing the numbers on their back.