Experiments for Data Structures, Algorithms and Strategies Solving Problems based on Programming Contests

From ICPC
Jump to: navigation, search

Experiments for Data Structures, Algorithms and Strategies Solving Problems based on Programming Contests


Yonghui Wu.jpg

Yonghui Wu

School of Computer Science, Fudan University, Shanghai, 200433, P.R.C
Department of Computer Science and Engineering,
National Sun Yat-sen University, Kaohsiung 80424, Taiwan, R.O.C.
yhwu@fudan.edu.cn

Abstract

From 1990s, ACM-ICPC has become a world-wide programming contest. Every year more than ten thousand students and more than one thousand universities participate in local contests, preliminary contests and regional contests all over the world. Programming contests’ problems from all over the world can also be gotten, analyzed and solved by us. These problems can be used not only for programming contests’ training, but also for education.

In my opinion, a programming contestant’s ability is based on his programming knowledge system and his strategies solving problems. Based on it, I’ve published experiment books for programming contest training and education using programming contests’ problems. A programming contestant’s knowledge system can be summarized as a famous formula: “Algorithms + Data Structures = Programs”. It is also the foundation for knowledge system of computer science and engineering. For data structure and algorithm, my books “Data structure Experiment: for Collegiate Programming Contest and Education” and “Algorithm Design Experiment: for Collegiate Programming Contest and Education” have been published, to improve experiments and to polish students’ programming skill better. Characters of the books are as follow. (1) The books’ outlines are based on the outlines of data structure and algorithm. Programming contest problems and their analyses and solutions are used as experiments. For each chapter, there is a section “Problems” to let students solve programming contests’ problems. Such a layout lets the books be used not only for education, but also for programming contests’ training. (2) Problems in my books are all selected from ACM-ICPC regional and world finals programming contests, universities’ local contests and on-line contests, and from 1990 to now. That is, the essence of programming contests’ problems is tried to select and show in the books. (3) Not only analyses and solutions to problems are showed, but also test data for problems are provided. It can make readers can polish their programming skill easily and better. The two books have been widely used in Mainland China, Taiwan, and other Chinese regions. And the English versions of the books are being written, and will be published by CRC Press.

Strategies solving problems are strategies for data modeling and algorithm design. When problems are not problems of standard modes, we need to consider what strategies we can make use of to solve such problems, for example, traditional algorithms are optimized or improved in order to solve problems; some advanced data structures, such as segment trees, splay trees and network flows, are used to model data; and so on. My book “Strategies Solving Problems: for Collegiate Programming Contest and Education” will be finished soon, and will be published this year. The book is based on many papers for analysis to programming contests’ problems.