Introduction of Advanced Algorithms in Software Engineering: A Computational Theory View
DOI:
https://doi.org/10.66395/globeis.5Keywords:
Algorithms, Software Engineering, Computational Complexity, Algorithm Design, Software OptimizationAbstract
The fast changing nature of software systems has led to the need to come up with advanced algorithmic methods that can be used to bridge the theoretical knowledge foundations of computations and their implementation in the context of engineering. In this paper, the intersection point of algorithms and software engineering practices and computational theory are thoroughly discussed and the impact of theoretical constructs on contemporary methods of software development are examined. This paper investigates some basic algorithm paradigms such as divide and conquer, dynamic programming and greedy algorithms and their use in modern software systems. We examine the complex-performance trade-offs of selecting an algorithm to use in large-scale software applications, both under time and space complexity factors. The paper also discusses the new trends in quantum computing algorithms, software optimization based on machine learning, and how computational theory can inform the next-generation software structures. This study contributes to an understanding of the best plans in integrating algorithms in a software engineering project through the systematic study of algorithm efficiency measures, software design patterns, and abstract theoretical computational models. The results indicate that a profound knowledge of the computational theory is highly beneficial to the quality of software, its scalability, and its sustainability. This research work adds to the existing literature bridging the gap between theory and practice in applying computer science to software engineering practice, provides advice to practitioners and researchers in choosing and applying algorithms that trade off between theoretical optimality and practical software engineering constraints.
Downloads
References
1. Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151-158. https://doi.org/10.1145/800157.805047 DOI: https://doi.org/10.1145/800157.805047
2. Knuth, D. E. (1976). The art of computer programming, Volume 1: Fundamental algorithms (2nd ed.). Addison-Wesley.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
4. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.
5. Bentley, J. L. (1980). Multidimensional divide-and-conquer. Communications of the ACM, 23(4), 214-229. https://doi.org/10.1145/358841.358850 DOI: https://doi.org/10.1145/358841.358850
6. Strassen, V. (1969). Gaussian elimination is not optimal. Numerische Mathematik, 13(4), 354-356. https://doi.org/10.1007/BF02165411 DOI: https://doi.org/10.1007/BF02165411
7. de Berg, M., van Kreveld, M., Overmars, M., & Schwarzkopf, O. (2008). Computational geometry: Algorithms and applications (3rd ed.). Springer-Verlag. DOI: https://doi.org/10.1007/978-3-540-77974-2
8. Bellman, R. (1957). Dynamic programming. Princeton University Press.
9. Dreyfus, S. E., & Law, A. M. (1977). The art and theory of dynamic programming. Academic Press.
10. Pressman, R. S., & Maxim, B. R. (2014). Software engineering: A practitioner's approach (8th ed.). McGraw-Hill Education.
11. Sommerville, I. (2015). Software engineering (10th ed.). Pearson.
12. Bass, L., Clements, P., & Kazman, R. (2012). Software architecture in practice (3rd ed.). Addison-Wesley Professional.
13. McConnell, S. (2004). Code complete (2nd ed.). Microsoft Press.
14. Martin, R. C. (2008). Clean code: A handbook of agile software craftsmanship. Prentice Hall.
15. Sipser, M. (2012). Introduction to the theory of computation (3rd ed.). Cengage Learning.
16. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman.
17. Karp, R. M. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, 85-103. https://doi.org/10.1007/978-1-4684-2001-2_9 DOI: https://doi.org/10.1007/978-1-4684-2001-2_9
18. Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Springer. DOI: https://doi.org/10.1007/978-1-4471-5559-1
19. Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146-160. https://doi.org/10.1137/0201010 DOI: https://doi.org/10.1137/0201010
20. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. https://doi.org/10.1007/BF01386390 DOI: https://doi.org/10.1007/BF01386390
21. Newman, M. E. (2010). Networks: An introduction. Oxford University Press.
22. Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509-512. https://doi.org/10.1126/science.286.5439.509 DOI: https://doi.org/10.1126/science.286.5439.509
23. Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep learning. MIT Press.
24. Bishop, C. M. (2006). Pattern recognition and machine learning. Springer.
25. Mitchell, T. M. (1997). Machine learning. McGraw-Hill.
26. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The elements of statistical learning: Data mining, inference, and prediction (2nd ed.). Springer. DOI: https://doi.org/10.1007/978-0-387-84858-7
27. Domingos, P. (2012). A few useful things to know about machine learning. Communications of the ACM, 55(10), 78-87. https://doi.org/10.1145/2347736.2347755 DOI: https://doi.org/10.1145/2347736.2347755
28. Gusfield, D. (1997). Algorithms on strings, trees, and sequences: Computer science and computational biology. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511574931
29. Crochemore, M., & Rytter, W. (2002). Jewels of stringology: Text algorithms. World Scientific. DOI: https://doi.org/10.1142/4838
30. Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762-772. https://doi.org/10.1145/359842.359859 DOI: https://doi.org/10.1145/359842.359859
31. Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: An aid to bibliographic search. Communications of the ACM, 18(6), 333-340. https://doi.org/10.1145/360825.360855 DOI: https://doi.org/10.1145/360825.360855
32. Muchnick, S. S. (1997). Advanced compiler design and implementation. Morgan Kaufmann.
33. Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, techniques, and tools (2nd ed.). Addison-Wesley.
34. Chaitin, G. J. (1982). Register allocation & spilling via graph coloring. ACM SIGPLAN Notices, 17(6), 98-105. https://doi.org/10.1145/872726.806984 DOI: https://doi.org/10.1145/872726.806984
35. Sanders, P., & Schultes, D. (2006). Engineering highway hierarchies. Journal of Experimental Algorithmics, 12, 1-40. https://doi.org/10.1145/1227161.1227162 DOI: https://doi.org/10.1145/1227161.1227162
36. Demetrescu, C., Goldberg, A. V., & Johnson, D. S. (2009). The shortest path problem: Ninth DIMACS implementation challenge. American Mathematical Society. DOI: https://doi.org/10.1090/dimacs/074
37. Weiss, M. A. (2011). Data structures and algorithm analysis in C++ (4th ed.). Pearson.
38. Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data structures and algorithms in Java (6th ed.). Wiley.
39. Brass, P. (2008). Advanced data structures. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511800191
40. Sleator, D. D., & Tarjan, R. E. (1985). Self-adjusting binary search trees. Journal of the ACM, 32(3), 652-686. https://doi.org/10.1145/3828.3835 DOI: https://doi.org/10.1145/3828.3835
41. Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596-615. https://doi.org/10.1145/28869.28874 DOI: https://doi.org/10.1145/28869.28874
42. Jájá, J. (1992). An introduction to parallel algorithms. Addison-Wesley.
43. Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Introduction to parallel computing (2nd ed.). Pearson.
44. Brent, R. P. (1974). The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21(2), 201-206. https://doi.org/10.1145/321812.321815 DOI: https://doi.org/10.1145/321812.321815
45. Herlihy, M., & Shavit, N. (2008). The art of multiprocessor programming. Morgan Kaufmann.
46. Michael, M. M., & Scott, M. L. (1996). Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 267-275. https://doi.org/10.1145/248052.248106 DOI: https://doi.org/10.1145/248052.248106
47. Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information (10th anniversary ed.). Cambridge University Press.
48. Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484-1509. https://doi.org/10.1137/S0097539795293172 DOI: https://doi.org/10.1137/S0097539795293172
49. Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 212-219. https://doi.org/10.1145/237814.237866 DOI: https://doi.org/10.1145/237814.237866
50. Vazirani, V. V. (2001). Approximation algorithms. Springer.
51. Hochbaum, D. S. (Ed.). (1996). Approximation algorithms for NP-hard problems. PWS Publishing Company.
52. Williamson, D. P., & Shmoys, D. B. (2011). The design of approximation algorithms. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511921735
53. Gendreau, M., & Potvin, J. Y. (Eds.). (2010). Handbook of metaheuristics (2nd ed.). Springer. DOI: https://doi.org/10.1007/978-1-4419-1665-5
54. Talbi, E. G. (2009). Metaheuristics: From design to implementation. Wiley. DOI: https://doi.org/10.1002/9780470496916
55. Motwani, R., & Raghavan, P. (1995). Randomized algorithms. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511814075
56. Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1), 128-138. https://doi.org/10.1016/0022-314X(80)90084-0 DOI: https://doi.org/10.1016/0022-314X(80)90084-0
57. Alon, N., & Spencer, J. H. (2008). The probabilistic method (3rd ed.). Wiley. DOI: https://doi.org/10.1002/9780470277331
58. Arora, S., & Barak, B. (2009). Computational complexity: A modern approach. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511804090
59. Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete mathematics: A foundation for computer science (2nd ed.). Addison-Wesley.
60. Brassard, G., & Bratley, P. (1996). Fundamentals of algorithmics. Prentice Hall.
61. Gamma, E., Helm, R., Johnson, R., & Vlissides, J. (1994). Design patterns: Elements of reusable object-oriented software. Addison-Wesley.
62. Fowler, M. (2002). Patterns of enterprise application architecture. Addison-Wesley.
63. Horowitz, E., & Sahni, S. (1978). Fundamentals of computer algorithms. Computer Science Press.
64. Preparata, F. P., & Shamos, M. I. (1985). Computational geometry: An introduction. Springer-Verlag. DOI: https://doi.org/10.1007/978-1-4612-1098-6
65. Von Neumann, J. (1945). First draft of a report on the EDVAC. IEEE Annals of the History of Computing, 15(4), 27-75. https://doi.org/10.1109/85.238389 DOI: https://doi.org/10.1109/85.238389
66. Bitton, D., DeWitt, D. J., Hsiao, D. K., & Menon, J. (1984). A taxonomy of parallel sorting. ACM Computing Surveys, 16(3), 287-318. https://doi.org/10.1145/2514.2516 DOI: https://doi.org/10.1145/2514.2516
67. Hoare, C. A. R. (1962). Quicksort. The Computer Journal, 5(1), 10-16. https://doi.org/10.1093/comjnl/5.1.10 DOI: https://doi.org/10.1093/comjnl/5.1.10
68. Sedgewick, R. (1978). Implementing quicksort programs. Communications of the ACM, 21(10), 847-857. https://doi.org/10.1145/359619.359631 DOI: https://doi.org/10.1145/359619.359631
69. LaMarca, A., & Ladner, R. E. (1999). The influence of caches on the performance of sorting. Journal of Algorithms, 31(1), 66-104. https://doi.org/10.1006/jagm.1998.0985 DOI: https://doi.org/10.1006/jagm.1998.0985
70. Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementations. Wiley.
71. Sniedovich, M. (2010). Dynamic programming: Foundations and principles (2nd ed.). CRC Press. DOI: https://doi.org/10.1201/EBK0824740993
72. Needleman, S. B., & Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443-453. https://doi.org/10.1016/0022-2836(70)90057-4 DOI: https://doi.org/10.1016/0022-2836(70)90057-4
73. Smith, T. F., & Waterman, M. S. (1981). Identification of common molecular subsequences. Journal of Molecular Biology, 147(1), 195-197. https://doi.org/10.1016/0022-2836(81)90087-5 DOI: https://doi.org/10.1016/0022-2836(81)90087-5
74. Skiena, S. S. (2008). The algorithm design manual (2nd ed.). Springer. DOI: https://doi.org/10.1007/978-1-84800-070-4
75. Bacon, D. F., Graham, S. L., & Sharp, O. J. (1994). Compiler transformations for high-performance computing. ACM Computing Surveys, 26(4), 345-420. https://doi.org/10.1145/197405.197406 DOI: https://doi.org/10.1145/197405.197406
76. Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial optimization: Algorithms and complexity. Dover Publications.
77. Korte, B., & Vygen, J. (2011). Combinatorial optimization: Theory and algorithms (5th ed.). Springer. DOI: https://doi.org/10.1007/978-3-642-24488-9
78. Huffman, D. A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9), 1098-1101. https://doi.org/10.1109/JRPROC.1952.273898 DOI: https://doi.org/10.1109/JRPROC.1952.273898
79. Salomon, D. (2007). Data compression: The complete reference (4th ed.). Springer.
80. Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48-50. https://doi.org/10.2307/2033241 DOI: https://doi.org/10.1090/S0002-9939-1956-0078686-7
81. Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389-1401. https://doi.org/10.1002/j.1538-7305.1957.tb01515.x DOI: https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
82. West, D. B. (2001). Introduction to graph theory (2nd ed.). Prentice Hall.
83. Bondy, J. A., & Murty, U. S. R. (2008). Graph theory. Springer. DOI: https://doi.org/10.1007/978-1-84628-970-5
84. Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90. https://doi.org/10.1090/qam/102435 DOI: https://doi.org/10.1090/qam/102435
85. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136 DOI: https://doi.org/10.1109/TSSC.1968.300136
86. Moore, E. F. (1959). The shortest path through a maze. Proceedings of the International Symposium on the Theory of Switching, 285-292.
87. Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The design and analysis of computer algorithms. Addison-Wesley.
88. Ford, L. R., & Fulkerson, D. R. (1962). Flows in networks. Princeton University Press. DOI: https://doi.org/10.1515/9781400875184
89. Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Prentice Hall.
90. Navarro, G., & Raffinot, M. (2002). Flexible pattern matching in strings: Practical on-line search algorithms for texts and biological sequences. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9781316135228
91. Charras, C., & Lecroq, T. (2004). Handbook of exact string matching algorithms. King's College London Publications.
92. Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323-350. https://doi.org/10.1137/0206024 DOI: https://doi.org/10.1137/0206024
93. Sunday, D. M. (1990). A very fast substring search algorithm. Communications of the ACM, 33(8), 132-142. https://doi.org/10.1145/79173.79184 DOI: https://doi.org/10.1145/79173.79184
94. Weiner, P. (1973). Linear pattern matching algorithms. 14th Annual Symposium on Switching and Automata Theory, 1-11. https://doi.org/10.1109/SWAT.1973.13 DOI: https://doi.org/10.1109/SWAT.1973.13
95. Manber, U., & Myers, G. (1993). Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing, 22(5), 935-948. https://doi.org/10.1137/0222058 DOI: https://doi.org/10.1137/0222058
96. Knuth, D. E. (1998). The art of computer programming, Volume 3: Sorting and searching (2nd ed.). Addison-Wesley.
97. Gonnet, G. H., & Baeza-Yates, R. (1991). Handbook of algorithms and data structures: In Pascal and C (2nd ed.). Addison-Wesley.
98. Estivill-Castro, V., & Wood, D. (1992). A survey of adaptive sorting algorithms. ACM Computing Surveys, 24(4), 441-476. https://doi.org/10.1145/146370.146381 DOI: https://doi.org/10.1145/146370.146381
99. Zwick, U. (2002). All pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of the ACM, 49(3), 289-317. https://doi.org/10.1145/567112.567114 DOI: https://doi.org/10.1145/567112.567114
100. Johnson, D. B. (1977). Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1), 1-13. https://doi.org/10.1145/321992.321993 DOI: https://doi.org/10.1145/321992.321993
101. Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345. https://doi.org/10.1145/367766.368168 DOI: https://doi.org/10.1145/367766.368168
102. Mehlhorn, K., & Sanders, P. (2008). Algorithms and data structures: The basic toolbox. Springer.
103. Drozdek, A. (2012). Data structures and algorithms in C++ (4th ed.). Cengage Learning.
104. Shaffer, C. A. (2011). Data structures and algorithm analysis (3rd ed.). Dover Publications.
105. Kleinberg, J., & Tardos, É. (2005). Algorithm design. Pearson.
106. Levitin, A. (2011). Introduction to the design and analysis of algorithms (3rd ed.). Pearson.
107. Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79. https://doi.org/10.22331/q-2018-08-06-79 DOI: https://doi.org/10.22331/q-2018-08-06-79
108. Montanaro, A. (2016). Quantum algorithms: An overview. npj Quantum Information, 2, 15023. https://doi.org/10.1038/npjqi.2015.23 DOI: https://doi.org/10.1038/npjqi.2015.23
109. Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science, 124-134. https://doi.org/10.1109/SFCS.1994.365700 DOI: https://doi.org/10.1109/SFCS.1994.365700
110. Bernstein, D. J., & Lange, T. (2017). Post-quantum cryptography. Nature, 549(7671), 188-194. https://doi.org/10.1038/nature23461 DOI: https://doi.org/10.1038/nature23461
111. Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79(2), 325-328. https://doi.org/10.1103/PhysRevLett.79.325 DOI: https://doi.org/10.1103/PhysRevLett.79.325
112. Boyer, M., Brassard, G., Høyer, P., & Tapp, A. (1998). Tight bounds on quantum searching. Fortschritte der Physik, 46(4-5), 493-505. https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P DOI: https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
113. LaRose, R. (2019). Overview and comparison of gate level quantum software platforms. Quantum, 3, 130. https://doi.org/10.22331/q-2019-03-25-130 DOI: https://doi.org/10.22331/q-2019-03-25-130
114. Fingerhuth, M., Babej, T., & Wittek, P. (2018). Open source software in quantum computing. PLOS ONE, 13(12), e0208561. https://doi.org/10.1371/journal.pone.0208561 DOI: https://doi.org/10.1371/journal.pone.0208561
115. Sculley, D., Holt, G., Golovin, D., Davydov, E., Phillips, T., Ebner, D., Chaudhary, V., Young, M., Crespo, J. F., & Dennison, D. (2015). Hidden technical debt in machine learning systems. Advances in Neural Information Processing Systems, 28, 2503-2511.
116. Amershi, S., Begel, A., Bird, C., DeLine, R., Gall, H., Kamar, E., Nagappan, N., Nushi, B., & Zimmermann, T. (2019). Software engineering for machine learning: A case study. 2019 IEEE/ACM 41st International Conference on Software Engineering: Software Engineering in Practice, 291-300. https://doi.org/10.1109/ICSE-SEIP.2019.00042 DOI: https://doi.org/10.1109/ICSE-SEIP.2019.00042
117. LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. Nature, 521(7553), 436-444. https://doi.org/10.1038/nature14539 DOI: https://doi.org/10.1038/nature14539
118. Han, S., Mao, H., & Dally, W. J. (2016). Deep compression: Compressing deep neural networks with pruning, trained quantization and Huffman coding. International Conference on Learning Representations. https://doi.org/10.48550/arXiv.1510.00149
119. Gholami, A., Kim, S., Dong, Z., Yao, Z., Mahoney, M. W., & Keutzer, K. (2022). A survey of quantization methods for efficient neural network inference. Low-Power Computer Vision, 291-326. https://doi.org/10.1201/9781003162810-13 DOI: https://doi.org/10.1201/9781003162810-13
120. Hoi, S. C., Sahoo, D., Lu, J., & Zhao, P. (2021). Online learning: A comprehensive survey. Neurocomputing, 459, 249-289. https://doi.org/10.1016/j.neucom.2021.04.112 DOI: https://doi.org/10.1016/j.neucom.2021.04.112
121. Losing, V., Hammer, B., & Wersing, H. (2018). Incremental on-line learning: A review and comparison of state of the art algorithms. Neurocomputing, 275, 1261-1274. https://doi.org/10.1016/j.neucom.2017.06.084 DOI: https://doi.org/10.1016/j.neucom.2017.06.084
122. Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction (2nd ed.). MIT Press.
123. Arulkumaran, K., Deisenroth, M. P., Brundage, M., & Bharath, A. A. (2017). Deep reinforcement learning: A brief survey. IEEE Signal Processing Magazine, 34(6), 26-38. https://doi.org/10.1109/MSP.2017.2743240 DOI: https://doi.org/10.1109/MSP.2017.2743240
124. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., & Protasi, M. (1999). Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer. DOI: https://doi.org/10.1007/978-3-642-58412-1
125. Shmoys, D. B. (1995). Computing near-optimal solutions to combinatorial optimization problems. Combinatorial Optimization, 20, 355-397. https://doi.org/10.1090/dimacs/020/14 DOI: https://doi.org/10.1090/dimacs/020/07
126. Dinur, I., & Safra, S. (2005). On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1), 439-485. https://doi.org/10.4007/annals.2005.162.439 DOI: https://doi.org/10.4007/annals.2005.162.439
127. Clarkson, K. L. (1983). A modification of the greedy algorithm for vertex cover. Information Processing Letters, 16(1), 23-25. https://doi.org/10.1016/0020-0190(83)90005-9 DOI: https://doi.org/10.1016/0020-0190(83)90007-8
128. Bar-Yehuda, R., & Even, S. (1981). A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2(2), 198-203. https://doi.org/10.1016/0196-6774(81)90020-1 DOI: https://doi.org/10.1016/0196-6774(81)90020-1
129. Bertsimas, D., & Weismantel, R. (2005). Optimization over integers. Dynamic Ideas.
130. Raghavan, P., & Thompson, C. D. (1987). Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4), 365-374. https://doi.org/10.1007/BF02579324 DOI: https://doi.org/10.1007/BF02579324
131. Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1985). The traveling salesman problem: A guided tour of combinatorial optimization. Wiley. DOI: https://doi.org/10.2307/2582681
132. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Graduate School of Industrial Administration, Carnegie Mellon University, Technical Report 388.
133. Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Springer.
134. Cygan, M., Fomin, F. V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized algorithms. Springer. DOI: https://doi.org/10.1007/978-3-319-21275-3
135. Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford University Press. DOI: https://doi.org/10.1093/acprof:oso/9780198566076.001.0001
136. Fellows, M. R., & Langston, M. A. (1989). An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. 30th Annual Symposium on Foundations of Computer Science, 520-525. https://doi.org/10.1109/SFCS.1989.63528 DOI: https://doi.org/10.1109/SFCS.1989.63528
137. Abu-Khzam, F. N., Fellows, M. R., Langston, M. A., & Suters, W. H. (2007). Crown structures for vertex cover kernelization. Theory of Computing Systems, 41(3), 411-430. https://doi.org/10.1007/s00224-007-1328-0 DOI: https://doi.org/10.1007/s00224-007-1328-0
138. Bodlaender, H. L. (1996). A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6), 1305-1317. https://doi.org/10.1137/S0097539793251219 DOI: https://doi.org/10.1137/S0097539793251219
139. Muthukrishnan, S. (2005). Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 1(2), 117-236. https://doi.org/10.1561/0400000002 DOI: https://doi.org/10.1561/0400000002
140. Cormode, G., & Hadjieleftheriou, M. (2008). Finding frequent items in data streams. Proceedings of the VLDB Endowment, 1(2), 1530-1541. https://doi.org/10.14778/1454159.1454225 DOI: https://doi.org/10.14778/1454159.1454225
141. Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: The count-min sketch and its applications. Journal of Algorithms, 55(1), 58-75. https://doi.org/10.1016/j.jalgor.2003.12.001 DOI: https://doi.org/10.1016/j.jalgor.2003.12.001
142. Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm. AOFA'07: Proceedings of the 2007 International Conference on Analysis of Algorithms, 137-156. DOI: https://doi.org/10.46298/dmtcs.3545
143. Babcock, B., Babu, S., Datar, M., Motwani, R., & Widom, J. (2002). Models and issues in data stream systems. Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 1-16. https://doi.org/10.1145/543613.543615 DOI: https://doi.org/10.1145/543613.543615
144. Aggarwal, C. C. (Ed.). (2007). Data streams: Models and algorithms. Springer. DOI: https://doi.org/10.1007/978-0-387-47534-9
145. Shaw, M., & Garlan, D. (1996). Software architecture: Perspectives on an emerging discipline. Prentice Hall.
146. Clements, P., Bachmann, F., Bass, L., Garlan, D., Ivers, J., Little, R., Merson, P., Nord, R., & Stafford, J. (2010). Documenting software architectures: Views and beyond (2nd ed.). Addison-Wesley.
147. Kazman, R., Klein, M., & Clements, P. (2000). ATAM: Method for architecture evaluation. Technical Report CMU/SEI-2000-TR-004, Software Engineering Institute, Carnegie Mellon University. DOI: https://doi.org/10.21236/ADA382629
148. Smith, C. U., & Williams, L. G. (2002). Performance solutions: A practical guide to creating responsive, scalable software. Addison-Wesley.
149. Buschmann, F., Meunier, R., Rohnert, H., Sommerlad, P., & Stal, M. (1996). Pattern-oriented software architecture, Volume 1: A system of patterns. Wiley.
150. Freeman, E., Robson, E., Bates, B., & Sierra, K. (2004). Head first design patterns. O'Reilly Media.
151. Bentley, J. L. (1982). Writing efficient programs. Prentice-Hall Software Series. Prentice Hall.
152. Leiserson, C. E., Rivest, R. L., Stein, C., & Cormen, T. H. (2001). Introduction to algorithms. MIT Press and McGraw-Hill, 2, 3-10.
153. Graham, S. L., Kessler, P. B., & McKusick, M. K. (1982). Gprof: A call graph execution profiler. ACM SIGPLAN Notices, 17(6), 120-126. https://doi.org/10.1145/872726.806987 DOI: https://doi.org/10.1145/872726.806987
154. Fog, A. (2004). Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms. Technical University of Denmark.
155. Frigo, M., Leiserson, C. E., Prokop, H., & Ramachandran, S. (1999). Cache-oblivious algorithms. 40th Annual Symposium on Foundations of Computer Science, 285-297. https://doi.org/10.1109/SFFCS.1999.814600 DOI: https://doi.org/10.1109/SFFCS.1999.814600
156. Hennessy, J. L., & Patterson, D. A. (2011). Computer architecture: A quantitative approach (5th ed.). Morgan Kaufmann.
157. Bondi, A. B. (2000). Characteristics of scalability and their impact on performance. Proceedings of the 2nd International Workshop on Software and Performance, 195-203. https://doi.org/10.1145/350391.350432 DOI: https://doi.org/10.1145/350391.350432
158. Hill, M. D. (1990). What is scalability? ACM SIGARCH Computer Architecture News, 18(4), 18-21. https://doi.org/10.1145/121973.121975 DOI: https://doi.org/10.1145/121973.121975
159. Lynch, N. A. (1996). Distributed algorithms. Morgan Kaufmann.
160. Tel, G. (2000). Introduction to distributed algorithms (2nd ed.). Cambridge University Press. DOI: https://doi.org/10.1017/CBO9781139168724
161. Myers, G. J., Sandler, C., & Badgett, T. (2011). The art of software testing (3rd ed.). Wiley. DOI: https://doi.org/10.1002/9781119202486
162. Beizer, B. (1990). Software testing techniques (2nd ed.). Van Nostrand Reinhold.
163. Hoare, C. A. R. (1969). An axiomatic basis for computer programming. Communications of the ACM, 12(10), 576-580. https://doi.org/10.1145/363235.363259 DOI: https://doi.org/10.1145/363235.363259
164. Clarke, E. M., Grumberg, O., & Peled, D. A. (1999). Model checking. MIT Press.
165. Jain, R. (1991). The art of computer systems performance analysis: Techniques for experimental design, measurement, simulation, and modeling. Wiley.
166. Weyuker, E. J., & Vokolos, F. I. (2000). Experience with performance testing of software systems: Issues, an approach, and case study. IEEE Transactions on Software Engineering, 26(12), 1147-1156. https://doi.org/10.1109/32.888628 DOI: https://doi.org/10.1109/32.888628
167. McGeoch, C. C. (2012). A guide to experimental algorithmics. Cambridge University Press. DOI: https://doi.org/10.1017/CBO9780511843747
168. Demetrescu, C., Finocchi, I., & Italiano, G. F. (2008). Algorithm engineering. Bulletin of the European Association for Theoretical Computer Science, 94, 48-72.
169. Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3-5), 75-174. https://doi.org/10.1016/j.physrep.2009.11.002 DOI: https://doi.org/10.1016/j.physrep.2009.11.002
170. Batagelj, V., & Mrvar, A. (1998). Pajek—Program for large network analysis. Connections, 21(2), 47-57.
171. Sculley, D., Holt, G., Golovin, D., Davydov, E., Phillips, T., Ebner, D., Chaudhary, V., Young, M., Crespo, J. F., & Dennison, D. (2015). Hidden technical debt in machine learning systems. Advances in Neural Information Processing Systems, 28, 2503-2511.
172. Breck, E., Cai, S., Nielsen, E., Salib, M., & Sculley, D. (2017). The ML test score: A rubric for ML production readiness and technical debt reduction. 2017 IEEE International Conference on Big Data, 1123-1132. https://doi.org/10.1109/BigData.2017.8258038 DOI: https://doi.org/10.1109/BigData.2017.8258038
173. Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G., Buell, D. A., et al. (2019). Quantum supremacy using a programmable superconducting processor. Nature, 574(7779), 505-510. https://doi.org/10.1038/s41586-019-1666-5 DOI: https://doi.org/10.1038/s41586-019-1666-5
174. Steiger, D. S., Häner, T., & Troyer, M. (2018). ProjectQ: An open source software framework for quantum computing. Quantum, 2, 49. https://doi.org/10.22331/q-2018-01-31-49 DOI: https://doi.org/10.22331/q-2018-01-31-49
175. Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., & Coles, P. J. (2021). Variational quantum algorithms. Nature Reviews Physics, 3(9), 625-644. https://doi.org/10.1038/s42254-021-00348-9 DOI: https://doi.org/10.1038/s42254-021-00348-9
176. Hochbaum, D. S. (1997). Approximation algorithms for NP-hard problems. PWS Publishing Company. DOI: https://doi.org/10.1145/261342.571216
177. Khot, S., Kindler, G., Mossel, E., & O'Donnell, R. (2007). Optimal inapproximability results for MAX‐CUT and other 2‐variable CSPs? SIAM Journal on Computing, 37(1), 319-357. https://doi.org/10.1137/S0097539705447372 DOI: https://doi.org/10.1137/S0097539705447372
178. Marx, D. (2010). Parameterized complexity and approximation algorithms. The Computer Journal, 51(1), 60-78. https://doi.org/10.1093/comjnl/bxm048 DOI: https://doi.org/10.1093/comjnl/bxm048
179. Lokshtanov, D., Marx, D., & Saurabh, S. (2018). Known algorithms on graphs of bounded treewidth are probably optimal. ACM Transactions on Algorithms, 14(2), 1-30. https://doi.org/10.1145/3170442 DOI: https://doi.org/10.1145/3170442
180. Gibbons, P. B., & Matias, Y. (1998). New sampling-based summary statistics for improving approximate query answers. ACM SIGMOD Record, 27(2), 331-342. https://doi.org/10.1145/276305.276334 DOI: https://doi.org/10.1145/276305.276334
181. Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2001). Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. VLDB'01: Proceedings of the 27th International Conference on Very Large Data Bases, 79-88.
182. Taylor, R. N., Medvidovic, N., & Dashofy, E. M. (2009). Software architecture: Foundations, theory, and practice. Wiley.
183. Buschmann, F., Henney, K., & Schmidt, D. C. (2007). Pattern-oriented software architecture, Volume 4: A pattern language for distributed computing. Wiley.
184. Hofmeister, C., Nord, R., & Soni, D. (2000). Applied software architecture. Addison-Wesley.
185. Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimensionality. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, 604-613. https://doi.org/10.1145/276698.276876 DOI: https://doi.org/10.1145/276698.276876
186. Blelloch, G. E., Fineman, J. T., Gibbons, P. B., & Shun, J. (2012). Internally deterministic parallel algorithms can be fast. ACM SIGPLAN Notices, 47(8), 181-192. https://doi.org/10.1145/2370036.2145840 DOI: https://doi.org/10.1145/2370036.2145840
187. Caruana, R., Lou, Y., Gehrke, J., Koch, P., Sturm, M., & Elhadad, N. (2015). Intelligible models for healthcare: Predicting pneumonia risk and hospital 30-day readmission. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1721-1730. https://doi.org/10.1145/2783258.2788613 DOI: https://doi.org/10.1145/2783258.2788613
188. Robins, A., Rountree, J., & Rountree, N. (2003). Learning and teaching programming: A review and discussion. Computer Science Education, 13(2), 137-172. https://doi.org/10.1076/csed.13.2.137.14200 DOI: https://doi.org/10.1076/csed.13.2.137.14200
189. Hazzan, O., Lapidot, T., & Nishizaki, Y. (2011). Guide to teaching computer science: An activity-based approach. Springer. DOI: https://doi.org/10.1007/978-0-85729-443-2
190. Roughgarden, T. (2010). Computing and teaching the traveling salesman problem. Notices of the AMS, 57(6), 691-699.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 GlobeIS International Journal of Global Information Systems
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
