Preview

Informatics and education

Advanced search

CREATING TEST EXAMPLES FOR AUTOMATIC CHECKING THE SOLUTIONS OF TASKS IN TRAINING COURSES AND COMPETITIONS IN PROGRAMMING

Abstract

We consider automated testing (without manual code inspection) for problems that require implementation of flow algorithms. If only graphs that were generated almost at random are used, it is impossible to estimate whether the implemented algorithm has right complexity or not. For almost all algorithms real running time on such test cases will grow significantly below theoretical bounds, while for advanced algorithms it might even grow quasilinear. In this work we consider how to build a test cases that will force popular implementation of Ford—Fulkerson algorithm match the expected complexity with running time depending exponentially from the size of the test.

About the Author

G. O. Evstropov
National Research University High School of Economics
Russian Federation
gevstropov@hse.ru


References

1. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. 2-е изд. / пер. с англ. М.: Вильямс, 2009.

2. Dean B. C., Goemans M. X., Immorlica N. Finite termination of “augmenting path” algorithms in the presence of irrational problem data // Algorithms - ESA 2006. Azar Y., Erlebach T. (eds). Lecture Notes in Computer Science. 2006. V. 4168. Berlin, Heidelberg: Springer, 2006.

3. Dinitz Ye. Algorithm for solution of a problem of maximum flow in a network with power estimation // Doklady Akademii nauk SSSR. 1970. № 11.

4. Edmonds J., Karp R. M. Theoretical improvements in algorithmic efficiency for network flow problems // Journal of the ACM. Association for Computing Machinery. 1972. № 19 (2). doi:10.1145/321694.321699.

5. Ford L. R., Fulkerson D. R. Maximal flow through a network // Canadian Journal of Mathematics. 1956. № 8. doi:10.4153/CJM-1956-045-5.

6. Orlin J. B. Max flows in O(nm) Time, or better // STOC ‘13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing (Palo Alto, California, USA - June 01-04, 2013). New York, USA: ACM, 2013.


Review

For citations:


Evstropov G.O. CREATING TEST EXAMPLES FOR AUTOMATIC CHECKING THE SOLUTIONS OF TASKS IN TRAINING COURSES AND COMPETITIONS IN PROGRAMMING. Informatics and education. 2017;(8):44-47. (In Russ.)

Views: 294


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 0234-0453 (Print)
ISSN 2658-7769 (Online)