Optimization of River Water Quality Surveys by Multivariate Analysis of Physicochemical, Bacteriological and Ecotoxicological Data

This study aims to optimize the water quality monitoring of a polluted watercourse (Leça River, Portugal) through the principal component analysis (PCA) and cluster analysis (CA). These statistical methodologies were applied to physicochemical, bacteriological and ecotoxicological data (with the marine bacterium Vibrio fischeri and the green alga Chlorella vulgaris) obtained with the analysis of water samples monthly collected at seven monitoring sites and during five campaigns (February, May, June, August, and September 2006). The results of some variables were assigned to water quality classes according to national guidelines. Chemical and bacteriological quality data led to classify Leça River water quality as “bad” or “very bad”. PCA and CA identified monitoring sites with similar pollution pattern, giving to site 1 (located in the upstream stretch of the river) a distinct feature from all other sampling sites downstream. Ecotoxicity results corroborated this classification thus revealing differences in space and time. The present study includes not only physical, chemical and bacteriological but also ecotoxicological parameters, which broadens new perspectives in river water characterization. Moreover, the application of PCA and CA is very useful to optimize water quality monitoring networks, defining the minimum number of sites and their location. Thus, these tools can support appropriate management decisions.

Performance of state space and ARIMA models for consumer retail sales forecasting

Forecasting future sales is one of the most important issues that is beyond all strategic and planning decisions in effective operations of retail businesses. For profitable retail businesses, accurate demand forecasting is crucial in organizing and planning production, purchasing, transportation and labor force. Retail sales series belong to a special type of time series that typically contain trend and seasonal patterns, presenting challenges in developing effective forecasting models. This work compares the forecasting performance of state space models and ARIMA models. The forecasting performance is demonstrated through a case study of retail sales of five different categories of women footwear: Boots, Booties, Flats, Sandals and Shoes. On both methodologies the model with the minimum value of Akaike's Information Criteria for the in-sample period was selected from all admissible models for further evaluation in the out-of-sample. Both one-step and multiple-step forecasts were produced. The results show that when an automatic algorithm the overall out-of-sample forecasting performance of state space and ARIMA models evaluated via RMSE, MAE and MAPE is quite similar on both one-step and multi-step forecasts. We also conclude that state space and ARIMA produce coverage probabilities that are close to the nominal rates for both one-step and multi-step forecasts.

The Teggiolo zone: a key to the Helvetic-Penninic connection (stratigraphy and tectonics in the Val Bavona, Ticino, Central Alps)

The Teggiolo zone is the sedimentary cover of the Antigorio nappe, one of the lowest tectonic units of the Penninic Central Alps. Detailed mapping, stratigraphic and structural analyses, and comparisons with less metamorphic series in several well-studied domains of the Alps, provide a new stratigraphic interpretation. The Teggiolo zone is comprised of several sedimentary cycles, separated by erosive surfaces and large stratigraphic gaps, which cover the time span from Triassic to Eocene. At Mid-Jurassic times it appears as an uplifted, partially emergent block, marking the southern limit of the main Helvetic basin (the Limiting South-Helvetic Rise LSHR). The main mass of the Teggiolo calcschists, whose base truncates the Triassic-Jurassic cycles and can erode the Antigorio basement, consists of fine-grained clastic sediments analogous to the deep-water flyschoid deposits of Late Cretaceous to Eocene age in the North-Penninic (or Valais s.l.) basins. Thus the Antigorio-Teggiolo domain occupies a crucial paleogeographic position, on the boundary between the Helvetic and Penninic realms: from Triassic to Early Cretaceous its affinity is with the Helvetic; at the end of Cretaceous it is incorporated into the North-Penninic basins. An unexpected result is the discovery of the important role played by complex formations of wildflysch type at the top of the Teggiolo zone. They contain blocks of various sizes. According to their nature, three different associations are distinguished that have specific vertical and lateral distributions. These blocks give clues to the existence of territories that have disappeared from the present-day level of observation and impose constraints on the kinematics of early folding and embryonic nappe emplacement. Tectonics produced several phases of superimposed folds and schistosities, more in the metasediments than in the gneissic basement. Older deformations that predate the amplification of the frontal hinge of the nappe generated the dominant schistosity and the km-wide Vanzèla isoclinal fold.

The Arabidopsis PHYTOCHROME KINASE SUBSTRATE2 protein is a phototropin signaling element that regulates leaf flattening and leaf positioning.

In Arabidopsis (Arabidopsis thaliana), the blue light photoreceptor phototropins (phot1 and phot2) fine-tune the photosynthetic status of the plant by controlling several important adaptive processes in response to environmental light variations. These processes include stem and petiole phototropism (leaf positioning), leaf flattening, stomatal opening, and chloroplast movements. The PHYTOCHROME KINASE SUBSTRATE (PKS) protein family comprises four members in Arabidopsis (PKS1-PKS4). PKS1 is a novel phot1 signaling element during phototropism, as it interacts with phot1 and the important signaling element NONPHOTOTROPIC HYPOCOTYL3 (NPH3) and is required for normal phot1-mediated phototropism. In this study, we have analyzed more globally the role of three PKS members (PKS1, PKS2, and PKS4). Systematic analysis of mutants reveals that PKS2 (and to a lesser extent PKS1) act in the same subset of phototropin-controlled responses as NPH3, namely leaf flattening and positioning. PKS1, PKS2, and NPH3 coimmunoprecipitate with both phot1-green fluorescent protein and phot2-green fluorescent protein in leaf extracts. Genetic experiments position PKS2 within phot1 and phot2 pathways controlling leaf positioning and leaf flattening, respectively. NPH3 can act in both phot1 and phot2 pathways, and synergistic interactions observed between pks2 and nph3 mutants suggest complementary roles of PKS2 and NPH3 during phototropin signaling. Finally, several observations further suggest that PKS2 may regulate leaf flattening and positioning by controlling auxin homeostasis. Together with previous findings, our results indicate that the PKS proteins represent an important family of phototropin signaling proteins.

Heidegger on the way of thinking

This thesis attempts to clarify what Heidegger meant by the term "thinking" (Denken), where this ^'meanr is submitted in the double sense: firstly, in the sense of what Heidegger intended by the use and exposition of this term that we find in his lecture series. Was Heisst Denken?, where Heidegger quickly makes it clear that this intention is to actually bring thinking on the way, viz. making provision for the leap into thinking, and where this intention was carried out with the employment of a specific guiding phrase. In the second sense, it is an attempt at clarifying the meaning of the term. But this is not to say that we are here simply out to see how Heidegger defines the word '*thinking." It is in fact precisely within such definitive discourse that thought dies out. It is not merely be a case of defining a word, because this enterprise would be just as shallow as much as it would be unworkable. It is for this reason that Heidegger decided to establish for himself the task, not merely of explaining thinking as something to be beheld at a distance, but rather of bringing thinking underway by means of his lecture, proclaiming that, "Only the leap into the river tells us what is swimming. The question 'What is called thinking?' can never be answered by proposing a definition of the concept thinking, and then diligently explaining what is contained in that definition." (WCT, 21) This being Heidegger's intention, in order to understand Heidegger in his treatment of the term thinking, it is clear that we must also undergo an experience with thinking. It is in this spirit that the present work was written so as to collaborate the two senses of what Heidegger meant by "thinking."

The normal co-ordinate analysis, vibrational spectra and theoretical infrared intensities of some thiocarbonyl halide molecules /

TITLE: The normal co-ordinate analysis, vibrational spectra and theoretical infrared intensities of some thiocarbonyl halides. AUTHOR: J. L. Brema SUPERVISOR: Dr. D. C. Moule NUMBER OF PAGES: 89 ABSTRACT: The vibrational assignment of the five-in-plane fundamental modes of CSClBr has been made on the basis of infrared gas phase and liquid Raman spectral analyses to supplement our earlier vibrational studies. Even though the one out-of-plane fundamental was not observed spectroscopically an attempt has been made to predict its frequency. The vibrational spectra contained impurity bands and the CSClBr assignment was made only after a thorough analysis of the impurities themselves. A normal co-ordinate analysis calculation was performed assuming a Urey-Bradley force field. This calculation yielded the fundamental frequencies in good agreement with those observed after refinement of the originally transferred force constants. The theoretical frequencies are the eigenvalues of the secular equation and the calculation also gave the corresponding eigenvectors in the form of the very important LLj matrix. The [l] matrix is the transfoirmation between internal co-ordinates and normal co-ordinates and it is essential for Franck-Condon calculations on electronically excited molecules and for infrared Integrated band intensity studies. Using a self-consistent molecular orbital calculation termed "complete neglect of differential overlap" (CNDO/2) , theoretical values of equilibrium bond lengths and angleswere calcuted for a series of carbonyl and thlocarbonyl molecules. From these calculations valence force field force constants were also determined but with limited success. With the CNIX)/2 method theoretical dipole moment derivatives with respect to symmetrized internal co-ordinates were calculated and the results should be useful in a correlation with experimentally determined values.

Attention focus and balance control in young and older adults

This thesis investigated attention focus and balance control in eighteen healthy young adults and eighteen healthy older adults. All participants performed sixteen consecutive trials of a balance task which involved standing for 30-s on an unstable platform that could rotate only in the roll direction. There were no attention focus instructions provided on any of the sixteen trials. Following the completion of the initial and final attempt in the series, participants reported "where" their attention had been focused when performing the task. The results showed differences in balance between young and older adults and improvements in balance with practice in both young and older adults. However, there were no differences in attention focus strategies between young and older adults. Both age groups directed attention to multiple sources during the balance task. An equal focus on internal (i.e., feet, trunk, and other body parts) and external (i.e., the platform) sources with little focus on events not related to the task dominated on the first attempt of the balance task. Focus on internal sources was maintained and focus on events not related to the task increased at the expense of focus on external sources on the final attempt of the balance task. Following the series of sixteen trials to establish "natural" attention focus, participants performed three randomly presented trials, each with specific attention focus instructions (i.e., think about minimizing movements of the feet, the trunk, or the platform). The results showed that, in contrast to the literature, instructions to focus on an internal source, the trunk, actually augmented control of the task as reflected in reduced trunk sway whereas instructions to focus on an internal source, the feet, or an external source, the platform, did not benefit performance on the task. Thus, the distance fi-om the interaction point of the body with the external source is critical and may not depend on whether the source is internal or external. Thus, a global attention focus instruction may not be beneficial and the nature of the task should be considered when adopting attention focus instructions for young and older adults.

The green movement in Canada

The green movement has evolved over the last twenty years from various social, peace and ecology activist organizations into direct political participation in parliamentary institutions through the Green Party. Although there is no definable theory of green politics, the culmination of interacting social movements as well as feminist, decentralist and in many cases, left wing political ideology, has produced a specific kind of political direction for the Greens internationally. As a result of the increased a ttention and awareness given to ecological issues , combined with the heightened evidence of large scale environmental deterioration, public attitudes and government decisions on development and natural resource management have been significantly altered. The Green Party of Canada is still r elatively young in comparison to its European counterparts, although ecologica l awareness and interest in t he green movement in Canada is strong, as reflected not only in support on a political level for the Canadian Greens I but for environmental issues and a ctivism in general. For this reason it s important to determine whether or not the Green Party is a significant aspect of the Canadian green movement, and if in fact its representation is necessary as an active participant in the Canadian political system . The Green Party of Canada, as a vital aspect of the Canadian green movement, and its connection to international green organizations can be examined primarily through the examp l es of both the Canadian Greens and the Green party of Ontario , by using original party documents and literature, information gained through Green party meetings and discussions with members, and commentary by Green theorists where app licable. As well, the influence on the Canadian green movement by the German Green Party is outlined , again mainly through party literature, documents and critiques of the party's experiences. This study reveals several existing and potential problems fo r t he Green Party in Canada, and the political fut ure of the Canadian green movement in general. Some, such as the real i ties of the Canadian political system are external to the movement, and may be overcome with adjustments in goals and methods, and a realization of the changing attitude towards environmental issues in a political context . On the other hand, internal party disfunctions in both organization and direction, caused mainly by the indefinite parameters of green ideology, threaten to exploit the already problematic aspects evident in t he Green Party . Aside from its somewhat slow beginnings, the Green Party in Canada has developed into a strong grassroots social movement, not however from its political visibility but from the steady growth in the popul ari ty of ecological pol i t ics in Canada. Due to the seeming enormity of the obstacles facing the Greens in their effort 4 to achieve electoral success, it is doubtful that Parliamentary representation will be achieved without a major re-orientation of party organization and methods. UI timately the strength of the Green Party in Canada will be based upon its ability to survive as a significant movement, and its willingness to continue to challenge political thought and practice.

Orientation of Non-Native 2-Monosubstituted and 2,3-Disubstituted 1,4-Naphthoquinones in the A1 binding site of PSI and the effect on the rate of electron transfer : an electron paramagnetic resonance spectroscopy study

The proce-ss ofoxygenic photosynthesis is vital to life on Earth. the central event in photosynthesis is light induced electron transfer that converts light into energy for growth. Ofparticular significance is the membrane bound multisubunit protein known as Photosystem I (PSI). PSI is a reaction centre that is responsible for the transfer of electrons across the membrane to reduce NADP+ to NADPH. The recent publication ofa high resolution X-ray structure of PSI has shown new information about the structure, in particular the electron transfer cofactors, which allows us to study it in more detail. In PSI, the secondary acceptor is crucial for forward electron transfer. In this thesis, the effect of removing the native acceptor phylloquinone and replacing it with a series of structurally related quinones was investigated via transient electron paramagnetic resonance (EPR) experiments. The orientation of non native quinones in the binding site and their ability to function in the electron transfer process was determined. It was found that PSI will readily accept alkyl naphthoquinones and anthraquinone. Q band EPR experiments revealed that the non-native quinones are incorporated into the binding site with the same orientation of the headgroup as in the native system. X band EPR spectra and deuteration experiments indicate that monosubstituted naphthoquinones are bound to the Al site with their side group in the position occupied by the methyl group in native PSI (meta to the hydrogen bonded carbonyl oxygen). X band EPR experiments show that 2, 3- disubstituted methyl naphthoquinones are also incorporated into the Al site in the same orientation as phylloquinone, even with the presence of a halogen- or sulfur-containing side chain in the position normally occupied by the phytyl tail ofphylloquinone. The exception to this is 2-bromo-3-methyl --.- _. -. - -- - - 4 _._ _ _ - _ _ naphthoquinone which has a poorly resolved spectrum, making determination of the orientation difficuh. All of the non-native quinones studied act as efficient electron acceptors. However, forward electron transfer past the quinone could only be demonstrated for anthraquinone, which has a more negative midpoint potential than phylloquinone. In the case of anthraquinone, an increased rate of forward electron transfer compared to native PSI was found. From these results we can conclude that the rate ofelectron transfer from Al to Fx in native PSI lies in the normal region ofthe Marcus Curve.

Iridium(I) complexes of phenanthroline-derived benzimidazolylidenes : synthetic, structural and catalytic studies

N-heterocyclic carbenes (NHCs) have undergone rapid development in recent years. Due to their strong a-electron donation and structural variability properties, NHCs are becoming a major class of ligands in organometallic chemistry. Compared with the other two types of NHCs (imidazolylidenes and imidazolinylidenes), benzimidazolylidenes have not been well represented. Limited synthetic approaches may impede the development ofbenzimidazolylidenes. This thesis is focused on the synthesis of phenanthroline-derived benzimidazolylidene ligands and their metal complexes. A series of benzimidazolylidene-iridium complexes were synthesized and characterized spectroscopically and crystallographic ally. All of the new complexes showed varying degrees of catalytic activity and enantioselectivity toward transfer hydrogenation and asymmetric hydrogenation. The best results were achieved in hydrogenation of methyl-2-acetamidoacrylate, which afforded (-)-(R)-methyl-2-acetamidopropanoate in 97% yield and 81 % ee.

Determination of viral load and integration status of HPV 16 in normal and LSIL exfoliated cervical cells

L’intégration du génome du virus papilloma humain (VPH) a été reconnu jusqu’`a récemment comme étant un événnement fréquent mais pourtant tardif dans la progression de la maladie du col de l’utérus. La perspective temporelle vient, pourtant, d’être mise au défi par la détection de formes intégrées de VPH dans les tissus normaux et dans les lésions prénéoplasiques. Notre objectif était de déterminer la charge virale de VPH-16 et son état physique dans une série de 220 échantillons provenant de cols uterins normaux et avec des lésions de bas-grade. La technique quantitative de PCR en temps réel, méthode Taqman, nous a permis de quantifier le nombre de copies des gènes E6, E2, et de la B-globine, permettant ainsi l’évaluation de la charge virale et le ratio de E6/E2 pour chaque spécimen. Le ratio E6/E2 de 1.2 ou plus était suggestif d’intégration. Par la suite, le site d’intégration du VPH dans le génome humain a été déterminé par la téchnique de RS-PCR. La charge virale moyenne était de 57.5±324.6 copies d'ADN par cellule et le ratio E6/E2 a évalué neuf échantillons avec des formes d’HPV intégrées. Ces intégrants ont été amplifiés par RS-PCR, suivi de séquençage, et l’homologie des amplicons a été déterminée par le programme BLAST de NCBI afin d’identifier les jonctions virales-humaines. On a réussi `a identifier les jonctions humaines-virales pour le contrôle positif, c'est-à-dire les cellules SiHa, pourtant nous n’avons pas detecté d’intégration par la technique de RS-PCR dans les échantillons de cellules cervicales exfoliées provenant de tissus normaux et de lésions de bas-grade. Le VPH-16 est rarement intégré dans les spécimens de jeunes patientes.

Développement d'un indice de vulnérabilité à l'érosion éolienne à partir d'images satellitales, dans le Bassin arachidier du Sénégal : cas de la région de Thiès.

L’érosion éolienne est un problème environnemental parmi les plus sévères dans les régions arides, semi-arides et les régions sèches sub-humides de la planète. L’érosion des sols accélérée par le vent provoque des dommages à la fois localement et régionalement. Sur le plan local, elle cause la baisse des nutriments par la mobilisation des particules les plus fines et de la matière organique. Cette mobilisation est une des causes de perte de fertilité des sols avec comme conséquence, une chute de la productivité agricole et une réduction de la profondeur de la partie arable. Sur le plan régional, les tempêtes de poussières soulevées par le vent ont un impact non négligeable sur la santé des populations, et la déposition des particules affecte les équipements hydrauliques tels que les canaux à ciel ouvert ainsi que les infrastructures notamment de transport. Dans les régions où les sols sont fréquemment soumis à l’érosion éolienne, les besoins pour des études qui visent à caractériser spatialement les sols selon leur degré de vulnérabilité sont grands. On n’a qu’à penser aux autorités administratives qui doivent décider des mesures à prendre pour préserver et conserver les potentialités agropédologiques des sols, souvent avec des ressources financières modestes mises à leur disposition. Or, dans certaines de ces régions, comme notre territoire d’étude, la région de Thiès au Sénégal, ces études font défaut. En effet, les quelques études effectuées dans cette région ou dans des contextes géographiques similaires ont un caractère plutôt local et les approches suivies (modèles de pertes des sols) nécessitent un nombre substantiel de données pour saisir la variabilité spatiale de la dynamique des facteurs qui interviennent dans le processus de l’érosion éolienne. La disponibilité de ces données est particulièrement problématique dans les pays en voie de développement, à cause de la pauvreté en infrastructures et des problèmes de ressources pour le monitoring continu des variables environnementales. L’approche mise de l’avant dans cette recherche vise à combler cette lacune en recourant principalement à l’imagerie satellitale, et plus particulièrement celle provenant des satellites Landsat-5 et Landsat-7. Les images Landsat couvrent la presque totalité de la zone optique du spectre exploitable par télédétection (visible, proche infrarouge, infrarouge moyen et thermique) à des résolutions relativement fines (quelques dizaines de mètres). Elles permettant ainsi d’étudier la distribution spatiale des niveaux de vulnérabilité des sols avec un niveau de détails beaucoup plus fin que celui obtenu avec des images souvent utilisées dans des études environnementales telles que AVHRR de la série de satellites NOAA (résolution kilométrique). De plus, l’archive complet des images Landsat-5 et Landsat-7 couvrant une période de plus de 20 ans est aujourd’hui facilement accessible. Parmi les paramètres utilisés dans les modèles d’érosion éolienne, nous avons identifiés ceux qui sont estimables par l’imagerie satellitale soit directement (exemple, fraction du couvert végétal) soit indirectement (exemple, caractérisation des sols par leur niveau d’érodabilité). En exploitant aussi le peu de données disponibles dans la région (données climatiques, carte morphopédologique) nous avons élaboré une base de données décrivant l’état des lieux dans la période de 1988 à 2002 et ce, selon les deux saisons caractéristiques de la région : la saison des pluies et la saison sèche. Ces données par date d’acquisition des images Landsat utilisées ont été considérées comme des intrants (critères) dans un modèle empirique que nous avons élaboré en modulant l’impact de chacun des critères (poids et scores). À l’aide de ce modèle, nous avons créé des cartes montrant les degrés de vulnérabilité dans la région à l’étude, et ce par date d’acquisition des images Landsat. Suite à une série de tests pour valider la cohérence interne du modèle, nous avons analysé nos cartes afin de conclure sur la dynamique du processus pendant la période d’étude. Nos principales conclusions sont les suivantes : 1) le modèle élaboré montre une bonne cohérence interne et est sensible aux variations spatiotemporelles des facteurs pris en considération 2); tel qu’attendu, parmi les facteurs utilisés pour expliquer la vulnérabilité des sols, la végétation vivante et l’érodabilité sont les plus importants ; 3) ces deux facteurs présentent une variation importante intra et inter-saisonnière de sorte qu’il est difficile de dégager des tendances à long terme bien que certaines parties du territoire (Nord et Est) aient des indices de vulnérabilité forts, peu importe la saison ; 4) l’analyse diachronique des cartes des indices de vulnérabilité confirme le caractère saisonnier des niveaux de vulnérabilité dans la mesure où les superficies occupées par les faibles niveaux de vulnérabilité augmentent en saison des pluies, donc lorsque l’humidité surfacique et la végétation active notamment sont importantes, et décroissent en saison sèche ; 5) la susceptibilité, c’est-à-dire l’impact du vent sur la vulnérabilité est d’autant plus forte que la vitesse du vent est élevée et que la vulnérabilité est forte. Sur les zones où la vulnérabilité est faible, les vitesses de vent élevées ont moins d’impact. Dans notre étude, nous avons aussi inclus une analyse comparative entre les facteurs extraits des images Landsat et celles des images hyperspectrales du satellite expérimental HYPERION. Bien que la résolution spatiale de ces images soit similaire à celle de Landsat, les résultats obtenus à partir des images HYPERION révèlent un niveau de détail supérieur grâce à la résolution spectrale de ce capteur permettant de mieux choisir les bandes spectrales qui réagissent le plus avec le facteur étudié. Cette étude comparative démontre que dans un futur rapproché, l’amélioration de l’accessibilité à ce type d’images permettra de raffiner davantage le calcul de l’indice de vulnérabilité par notre modèle. En attendant cette possibilité, on peut de contenter de l’imagerie Landsat qui offre un support d’informations permettant tout de même d’évaluer le niveau de fragilisation des sols par l’action du vent et par la dynamique des caractéristiques des facteurs telles que la couverture végétale aussi bien vivante que sénescente.

Short-term effects of human urine fertiliser and wood ash on soil pH and electrical conductivity

The fertiliser value of human urine has been examined on several crops, yet little is known about its effects on key soil properties of agronomic significance. This study investigated temporal soil salinization potential of human urine fertiliser (HUF). It further looked at combined effects of human urine and wood ash (WA) on soil pH, urine-NH_3 volatilisation, soil electrical conductivity (EC), and basic cation contents of two Acrisols (Adenta and Toje series) from the coastal savannah zone of Ghana. The experiment was a factorial design conducted in the laboratory for 12 weeks. The results indicated an increase in soil pH by 1.2 units for Adenta series and 1 unit for Toje series after one week of HUF application followed by a decline by about 2 pH units for both soil types after twelve weeks. This was attributed to nitrification of ammonium to nitrate leading to acidification. The EC otherwise increased with HUF application creating slightly saline conditions in Toje series and non-saline conditions in Adenta series. When WA was applied with HUF, both soil pH and EC increased. In contrast, the HUF alone slightly salinized Toje series, but both soils remained non-saline whenWA and HUF were applied together. The application ofWA resulted in two-fold increase in Ca, Mg, K, and Na content compared to HUF alone. Hence, WA is a promising amendment of acid soils and could reduce the effect of soluble salts in human urine fertilizer, which is likely to cause soil salinity.

On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript ∞]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript ∞]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript ∞]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript ∞]), but the work is increased by a factor of O(lg n).

COMP3016 Web Technology - Strand "XML" Lecture 2

Lecture 1: DTDs and XML Structure Verification Lecture slides and exercises for validating XML with DTDs.