Solving the Curriculum Sequencing Problem with DNA Computing Approach

1. Introduction And Motivation

The e- learning field is “learning via computing devices and the internet” (Chu & Chang & Tsai, 2009). This kind of education enables the learning process to take effect at anytime and anywhere, following a learner’s preferred path and space (Tattersall & Manderveld & den Berg & van Es & Janssen & Koper, 2005;Janssen & Tattersall & Waterink & den Berg & van Es & Bolman & Koper, 2005;Chen & Peng & Shiue, 2008) . The e- learning system is an environment that provides the e-learning materials and manage the learning content in the one hand and monitor the learning experience and progress in the other hand (Chu & Chang& Tsai,2009). Most e-learning systems provide a one size fits all environments where all the learners are treated the same way in terms of learning materials, and are self-guided with limited instructor support. Thus new learning materials are available every day, this huge amount of information can lead to information overload and disorientation (Chen & Peng & Shiue, 2008). The personalization is an important feature of current century (Hauger& Kock, 2007). Personalization in e –learning is considered as the center stage for an effective learning experience (Hauger & Kock, 2007). It consists of adapting the knowledge according to learner’s needs such as preferences, competencies and requirements. For the purpose of the personalization comes the idea of delivering to each learner a personalized learning path known as the curriculum sequence. The Curriculum Sequencing problem (CS) consists “to generate an individualized course for each student by dynamically selecting the most optimal teaching operation (presentation, example, question or problem) at any given moment” (Huang & Huang& Chen, 2007). In fact, the structure of the knowledge model consists of graph. Hence, the real problem consists of searching for the optimal learning path leading to the goal from a start point until an end point passing by some nodes. Given a graph consisting of nodes (vertices) linked by edges, find a route/ path which starts at a given node and ends at another given node assuming that the arcs are labeled with weights. This has to be done by calculating the maximum sum of weights between each two nodes. The point here is there is no known algorithm which works in polynomial time for identifying a graph’s optimal route between two nodes. Meaning that if there were a non deterministic machine which could explore each of the rules in parallel, each route can be computed in polynomial time, but the space of possible routes grows exponentially. As a result the CS problem falls in the NP complete class of problems (Acompora & Gaeta & Loia, 2009), this has been proved in [INSERT FIGURE 096][INSERT FIGURE 094](Marcos, 2007;Marcos, 2008). by calculating its complexity for an example of 23 courses for a master and engineering program. The possible number of sequences is about feasible solutions to the problem. DNA computing has shown its efficiency for solving NP hard problems such as spanning tree, Travel Salesman Problem (TSP), Hamiltonian path Problem (HPP). The power of this approach is due to the encoding of data in DNA strands and the use of tools from molecular biology to execute computational operations (Kari,1997). Besides its novelty, molecular computing has the potential to outperform electronic computers. For example, DNA computations may use a billion times less energy than an electronic computer, while storing data in a trillion times less space (Baum,1995). Furthermore, computing with DNA is strongly parallel which means that there could be billions upon trillions of DNA molecules undergoing chemical reactions, that is, performing computations, simultaneously (Reif,1995). In our study we propose a new bio-inspired method which consists of the use of the DNA computing method for solving the sequencing problem (optimal route/path) in e-learning system for pedagogical sequencing. The paper is organized as follows. section 2 summarizes some of the related works, after that section 3 describes the Curriculum sequencing problem and its mathematical formalization, later in section 4 we present the DNA computing approach, in section 5 we describe the DNA algorithm for solving the curriculum sequencing problem. Section 6 tackles the results and discussion. Later section 7 presents a brief conclusion of the work.