Wu / Wang Data Structure Practice

for Collegiate Programming Contests and Education
Erscheinungsjahr 2016
ISBN: 978-1-4822-1540-3
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 512 Seiten

Combining knowledge with strategies, Data Structure Practice for Collegiate Programming Contests and Education presents the first comprehensive book on data structure in programming contests. This book is designed for training collegiate programming contest teams in the nuances of data structure and for helping college students in computer-related majors to gain deeper understanding of data structure.

Based on successful experiences in many world-level contests, the book includes 204 typical problems and detailed analyses selected from the ACM International Collegiate Programming Contest and other major programming contests since 1990. It is divided into four sections that focus on:

- Fundamental programming skills

- Experiments for linear lists

- Experiments for trees

- Experiments for graphs

Each chapter contains a set of problems and includes hints. The book also provides test data for most problems as well as sources and IDs for online judgments that help with improving programming skills.

Introducing a multi-options model and considerations of context, Data Structure Practice for Collegiate Programming Contests and Education encourages students to think creatively in solving programming problems. By taking readers through practical contest problems from analysis to implementation, it provides a complete source for enhancing understanding and polishing skills in programming.

Autoren/Hrsg.

Wu, Yonghui

Wang, Jiande

Fachgebiete

• Mathematik | Informatik Mathematik Algebra Zahlentheorie
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Programmier- und Skriptsprachen

Inhaltsverzeichnis

FUNDAMENTAL PROGRAMMING SKILLS

Practice for Simple Computing
Improving Programming Style
Multiple Test Cases
Precision of Real Numbers
Improving Time Complexity by Dichotomy
Problems

Simple Simulation
Simulation of Direct Statement
Simulation by Sieve Method
Construction Simulation
Problems

Simple Recursion
Calculation of Recursive Functions
Solving Problems by Recursive Algorithms
Solving Recursive Datum
Problems
Summary of Section I

EXPERIMENTS FOR LINEAR LISTS

Linear Lists Accessed Directly
Application of Arrays 1: Calculation of Dates
Application of Arrays 2: Calculation of High-Precision Numbers
Application of Arrays 3: Representation and Computation of Polynomials
Application of Arrays 4: Calculation of Numerical Matrices
Character Strings 1: Storage Structure of Character Strings
Character Strings 2: Pattern Matching of Character Strings
Problems

Applications of Linear Lists for Sequential Access
Application of Sequence Lists
Application of Stacks
Application of Queues
Problems

Generalized List Using Indexes
Solving Problems Using Dictionaries
Solving Problems Using a Hash Table and the Hash Method
Problems

Sort of Linear Lists
Using Sort Function in STL
Using Sort Algorithms
Problems
Summary of Section II

EXPERIMENTS FOR TREES

Programming by Tree Structure
Solving Hierarchical Problems by Tree Traversal
Union–Find Sets Supported by Tree Structure
Calculation of Sum of Weights of Subtrees by Binary Indexed Trees
Problems

Applications of Binary Trees
Converting Ordered Trees to Binary Trees
Paths of Binary Trees
Traversal of Binary Trees
Problems

Applications of Classical Trees
Binary Search Trees
Binary Heaps
Huffman Trees
Problems
Summary of Section III

EXPERIMENTS FOR GRAPHS

Applications of Graph Traversal
BFS Algorithm
DFS Algorithm
Topological Sort
Connectivity of Undirected Graphs
Problems

Algorithms of Minimum Spanning Trees
Kruskal Algorithm
Prim Algorithm
Problems

Algorithms of Best Paths
Warshall Algorithm and Floyd–Warshall Algorithm
Dijkstra’s Algorithm
Bellman–Ford Algorithm
Shortest Path Faster Algorithm
Problems

Algorithms of Bipartite Graphs and Flow Networks
Maximum Matching in Bipartite Graphs
Flow Networks
Problems
Summary of Section IV

Über Autor(innen)

Yonghui Wu was the coach of Fudan University programming contest teams from 2001 to 2011. Under his guidance, Fudan University qualified for the Association for Computing Machinery International Collegiate Programming Contest (ACM-ICPC) World Finals every year, winning three medals during that span: the bronze medal in 2002, silver medal in 2005, and bronze medal in 2010. Since 2012, he has published a series of books for programming contests and education. He is now the chair of the ICPC Asia Programming Contest 1st Training Committee.

Jian-De Wang is a famous coach for the Olympiad in Informatics in China. Under his guidance, his students have won seven gold medals, three silver medals, and two bronze medals for China in the International Olympiad in Informatics. He has published 24 books for programming contests.