Solving the Curriculum Sequencing Problem with DNA Computing Approach

Solving the Curriculum Sequencing Problem with DNA Computing Approach

Amina Debbah (LRI (Laboratory of Computer Research), Computer Science Department, University of Badji Mokhtar, El Hadjar, Algeria) and Yamina Mohamed Ben Ali (LRI (Laboratory of Computer Research), Computer Science Department, University of Badji Mokhtar, El Hadjar, Algeria)
Copyright: © 2014 |Pages: 18
DOI: 10.4018/ijdet.2014100101
OnDemand PDF Download:


In the e-learning systems, a learning path is known as a sequence of learning materials linked to each others to help learners achieving their learning goals. As it is impossible to have the same learning path that suits different learners, the Curriculum Sequencing problem (CS) consists of the generation of a personalized learning path for each learner according to one's learner profile. This last one includes one's knowledge and preferences. In fact the CS problem is considered as NP hard problem, so many heuristics and meta-heuristics have been used to approximate its solutions. Therefore the results have shown their efficiency to solve such a problem. This work presents a DNA computing approach that aims to solve the CS problem.
Article Preview

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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 15: 4 Issues (2017)
Volume 14: 4 Issues (2016)
Volume 13: 4 Issues (2015)
Volume 12: 4 Issues (2014)
Volume 11: 4 Issues (2013)
Volume 10: 4 Issues (2012)
Volume 9: 4 Issues (2011)
Volume 8: 4 Issues (2010)
Volume 7: 4 Issues (2009)
Volume 6: 4 Issues (2008)
Volume 5: 4 Issues (2007)
Volume 4: 4 Issues (2006)
Volume 3: 4 Issues (2005)
Volume 2: 4 Issues (2004)
Volume 1: 4 Issues (2003)
View Complete Journal Contents Listing