Using a project-based learning method in each advanced data structures – priority queues

JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 179-188 This paper is available online at USING A PROJECT-BASED LEARNING METHOD IN EACH ADVANCED DATA STRUCTURES – PRIORITY QUEUES Doan Thi Thu Huyen Faculty of Information Technology, Hanoi National University of Education Email: huyendtt88@gmail.com Abstract. In this paper, we propose a new approach to teach advanced data structures - priority queues to junior and senior Information Technology (IT) students by applying the project-based learning method, a student-centered method which aims to create a learning environment in which students work individually to complete an open-ended project. To estimate how effectively project-based method works in IT education and show how the method works in a specific IT project, results are presented from a pedagogical experiment on group of 15 students studying IT at Hanoi University of Science and Technology. Based on the results of this experiment, the project proved that this new approach in teaching advanced data structures to IT students was effective. Keywords: Project-based learning, advanced data structures, priority queues. 1. Introduction Project-based learning (PBL) method, which consists of many ways to develop a curriculum, allows for an active and constructive way to develop a central didactic principle that integrates several skills and competences through real work tasks and processes [1]. PBL is synonymous with learning in depth. A well-designed project provokes students to encounter central concepts and principles of a discipline. The use of projects in the university comprises several tasks that are usually perceived as separate units: to do research and transfer projects, to teach project management and dedicated subjects, to educate students to carry out research and do practical work, and to achieve relevant results within student’s projects [1,4,3]. In computer science (CS) education and, more specifically, in the teaching of data structures and algorithms, doing with each project, learners are forced to either modify existing concepts or develop new ones. This helps them practice their abstract thinking and algorithm thinking through levels of abstraction in an algorithm concept. Jacob C. 179 Doan Thi Thu Huyen Perrenet [2] suggested that students study making use of 4 levels of abstraction: the execution level, the program level, the object level and the problem level. They must specify a problem precisely, analyze given problems, determine the basic actions that are adequate to the given problem, construct a correct algorithm to a given problem using the basic actions, think about all possible particulars and normal cases of a problem and to improve the efficiency of an algorithm. PBL has been used for multiple classrooms [9], groups [1,5] and individuals [10,11]. Universities and colleges in Vietnam have widely utilized PBL in many subjects. FPT Polytechnic designs a training program for each term include the PBL method, and a case-study for every subject. They provide flexible engagement models which ensure that the program will meet the diverse needs and requirements of society. The method is used at the Hanoi National University of Education, Hanoi University of Science and Technology (HUST) and others, with some practical subjects for senior students. For our priority queue major, one of the interested abstract data types today, PBL applied to individuals is a promising method since to become knowledgeable in this field demands a profound background and it is difficult to utilize conventional education method, when the presentation of programming and code are impossible. In addition, abstraction, the ability to perform abstract thinking and to exhibit abstraction skills, one of the fundamental principles of software engineering in order to master complexity, takes an important role in computer science education [11,12,13], especially in studying these data structures because the concept of queue only exists in real life, but computer. In CS curriculum, heap and binary heap, however, are only presented to approach priority queue data structures, whereas in many instances types of priority queue are used the most popular being that of Van Emde Boas, which is presented in many English materials and courses around the world [7,8]. We assume that some skills, including abstract thinking (especially at the object and the problem level), algorithm thinking, research skills and some soft-skills related to carrying out projects, can be best learned in authentic and student-centered projects by making the suitable pedagogical environment that includes giving students the chance to explore many questions based primarily on surmise - inspiring them to describe the way they deal with problems - and teaching broad concepts in preference to just facts. This paper describes a general curricular concept of PBL which can be applied to each student. In one example, the goals and objectives as well as the organization will be described. The focus of this paper is on the learning process for students carrying out projects. 180 Using project-based learning method to each advanced data structures... 2. Content 2.1. Project-based learning and design project example 2.1.1. Project-based learning method The first documented effort of PBL can be found in the engineering curriculum at the University of Aalborg (Denmark) in 1974. Features of PBL, its roles and effectiveness have been widely researched from many standpoints [3]. Basically, most approaches proposed that: PBL creates a "constructivist" learning environment in which students construct their own knowledge. They are taught about skills as well as content. These skills can be categorized as communication and presentation skills, organization and time management skills, research and inquiry skills, self-assessment and reflection skills, group participation and leadership skills. In addition, PBL allows students to reflect upon their own ideas and opinions, exercise voice and choice, and make decisions that affect project outcomes and the learning process in general. PBL offers a wide range of benefits to both students and teachers. A growing body of academic research supports the use of PBL in universities and colleges to engage students, cut absenteeism, boost cooperative learning skills and improve academic performance. In a project, students have some choices in deciding what they will work on, they plan their own project and participate in defining criteria and rubrics to assess their project and they solve problems they encounter while working on their project and make some sorts of final presentation of their project. Thus, students involved in projects take greater responsibility for their own learning than during more traditional classroom activities. Especially, with CS projects, they have opportunities to develop a different set of skills: project management, time management, organization, research procurement and debugging and complex skills, such as higher-order thinking, problem-solving, collaborating and communicating. In order to have a well-designed project, it’s important for lecturers to recognize situations that would make for good projects, to structure problems as learning opportunities, to collaborate with colleagues to develop interdisciplinary projects, to manage the learning process, to integrate technologies where appropriate and to develop authentic assessments[4]. In this method, the project is often divided into several steps and phases in a variety of approaches [1,5,14]. To generate a curriculum, we apply a method that divides the project design design into 7 major steps [5]. We utilize this direction to design a project about advanced data structure. Step 1. Preparation, getting involved: Students can get acquainted with the topic 181 Doan Thi Thu Huyen to be worked on in two ways: with the tools of the divergence and of the convergence. The introduction of the topic has to be from various angles. Participating in the project, students must know clearly the requirements their teachers have for them. Step 2. The examination of the topic: Information ought to be collected on the topic or problem in as many ways and from as many sources as possible. Step 3. The elaboration of the action plan: The distribution of the tasks to be accomplished, the schedule and the definition of the key events must be given. In this step, individual ideas can be developed, for original thoughts and unique solutions are welcome, but it is also the most time consuming step. Each step has to be accomplished within a certain deadline, and it must be done responsibly. Step 4. The fulfilment of the action plan: The task assignment, the collection of ideas and the preparation are followed by the fulfilment of the action plan. If the students find joy and anticipation in their work, the project will be carried out developed appropriately. Step 5. Presentation: Students don’t present an accomplished work, but the results of their work. Step 6. Evaluation, review, feedback: Students must experience success during the project. We ought to appreciate originality, the precision of the execution, and the good decisions made. Step 7. Planning the future: This step is needed if there is to be continued work on the project or if we transmit the results to other persons or groups. Base on size, type and features of a specific project, lecturers should flexibly apply these steps flexibly. Some steps may be grouped into one to reduce and simplify the process. 2.1.2. Project example Topic: Priority queues Parts of the topic: Some specific abstract data structures can be used to implement priority queues find a shortest path problem using the Dijkstra algorithm and solve other problems, designing and implementing them with each data structure. Target community: The junior and senior IT students Project duration: 12 sessions Aims: The core aims designated as fundamental to the project are: - To practice abstract thinking and algorithm thinking in CS education. - To understand the role of priority queues and study the implementation and use of several abstract data structures, such as: Binary heap, Fibonacci heap, Trinomial heap, Binomial heap, Relaxed heap, 2-3 heap, Skew heap, Van Emde Boas tree, Sorted linked list, Splay tree, Calendar queue, Lazy queue, Henriksen’s data structure, Skip lists, 182 Using project-based learning method to each advanced data structures... SPEEDESQ and Ladder Queue. - To design Java applet simulations and some simple applications, for example, heap sort, a container, a searchable container, Dijkstra algorithm, graph algorithms and backtracking algorithms. Methods and procedures: Study, discovery, analysis, design, presenting unsolved problems, individual work, presentation, conversation, didactic play, seminars, learning activities and the project itself. Keywords: Algorithm, Data structures, Priority queues. Background: In order to fully appreciate the requirement of data structures that can be used to implement priority queues, it is important to have details on the followings: Essentials of algorithm and data structure skills (array, linked list, stack, queue, tree and operations on them), fluent use of programming languages (for example, Pascal, C, C++ or Java) and algorithm analysis techniques (worst-case, best-case, average-case, amortized analysis). Information Sources: References: Introduction to algorithms [7], Van Emde Boas Queues [8] and some scientific papers; Alternative information sources, such as the internet, newspaper articles, books, lectures of teachers, information furnished by firms, other teachers’ and friends’ opinion; Java applet demos for data structures and class templates support the programming process. Participants: Junior and senior IT students. The process: Step 1: Preparation, introduction Project ideas: Scheduling the unit-time task problem “The problem of optimally scheduling unit-time tasks on a single processor, where each task has a deadline, along with a penalty paid if the task misses its deadline. A unit-time task is a job, such as a program to be run on a computer that requires exactly one unit of time to complete. Given a finite-set S of unit-time tasks, a schedule for S is a permutation of S specifying the order in which to perform these tasks. The first task in the schedule begins at time 0 and finishes at time 1, the second task begins at time 1 and finishes at time 2, and so on. We wish to find a schedule for S that minimizes the total penalty incurred for missed deadlines.” [7] The lecturer uses the brainstorming technique asks students to imagine problems to which this abstract data type can be applied, and then gives them a few minutes to think and then say what they think. The lecturer make clear the basic differences between queue and priority queue. The lecturer talks with the students about the role of priority queues in computer science and in problems of the real life and its applications: Find shortest path 183 Doan Thi Thu Huyen problem using the Dijikstra algorithm; manage limited resources such as bandwidth on a transmission line from a network router, simulations, and in the implementation of some algorithms (e.g., some graph algorithms, some backtracking algorithms); Huffman coding; A* and SMA* search algorithms; schedule events; the procedure used by several sorting algorithms, such as heapsort, smoothsort, selection sort, insertion sort and tree sort,. . . Splay, Calender and skip list: they are not implemented in priority queue, but they are used for binary search and binary tree search is applied in priority queue. Continuously, the lecturer gives students keywords and main references and informs them of the Project requirements. Project work for each topic consists of the following: - Study data structures you chose. - Design an application that demonstrates the Dijkstra algorithm for each data structure. - Design simple applications using data structures in the study and measure the program running time and time complexity for each application. - Write a report about your study and give a presentation that summarizes the content of your study and the results you got. The installation program must ensure these requirements: 1. Programming language: structural/ object - oriented language 2. Each element has a key ordered. 3. Install procedures for each data type (Insert, Delete, ext-min, min, decrease key,. . . ). 4. Use console interface with selection menu. 5. Input: From keyboard and from file; Output: Display on the screen and write to file. Students are responsible for determining and conducting all of the intermediate steps. The last half of each course is entirely devoted to project work, giving the students plenty of time to complete and document the project. During this phase of the project, the instructors act as coaches rather than as experts. At the same time, a Project Charter that serves as a contract between the students and the lecturer is given. All students must agree to the Project Charter that is a formal demonstration of the student-centered approach used in these courses. In addition, by asking the students to include evaluation criteria, it reinforces the idea that they are responsible for the project in general and for their individual behavior in the course. And lastly, the lecturer present Project evaluation planning. In this course, students are allowed to determine the extent that their project determine their grades and its generally worth 60% of the overall course grade. The rest is determined by the course 184 Using project-based learning method to each advanced data structures... instructor. Assessments are based on the Table of evaluation criteria. Step 2: Examination of the topic, data collection Each student has a chance to choose two of fifteen topics below to study and present his result. Each subject is given a weight, valued from 1 to 5, corresponding to difficulty of each topic. 1: Binary heap, Binomial heap, Fibonacci heap. 2: Trinomial heap, Skew heap, 2-3 heap. 3: Splay tree, Calendar queue, Skip lists. 4: Sorted linked list, Ladder Queue, Lazy queue. 5: Relaxed heap, Van Emde Boas queues, Henriksen’s data structure. The total weight of a student’s selected topics must be equal to or greater than 6. With this extensive selection, students can be ensured of an active role in making the selections, and chosen subjects will likely be suitable to every one. Step 3: Elaboration of the action plan - Design a set of inputs that can test students’ programs and applications. - Project risk management: Difficulty in reading comprehension (since almost materials supplied in English): get additional explanation from the lecturer via a variety of communication channels: email, forum, discussion. . . ; difficulty in implemention when using a specific programming language provide programming languages materials for reference. Step 4: Carrying out the action plan Duting the first session, the subject, priority queues, is presented. Students listen to the lectures about priority queues and, in general, enumerate some data structures used to implement priority queues. Ideas and information are collected. From the 2nd session to the 7th session, students do their project themselves, study their own chosen data structures and design applications, measure program running time and time complexity, write their report and prepare to make their presentation before the class. From the 8th session to the 12th session, each student in succession presents his project. At the end of the 12th session, the lecturer summarizes what is know about priority queues and related data structures, shows the data structures that are most commonly used nowadays and evaluates the study progress and results of each student. Step 5: Presentation The PBL helps students become more confident in their communication by requiring a presentation before other people. Additionally, posting question is another skill that is pressed in this course. Continuous feedback by course instructor and external 185 Doan Thi Thu Huyen participants encourage additional student learning progress. Throughout continuous feedback is necessary for the project students. Thus, at this step, the lecturer always needs to encourage his students to post questions and be skeptical about the correctness of their results and that of others. Here are some questions that the lecturer can ask after students’ presentations: - What do you now think are the important questions? Which ones are different from your original questions? Has any of this changed your thinking? About what? What are the answers to your questions? - What are advantages and disadvantages of this data structure? - From your perspective, what problems did you encountered with your programs? What concerns do you have concerning their reliability? - What could be done to improve or enhance your programs in the future? - - What errors and mistakes did you make? Why were these mistakes made? Which of these errors were corrected? How were they corrected? - After this experience, what other project would you like to tackle next? - - Regarding the questions from the other students, which questions could you not answer immediately? Do you have any questions? Step 6: Evaluation, review The lecturer evaluates the performance of students and draws conclusions about the role of priority queues in data structures and algorithms of CS, in implementing Prim’s algorithm and Dijkstra’s algorithm and other problems in our life. The lecturer makes comments about each student and evaluates his