Data Structure Practice: for Collegiate Programming Contests and Education, 1st Edition (Hardback) book cover

Data Structure Practice

for Collegiate Programming Contests and Education, 1st Edition

By Yonghui Wu, Jiande Wang

CRC Press

496 pages | 77 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781482215397
pub: 2016-02-04
SAVE ~$19.39
$96.95
$77.56
x
eBook (VitalSource) : 9780429090882
pub: 2016-02-22
from $48.48


FREE Standard Shipping!

Description

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.

Table of Contents

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

About the Authors

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.

Subject Categories

BISAC Subject Codes/Headings:
COM051010
COMPUTERS / Programming Languages / General
MAT000000
MATHEMATICS / General
MAT004000
MATHEMATICS / Arithmetic