No description available.

This thesis studies data structures in the word-RAM and bitprobe models, with an emphasis on space efficiency. In the word-RAM model of computation the space cost of a data structure is measured in terms of the number of w-bit words stored in memory, and the cost of answering a query is measured in terms of the number of read, write, and arithmetic operations that must be performed. In the bitprobe model, like the word-RAM model, the space cost is measured in terms of the number of bits stored in memory, but the query cost is measured solely in terms of the number of bit accesses, or probes, that are performed. First, we examine the problem of succinctly representing a partially ordered set, or poset, in the word-RAM model with word size Theta(lg n) bits. A succinct representation of a combinatorial object is one that occupies space matching the information theoretic lower bound to within lower order terms. We show how to represent a poset on n vertices using a data structure that occupies n^2/4 + o(n^2) bits, and can answer precedence (i.e., less-than) queries in constant time. Since the transitive closure of a directed acyclic graph is a poset, this implies that we can support reachability queries on an arbitrary directed graph in the same space bound. As far as we are aware, this is the first representation of an arbitrary directed graph that supports reachability queries in constant time, and stores less than n choose 2 bits. We also consider several additional query operations. Second, we examine the problem of supporting range queries on strings of n characters (or, equivalently, arrays of n elements) in the word-RAM model with word size Theta(lg n) bits. We focus on the specific problem of answering range majority queries: i.e., given a range, report the character that is the majority among those in the range, if one exists. We show that these queries can be supported in constant time using a linear space (in words) data structure. We generalize this result in several directions, considering various frequency thresholds, geometric variants of the problem, and dynamism. These results are in stark contrast to recent work on the similar range mode problem, in which the query operation asks for the mode (i.e., most frequent) character in a given range. The current best data structures for the range mode problem take soft-Oh(n^(1/2)) time per query for linear space data structures. Third, we examine the deterministic membership (or dictionary) problem in the bitprobe model. This problem asks us to store a set of n elements drawn from a universe [1,u] such that membership queries can be always answered in t bit probes. We present several new fully explicit results for this problem, in particular for the case when n = 2, answering an open problem posed by Radhakrishnan, Shah, and Shannigrahi [ESA 2010]. We also present a general strategy for the membership problem that can be used to solve many related fundamental problems, such as rank, counting, and emptiness queries. Finally, we conclude with a list of open problems and avenues for future work.

This thesis studies data structures in the word-RAM and bitprobe models, with an emphasis on space efficiency. In the word-RAM model of computation the space cost of a data structure is measured in terms of the number of w-bit words stored in memory, and the cost of answering a query is measured in terms of the number of read, write, and arithmetic operations that must be performed. In the bitprobe model, like the word-RAM model, the space cost is measured in terms of the number of bits stored in memory, but the query cost is measured solely in terms of the number of bit accesses, or probes, that are performed. First, we examine the problem of succinctly representing a partially ordered set, or poset, in the word-RAM model with word size Theta(lg n) bits. A succinct representation of a combinatorial object is one that occupies space matching the information theoretic lower bound to within lower order terms. We show how to represent a poset on n vertices using a data structure that occupies n^2/4 + o(n^2) bits, and can answer precedence (i.e., less-than) queries in constant time. Since the transitive closure of a directed acyclic graph is a poset, this implies that we can support reachability queries on an arbitrary directed graph in the same space bound. As far as we are aware, this is the first representation of an arbitrary directed graph that supports reachability queries in constant time, and stores less than n choose 2 bits. We also consider several additional query operations. Second, we examine the problem of supporting range queries on strings of n characters (or, equivalently, arrays of n elements) in the word-RAM model with word size Theta(lg n) bits. We focus on the specific problem of answering range majority queries: i.e., given a range, report the character that is the majority among those in the range, if one exists. We show that these queries can be supported in constant time using a linear space (in words) data structure. We generalize this result in several directions, considering various frequency thresholds, geometric variants of the problem, and dynamism. These results are in stark contrast to recent work on the similar range mode problem, in which the query operation asks for the mode (i.e., most frequent) character in a given range. The current best data structures for the range mode problem take soft-Oh(n^(1/2)) time per query for linear space data structures. Third, we examine the deterministic membership (or dictionary) problem in the bitprobe model. This problem asks us to store a set of n elements drawn from a universe [1,u] such that membership queries can be always answered in t bit probes. We present several new fully explicit results for this problem, in particular for the case when n = 2, answering an open problem posed by Radhakrishnan, Shah, and Shannigrahi [ESA 2010]. We also present a general strategy for the membership problem that can be used to solve many related fundamental problems, such as rank, counting, and emptiness queries. Finally, we conclude with a list of open problems and avenues for future work.

No description available.

Background: RNA secondary structure prediction by energy minimization is the central computational tool for the analysis of structural non-coding RNAs and their interactions. Sparsification has been successfully applied to improve the time efficiency of various structure prediction algorithms while guaranteeing the same result; however, for many such folding problems, space efficiency is of even greater concern, particularly for long RNA sequences. So far, spaceefficient sparsified RNA folding with fold reconstruction was solved only for simple base-pair-based pseudo-energy models. Results: Here, we revisit the problem of space-efficient free energy minimization. Whereas the space-efficient minimization of the free energy has been sketched before, the reconstruction of the optimum structure has not even been discussed. We show that this reconstruction is not possible in trivial extension of the method for simple energy models. Then, we present the time- and space-efficient sparsified free energy minimization algorithm SparseMFEFold that guarantees MFE structure prediction. In particular, this novel algorithm provides efficient fold reconstruction based on dynamically garbage-collected trace arrows. The complexity of our algorithm depends on two parameters, the number of candidates Z and the number of trace arrows T; both are bounded by n2, but are typically much smaller. The time complexity of RNA folding is reduced from O(n3) to O(n2 + nZ); the space complexity, from O(n2) to O(n + T + Z). Our empirical results show more than 80 % space savings over RNAfold [Vienna RNA package] on the long RNAs from the RNA STRAND database (≥2500 bases). Conclusions: The presented technique is intentionally generalizable to complex prediction algorithms; due to their high space demands, algorithms like pseudoknot prediction and RNA–RNA-interaction prediction are expected to profit even stronger than \"standard\" MFE folding. SparseMFEFold is free software, available at http://www.bioinf.unileipzig. de/~will/Software/SparseMFEFold.

Cargo cycles can play a considerable role in mitigating the negative impacts of urban freight transport while still ensure that the material needs of the city are fulfilled. Their small size, lower operating costs, smaller carbon footprint, lack of tailpipe emissions, and manoeuvrability in congested areas are considerable advantages over traditional urban freight vehicles. However, the advantages of cargo cycles are not inherent in every urban environment and under all conditions. This problematics is in general insufficiently researched and more context specific knowledge is needed. Thus, this study investigates the obstacles and facilitating factors for utilising cargo cycles in urban freight transport in Stockholm, Sweden. To investigate these context specifications, case study approach was employed and consisted of qualitative content analysis, semi-structured interviews, and observations. This study argues that in Stockholm, contradictory forces affect the utilisation of cargo cycles in urban freight transport. On one hand, the facilitating factors are mostly associated with measures of sustainable urban freight transport and sustainable development in general: reaction to traffic situation; strategic orientation of the city; public-private partnership; and bicycle infrastructure. On the other hand, path dependence of the city connected to traditional urban freight vehicles (vans) symbolises obstacles: the absence of direct planning for cargo cycles; lack of recognition; and inconsistency of bicycle infrastructure.

The way office work has been conducted has been reflected upon the society and historical moments. Due to the pandemic working from home has been applied on a large scale for the first time in history and some changes will certainly stay.  This project aimed to investigate and develop a product that could aid a better work environment while working from home. Therefore, a certain product was not defined beforehand.The goal was to explore product solutions that solved issues that users were facing. Since the aim was to design a product that was guided by the research, the final result did not only cover the field of working from home but also working from anywhere. The result did also cover a more sustainable solution by mainly using one material, and by being able to replace and repair parts. The main methods used in this thesis were Double Diamond, Design Thinking, and a Human-centered approach. The findings of the different methods and tools used in the project laid a foundation and guided the final result and outcome of the project.  The project was conducted together with Yellon, a Brand Experience – firm, as supervisor.

Tomtmarkerna i urban bebyggelse blir allt mer attraktiva. En minskning av byggnadsarean medger positiva ekonomiska effekter på markkostnaden då tomtpriserna tenderar att bli allt högre i stadsmiljö. En stor del av totalkostnaden vid nyproduktionen av ett enbostadshus är tomtpriset. Framtidens enbostadshus bör utformas med ett begränsat tomtbehov samt uppfylla framtida energikrav.   Examensarbetet har utförts i samarbete med småhustillverkaren Eksjöhus, vilka till följd av de ökade markpriserna upplever en minskad efterfrågan för nyproduktion av småhus. Likt övriga hustillverkare står Eksjöhus också inför uppfyllandet av framtida energikrav.   Syftet med examensarbetet är att utforma framtidens enbostadshus, genom att effektivisera tomtutnyttjandet och förbättra energiprestandan. Frågeställningarna vilka besvaras i arbetet är ”Vilken är den minsta möjliga bostadsarean för entréplanet i ett enbostadshus, med bibehållen tillgänglighet enligt svenska krav?”, ”Hur kan rumsfunktionerna disponeras för ett enbostadshus i tre våningar med bibehållna boendekvalitéer?”, ”Hur kan ett enbostadshus utformas för att klara EUs direktiv för år 2020 beträffande byggnaders energiprestanda?”. Målet med arbetet är att utforma ett enbostadshus i tre våningar med minsta möjliga bostadsarea på entréplanet, som klarar EUs direktiv för år 2020 beträffande byggnaders energiprestanda.   En litteraturstudie genomfördes för att utreda kompaktboendets effekter på boendekvalitén samt energieffektiv byggnadsutformning. En fallstudie av tre byggnader utreddes boende i flera plan. Utformningen av framtidens enbostadshus genomfördes i ett skissarbete och slutligen beräknades byggnaden för att uppfylla den rådande kravspecifikationen för NNE-hus.   En yteffektiv planutformning åstadkoms genom överlappandet av betjäningsareor, effektiv disposition av rumsfunktioner samt gemensamma kommunikationsytor. Entréplanets utformning resulterade i en bostadsarea på 51,4 m2. Byggnaden är utformad för att tillgodose kravet på tillgänglighet i enlighet med BBR och SIS. Rumsfunktionerna som finns representerade på entréplanet är kök, badrum, avskiljbar sängplats samt utrymme för sittgrupp, matplats, tvätt och förvaring. Plan 2 utgörs till största del av ett vardagsrum vilket knyts samman med entréplanets sociala funktioner. Byggandens privata våning utgörs av plan 3 vilket inrymmer två av byggandens tre sovrum.   Byggnaden följer nu gällande krav för 2020-målet, utformat som ett NNE-hus genom en energieffektiv utformning och egenproduktion av el från solceller. Vår slutsats är att förhållande, disponering, kommunikation av rumsfunktioner samt åtskild placering av privata och sociala utrymmen är väsentligt för att minimera bostadsarean samt för att bibehålla en god bostadskvalité. / Building plots in urban settlements are becoming more attractive. A reduction of the gross floor area allows a positive economic impact on the cost when the prices tend to become high in urban settlements. A large amount of the total cost for the production of a new one-family house is the price of the building plot. The future one-family house should be designed with a limited need of land and also meet future energy demands.   The work was performed in collaboration with the small house manufacturer Eksjöhus, which due to the increased price of land are experiencing a decline in demand for construction of new one-family houses. Like the rest of the small house manufacturer, Eksjöhus are also facing the fulfillment of future energy requirements.   The purpose of this study is to design tomorrow's one-family house, by increasing the efficiency of land use and to improve the energy performance. The questions, which are answered in this work are "What is the minimum floor space for the ground floor of a one-family house, while maintaining accessibility according to Swedish demands?", "How can room functions be arrange for a one-family house in three floors with maintained housing qualities?", "How can a one-family house be designed to meet the future EU energy strategy towards 2020 concerning energy performance of buildings? ". The goal of this work is to design a one-family house in three floors with a minimum floor space on the entrance floor, which meet the future EU energy strategy towards 2020.   A literature study was conducted to investigate the impact of compact living on the living quality and energy efficient building design. In a case study of three buildings, housing in several floors was investigated. The design of a future onefamily house was conducted in a sketch work and finally the building was calculated to fulfill the current specification for a Zero-energy building.   A space-efficient plan design is accomplished by overlap the service areas, efficient disposition of room functions and by shared communication areas. The design of the entrance floor resulted in a gross internal area of 51,4 m2. The building is designed to meet the requirement of accessibility according to BBR and SIS.   Room functions which are represented on the entrance floor are kitchen, bathroom, separable bed space and space for sitting, dining, laundry and storage. Plan 2 consists of a large living room which is connected to the social functions on the entrance floor. The private floor of the building is plan 3 which consist of two of the building's three bedrooms.   The building is designed to meet the future EU energy strategy towards 2020. The building is a Zero-energy building due to the energy efficient design and the selfproduction of electricity from solar cells.   Our conclusion is that the relationship, disposition, communication and the separate placement of private and social spaces is essential to reduce the living space and to maintain good housing quality.

Background: RNA secondary structure prediction by energy minimization is the central computational tool for the analysis of structural non-coding RNAs and their interactions. Sparsification has been successfully applied to improve the time efficiency of various structure prediction algorithms while guaranteeing the same result; however, for many such folding problems, space efficiency is of even greater concern, particularly for long RNA sequences. So far, spaceefficient sparsified RNA folding with fold reconstruction was solved only for simple base-pair-based pseudo-energy models. Results: Here, we revisit the problem of space-efficient free energy minimization. Whereas the space-efficient minimization of the free energy has been sketched before, the reconstruction of the optimum structure has not even been discussed. We show that this reconstruction is not possible in trivial extension of the method for simple energy models. Then, we present the time- and space-efficient sparsified free energy minimization algorithm SparseMFEFold that guarantees MFE structure prediction. In particular, this novel algorithm provides efficient fold reconstruction based on dynamically garbage-collected trace arrows. The complexity of our algorithm depends on two parameters, the number of candidates Z and the number of trace arrows T; both are bounded by n2, but are typically much smaller. The time complexity of RNA folding is reduced from O(n3) to O(n2 + nZ); the space complexity, from O(n2) to O(n + T + Z). Our empirical results show more than 80 % space savings over RNAfold [Vienna RNA package] on the long RNAs from the RNA STRAND database (≥2500 bases). Conclusions: The presented technique is intentionally generalizable to complex prediction algorithms; due to their high space demands, algorithms like pseudoknot prediction and RNA–RNA-interaction prediction are expected to profit even stronger than \"standard\" MFE folding. SparseMFEFold is free software, available at http://www.bioinf.unileipzig. de/~will/Software/SparseMFEFold.

Bostadsbristen för unga växer i takt med att fler byggherrar avstår från att bygga små lägenheter, då rådande lagar gör det svårt att på ett gynnsamt sätt producera kostnads- och yteffektiva bostäder. Bostäder har i dag krav på sig från kommuner och beställare att uppfylla svensk standard. Däri har handikapporganisationer drivit fram tillgänglighetskrav som medför att alla nyproducerade bostäder är tillgänglighetsanpassade. Genom att ifrågasätta svensk funktionshinderspolitik i samband med bostadsbyggande har detta examensarbete som mål att hitta lösningar för att öka nyproduktionen av små bostäder. Granskningen resulterade i ett förslag till en ny standard för ungdoms- och studentbostäder vilken underlättar vid projektering av mindre enskilda bostadslägenheter. / The housing shortage for young people is growing as more developers refrain from building small houses since current laws make it difficult to favorably produce space-efficient buildings. Buildings must, as requirements from municipalities and clients, achieve the Swedish Standard. A standard where disability organizations have driven the availability requirements that entail that all new buildings are adapted for accessibility. By questioning the Swedish disability policy related to the building trade this thesis aims to find solutions to increase the new constructions of small apartments. The result became a proposal to a new standard for youths and students apartments, simplifying the planning of small apartments.