We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the list-chromatic number of hypergraphs. One method uses hypergraph polynomials, which invokes Alon's combinatorial nullstellensatz. This method usually requires computer power to complete the calculations needed for even a modest-sized hypergraph. The other method is elementary, and uses the idea of minimum improper colourings. We apply these methods to various classes of hypergraphs, including the projective planes. We focus on solving the list-colouring problem for Steiner triple systems (STS). It is not hard using either method to determine that Steiner triple systems of orders 7, 9 and 13 are 3-list-chromatic. For systems of order 15, we show that they are 4-list-colourable, but they are also ``almost'' 3-list-colourable. For all Steiner triple systems, we prove a couple of simple upper bounds on their list-chromatic numbers. Also, unlike ordinary colouring where a 3-chromatic STS exists for each admissible order, we prove using probabilistic methods that for every $s$, every STS of high enough order is not $s$-list-colourable. The second problem is on embedding nearly-spanning bounded-degree trees in sparse graphs. We determine sufficient conditions based on expansion properties for a sparse graph to embed every nearly-spanning tree of bounded degree. We then apply this to random graphs, addressing a question of Alon, Krivelevich and Sudakov, and determine a probability $p$ where the random graph $G_{n,p}$ asymptotically almost surely contains every tree of bounded degree. This $p$ is nearly optimal in terms of the maximum degree of the trees that we embed. Finally, we solve a problem that arises from quantum computing, which can be formulated as an extremal question about maximizing the size of a type of acyclic directed graph.

In this thesis we introduce and evaluate several new models for the analysis of online algorithms. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as paging and routing are intrinsically online and thus the design and analysis of online algorithms is one of the main research areas in theoretical computer science. Competitive analysis is the standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to online graph coloring. While in several instances competitive analysis gives satisfactory results, for certain problems it results in unrealistically pessimistic ratios and/or fails to distinguish between algorithms that have vastly differing performance under any practical characterization. Addressing these shortcomings has been the subject of intense research by many of the best minds in the field. In this thesis, building upon recent advances of others we introduce some new models for analysis of online algorithms, namely Bijective Analysis, Average Analysis, Parameterized Analysis, and Relative Interval Analysis. We show that they lead to good results when applied to paging and list update algorithms. Paging and list update are two well known online problems. Paging is one of the main examples of poor behavior of competitive analysis. We show that LRU is the unique optimal online paging algorithm according to Average Analysis on sequences with locality of reference. Recall that in practice input sequences for paging have high locality of reference. It has been empirically long established that LRU is the best paging algorithm. Yet, Average Analysis is the first model that gives strict separation of LRU from all other online paging algorithms, thus solving a long standing open problem. We prove a similar result for the optimality of MTF for list update on sequences with locality of reference. A technique for the analysis of online algorithms has to be effective to be useful in day-to-day analysis of algorithms. While Bijective and Average Analysis succeed at providing fine separation, their application can be, at times, cumbersome. Thus we apply a parameterized or adaptive analysis framework to online algorithms. We show that this framework is effective, can be applied more easily to a larger family of problems and leads to finer analysis than the competitive ratio. The conceptual innovation of parameterizing the performance of an algorithm by something other than the input size was first introduced over three decades ago [124, 125]. By now it has been extensively studied and understood in the context of adaptive analysis (for problems in P) and parameterized algorithms (for NP-hard problems), yet to our knowledge this thesis is the first systematic application of this technique to the study of online algorithms. Interestingly, competitive analysis can be recast as a particular form of parameterized analysis in which the performance of opt is the parameter. In general, for each problem we can choose the parameter/measure that best reflects the difficulty of the input. We show that in many instances the performance of opt on a sequence is a coarse approximation of the difficulty or complexity of a given input sequence. Using a finer, more natural measure we can separate paging and list update algorithms which were otherwise indistinguishable under the classical model. This creates a performance hierarchy of algorithms which better reflects the intuitive relative strengths between them. Lastly, we show that, surprisingly, certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results. We test list update algorithms in the context of a data compression problem known to have locality of reference. Our experiments show MTF outperforms other list update algorithms in practice after BWT. This is consistent with the intuition that BWT increases locality of reference.

Methods for conditional Poisson sampling (CP-sampling) and Sampford sampling are compared and the focus is on the efficiency of the methods. The efficiency is investigated by simulation in different sampling situations. It was of interest to compare methods since new methods for both CP-sampling and Sampford sampling were introduced by Bondesson, Traat & Lundqvist in 2004. The new methods are acceptance rejection methods that use the efficient Pareto sampling method. They are found to be very efficient and useful in all situations. The list sequential methods for both CP-sampling and Sampford sampling are other methods that are found to be efficient, especially if many samples are to be generated.

This thesis is an expansion of an ongoing examination of gist and verbatim memory in young adults with language-learning disabilities (LLD) using the DRM paradigm (Deese, 1959; Roediger & McDermott, 1995). This study uses lists based on situation semantic features in addition to DRM lists based on backwards associative strength (BAS), which were categorized as strong-, mid-, and low-BAS (Stadler, Roediger, & McDermott, 1999). Items in each list (e.g., bacon, toast, cereal, muffin) related to a non-presented word (e.g., breakfast): the critical lure (CL). BAS is a measure of the likelihood that a list item will elicit the CL. Thirty young adults participated in this study and were divided into three groups: true LLD, compensated LLD, and typically developing (TD). Participants listened to word lists and verbally recalled the words they remembered hearing. Accurate recall was an indicator of verbatim memory; CL recall was an indicator of gist memory. The true LLD group recalled CL at a significantly higher rate than the other groups in the case of the situation lists; additionally, the compensated LLD group recalled CL for the low-BAS lists at a significantly higher rate than the other groups. These findings suggest that the LLD participants may process semantic information differently or may rely on gist memory to a greater extent than the TD controls. Results also indicated list type differences for both verbatim and gist recalls, supporting the effects of both semantic features and BAS together with other factors. / text

Bumblebees are important pollinators that are said to be in decline all over the world. Swedish bumblebees have now been inventoried through a nationwide monitoring program for which data for the first time have been analysed. The aim here was to give an indication of how 35 bumblebee species in Sweden have changed in occurrence over five years interval in the national inventory program. The results given in this report showed that 5 bumblebee species (B. lucorum, B. magnus, B. cryptarum, B. terrestris and B. pascuorum) had declined significantly. Furthermore bumblebees as a group had a significant decline while none of the species had increased. Moreover, declining Swedish bumblebees are species that are common in Europe while species that are declining in Europe do not seem to decline in Sweden. This result was somewhat unexpected, considering the European status of bumblebee species. Furthermore results showed that early emerging species and species living in ubiquitous and open areas had declined. This was also surprising comparing with previous research. Lastly the results showed that two bumblebee species (B. hortorum and B. terrestris) have shifted towards the south within Sweden while none shifted towards north or in a west-east direction.

Στην παρούσα εργασία γίνεται Μελέτη και Καταγραφή των σημαντικότερων υπηρεσιών που παρέχουν 12 από τα πιο γνωστά Client Management Tools που υπάρχουν στην αγορά. Παρουσιάζεται ένας πίνακας με τις λειτουργίες που παρέχει κάθε ένα από αυτά τα Client Management Tool. Επιπλέον γίνεται μια μελέτη για την Τιμολογιακή Πολιτική που ακολουθούν τα Client Management Tools. Στην συνέχεια γίνεται μία έρευνα για την CMDB, καθώς επίσης και τα βήματα τα οποία ακολουθούνται για την σχεδίασή της. Μελετάται το ITIL, και παρουσιάζεται ο τρόπος με τον οποίο ένα Client Management Tool μπορεί να γίνει ITIL Compatible. Στην συνέχεια, παρουσιάζεται το SchoolView, μία υπηρεσία ανάλογη με αυτή της υπηρεσίας TeamViewer, με την οποία αναβαθμίζεται το SchoolRSM. Και τέλος, προτείνονται κάποιες ενέργειες που πρέπει να γίνουν έτσι ώστε να μπορέσουμε να εφαρμόσουμε την CMDB στο OpenRSM. / The current thesis has done a study and a listing of the most important functions provided by twelve of the most renowned Client Management Tools. A table is presented with the functions that are provided by each of these Client Management Tools. Additionally a study is done for the price list policy that the Client Management Tools follow. Moreover a research is done for the CMDB and definitions associated with it are given as well as the steps that are followed for its construction. What is more, the ITIL is being studied, and the way in which a Client Management Tool can be ITIL Compatible is presented. Additionally, the SchoolView is being presented, a service similar to TeamViewer, with which SchoolRSM is being upgraded. Finally, there is a suggestion of some actions that should be done so as to adjust the CMDB to OpenRSM.

Signaling Overhead has always been a concern for network operators. LTE offers many improvements aimed at improved network performance and management. This thesis exploit Tracking Area List (TAL) concept in LTE networks. An algorithm to design TAL using UE traces is developed. The performance of TAL design is compared to conventional TA design. Performance is also compared with rule of thumb TAL design which is another approach to designing TAL

Event-related potentials were recorded as subjects were presented with pairs of words, one word at a time, to examine the electrocortical manifestations of association formation and the effect of intra-list semantic similarity. Two types of lists were presented: Same – all pairs belonged to the same semantic category; Different – all pairs belonged to a different semantic category. Subjects were told to memorize the pairs for a following paired associate recall test. Recall was better for the Different than Same lists. Subsequent recall was predicted by the amplitudes of a potential lasting throughout the epoch and the P555 to each word of a pair (likely reflecting state- and item-related encoding activity, respectively), as well as a late positive wave that occurred after the offset of the second word, which is thought to reflect association formation. A larger N425 was elicited by pairs in the Different than Same lists, likely reflecting semantic integration.

Encouraging the participation of the local population in the preservation of World Heritage Sites is one of the mission’s of UNESCO’s World Heritage Centre. Community involvement is also critical in the planning process. This dissertation argues that community involvement should be part of the World Heritage List nomination process and long-term preservation of the sites and that mechanisms should be in place to ensure this as part of the nomination file. To support this argument, literature on community involvement and World Heritage Sites is reviewed. Part of this dissertation is to provide a framework for community involvement at World Heritage Sites. In order to accomplish this, the known potential socio-economic benefits of World Heritage designation are also reviewed. This provides a framework whereby communities can be consulted and involved in activities at World Heritage Sites with the goal of preservation of the site and achieving additional socio-economic benefits. This framework was used to explore the attitudes of eight Western Ukrainian communities on the use of their wooden churches that are nominated to the UNESCO World Heritage List to improve their socio-economic conditions as well as preserve the churches. Previous studies focused mostly on the effects of World Heritage Site designation to produce social and economic benefits. This dissertation takes a different approach by involving the community at the nomination stage to determine which of these benefits they support and develop a plan of action and guidelines focused on achieving the desired changes. A community survey was developed under the supervision of this dissertation committee and Dr. Bevz at the Department of Restoration and Reconstruction of Architectural Complexes at Lviv Polytechnic National University as part of a J. William Fulbright grant to Ukraine. The survey responses were analyzed using both summary and statistical analysis to develop guidelines and a plan of action to be implemented by Lviv Polytechnic. This dissertation provides much needed research into community involvement at World Heritage Sites for their preservation and to achieve socio-economic benefits for the surrounding communities. The framework laid out in this dissertation has implications not only for Western Ukraine, but cultural heritage sites throughout the world.

In this work wireless communication systems with multiple co-channel signals present at the receiver are considered. One of the major challenges in the development of such systems is the computational complexity required for the detection of the transmitted signals. This thesis addresses this problem and develops reduced complexity algorithms for the detection of multiple co-channel signals in receivers with multiple antennas. The signals are transmitted from either a single user employing multiple transmit antennas, from multiple users or in the most general case by a mixture of the two. The receiver is assumed to be overloaded in that the number of transmitted signals exceeds the number of receive antennas. Joint Maximum Likelihood (JML) is the optimum detection algorithm which has exponential complexity in the number of signals. As a result, detection of the signals of interest at the receiver is challenging and infeasible in most practical systems. The thesis presents a framework for the detection of multiple co-channel signals in overloaded receivers. It proposes receiver structures and two list-based signal detection algorithms that allow for complexity reduction compared to the optimum detector while being able to maintain near optimum performance. Complexity savings are achieved by first employing a linear preprocessor at the receiver to reduce the effect of Co-Channel Interference (CCI) and second, by using a detection algorithm that searches only over a subspace of the transmitted symbols. Both algorithms use iterative processing to extract ordered lists of the most likely transmit symbols. Soft information can be obtained from the detector output list and can then be used by error control decoders. The first algorithm named Parallel Detection with Interference Estimation (PD-IE) considers the Additive White Gaussian Noise (AWGN) channel. It relies on a spatially reduced search over subsets of the transmitted symbols in combination with CCI estimation. Computational complexity under overload is lower than that of JML. Performance results show that PD-IE achieves near optimum performance in receivers with Uniform Circular Array (UCA) and Uniform Linear Array (ULA) antenna geometries. The second algorithm is referred to as List Group Search (LGS) detection. It is applied to overloaded receivers that operate in frequency-flat multipath fading channels. The List Group Search (LGS) detection algorithm forms multiple groups of the transmitted symbols over which an exhaustive search is performed. Simulation results show that LGS detection provides good complexity-performance tradeoffs under overload. A union bound for group-wise and list-based group-wise symbol detectors is also derived. It provides an approximation to the error performance of such detectors without the need for simulation. Moreover, the bound can be used to determine some detection parameters and tradeoffs. Results show that the bound is tight in the high Signal to Interference and Noise Ratio (SINR) region.