This paper includes some basic ideas about the computation of a function theta(G), the theta number of a graph G, which is known as the Lovasz number of G. theta(G^c) lies between two hard-to-compute graph numbers omega(G), the size of the largest lique in a graph G, and chi(G), the minimum number of colors need to properly color the vertices of G. Lovasz and Grotschel called this the "Sandwich Theorem". Donald E. Knuth gives four additional definitions of theta, theta_1, theta_2, theta_3, theta_4 and proves that they are all equal. First I am going to describe the proof of the equality of theta, theta_1 and theta_2 and then I will show the calculation of the theta function for some specific graphs: K_n, graphs related to K_n, and C_n. This will help us understand the theta function, an important function for graph theory. Some of the results are calculated in different ways. This will benefit students who have a basic knowledge of graph theory and want to learn more about the theta function.

This thesis presents an investigation of a new three-dimensional urban form where walking distances are less than a half-mile and congestion is minimal. The car-free urban form investigated herein is a city composed of skyscrapers massively interconnected with skybridges at multiple levels. The investigation consists of optimizing space use arrangement, skybridge presence or absence, and elevator number to simultaneously minimize total travel time, skybridge light blockage, and elevator energy usage in the city. These objectives are evaluated using three objective functions, the most significant of which involves a three-dimensional, pedestrian-only, three-step version of the traditional four-step planning model. Optimal and diverse designs are discovered with a genetic algorithm that generates always-feasible designs and uses the maximum fitness function. The space use arrangements and travel times of four extreme designs are analyzed and discussed, and the overall results of the investigation are presented. Conclusions suggest that skybridges are beneficial in reducing travel time and that travel times are shorter in cities wherein space use is mixed vertically as well as horizontally.

We study the Feasible Generalized Least-Squares (FGLS) estimation of the parameters of a linear regression model in which the errors are allowed to exhibit heteroskedasticity of unknown form and to be serially correlated. The main contribution is two fold; first we aim to demystify the reasons often advanced to use OLS instead of FGLS by showing that the latter estimate is robust, and more efficient and precise. Second, we devise consistent FGLS procedures, robust to misspecification, which achieves a lower mean squared error (MSE), often close to that of the correctly specified infeasible GLS. In the first chapter we restrict our attention to the case with independent heteroskedastic errors. We suggest a Lasso based procedure to estimate the skedastic function of the residuals. This estimate is then used to construct a FGLS estimator. Using extensive Monte Carlo simulations, we show that this Lasso-based FGLS procedure has better finite sample properties than OLS and other linear regression-based FGLS estimates. Moreover, the FGLS-Lasso estimate is robust to misspecification of both the functional form and the variables characterizing the skedastic function. The second chapter generalizes our investigation to the case with serially correlated errors. There are three main contributions; first we show that GLS is consistent requiring only pre-determined regressors, whereas OLS requires exogenous regressors to be consistent. The second contribution is to show that GLS is much more robust that OLS; even a misspecified GLS correction can achieve a lower MSE than OLS. The third contribution is to devise a FGLS procedure valid whether or not the regressors are exogenous, which achieves a MSE close to that of the correctly specified infeasible GLS. Extensive Monte Carlo experiments are conducted to assess the performance of our FGLS procedure against OLS in finite samples. FGLS achieves important reductions in MSE and variance relative to OLS. In the third chapter we consider an empirical application; we re-examine the Uncovered Interest Parity (UIP) hypothesis, which states that the expected rate of return to speculation in the forward foreign exchange market is zero. We extend the FGLS procedure to a setting in which lagged dependent variables are included as regressors. We thus provide a consistent and efficient framework to estimate the parameters of a general k-step-ahead linear forecasting equation. Finally, we apply our FGLS procedures to the analysis of the two main specifications to test the UIP.

Decreasing gas prices and the pressing need for fast-responding electric power generators are currently transforming natural gas networks. The intermittent operation of gas-fired plants to balance wind generation introduces spatiotemporal fluctuations of increasing gas demand. At the heart of modeling, monitoring, and control of gas networks is a set of nonlinear equations relating nodal gas injections and pressures to flows over pipelines. Given gas demands at all points of the network, the gas flow task aims at finding the rest of the physical quantities. For a tree network, the problem enjoys a closed-form solution; yet solving the equations for practical meshed networks is non-trivial. This problem is posed here as a feasibility problem involving quadratic equalities and inequalities, and is further relaxed to a convex semidefinite program (SDP) minimization. Drawing parallels to the power flow problem, the relaxation is shown to be exact if the cost function is judiciously designed using a representative set of network states. Numerical tests on a Belgian gas network corroborate the superiority of the novel method in recovering the actual gas network state over a Newton-Raphson solver. This thesis also considers the coupled infrastructures of natural gas and electric power systems. The gas and electric networks are coupled through gas-fired generators, which serve as shoulder and peaking plants for the electric power system. The optimal dispatch of coupled natural gas and electric power systems is posed as a relaxed convex minimization problem, which is solved using the feasible point pursuit (FPP) algorithm. For a decentralized solution, the alternating direction method of multipliers (ADMM) is used in collaboration with the FPP. Numerical experiments conducted on a Belgian gas network connected to the IEEE 14 bus benchmark system corroborate significant enhancements on computational efficiency compared with the centralized FPP-based approach. / Master of Science / The increase in penetration of renewable energy in the electric power grid has led to increased fluctuations in the power. The conventional coal based generators are inept to handle these fluctuations and thus, natural gas generators, which have fast response times are used to handle the intermittency caused by renewable energy sources. This manuscript solves the problem of finding the optimal dispatch of coupled natural gas and electric power systems. First, the optimal dispatch problem is framed as a optimization problem and then mathematical solvers are developed. Using the mathematical tools of Feasible point pursuit and Alternating direction method of multipliers, a distributed solver is developed, which can solve the optimal dispatch for large power and natural gas networks. The proposed algorithm is tested on a part of a Belgian gas network and the IEEE 14 bus power system. The algorithm is shown to converge to a feasible point.

A pragmatic method for designing compliant mechanisms is developed in this thesis, by selecting among existing mechanisms one that may be modified as required. This method complements existing techniques by answering questions of the existence and multiplicity of solutions for the given specifications of a practical problem. The premise for the method is a 2D map that juxta- poses the problem-specifications and the characteristics of compliant mechanisms in a database. The selection of the most suitable mechanisms is similar to Ashby's method of material selection. In our method, stuffiness, inertia, and the inherent kinematic characteristics of compliant mechanisms are analogous to material properties in Ashby's method. These characteristics capture the lumped behavior of compliant mechanisms in static and dynamic situations using spring-lever (SL) and spring-mass-lever (SML) models. The work includes the development of computation- ally efficient methods to compute the SL and SML model characteristics of single-input and single-output compliant mechanisms. Also developed in this work is a method to determine a feasible map by solving the governing equations of equilibrium and several inequalities pertaining to problem- specifications. The map helps not only in assessing the feasibility of the specifications but also in re-designing the mechanisms in predetermined ways to nd multiple solutions, all of which account for practical considerations. The method pays due attention to the overall size, strength considerations, manufacturability, and choice of material. It also enables minimal alterations of the problem-specifications when the user prefers a particular mechanism in the database. All these features are implemented in a web-based Java program with a graphical user interface that can be accessed at http://www.mecheng.iisc.ernet.in/ m2d2/CM design. Six case- studies that include micro machined inertial sensors, miniature valve mechanisms, ultra-sensitive force sensors, etc., are documented in detail to demonstrate the usefulness of the method in practice.

The extended finite state machine (EFSM) is a powerful modelling approach that has been applied to represent a wide range of systems. Despite its popularity, testing from an EFSM is a substantial problem for two main reasons: path feasibility and path test case generation. The path feasibility problem concerns generating transition paths through an EFSM that are feasible and satisfy a given test criterion. In an EFSM, guards and assignments in a path‟s transitions may cause some selected paths to be infeasible. The problem of path test case generation is to find a sequence of inputs that can exercise the transitions in a given feasible path. However, the transitions‟ guards and assignments in a given path can impose difficulties when producing such data making the range of acceptable inputs narrowed down to a possibly tiny range. While search-based approaches have proven efficient in automating aspects of testing, these have received little attention when testing from EFSMs. This thesis proposes an integrated search-based approach to automatically test from an EFSM. The proposed approach generates paths through an EFSM that are potentially feasible and satisfy a test criterion. Then, it generates test cases that can exercise the generated feasible paths. The approach is evaluated by being used to test from five EFSM cases studies. The achieved experimental results demonstrate the value of the proposed approach.

Linear programming (LP) stands for an optimization of a linear objective function, subject to linear and non-negativity constraints. For this purpose many methods for LP emerged. The best known is Simplex Method. Another group of methods for LP is represented by Interior Point Methods (IPM). These methods are based on interior points of feasible region of a problem, while Simplex Method uses basic feasible solution of a problem. This thesis focuses on theoretical background of IPM and brings it into relation with algorithms based on IPM. KKT system and its significance are included and the algorithm solving Linear Complementarity Problem is discussed as well. In this thesis, two algorithms based on IPM are introduced and used for solving a sample LP problem.

A presente pesquisa teve por objetivo investigar sob quais condições é possível promover o exercício da cidadania desde a infância no contexto da escola pública. O pressuposto assumido nesse estudo foi a noção das crianças como grupo social com interesses específicos, capazes de expressar sua visão sobre o que significa viver a cidadania e de participar em decisões sobre assuntos que as envolvam, propondo soluções criativas em diálogos com os adultos. Buscou-se estudar a experiência de transformação curricular em uma escola da rede pública municipal, em São Paulo, que se apresenta com uma proposta de formação cidadã desde a infância. Adotou-se como perspectiva metodológica a abordagem qualitativa, por meio de estudo de caso inspirado pelas orientações etnográficas. O percurso da pesquisa e a construção da metodologia estabeleceram coerência entre fundamentos que permitissem enfatizar a sintonia entre ética e pesquisa. A produção de dados envolveu leitura de documentos institucionais, o registro em diário de campo, observações participantes e entrevistas com trinta e nove crianças, três adolescentes e nove adultos. A literatura no que se refere à pesquisa com crianças subsidiou todo o processo investigativo, dando ênfase aos aspectos éticos, tais como: participação voluntária, consentimento dos pais e deles próprios e privacidade. Os fundamentos da pedagogia de Paulo Freire foram a principal base de sustentação teórico-prática da pesquisa. Os resultados obtidos revelaram que é plenamente viável a realização de propostas na educação escolar que proporcionem à criança participar ativamente da construção de sua cidadania. Para tanto, conclui-se que a escola pesquisada criou condições concretas em parceria com a comunidade local, para superar situaçõeslimites, e descobrir inéditos viáveis, configurando-se em uma escola inovadora, sem muros e sem paredes. Rompeu com um ensino tradicional, abriu espaço para que o currículo da educação básica fosse repensado, com vistas a formular metodologias que respeitassem a cultura, o tempo, o espaço e as características do ser criança e considerassem a ludicidade, a música, a brincadeira, entre outras linguagens. Pelas vozes das crianças, a cidadania desde a infância foi traduzida em exercício dos direitos, ações propositivas para a vida em sociedade e a aprendizagem da democracia por meio da participação delas em Assembleias de Estudantes, Rodas de Conversas, Comissões Mediadoras, Conselho de Escola e República de Estudantes. Em coerência com os princípios metodológicos, a pesquisa foi avaliada pelos participantes e os estudantes apresentaram importantes indicações para novos estudos sobre escolas públicas e privadas. Por fim, a pesquisa anunciou outro mundo possível na perspectiva das crianças, que apresentaram o princípio ético da vida como um bem precioso em comum. / The present research aimed to investigate under what conditions it is possible to promote the exercise of citizenship from childhood in the context of the public school. The assumption assumed in this study was the notion of children as a social group with specific interests, capable of expressing their vision about what it means to live citizenship and to participate in decisions on subjects that involve them, proposing creative solutions in dialogues with adults. We sought to study the experience of curricular transformation in a school of the municipal public network, in São Paulo, which presents itself with a proposal of citizen training from childhood. The qualitative approach was adopted as a methodological perspective, through a case study inspired by the ethnographic orientations. The course of the research and the construction of the methodology established coherence among foundations that allowed to emphasize the harmony between ethics and research. Data production involved reading institutional documents, field journaling, participant observations and interviews with thirtynine children, three adolescents, and nine adults. The literature regarding research with children subsidized the entire investigative process, emphasizing ethical aspects such as: voluntary participation, consent of parents and themselves and privacy. The fundamentals of Paulo Freire\'s pedagogy were the main basis for theoretical and practical support of the research. The results showed that it is fully feasible to make proposals in school education that allow children to participate actively in the construction of their citizenship. In order to do so, we conclude that the researched school created concrete conditions in partnership with the local community, to overcome \"limiting situations\", and to discover \"viable unpublished\", being configured in an innovative school, \"without walls\". It broke with a traditional teaching, opened space for the basic education curriculum to be rethought, with a view to formulating methodologies that respected the culture, time, space and characteristics of \"being a child\" and considered playfulness, music, games, among other languages. Through the voices of children, citizenship from childhood has been translated into the exercise of rights, propositional actions for life in society and the learning of democracy through their participation in Student Assemblies, Circle Conversation, Mediation Commissions, School Council and Republic of students. Consistent with the methodological principles, the research was evaluated by the participants and the students presented important indications for new studies on public and private schools. Finally, the research announced \"another possible world\" from the perspective of children, who presented the ethical principle of life as a precious commodity in common.

Evolutionära algoritmer har visat sig vara effektiva för att utveckla spelnivåer. Dock finns fortfarande ett behov av nivåer som både uppfyller de krav som spelen har, samt att nivåerna som skapas ska vara så olika som möjligt för att uppmuntra upprepade spelomgångar. För att åstadkomma detta kan man använda Novelty Search. Dock saknar Novelty Search funktioner som gör att populationen vill uppfylla de krav som nivåerna ska ha. Arbetet fokuserar därför på att jämföra två Novelty Search baserade algoritmer som båda uppmuntrar kravuppfyllning: Feasible Infeasible Novelty Search (FINS) och Pareto based Multi-objective evolutionary algorithm (PMOEA) med två mål: krav och Novelty Search. Studien jämför algoritmerna utifrån tre värden: hur stor andel av populationen som följer de ställda kraven, hur bra dessa individer är på att lösa ett nivårelaterat problem samt diversiteten bland dessa individer. Utöver PMOEA och FINS implementeras även en Novelty Search algoritm och en traditionell evolutionär algoritm. Tre experiment genomförs där nivåernas storlek och antalet krav varierade. Resultatet visar att PMOEA var bättre på att skapa fler individer som följde alla kraven och att dessa individer överlag var bättre på att optimera lösningar än vanlig Novelty Search och FINS. Dock hade FINS högre diversitet bland individerna än alla algoritmerna som testades. Studiens svaghet är att resultatet är subjektivt till algoritmernas uppsättning i artefakten, som sådan borde framtida arbeten fokusera på att utforska nya uppsättningar för att generalisera resultatet.

In this thesis, the problem of optimal resource allocation in real-time systems is studied. A recently proposed resource allocation approach called Q-RAM (Quality of Service based Resource Allocation Model) is investigated in detail. The goal of the Q-RAM based approaches is to minimize the execution speed in real-time systems while meeting resource constraints and maximizing total utility. Phased array radar system is an example of a system in which multiple tasks contend for multiple resources in order to satisfy their requirements. In this system, multiple targets are tracked (each a separate task) by the radar system simultaneously requiring processor and energy resources of the radar system. Phased array radar system is considered as an illustrative application area in order to comparatively evaluate the resource allocation approaches. For the problem of optimal resource allocation with single resource type, the Q-RAM algorithm appears incompletely specified, namely it does not have a termination criteria set that can terminate the algorithm in all possible cases. In the present study, first, the Q-RAM solution approach to the radar resource allocation problem with single resource type is extended to give a global optimal solution in all possible termination cases. For the case of multiple resource types, the Q-RAM approach can only generate near-optimal results. In this thesis, for the formulated radar resource allocation problem with multiple resource types, the Methods of Feasible Directions are considered as an alternative solution approach. For the multiple resource type case, the performances of both the Q-RAM approach and the Methods of Feasible Directions are investigated in terms of optimality and convergence speed with the help of Monte-Carlo simulations. It is observed from the results of the simulation experiments that the Gradient Projection Method produce results outperforming the Q-RAM approach in closeness to optimality with comparable execution times.