{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T19:51:43Z","timestamp":1783972303208,"version":"3.55.0"},"reference-count":60,"publisher":"National Library of Serbia","issue":"3","license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ComSIS","COMPUT SCI INF SYST","COMPUT SCI INFORM SY","COMPUTER SCI INFORM","COMSIS J"],"published-print":{"date-parts":[[2024]]},"abstract":"<jats:p>Computational complexity analysis plays an essential part in the education of computer and software engineers. For that reason, it is carefully studied in programming courses, as well as in the algorithms and data structures courses. The number of students who learn programming is rapidly growing, but the number of teachers cannot keep up with that trend. Therefore, it is necessary to develop tools that can ease and accelerate the daily tasks of teachers, especially for learning purposes and in the context of automating the processes of exam preparation. We propose a novel template- and rule-based approach and a corresponding software system for assembling synthetic source code segments of defined time complexity. Based on the developed grammar, the system can produce source code segments with a broad scope of different time complexities while guaranteeing the complexity of the generated segment. The system can be used for generating questions for exams as it can assemble a large number of different code segments that can be given as questions that have similar difficulty levels. The system was evaluated both by human experts and ChatGPT tool.<\/jats:p>","DOI":"10.2298\/csis230730015p","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T12:23:20Z","timestamp":1715689400000},"page":"781-806","source":"Crossref","is-referenced-by-count":1,"title":["A novel approach to source code assembling in the field of algorithmic complexity"],"prefix":"10.2298","volume":"21","author":[{"given":"Dordje","family":"Pesic","sequence":"first","affiliation":[{"name":"University of Belgrade, School of Electrical Engineering, Belgrade, Serbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5396-0644","authenticated-orcid":false,"given":"Milena","family":"Vujosevic-Janicic","sequence":"additional","affiliation":[{"name":"University of Belgrade, Faculty of Mathematics, Belgrade, Serbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7369-4010","authenticated-orcid":false,"given":"Marko","family":"Misic","sequence":"additional","affiliation":[{"name":"University of Belgrade, School of Electrical Engineering, Belgrade, Serbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jelica","family":"Protic","sequence":"additional","affiliation":[{"name":"University of Belgrade, School of Electrical Engineering, Belgrade, Serbia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1078","reference":[{"key":"ref1","unstructured":"Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley Longman Publishing Co., Inc., USA (2006)"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"Aiyappa, R., An, J., Kwak, H., Ahn, Y.Y.: Can we trust the evaluation on chatgpt? arXiv preprint arXiv:2303.12767 (2023)","DOI":"10.18653\/v1\/2023.trustnlp-1.5"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"Ala-Mutka, K.M.: A survey of automated assessment approaches for programming assignments. Computer science education 15(2), 83-102 (2005), https:\/\/doi.org\/10.1080\/08993400500150747","DOI":"10.1080\/08993400500150747"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"Alon, U., Zilberstein, M., Levy, O., Yahav, E.: code2vec: Learning distributed representations of code. Proceedings of the ACM on Programming Languages 3(POPL), 1-29 (2019), https: \/\/doi.org\/10.1145\/3290353","DOI":"10.1145\/3290353"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational complexity: a modern approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"Barrett, C., Tinelli, C.: Satisfiability modulo theories, Handbook of Model Checking. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-10575-8_11"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"Bentley, J.L., Haken, D., Saxe, J.B.: A general method for solving divide-and-conquer recurrences. ACM SIGACT News 12(3), 36-44 (1980), https:\/\/doi.org\/10.1145\/1008861.1008865","DOI":"10.1145\/1008861.1008865"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"Biermann, A.W.: A simple methodology for studying program time complexity. Computer Science Education 1(4), 281-292 (1990), https:\/\/doi.org\/10.1080\/0899340900010402","DOI":"10.1080\/0899340900010402"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"Biswas, S.: Role of chatgpt in computer programming. Mesopotamian Journal of Computer Science 2023, 8-16 (2023)","DOI":"10.58496\/MJCSC\/2023\/002"},{"key":"ref10","unstructured":"Bo\u0161njakovi\u0107, A., Protic, J., Boji\u0107, D., Tartalja, I.: Automating the knowledge assessment workflow for large student groups: A development experience. The International journal of engineering education 31(4), 1058-1070 (2015)"},{"key":"ref11","unstructured":"Conway, J.: Unpredictable iterations. The Ultimate Challenge: The 3x+ 1 Problem pp. 49-52 (1972)"},{"key":"ref12","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT press (2022)"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"Dagien\u0117, V., Jevsikova, T., Stupurien\u0117, G., Ju\u0161kevi\u010dcien\u0117, A.: Teaching computational thinking in primary schools: Worldwide trends and teachers\u2019 attitudes. Computer Science and Information Systems 19(1), 1-24 (2022)","DOI":"10.2298\/CSIS201215033D"},{"key":"ref14","unstructured":"Dasgupta, S., Papadimitriou, C.H., Vazirani, U.: Algorithms. McGraw-Hill Education (2006)"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"Draskovic, D., Misic, M., Stanisavljevic, Z.: Transition from traditional to lms supported examining: A case study in computer engineering. Computer Applications in Engineering Education 24(5), 775-786 (2016), https:\/\/doi.org\/10.1002\/cae.21750","DOI":"10.1002\/cae.21750"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"Geerlings, H., van der Linden, W.J., Glas, C.A.: Optimal test design with rule-based item generation. Applied Psychological Measurement 37(2), 140-161 (2013), https:\/\/doi.org\/10.1177\/0146621612468313","DOI":"10.1177\/0146621612468313"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"Glas, C.A., van der Linden, W.J.: Computerized adaptive testing with item cloning. Applied Psychological Measurement 27(4), 247-261 (2003), https:\/\/doi.org\/10.1177\/0146621603027004001","DOI":"10.1177\/0146621603027004001"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"Glas, C.A., van der Linden,W.J., Geerlings, H.: Estimation of the parameters in an item-cloning model for adaptive testing. In: Elements of adaptive testing, pp. 289-314. Springer (2009)","DOI":"10.1007\/978-0-387-85461-8_15"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"Goldsmith, S.F., Aiken, A.S.,Wilkerson, D.S.: Measuring empirical computational complexity. In: Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering. pp. 395-404 (2007), https:\/\/doi.org\/10.1145\/1287624.1287681","DOI":"10.1145\/1287624.1287681"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"Graham, S.L., Kessler, P.B., McKusick, M.K.: Gprof: A call graph execution profiler. ACMSigplan Notices 17(6), 120-126 (1982), https:\/\/doi.org\/10.1145\/872726.806987","DOI":"10.1145\/872726.806987"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"Gulwani, S., Mehra, K.K., Chilimbi, T.: Speed: precise and efficient static estimation of program computational complexity. ACM Sigplan Notices 44(1), 127-139 (2009), https: \/\/doi.org\/10.1145\/1594834.1480898","DOI":"10.1145\/1594834.1480898"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"Gustafsson, J., Ermedahl, A., Sandberg, C., Lisper, B.: Automatic derivation of loop bounds and infeasible paths for wcet analysis using abstract execution. In: 2006 27th IEEE International Real-Time Systems Symposium (RTSS\u201906). pp. 57-66. IEEE (2006), https: \/\/doi.org\/10.1109\/RTSS.2006.12","DOI":"10.1109\/RTSS.2006.12"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"Hernandez-Del-Olmo, F., Gaudioso, E.: Autotest: An educational software application to support teachers in creating tests. Computer Applications in Engineering Education 21(4), 636- 640 (2013), https:\/\/doi.org\/10.1002\/cae.20508","DOI":"10.1002\/cae.20508"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"Ihantola, P., Ahoniemi, T., Karavirta, V., Seppala, O.: Review of recent systems for automatic assessment of programming assignments. In: Proceedings of the 10th Koli calling international conference on computing education research. pp. 86-93 (2010), https:\/\/doi.org\/10.1145\/1930464.1930480","DOI":"10.1145\/1930464.1930480"},{"key":"ref25","unstructured":"Knuth, D.E.: The art of computer programming. Vol. 1: Fundamental algorithms. Addison- Wesley (1968)"},{"key":"ref26","unstructured":"Knuth, D.E.: The analysis of algorithms. In: Actes du Congres International des Mathematiciens (Nice, 1970). vol. 3, pp. 269-274 (1970)"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"Knuth, D.E.: Big omicron and big omega and big theta. ACM Sigact News 8(2), 18-24 (1976), https:\/\/doi.org\/10.1145\/1008328.1008329","DOI":"10.1145\/1008328.1008329"},{"key":"ref28","unstructured":"Licht, B.: Obstacles in learning algorithm run-time complexity analysis. University of Nebraska at Omaha (2022), theses\/Capstones\/Creative Projects. 193. https:\/\/digitalcommons.unomaha.edu\/university_honors_program\/193"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"Lo, C.K.: What is the impact of chatgpt on education? a rapid review of the literature. Education Sciences 13(4), 410 (2023)","DOI":"10.3390\/educsci13040410"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"McCabe, T.J.: A complexity measure. IEEE Transactions on software Engineering SE-2(4), 308-320 (1976), https:\/\/doi.org\/10.1109\/TSE.1976.233837","DOI":"10.1109\/TSE.1976.233837"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"McGeoch, C.C., Cohen, P.: How to find big-oh in your data set (and how not to). In: Sixth International Workshop on Artificial Intelligence and Statistics. pp. 347-354. PMLR (1997)","DOI":"10.1007\/BFb0052828"},{"key":"ref32","unstructured":"MIDAS Research Laboratory, I.D.: Corcod: Code runtime complexity dataset (2019), [Online]. Available: https:\/\/github.com\/midas-research\/corcod-dataset (current October 2023)"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"Mi\u0161i\u0107, M., Lazi\u0107, M., Proti\u0107, J.: A software tool that helps teachers in handling, processing and understanding the results of massive exams. In: Proceedings of the Fifth Balkan Conference in Informatics. pp. 259-262 (2012), https:\/\/doi.org\/10.1145\/2371316.2371370","DOI":"10.1145\/2371316.2371370"},{"key":"ref34","unstructured":"Moudgalya, K., Ramakrishnan, A., Chemudupati, V., Lu, X.H.: Tasty: A transformer based approach to space and time complexity. arXiv preprint arXiv:2305.05379 (2023)"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"Nethercote, N., Seward, J.: Valgrind: a framework for heavyweight dynamic binary instrumentation. ACM Sigplan notices 42(6), 89-100 (2007), https:\/\/doi.org\/10.1145\/1273442.1250746","DOI":"10.1145\/1273442.1250746"},{"key":"ref36","unstructured":"Ne\u0161kovi\u0107, R.: Predicting time complexity of algorithms on pascal programming language using machine learning techniques. University of Belgrade, School of Electrical Engineering (2021), master thesis (in Serbian)"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"Omonayajo, B., Al-Turjman, F., Cavus, N.: Interactive and innovative technologies for smart education. Computer science and information systems 19(3), 1549-1564 (2022)","DOI":"10.2298\/CSIS210817027O"},{"key":"ref38","unstructured":"OpenAI: ChatGPT, https:\/\/chat.openai.com\/"},{"key":"ref39","unstructured":"Papadimitriou, C.H.: Computational complexity. In: Encyclopedia of computer science, pp. 260-265. John Wiley and Sons (2003)"},{"key":"ref40","unstructured":"Pe\u0161i\u0107, D., Mi\u0161i\u0107, M., Proti\u0107, J., Vujo\u0161evi\u0107 Jani\u010di\u0107, M.: Sistem za generisanje programskih segmenata za ispitivanje u oblasti vremenske slozenosti algoritama. In: ETRAN 2017, Kladovo, Serbia (2017), (in Serbian)"},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"Pe\u0161i\u0107, D., Mi\u0161i\u0107, M., Proti\u0107, J., Vujo\u0161evi\u0107 Jani\u010di\u0107, M.: Prototype implementation of segment assembling software. SJEE 15(1), 71-83 (2018)","DOI":"10.2298\/SJEE1801071P"},{"key":"ref42","unstructured":"Pe\u0161i\u0107, D., Mi\u0161i\u0107, M., Vujo\u0161evi\u0107 Jani\u010di\u0107, M., Proti\u0107, J.: Task generator project, https: \/\/github.com\/djpesic\/TaskGenerator"},{"key":"ref43","unstructured":"Pe\u0161i\u0107, D., Proti\u0107, J., Vujo\u0161evi\u0107 Jani\u010di\u0107, M., Mi\u0161i\u0107, M.: Ispitivanje kvaliteta softverski generisanih segmenata u oblasti vremenske slo\u017eenosti algoritama za automatizovano sastavljanje ispita. In: XXV Skup Trendovi razvoja: Kvalitet visokog obrazovanja, Kopaonik (2019), (in Serbian)"},{"key":"ref44","unstructured":"Pe\u0161i\u0107, D., Puri\u0107, S., Mi\u0161i\u0107, M., Proti\u0107, J.: Softversko generisanje pitanja i odgovora iz oblasti analize slo\u017eenosti algoritama za testove na kursevima programianja. In: XXII Skup Trendovi razvoja: Nove tehnologije u nastavi, Zlatibor (2016), (in Serbian)"},{"key":"ref45","unstructured":"Pe\u0161i\u0107, D., Puri\u0107, S., Mi\u0161i\u0107, M., Proti\u0107, J.: Softversko generisanje programskih segmenata baziranih na strategijama modeliranim pomo\u0107u xml-a. In: ETRAN 2016, Zlatibor, Serbia (2016), (in Serbian)"},{"key":"ref46","unstructured":"Prechelt, L., Malpohl, G., Philippsen, M., et al.: Finding plagiarisms among a set of programs with jplag. Journal of Universal Computer Science 8(11), 1016 (2002), http:\/\/dx.doi.org\/10.3217\/jucs-008-11-1016"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"Rudolph, J., Tan, S., Tan, S.: Chatgpt: Bullshit spewer or the end of traditional assessments in higher education? Journal of Applied Learning and Teaching 6(1) (2023)","DOI":"10.37074\/jalt.2023.6.1.9"},{"key":"ref48","doi-asserted-by":"crossref","unstructured":"Savic, M., Ivanovic, M., Lukovic, I., Deliba\u0161ic, B., Protic, J., Jankovic, D.: Students\u2019 preferences in selection of computer science and informatics studies-a comprehensive empirical case study. Computer Science and Information Systems 18(1), 251-283 (2021)","DOI":"10.2298\/CSIS200901054S"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"Schleimer, S., Wilkerson, D.S., Aiken, A.: Winnowing: local algorithms for document fingerprinting. In: Proceedings of the 2003 ACM SIGMOD international conference on Management of data. pp. 76-85 (2003), https:\/\/doi.org\/10.1145\/872757.872770","DOI":"10.1145\/872757.872770"},{"key":"ref50","unstructured":"Sedgewick, R., Flajolet, P.: An introduction to the analysis of algorithms. Pearson Education India (2013)"},{"key":"ref51","unstructured":"ShanghaiRanking: Computer science & engineering. Global Ranking of Academic Subjects (2022), [Online]. Available: http:\/\/www.shanghairanking.com\/rankings\/gras\/2022\/RS0210 (current July 2023)"},{"key":"ref52","doi-asserted-by":"crossref","unstructured":"Siddiq, M.L., Samee, A., Azgor, S.R., Haider, M.A., Sawraz, S.I., Santos, J.C.: Zero-shot prompting for code complexity prediction using github copilot. In: 2023 IEEE\/ACM 2nd InternationalWorkshop on Natural Language-Based Software Engineering (NLBSE). pp. 56-59. IEEE Computer Society (2023)","DOI":"10.1109\/NLBSE59153.2023.00018"},{"key":"ref53","doi-asserted-by":"crossref","unstructured":"Sikka, J., Satya, K., Kumar, Y., Uppal, S., Shah, R.R., Zimmermann, R.: Learning based methods for code runtime complexity prediction. In: Advances in Information Retrieval: 42nd European Conference on IR Research, ECIR 2020, Lisbon, Portugal, April 14-17, 2020, Proceedings, Part I 42. pp. 313-325. Springer (2020)","DOI":"10.1007\/978-3-030-45439-5_21"},{"key":"ref54","doi-asserted-by":"crossref","unstructured":"Strej\u010dek, J., Trtik, M.: Abstracting path conditions. In: Proceedings of the 2012 International Symposium on Software Testing and Analysis. pp. 155-165 (2012), https:\/\/doi.org\/10.1145\/2338965.2336772","DOI":"10.1145\/2338965.2336772"},{"key":"ref55","doi-asserted-by":"crossref","unstructured":"Surameery, N.M.S., Shakor, M.Y.: Use chat gpt to solve programming bugs. International Journal of Information Technology & Computer Engineering (IJITC) ISSN: 2455-5290 3(01), 17- 22 (2023)","DOI":"10.55529\/ijitc.31.17.22"},{"key":"ref56","doi-asserted-by":"crossref","unstructured":"Turing, A.M., et al.: On computable numbers, with an application to the entscheidungsproblem. J. of Math 58(345-363), 5 (1936)","DOI":"10.1093\/oso\/9780198250791.003.0005"},{"key":"ref57","doi-asserted-by":"crossref","unstructured":"Vujosevic-Janicic, M., Maric, F.: Regression verification for automated evaluation of students programs. Comput. Sci. Inf. Syst. 17(1), 205-227 (2020), https:\/\/doi.org\/10.2298\/CSIS181220019V","DOI":"10.2298\/CSIS181220019V"},{"key":"ref58","doi-asserted-by":"crossref","unstructured":"Vujo\u0161evi\u0107-Jani\u010di\u0107, M., Nikoli\u0107, M., To\u0161i\u0107, D., Kuncak, V.: Software verification and graph similarity for automated evaluation of students\u2019 assignments. Information and Software Technology 55(6), 1004-1016 (2013), https:\/\/doi.org\/10.1016\/j.infsof.2012.12.005","DOI":"10.1016\/j.infsof.2012.12.005"},{"key":"ref59","doi-asserted-by":"crossref","unstructured":"Yildirim, M.: A genetic algorithm for generating test from a question bank. Computer Applications in Engineering Education 18(2), 298-305 (2010), https:\/\/doi.org\/10.1002\/cae.20260","DOI":"10.1002\/cae.20260"},{"key":"ref60","doi-asserted-by":"crossref","unstructured":"Zheng, G., Zhang, X., Wang, R., Zhao, L., Wang, C., Wang, C.: Construction of innovative thinking training system for computer majors under the background of new engineering subject. Computer Science and Information Systems 19(3), 1499-1516 (2022)","DOI":"10.2298\/CSIS210608021Z"}],"container-title":["Computer Science and Information Systems"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,7,30]],"date-time":"2024-07-30T11:02:44Z","timestamp":1722337364000},"score":1,"resource":{"primary":{"URL":"https:\/\/doiserbia.nb.rs\/Article.aspx?ID=1820-02142400015P"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024]]}},"URL":"https:\/\/doi.org\/10.2298\/csis230730015p","relation":{},"ISSN":["1820-0214","2406-1018"],"issn-type":[{"value":"1820-0214","type":"print"},{"value":"2406-1018","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]}}}