B-TREE algorithm complexity analysis to evaluate the feasibility of its application in the university course timetabling problem

• Autorzy: Cruz Chávez M. A. , Martínez Oropeza A.

Identyfikatory

DOI

10.2478/jaiscr-2014-0018

• Języki publikacji: EN

Abstrakty

EN

This paper presents a comparative analysis of complexity between the B-TREE and the Binary Search Algorithms, both theoretically and experimentally, to evaluate their efficiency in finding overlap of classes for students and teachers in the University Course Timetabling Problem (UCTP). According to the theory, B-TREE Search complexity is lower than Binary Search. The performed experimental tests showed the B-TREE Search Algorithm is more efficient than Binary Search, but only using a dataset larger than 75 students per classroom.

Słowa kluczowe

EN

B-TREE; algorithm; Binary Search Algorithms; complexity analysis; University Course Timetabling Problem; UCTP

• Wydawca: University of Social Sciences
• Czasopismo: Journal of Artificial Intelligence and Soft Computing Research
• Rocznik: 2013
• Tom: Vol. 3, No. 4
• Strony: 251--263
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Cruz Chávez M. A.

• CIICAp, Universidad Autonoma del Estado de Morelos Av. Universidad 1001. Col. Chamilpa, C.P. 62209. Cuernavaca, Morelos, Mexico

autor

Martínez Oropeza A.

• CIICAp, Universidad Autonoma del Estado de Morelos Av. Universidad 1001. Col. Chamilpa, C.P. 62209. Cuernavaca, Morelos, Mexico

Bibliografia

• [1] M.R. Garey, and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NPCompleteness, W.H. Freeman and Company, New York, USA, ISBN 0-7167-1044-7, 1979.
• [2] S. Even, A. Itai, and A. Shamir, On the Complexity of Timetable and Multicommodity Flow Problems, SIAM Journal on Computing, 5(4):691-703, ISSN 0097-5397, 1976.
• [3] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications Inc., U.S.A., ISBN 0-486-40258-4, p. 496, 1998.
• [4] R. Johnsonbaugh, Discrete Mathematics, 6th Edition, Prentice Hall, U.S.A., ISBN 0-13-117686-2, ISBN 0-13-117686-2.
• [5] B. Paechter, R. C. Ranking, A. Cumming and T. C. Fogarty, Timetabling the Classes of an Entire University with an Evolutionary Algorithm. Parallel Problem Solving from Nature (PPSN) V. Lectures Notes in Computer Science 1498, Springer-Verlag, Berlin, pp. 865-874, 1998.
• [6] O. Rossi-Doria, M. Samples, M. Birattari, M. Chiarandini, M. Dorigo, L. M. Gambardella, J. Knowles, M. Manfrin, M. Mastrolilli, B. Paechter, L. Paquete, and T. Sttzle. A Comparison of the Performance of Different Metaheuristics on the Timetabling Problem, Lecture Notes in Computer Science, Vol. 2740 pp. 329-351. Springer-Verlag, Berlin, Germany, 2003.
• [7] J. F. Korsh, Data Structures, Algorithms and Program Style, ISBN: 0871509369, PWS Computer Science, USA, p. 499, 1986.
• [8] O. Cair, and S. Guardati., Data Structures, ISBN:9701059085, McGraw-Hill, p. 423, Mxico 2006.
• [9] D. F. Stubbs and N. W. Webre, Data Structures with Abstract Data Types and Pascal, ISBN: 0534092640, Brooks/Cole Pub. Co., p. 471, 1994.
• [10] T. H. Cormen, C. E. Leiserson and C. D. Stein, Introduction to Algorithms, 2nd Edition. Mit Press, U.S.A., ISBN 0-262-03293-7, 2001.
• [11] T. Cunnolly and C. Begg, Database Systems, A Practical Approach to Design, Implementation and Management, Fourth Edition, Addison Wesley, U.S.A., ISBN 0-201-70857-4, 2004.