The idea of a hierarchical design and integration of programming projects in the computer science undergraduate curriculum is proposed and discussed. Research results in software reuse and object-oriented design and development may be used in the design and the development of the set of integrated programming projects. By a hierarchical design and integration of programming projects, this approach aims to increase the effectiveness of the undergraduate learning experience. Using the approach, programming projects in computer science courses may be developed in such a way that programming projects in the lower level courses are used as components (parts) to implement programming projects in the higher level courses. In this way, a hierarchical structure of programming projects can be built and a student's programming projects in different courses can be integrated. Such an integration may lead to the development of complex software systems in the senior year.

The segmented channel routing problem arises in the wiring and the physical design automation for Field Programmable Gate Arrays (FPGA's), a new type of electrically programmable VLSI. It may also be applicable to configurable multiprocessors. This new routing problem poses interesting algorithmic problems. In a previous paper by V. P. Roychowdhury et al. (see ibid., vol.12, no. 1, p. 79-95, 1993), the study of the complexity of segmented channel routing was reported. In this paper, we point out that the strong NP-completeness proof of segmented channel routing in that previous paper is incomplete and incorrect. We provide a correct proof which shows that the problem is indeed NP-complete in the strong sense and, therefore, that an exact polynomial time algorithm for the general case of the problem does not exist unless P=NP. Since our construction also holds for the case where connection lengths are bounded by a constant, we then settle an open question raised by Roychowdhury et al.>

The discrete gate sizing problem has been studied by several researchers recently. Some complexity results have been obtained, and a number of heuristic algorithms have been proposed. For circuit networks that are restricted to the set of trees, or series-parallel graphs, pseudo-polynomial time algorithms to obtain the exact solution have also been proposed, through none can be extended to arbitrary DAGs (directed acyclic graphs). We prove that the problem is strongly NP-hard. Our results implies that for arbitrary DAGs there is no pseudo-polynomial time algorithm to obtain the exact solution unless P=NP. Our result also provides insight into the difficulties of the problem, and may lead to better heuristics.>

The authors consider the problem of selecting an implementation of each circuit module from a cell library so as to satisfy overall delay and area (or delay and power) requirements. Two versions of the circuit implementation problem, the basic circuit implementation problem and the general circuit implementation problem, are shown to be NP-hard. A pseudo-polynomial-time algorithm for the basic circuits is developed, and heuristics for the basic circuit implementation problem on general circuits are formulated and experimented with.>

The polynomial time algorithm obtained earlier by the authors is extended to find a minimal cardinality path set that long covers each lead or gate input of a digital logic circuit. It is shown how to find, in polynomial time, a minimal cardinality set MinMaxSP for a given combinational logic circuit. Combinational circuit verification is used to verify the sequential circuit delays.>

A polynomial-time algorithm for the pull up transistor assignment problem is developed, and it is shown that the interval selection and interval selection with pull up transistor assignment problems are NP-hard. Heuristics for these problems are proposed and compared with that proposed by C. Lursinsap and G. Gajski (ibid., vol.7, no.8, p.887-96, 1988).>

In order to ascertain correct operation of digital logic circuits it is necessary to verify correct functional operation as well as correct operation at desired clock rates. To ascertain correct operation at desired clock rates, it is verified that signal propagation delays along a set of selected paths fall within allowed limits by applying appropriate stimuli. It has previously been suggested that an appropriate set of paths to test would be the one that includes at least one path, with maximum modeled delay, for each circuit lead or gate input. Here, algorithms to select such sets of paths with minimum cardinality are given.>