Nowadays computer modeling and simulation are widely used in computer science education. There are several ways of increasing the eficiency of the educational process. One of such ways is visualization, the other way is flipped classroom concept. The study aims to present some ways of increasing the eficiency of teaching data structures (hashing, trees) during the Algorithms and data structures course. We conducted two experiments with four study groups of two subjects of the Algorithms and Data Structures - (1) Hashing, (2) Trees (BST, RBT, AVL), - taught second-year bachelor students. In the ifrst experiment, study groups were prepared on the subjects (1) and (2) by the same level of teaching technique with or without visualization tools. Unlike the first experiment, in the second experiment, we used flipped classroom concepts for one study group and a standard way of teaching for another group.
Computer modeling and simulation has become a widely used tool for solving real-world problems, for training and research on human-computer interaction with complex work and diferent environments. A simulation is defined as a working representation of reality [ 1] and can be an abstracted, simplified, or accelerated model of a process or system. Computer modeling and simulation allow exploration cases even if reality is too expensive, complex, or dangerous [1]. For purpose of appropriately using computer modeling and simulation, we need to prepare students to develop and operate with such applications.
Many concepts of computer science and software engineering are dificult for students to understand. Algorithms and Data structures are one of the most important subjects in Computer Science, which is required by all programmers. Programmers need to know how to handle the data in huge quantities, how the data should be stored in the memory and how the memory should be used eficiently. We search the efective ways for implementing pedagogical tools and approaches for proper demonstration of important concepts of algorithms and data structures.
Lee and Lee [2], Knutas et al. [3], Ling et al. [4] discuss the flipped classroom methods for programming courses and promoting student engagement using this method for ordinary or large-scale courses.
The topics of team-based learning and other trends in higher education are considered by Vlachopoulos et al. [5], Burbules et al. [6]. Chang et al. [7] examine the diference in student motivation during data structure courses conducted with the visual programming language and Java.
Karavirta et al. [8], Budiman et al. [9, 10], Stasko [11], Ševčíková and Milková [12] describe the taxonomy of algorithm animation languages, multimedia applications for data structure visualization, and tools for visualizing contents media of data structure courses for mobile learning. Wang [13] proposes a public computer lab management system with four functional parts that provide a convenient and eficient way for the teachers and students to communicate and improves the management level of a public computer lab.
The flipped classroom approaches presented by Tyler and Abdrakhmanova [14], Peethambaran et al. [15], Bikanga Ada [16], Hossain [17], Hendrik and Hamzah [18]. These studies show the efectiveness of flipped classrooms in a wide range of subjects like Engineering, Education Technology, Mathematics, and Statistics, etc. The studies also show the efectiveness of lfipped classrooms in programming courses. These studies also found that the flipped classroom method facilitated learning, helped students to develop soft and hard skills, improved students’ innovative consciousness and attitudes.
There are other pedagogical approaches that can be used in teaching. Mutua et al. [19], Šimoňák [20, 21, 22, 23], Šimoňák and Benej [24], Supli et al. [25], Mocinecová and Steingartner [26] described diferent algorithm visualization platforms that can be divided as web, mobile and desktop applications.
To study this problem, we use such methods as a literature review, own experience in teaching algorithms and data structures, tasks, tests, statistical analysis, etc.
Algorithms and Data structures are really important courses for every concept used in computer science and software engineering. There are many concepts involved in the subjects of Algorithms and Data structures. There will be many questions for educators like how to learn Algorithms and Data structures, as there are many concepts involved without getting confused during attending the course. For teaching the one-semester course “Algorithms and Data structures” we used the third edition of the fundamental classic CLRS book [27].
The roadmap of teaching and learning and Data structures we define as two main parts presented in schemes on figure 1 (part 1 – Algorithms) and figure 2 (part 2 – Data structures). Part 1 includes such topics as: • Algorithms analysis technics – asymptotic analysis and notations, Big-Oh, complexities of algorithms, worst, average, best cases of algorithm performing, recurrences, master theorem for solving some types of recurrence equations; • Sorting algorithms with comparisons – bubble sort, selection sort, insertion sort, merge sort, heap sort, quicksort; • Sorting algorithms without comparisons (in linear-time) – bucket sort, counting sort, radix sort; • Searcher algorithms – linear search, binary search, jump search.
Part 2 includes data structures topics: • Linear data structures – array, stack, queue, linked list; • Non-linear data structures – hashing (direct hash tables, collisions, open addressing, double hashing, perfect hashing), trees (BST, RBT, AVL), graphs, heaps; • Augmented data structures.
Algorithms and Data structures are used to design an eficient algorithm, organize data access, and economize the execution time of programs. Data structures are widely used in operating systems, database management systems, statistical soft-ware, compiler design, numerical analysis, and artificial intelligence simulations. Algorithms and Data structures play a significant role in the computer science and soft-ware engineering domain. The course of algorithms and data structure introduces the basic data type, such as byte and character string, and presents collective data types, linked lists, stacks, arrays, queues, trees, heaps, and priority queues and complex data structures and, and focuses on programming methodologies, problem-solving strategies, and algorithm development.
The algorithms and data structures courses are typically conducted with lectures with homework, labs, and projects. Students are asked to learn algorithms implementation, data structures representations. However, students often have misconceptions. Without proper knowledge of the many classical algorithms and data structures considered in the course, it is dificult for students to understand when best to use which data structures. Such approach with the in-class lecture was mostly teacher-centered and student-teacher interaction in the class was not enough.
To find more efective ways of teaching algorithms and data structures we considered diferent approaches – visualization and flipped classroom concept. We decided to compare the efect on students learning results of using both approaches. The results of our research are presented in the last section. We chose Hashing and Trees topics for our research study.
The main problem of hashing, studied in the classical course Algorithms and Data Structures
includes the following topics: hash tables (a generalization of an array representation), direct
addressing (using an array, the size of which is comparable to the number of actual keys
stored in it), resolving possible collisions (avoiding cases of diferent keys entering the same
slot), constructing hash functions (there are a large number of implementation options), open
addressing (collision resolution method), universal and ideal hashing (used to maintain (
Binary Search Trees (BST) support operations: queries – tree traversal, finding the minimum by value, finding the maximum by value, finding the next by value, finding the previous by value, finding a node with a given key value, and operations that update BST – Insertion and Removal of a Node. When studying these operations, it is necessary to draw the attention of students to the peculiarities of performing these operations, as well as the peculiarities of inserting and removing nodes. When deleting nodes, students need to consider all three possible deletion scenarios.
Red and Black Trees (RBT) are challenging enough for students to learn. RBT is a binary search tree that has an additional field x.color (red or black) and obeys the red-black properties (RB properties): • each node is either red or black; • tree root and leaves (nil[T]) are black; • if the node is red, then both child nodes are black; • for each node, all paths from it to the leaves, descendants of this node, contain the same number of black nodes.
The color field and RB properties allow the tree to be balanced. Query operations in the RBtree are performed in the same way as in the BST. Structure-altering operations, INSERTs, and DELETEs can violate RB properties and require balancing. In the case of RB trees, the ROTATE operation is used to restore the RB property. In codes, the rotation operation is implemented by redesignating node pointers.
Another example of a balanced binary search tree that we recommend to study with students is AVL trees, which for balancing are supplemented with a node height parameter (or store the value of the diference in heights of the left and right subtrees, i.e., one of the values -1, 0, +1), and also obey the property of the AVL tree: the value of the left and right subtrees of any node should not difer by more than 1. The operations supported by AVL trees are the same as in the BST (binary search tree), RBT (red-black trees). Searching for the smallest (MIN), largest (MAX), next, and preceding element by value, searching for a node with a given key – are performed according to the same algorithms as in BST. The operations of inserting and deleting a node are ifrst performed, as in the binary search tree, but then it is necessary to check whether the AVL property is violated. After that, it is necessary to carry outbalancing.
Flipped classroom approach has become popular in education in recent decades. The flipped classroom is a student-centered pedagogical approach in which the typical course lecture and homework are reversed. Successful flipped classroom implementation involves not just having lecture videos available before class.
The algorithms and data structures course lasts 18 weeks over a semester. The class meets twice a week. We chose two topics of data structures – Hashing and Trees – for using flipped classroom concept. Each week, we recorded the lecture in several 15-to-30-minute videos. The lecture videos are made available on Moodle before the in-class lecture. Students were instructed to watch the lecture videos before coming to class each week. In a class, face-to-face meeting, students are given worksheets, which ask students to practice the topics of data structures presented in the lecture videos each week. At the end of class, the worksheets are checked for completeness and returned to the students. Students are encouraged to help answer any questions by a teacher, to discuss, and to work out the tasks on the worksheets together with other students.
The same two topics – Hashing and Trees – we chose for implementing the visualization approach. There are a lot of algorithms and data structures visualization systems available. And it is not easy to find tools that fully meet the needed requirements. As a tool of visualization, we chose the visualization modules suggested by Mathematica 12.0 that include visualization features of hashing and trees.
Algorithms and data structures visualization can be seen as a valuable supporting pedagogical tool, used as an addition to standard classical ways of education in the field of computer science and software engineering.
Šimoňák [23] concludes, that studies in which students only viewed visualizations, usually did not indicate significant learning advantages over students using conventional learning materials. It can mean that using visualizations does not guarantee students’ better understanding of algorithms.
We conducted two experiments with four study groups of the two subjects of the Algorithms
and Data Structures – (
The second experiment involved two groups – A2, B2. They also studied Hashing (A2_h, B2_h) and Trees (A2_t, B2_t) topics. Unlike the first experiment, in the second experiment, we used flipped classroom concept for group A2 as a pedagogical approach. Study group B2 was prepared by the same teacher in a standard way using the whiteboard.
In the first experiment, the number of students in group A1 was 28, group B1 had 26 students. In the second experiment, the number of students in group A2 was 31, the number of students in group B2 was 25.
The tests at the end of studying topics of subjects (
In both experiments questions on Hashing were selected from the set of questions from trivial hashing, chaining for collision handling, open addressing, double hashing, perfect hashing. For a test on Trees subjects, we selected questions from BST, RBT, and AVL trees.
The total scores achieved by students from group A1 on Hashing (A1_h) and Trees (A1_t) were 30 and 22 respectively. Average scores within the group A1 on Hashing (A1_h) and Trees (A1_t) were approximately 1.071 points and 0.789 points respectively.
The total scores for group B1 on Hashing (B1_h) and Trees (B1_t) were 20 and 20 respectively. Average scores within the group B1 on Hashing (B1_h) and Trees (B1_t) were approximately 0.769 points for B1_h and B1_t.
The total scores achieved by students from group A2 on Hashing (A2_h) and Trees (A2_t) were 32 and 31.5 respectively. Average scores within the group A2 on Hashing (A2_h) and Trees (A2_t) were approximately 1.032 points and 1.016 points respectively. The total scores for group B2 on Hashing (B2_h) and Trees (B2_t) were 19 and 19.5 respectively. Average scores in group B2 were approximately 0.760 points for B2_h and 0.780 for B2_t.
Results of the first and second experiments are presented in table 1. From the results we can
conclude the following:
• In the first experiment, group A1 that used visualizations achieved better results. In
the case of topic (
There are a lot of approaches to the implementation of some ways of increasing the eficiency
of teaching data structures (hashing, trees). We conducted two experiments with four study
groups of two subjects of the Algorithms and Data Structures – (
Flipped classroom and visualization as pedagogical tools can be used to teach students the necessary skills and competencies in algorithms and data structures. [2] G. C. Lee, P.-L. Lee, Data structures in flipped classroom: Students’ efort and preference, in: 2015 International Conference on Learning and Teaching in Computing and Engineering, 2015, pp. 152–155. doi:10.1109/LaTiCE.2015.28. [3] A. Knutas, A. Herala, E. Vanhala, J. Ikonen, The flipped classroom method: Lessons learned from flipping two programming courses, in: Proceedings of the 17th International Conference on Computer Systems and Technologies 2016, CompSysTech ’16, Association for Computing Machinery, New York, NY, USA, 2016, p. 423–430. doi:10.1145/2983468. 2983524. [4] E. W. M. Ling, C. Y. Y. Li, A. R. M. Deni, Promoting student engagement using flipped classroom in large introductory financial accounting class, in: Proceedings of the 2019 3rd International Conference on Education and E-Learning, ICEEL 2019, Association for Computing Machinery, New York, NY, USA, 2019, p. 61–66. doi:10.1145/3371647. 3371658. [5] P. Vlachopoulos, S. K. Jan, R. Buckton, A case for team-based learning as an efective collaborative learning methodology in higher education, College Teaching 69 (2020) 69–77. doi:10.1080/87567555.2020.1816889. [6] N. C. Burbules, G. Fan, P. Repp, Five trends of education and technology in a sustainable future, Geography and Sustainability 1 (2020) 93–97. doi:10.1016/j.geosus.2020.05. 001. [7] C. Chang, Y. Yang, Y. Tsai, Exploring the engagement efects of visual programming language for data structure courses, Education for Information 33 (2017) 187–200. doi:10. 3233/EFI-170108. [8] V. Karavirta, A. Korhonen, L. Malmi, T. Naps, A comprehensive taxonomy of algorithm animation languages, Journal of Visual Languages & Computing 21 (2010) 1–22. doi:10. 1016/j.jvlc.2009.09.001. [9] E. Budiman, N. Pusnitasari, M. Wati, Haeruddin, J. A. Widians, A. Tejawati, Mobile learning media for computer science course, in: 2018 International Electronics Symposium on Knowledge Creation and Intelligent Computing (IES-KCIC), 2018, pp. 262–267. doi:10. 1109/KCIC.2018.8628559. [10] E. Budiman, Haeruddin, U. Hairah, F. Alameka, Mobile learning: Visualizing contents media of data structures course in mobile networks, Journal of Telecommunication, Electronic and Computer Engineering 10 (2018) 81–86. [11] J. Stasko, Data structure visualization, in: D. P. Mehta, S. Sahni (Eds.), Handbook of Data Structures and Applications, 2nd ed., Chapman and Hall/CRC, Boca Raton, 2018, pp. 697–705. doi:10.1201/9781315119335. [12] A. Ševčíková, E. Milková, Multimedia applications: Graph algorithms visualization, in: 2016 IEEE 17th International Symposium on Computational Intelligence and Informatics (CINTI), 2016, pp. 000231–000236. doi:10.1109/CINTI.2016.7846409. [13] F. Wang, The design of public computer lab management system based on network environment, in: Proceedings of the 2016 International Conference on Education, Management and Computer Science, Atlantis Press, 2016/05, pp. 263–267. doi:10.2991/icemc-16. 2016.55. [14] B. Tyler, M. Abdrakhmanova, Flipping the CS1 and CS2 classrooms in Central Asia, in: 2016 IEEE Frontiers in Education Conference (FIE), IEEE, 2016, pp. 1–5. doi:10.1109/FIE.