Page 132 [132]
OCR
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 suggested 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.
