For our first excursion into the area of sorting algorithms, we shall study several elementary methods that are appropriate for small files, or for files that have a special structure. 继续阅读“Sorting～Elementary Sorting Methods I”
Recursion and Trees～Graph Traversal
For our final example of a recursive program in this series, we consider one of the most important of all recursive programs: recursive graph traversal, or depth-first search. This method for systematically visiting all the nodes in a graph is a direct generalization of the tree-traversal methods that we considered in Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal, and it serves as the basis for many basic algorithms for processing graph. 继续阅读“Recursion and Trees～Graph Traversal”
Database Design ~ Database Design and the E-R Model V
A diagrammatic representation of the data model of an application is a very important part of designing a database schema. Creation of a database schema requires not only data modeling experts, but also domain experts who know the requirements of the application but may not be familiar with data modeling. An intuitive diagrammatic representation is particularly important since it eases communication of information between these groups of experts. 继续阅读“Database Design ~ Database Design and the E-R Model V”
Database Design ~ Database Design and the E-R Model IV
Although the basic E-R concepts can model most database features, some aspects of a database may be more aptly expressed by certain extensions to the basic E-R model. In this section, we discuss the extended E-R features of specialization, generalization, higher-and lower-level entity sets, attribute inheritance, and aggregation.
To help with the discussions, we shall use a slightly more elaborate database schema for the university. In particular, we shall model the various people within a university by defining an entity set person, with attributes ID, name, and address. 继续阅读“Database Design ~ Database Design and the E-R Model IV”
Database Design ~ Database Design and the E-R Model III
We can represent a database that conforms to an E-R database schema by a collection of relation schemas. For each entity set and for each relationship set in the database design, there is a unique relation schema to which we assign the name of the corresponding entity set or relationship set. 继续阅读“Database Design ~ Database Design and the E-R Model III”
Recursion and Trees～ Recursive Binary-Tree Algorithms
The tree-traversal algorithms that we considered in Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal exemplify the basic fact that we are led to consider recursive algorithms for binary trees, because of these trees’ very nature as recursive structures. Many tasks admit direct recursive divide-and-conquer algorithms, which essentially generalize the traversal algorithms. We process a tree by processing the root node and (recursively) its subtrees; we can do computation before, between, or after the recursive calls (or possibly all three). 继续阅读“Recursion and Trees～ Recursive Binary-Tree Algorithms”
Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal
Before beginning to consider tree-processing algorithms, we continue in a mathematical vein by considering a number of basic properties of trees. We focus on binary trees, because we use them frequently throughout this series. 继续阅读“Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal”
Recursion and Trees～ Trees
Trees are a mathematical abstraction that play a central role in the design and analysis of algorithms because
- We use trees to describe dynamic properties of algorithms.
- We build and use explicit data structures that are concrete realizations of trees.
We have already seen examples of both of these uses. We designed algorithms for the connectivity problem that are based on tree structure in 算法：C语言实现～连通性问题, and we described that call structure of recursive algorithms with tree structures in Recursion and Trees～ Divide and Conquer and Recursion and Trees～ Dynamic Programming. 继续阅读“Recursion and Trees～ Trees”
Recursion and Trees～ Dynamic Programming
An essential characteristic of the divide-and-conquer algorithms that we considered in Recursion and Trees～ Divide and Conquer is that they partition the problem into independent subproblems. When the subproblems are not independent, the situation is more complicated, primarily because direct recursive implementation of even the simplest algorithms of this type can require unthinkable amounts of time. In this article, we consider a systematic technique for avoiding this pitfall for an important class of problems. 继续阅读“Recursion and Trees～ Dynamic Programming”