Media-Propelled Computational Thinking (MPCT - pronounced impact) is a course designed to introduce programming in the context of engaging problems in media computation, math, and physics. Programming concepts are introduced as incremental steps needed to solve pragmatic problems students already understand. The problems, graphical API, and hands-on program features are intended to expose fundamental concepts in mathematics and quantitative science.MPCT is offered in an entering students program for freshmen who plan to specialize in a variety of STEM (science, technology, engineering and math) and non-STEM subjects. The curriculum is intended to strengthen student intuition and interest in mathematical modeling and programming by engaging students in the direct manipulation of simple mathematical systems that model and display familiar physical phenomena. MPCT uses programs as concrete and manipulatable examples of fundamental concepts to engage a diverse range of students including women and underrepresented minorities.Variants of MPCT are being developed for high schools, and as a means to introduce computational science to upper division undergraduates studying non-computational STEM disciplines. This paper provides an overview of MPCT and representative problem studies including models of ballistics and resonant systems. The evaluation plan is described and very preliminary results are presented.

A family of functions F that map [0,m-1] into [0,n-1] is said to be $\h$-wise independent if any tuple of $\h$ distinct points in $[0,m-1]$ have a corresponding image, for a randomly selected $f\in F$, that is uniformly distributed in $[0,n-1]^{\h}$. This paper shows that for suitably fixed $\epsilon < 1$ and any $\h < m^\epsilon$, there are families of $\h$-wise independent functions that can be evaluated in constant time for the standard random access model of computation. It is also proven that any such family requires a storage array of $m^\delta$ random seeds for a suitable $\delta<1$. These seeds can be pseudorandom values precomputed from an initial $O(\h)$ random seeds. A simple adaptation yields $n^\epsilon$-wise independent functions that require $n^\delta$ storage in many cases where $m\gg n$. Lower bounds are presented to show that neither storage requirement can be materially reduced. Previous constructions of random functions having constant evaluation time and sublinear storage exhibited only a constant degree of independence. Unfortunately, the explicit randomized constructions, while requiring a constant number of operations, are far too slow for any practical application. However, nonconstructive existence arguments are given, which suggest that this factor might be eliminated. The problem of eliminating this factor is shown to be equivalent to a fundamental open question in graph theory. As a consequence of these constructions, many probabilistic algorithms---from traditional hashing to Ranade's emulation of common PRAM algorithms---can for the first time be shown to achieve, up to constant factors, their expected asymptotic performance for a programmable, albeit formal and currently impractical, model of computation, and a research direction is now available that may eventually lead to implementations that are fast and provably sound.

A special case of the dynamic finger conjecture is proved; this special case introduces a number of useful techniques.

Chernoff–Hoeffding (CH) bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables (r.v.’s). We present a simple technique that gives slightly better bounds than these and that more importantly requires only limited independence among the random variables, thereby importing a variety of standard results to the case of limited independence for free. Additional methods are also presented, and the aggregate results are sharp and provide a better understanding of the proof techniques behind these bounds. These results also yield improved bounds for various tail probability distributions and enable improved approximation algorithms for jobshop scheduling. The limited independence result implies that a reduced amount and weaker sources of randomness are sufficient for randomized algorithms whose analyses use the CH bounds, e.g., the analysis of randomized algorithms for random sampling and oblivious packet routing.

Nonoblivious hashing, where information gathered from unsuccessful probes is used to modify subsequent probe strategy, is introduced and used to obtain the following results for static lookup on full tables: (1) An O (1)-time worst-case scheme that uses only logarithmic additional memory, (and no memory when the domain size is linear in the table size), which improves upon previously linear space requirements. (2) An almost sure O (1)-time probabilistic worst-case scheme, which uses no additional memory and which improves upon previously logarithmic time requirements. (3) Enhancements to hashing: (1) and (2) are solved for multikey recors, where search can be performed under any key in time O (1); these schemes also permit properties, such as nearest neighbor and rank, to be determined in logarithmic time.

This paper gives the first optimal bounds for classical closed hashing schemes in the case of limited randomness.We thereby establish the first proof of optimality for hashing arbitrarily selected data, by virtually any classical closed scheme, with hash functions that are programmable and initialized by a small number of random bits.Let D = (xl, x2,..., x~) be a sequence of an distinct search keys, for a < 1, belonging to the universe U = {0, 1,...,m}.The objective is to hash D into a search table without the use of pointers and without relocating placed items.We show that for any fixed load a < 1, universal classes of c log n-wise independent hash functions yield the same expected performance as fully random hash functions for uniform hashing, linear probing, and double hashing.That is, the expected number of probes to insert the an-th item is asymptotically the same for clog n-wise independent functions as for idealized fully random hash functions.It follows that O(loglog m + log s n) random bits suffice for these hash schemes.In addition, this relationship holds for the expected r-th moment of the probe count, for any fixed r, with an additive term of only O( n )due to the limited randomness.Our performance bound for double hashing readily applies to any robust generalization that exhibits approximate pairwise independence for the first O(logn) probes of any item.This result is new even in the case of full randomness.When combined with the highly independent fast hash functions of [S-89], these results give the first randomized algorithms featuring~ for a word model of computation, constant time per probe and optimal probe performance (for double hashing and uniform hashing).These results are derived from a novel formulation that overestimates the expected probe count by underestimating the presence of local items already inserted into the hash table, and from a sharp analysis of the underlying stochastic structures formed by colliding items.

The problem of constructing a dense static hash-based lookup table T for a set of n elements belonging to a universe $U = \{ 0, 1, 2,\cdots , m -1 \}$ is considered. Nearly tight bounds on the spatial complexity of oblivious $O(1)$-probe hash functions, which are defined to depend solely on their search key argument, are provided. This establishes a significant gap between oblivious and nonoblivious search. In particular, the results include the following: • A lower bound showing that oblivious k-probe hash functions require a program size of $\Omega(({n / k}^{2})e^{-k}+\log \log m)$ bits, on average. • A probabilistic construction of a family of oblivious k-probe hash functions that can be specified in $O(n e^{-k} +\log \log m)$ bits, which nearly matches the above lower bound. • A variation of an explicit $O(1)$ time 1-probe (perfect) hash function family that can be specified in $O(n+\log \log m)$ bits, which is tight to within a constant factor of the lower bound.

A mechanism is provided for constructing log-n-wise-independent hash functions that can be evaluated in O(1) time. A probabilistic argument shows that for fixed epsilon>

We consider two hashing models for storing a set S ⊂ {0, 1, 2, …, m - 1} in a table T of size n.

Non-oblivious hashing, where the information gathered by performing “unsuccessful” probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables:

We describe an implicit data structure for n multikey records that supports searching for a record, under any key, in the asymptotically optimal search time Ο(log n). This improves on [Mun87] in which Munro describes an implicit data structure for the problem of storing n k-key records so that search on any key can be performed in Ο(logk n(log log n)k-1) comparisons. The theoretical tools we develop also yield practical schemes that either halve the number of memory references over obvious solutions to the non-implicit version of the problem, or alternatively reduce the number of pointers involved significantly.

This work describes a large number of constructions for sortingNintegers in the range [0,M- 1], forN≤M≤N2, for the standard VLSI bit model. Among other results, we attain: VLSI sorter constructions that are within a constant factor of optimal size, for allMand almost all running timesT. a fundamentally new merging network for sorting numbers in a bit model. new organizational approaches for optimal tuning of merging networks and the proper management of data flow.

Efficient solutions are given to compute the optimal placement for a pair of VLSI modules interconnected by river routing. Specifically, let the (perpendicular) distance between the two modules be the separation, and call the (transverse) displacement the offset. This paper principally considers the separation problem: Given an offset and a wiring rule, find the minimum separation permitting a legal wiring. The design rules might use wires which are exclusively rectilinear, polygonal with a finite number of slopes, or possibly restricted to some other class of shapes such as circular arcs plus linear pieces. Techniques are developed which unify a variety of different placement problems, and give efficient solutions under extremely general conditions. The advantage of these generalizations is not only their theoretical framework; the results extend naturally to more precise models of real river routing, and the theory is applicable to placement problems for collections of modules.

This work comprises two parts: lower bounds and upper bounds in VLSI circuits. The upper bounds are for the sorting problem: we describe a large number of constructions for sorting N numbers in the range [0,M] for the standard VLSI bit model. Among other results, we attain: • VLSI sorter constructions that are within a constant factor of optimal size for almost all number ranges M (including M = N), and running times T. • A fundamentally new merging network for sorting numbers in a bit model. • New organizational approaches for optimal tuning of merging networks and the proper management of data flow. The lower bounds apply to a variety of problems. We present two new techniques for establishing lower bounds on the information flow in VLSI circuits. They are: • An averaging technique, which is easy to apply to a variety of problems, including a long standing question regarding the AT2 complexity for sorting. • A technique for constructing fooling sets in instances where our averaging method is unlikely to provide an adequate bound.

This paper analyzes how to sort n k-bit numbers in a minimum storage network. The techniques also give new AT2lower bounds for a VLSI sorting model. The principal results in this paper are as follows. • Lower bounds are given for the minimum storage (and area) needed to sort n k-bit numbers, and accompanying upper bounds (sorting networks) are presented, which match the lower bounds, up to a constant factor. • Sharp bounds are derived, which demonstrate that the minimum storage requirements depend quite strongly on the I/O schedule, and on the sorting model. • AT2lower bounds are established for a VLSI device that sorts n k-bit numbers where k < log n.

A solution to the 'Detailed Routing given a Homotopy' (DRH) problem is given in O(n + mlogm + D(m)) operations. The solution uses n + mlogm homotopy queries that are elementary; they are answerable based solely on "local properties" of modules, terminals, and wire connections. In addition, we need O(m) more complex queries, which are represented in the D(m) term. These queries must account for the total number of crossin s occurringfor selected test segments.

We introduce new paradigms for the construction of efficient parallel graph algorithms. These paradigms, called filtration and funnelled pipelining, are illustrated with VLSI circuits for computing connected components, minimum spanning forests, and biconnected components. These circuits use realistic I/O schedules and require time and area of O(n1+ε). Thus they are essentially optimal. Filtration is a technique used to rapidly discard irrelevant input data. This greatly reduces storage, time, and communications costs in a wide variety of problems. A funnelled pipeline is obtained by building a series of increasingly thorough filter stages. Transition times along such a pipeline of filters form an exponentially increasing sequence. The increasing amount of time exactly balances the increasing degree of filtration. This balance makes possible the cascaded filtration critical to the minimum spanning forest and the biconnected components algorithms.

We consider the problem of wiring together two parallel rows of points under a variety of conditions. The options include whether we allow the rows to slide relative to one another, whether we use only rectilinear wires or arbitrary wires, and whether we can use wires in one layer or several layers. In almost all of these combinations of conditions, we can provide a polynomial-time algorithm to minimize the distance between the parallel rows of points. We also compare two fundamentally different wiring approaches, where one and two layers are used. We show that although the theoretical model implies that there can be great gains for the two-layer strategy, even in cases where no crossovers are required, when we consider typical design rules for laying out VLSI circuits there is no substantial advantage to the two-layer approach over the one-layer approach.