Search

We study a sequential binary prediction setting where the forecaster is evaluated in terms of the calibration distance, which is defined as the L1 distance between the predicted values and the set of predictions that are perfectly calibrated in hindsight. This is analogous to a calibration measure recently proposed by Błasiok, Gopalan, Hu and Nakkiran (STOC 2023) for the offline setting. The calibration distance is a natural and intuitive measure of deviation from perfect calibration, and satisfies a Lipschitz continuity property which does not hold for many popular calibration measures, such as the L1 calibration error and its variants. We prove that there is a forecasting algorithm that achieves an O(√T) calibration distance in expectation on an adversarially chosen sequence of T binary outcomes. At the core of this upper bound is a structural result showing that the calibration distance is accurately approximated by the lower calibration distance, which is a continuous relaxation of the former. We then show that an O(√T) lower calibration distance can be achieved via a simple minimax argument and a reduction to online learning on a Lipschitz class. On the lower bound side, an Ω(T^(1/3)) calibration distance is shown to be unavoidable, even when the adversary outputs a sequence of independent random bits, and has an additional ability to early stop (i.e., to stop producing random bits and output the same bit in the remaining steps). Interestingly, without this early stopping, the forecaster can achieve a much smaller calibration distance of polylog(T).

We study the query version of the approximate heavy hitter and quantile problems. In the former problem, the input is a parameter ε and a set P of n points in ℝ^d where each point is assigned a color from a set C, and the goal is to build a structure such that given any geometric range γ, we can efficiently find a list of approximate heavy hitters in γ∩P, i.e., colors that appear at least ε |γ∩P| times in γ∩P, as well as their frequencies with an additive error of ε |γ∩P|. In the latter problem, each point is assigned a weight from a totally ordered universe and the query must output a sequence S of 1+1/ε weights such that the i-th weight in S has approximate rank iε|γ∩P|, meaning, rank iε|γ∩P| up to an additive error of ε|γ∩P|. Previously, optimal results were only known in 1D [Wei and Yi, 2011] but a few sub-optimal methods were available in higher dimensions [Peyman Afshani and Zhewei Wei, 2017; Pankaj K. Agarwal et al., 2012]. We study the problems for two important classes of geometric ranges: 3D halfspace and 3D dominance queries. It is known that many other important queries can be reduced to these two, e.g., 1D interval stabbing or interval containment, 2D three-sided queries, 2D circular as well as 2D k-nearest neighbors queries. We consider the real RAM model of computation where integer registers of size w bits, w = Θ(log n), are also available. For dominance queries, we show optimal solutions for both heavy hitter and quantile problems: using linear space, we can answer both queries in time O(log n + 1/ε). Note that as the output size is 1/ε, after investing the initial O(log n) searching time, our structure takes on average O(1) time to find a heavy hitter or a quantile! For more general halfspace heavy hitter queries, the same optimal query time can be achieved by increasing the space by an extra log_w(1/ε) (resp. log log_w(1/ε)) factor in 3D (resp. 2D). By spending extra log^O(1)(1/ε) factors in both time and space, we can also support quantile queries. We remark that it is hopeless to achieve a similar query bound for dimensions 4 or higher unless significant advances are made in the data structure side of theory of geometric approximations., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 7:1-7:17

The Energy Monitoring Framework, designed and developed by IAC, IUPUI, aims to provide a cloud-based solution that combines business analytics with sensors for real-time energy management at the plant level using wireless sensor network technology. The project provides a platform where users can analyze the functioning of a plant using sensor data. The data would also help users to explore the energy usage trends and identify any energy leaks due to malfunctions or other environmental factors in their plant. Additionally, the users could check the machinery status in their plant and have the capability to control the equipment remotely. The main objectives of the project include the following: Set up a wireless network using sensors and smart implants with a base station/ controller. Deploy and connect the smart implants and sensors with the equipment in the plant that needs to be analyzed or controlled to improve their energy efficiency. Set up a generalized interface to collect and process the sensor data values and store the data in a database. Design and develop a generic database compatible with various companies irrespective of the type and size. Design and develop a web application with a generalized structure. Hence the database can be deployed at multiple companies with minimum customization. The web app should provide the users with a platform to interact with the data to analyze the sensor data and initiate commands to control the equipment. The General Structure of the project constitutes the following components: A wireless sensor network with a base station. An Edge PC, that interfaces with the sensor network to collect the sensor data and sends it out to the cloud server. The system also interfaces with the sensor network to send out command signals to control the switches/ actuators. A cloud that hosts a database and an API to collect and store information. A web application hosted in the cloud to provide an interactive platform for users to analyze the data. The project was demonstrated in: Lecture Hall (https://iac-lecture-hall.engr.iupui.edu/LectureHallFlask/). Test Bed (https://iac-testbed.engr.iupui.edu/testbedflask/). A company in Indiana. The above examples used sensors such as current sensors, temperature sensors, carbon dioxide sensors, and pressure sensors to set up the sensor network. The equipment was controlled using compactable switch nodes with the chosen sensor network protocol. The energy consumption details of each piece of equipment were measured over a few days. The data was validated, and the system worked as expected and helped the user to monitor, analyze and control the connected equipment remotely.

Graph Neural Networks (GNNs) have become excessively popular and prominent deep learning techniques to analyze structural graph data for their ability to solve complex real-world problems. Because graphs provide an efficient approach to contriving abstract hypothetical concepts, modern research overcomes the limitations of classical graph theory, requiring prior knowledge of the graph structure before employing traditional algorithms. GNNs, an impressive framework for representation learning of graphs, have already produced many state-of-the-art techniques to solve node classification, link prediction, and graph classification tasks. GNNs can learn meaningful representations of graphs incorporating topological structure, node attributes, and neighborhood aggregation to solve supervised, semi-supervised, and unsupervised graph-based problems. In this study, the usefulness of GNNs has been analyzed primarily from two aspects - clustering and classification. We focus on these two techniques, as they are the most popular strategies in data mining to discern collected data and employ predictive analysis.

Motivation: Minimal perfect hashing is the problem of mapping a static set of n distinct keys into the address space {1, ... , n} bijectively. It is well-known that n log2(e) bits are necessary to specify a minimal perfect hash function (MPHF) f, when no additional knowledge of the input keys is to be used. However, it is often the case in practice that the input keys have intrinsic relationships that we can exploit to lower the bit complexity of f. For example, consider a string and the set of all its distinct k-mers as input keys: since two consecutive k-mers share an overlap of k - 1 symbols, it seems possible to beat the classic log2(e) bits/key barrier in this case. Moreover, we would like f to map consecutive k-mers to consecutive addresses, as to also preserve as much as possible their relationship in the codomain. This is a useful feature in practice as it guarantees a certain degree of locality of reference for f, resulting in a better evaluation time when querying consecutive k-mers.Results: Motivated by these premises, we initiate the study of a new type of locality-preserving MPHF designed for k-mers extracted consecutively from a collection of strings. We design a construction whose space usage decreases for growing k and discuss experiments with a practical implementation of the method: in practice, the functions built with our method can be several times smaller and even faster to query than the most efficient MPHFs in the literature.Code Availability: https://github.com/jermp/lphashData Availability: https://zenodo.org/record/7239205

Approaches to content moderation online draw from models used to manage behavior in the offline world—undesirable content and behaviors are identified and sanctioned are issued as a means of deterrence. Recent discussions in both offline and online contexts have emphasized the limits of a sanction-based approach and highlighted the gains that would flow from building self-regulatory models within which users are encouraged to take personal responsibility for following rules. Our concern is whether a procedural justice model—a model which has increasingly been adopted in offline legal settings—can be used for content moderation online, and furthermore, if the benefits of this self-regulatory model persist in an online setting where algorithms play a more central role. We review recent studies which demonstrate that it is possible to promote self-governance by having platforms employ enforcement procedures that users experience as being procedurally just. The challenge of such procedures is that at least some of their features—having voice, receiving an explanation, treatment with respect—appear to be in conflict with a reliance on algorithms used by many online platforms. This review of the literature suggests that there is not necessarily an inherent conflict between the use of algorithms and the user experience of procedural justice. Drawing upon findings from recent empirical work in this space, we argue that the necessary antecedents for procedural justice can be built into algorithmic decision making used in platforms’ content moderation efforts. Doing so, however, requires a nuanced understanding of how algorithms are viewed—both positively and negatively—in building trust during these decision making processes.

The first part of this thesis introduces two solution methods for energy-optimal path finding for Electric Vehicles (EVs). It also develops a complete pickup-and-delivery model with EVs. The second part addresses the key topics of bi-objective and weight constrained path finding. It first presents a new bi-objective search framework that improves the runtime and memory usage of the state of the art by several factors. It then introduces four fast algorithms for the weight constrained shortest path problem and show how our enhanced algorithms can improve the performance over the state of the art by several orders of magnitude.

The densest subgraph problem is an important problem with both theoretical and practical significance. We consider a variant of the problem, the directed densest subgraph problem, under the partially dynamic setting of edge insertions only. We give a algorithm maintaining a (1-ε)-approximate directed densest subgraph in O(log3n/ε6) amortized time per edge insertion, based on earlier work by Chekuri and Quanrud. This result partially improves on an earlier result by Sawlani and Wang, which guarantees O(log5n/ε7) worst case time for edge insertions and deletions.

Collecting user data is crucial for advancing machine learning, social science, and government policies, but the privacy of the users whose data is being collected is a growing concern. {\em Differential Privacy (DP)} has emerged as the most standard notion for privacy protection with robust mathematical guarantees. Analyzing such massive amounts of data in a privacy-preserving manner motivates the need to study differentially-private algorithms that are also super-efficient. This thesis initiates a systematic study of differentially-private sublinear-time and sublinear-space algorithms. The contributions of this thesis are two-fold. First, we design some of the first differentially private sublinear algorithms for many fundamental problems. Second, we develop general DP techniques for designing differentially-private sublinear algorithms. We give the first DP sublinear algorithm for clustering by generalizing a subsampling framework from the non-DP sublinear-time literature. We give the first DP sublinear algorithm for estimating the maximum matching size. Our DP sublinear algorithm for estimating the average degree of the graph achieves a better approximation than previous works. We give the first DP algorithm for releasing $L_2$-heavy hitters in the sliding window model and a pure $L_1$-heavy hitter algorithm in the same model, which improves upon previous works. We develop general techniques that address the challenges of designing sublinear DP algorithms. First, we introduce the concept of Coupled Global Sensitivity (CGS). Intuitively, the CGS of a randomized algorithm generalizes the classical notion of global sensitivity of a function, by considering a coupling of the random coins of the algorithm when run on neighboring inputs. We show that one can achieve pure DP by adding Laplace noise proportional to the CGS of an algorithm. Second, we give a black box DP transformation for a specific class of approximation algorithms. We show that such algorithms can be made differentially private without sacrificing accuracy, as long as the function has small global sensitivity. In particular, this transformation gives rise to sublinear DP algorithms for many problems, including triangle counting, the weight of the minimum spanning tree, and norm estimation.

Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector θ∈Rd of coefficients is constrained in either ℓ1-norm (for Lasso) or in ℓ2-norm (for Ridge). We study the complexity of quantum algorithms for finding ε-minimizers for these minimization problems. We show that for Lasso we can get a quadratic quantum speedup in terms of d by speeding up the cost-per-iteration of the Frank-Wolfe algorithm, while for Ridge the best quantum algorithms are linear in d, as are the best classical algorithms. As a byproduct of our quantum lower bound for Lasso, we also prove the first classical lower bound for Lasso that is tight up to polylog-factors.

We start by slightly modifying the generic framework for solving online covering and packing linear programs (LP) proposed in the seminal work of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) to obtain efficient implementations in settings in which one has access to a separation oracle. We then apply the generic framework to several online network connectivity problems with LP formulations, namely pairwise spanners and directed Steiner forests. Our results are comparable to the previous state-of-the-art results for these problems in the offline setting. Further, we extend the generic frameworks to online optimization problems enhanced with machine-learning predictions. In particular, we present learning-augmented algorithms for online covering LPs and semidefinite programs (SDP), which outperform any optimal online algorithms when the prediction is accurate while maintaining reasonable guarantees when the prediction is misleading. Specifically, we obtain general online learning-augmented algorithms for covering LPs with fractional advice and general constraints and initiate the study of learning-augmented algorithms for covering SDPs.

HDCT’s 4th Clinical Trial Intensive Workshop for 2022 covering Data, Analysis & Research Output. The Workshop is Hosted by Dr Erin Morton – Lead of Flinders University’s Health Data & Clinical Trials (HDCT). Internal and external guest speakers with expertise in the topic. – Dr. Maria Alejandra Pinero de Plaza – Joey Gerlach – Rhys Williams – Dr. Alline Beleigoli – Dr. Kelly Loffler 19 OCT HDCT Clinical Trial Intensive Workshop10:00 am - 1:00 pm Flinders medical Centre | Level 5 5E305 Collaborative Teaching Space Audience: General Public, Industry partners, Recent graduates, Researchers, Staff, Students.

We study the notion of local treewidth in sparse random graphs: the maximum treewidth over all $k$-vertex subgraphs of an $n$-vertex graph. When $k$ is not too large, we give nearly tight bounds for this local treewidth parameter; we also derive tight bounds for the local treewidth of noisy trees, trees where every non-edge is added independently with small probability. We apply our upper bounds on the local treewidth to obtain fixed parameter tractable algorithms (on random graphs and noisy trees) for edge-removal problems centered around containing a contagious process evolving over a network. In these problems, our main parameter of study is $k$, the number of initially ``infected'' vertices in the network. For the random graph models we consider and a certain range of parameters the running time of our algorithms on $n$-vertex graphs is $2^{o(k)}\textrm{poly}(n)$, improving upon the $2^{\Omega(k)}\textrm{poly}(n)$ performance of the best-known algorithms designed for worst-case instances of these edge deletion problems., Comment: Accepted to RANDOM 2022

Highly Commended for Imagery in the Judge's Choice category in the Postgraduate Research Poster Competition held by the Graduate School of The Open University on 15th June 2022.

Semialgebraic range searching, arguably the most general version of range searching, is a fundamental problem in computational geometry. In the problem, we are to preprocess a set of points in ℝ^D such that the subset of points inside a semialgebraic region described by a constant number of polynomial inequalities of degree Δ can be found efficiently. Relatively recently, several major advances were made on this problem. Using algebraic techniques, "near-linear space" data structures [Agarwal et al., 2013; Matoušek and Patáková, 2015] with almost optimal query time of Q(n) = O(n^{1-1/D+o(1)}) were obtained. For "fast query" data structures (i.e., when Q(n) = n^{o(1)}), it was conjectured that a similar improvement is possible, i.e., it is possible to achieve space S(n) = O(n^{D+o(1)}). The conjecture was refuted very recently by Afshani and Cheng [Afshani and Cheng, 2021]. In the plane, i.e., D = 2, they proved that S(n) = Ω(n^{Δ+1 - o(1)}/Q(n)^{(Δ+3)Δ/2}) which shows Ω(n^{Δ+1-o(1)}) space is needed for Q(n) = n^{o(1)}. While this refutes the conjecture, it still leaves a number of unresolved issues: the lower bound only works in 2D and for fast queries, and neither the exponent of n or Q(n) seem to be tight even for D = 2, as the best known upper bounds have S(n) = O(n^{m+o(1)}/Q(n)^{(m-1)D/(D-1)}) where m = binom(D+Δ,D)-1 = Ω(Δ^D) is the maximum number of parameters to define a monic degree-Δ D-variate polynomial, for any constant dimension D and degree Δ. In this paper, we resolve two of the issues: we prove a lower bound in D-dimensions, for constant D, and show that when the query time is n^{o(1)}+O(k), the space usage is Ω(n^{m-o(1)}), which almost matches the Õ(n^{m}) upper bound and essentially closes the problem for the fast-query case, as far as the exponent of n is considered in the pointer machine model. When considering the exponent of Q(n), we show that the analysis in [Afshani and Cheng, 2021] is tight for D = 2, by presenting matching upper bounds for uniform random point sets. This shows either the existing upper bounds can be improved or to obtain better lower bounds a new fundamentally different input set needs to be constructed., LIPIcs, Vol. 224, 38th International Symposium on Computational Geometry (SoCG 2022), pages 3:1-3:14

A minimum information model a virtual biobank based on the Minimum Information About BIobank Data Sharing (MIABIS)

This thesis addresses aspects of stochastic algorithms for the solution of global optimisation problems. The bulk of the research investigates algorithm models of the adaptive search variety. Performances of stochastic and deterministic algorithms are also compared. Chapter 2 defines pure adaptive search, the prototypical improving region search scheme from the literature. Analyses from the literature of the search duration of pure adaptive search in two specialised situations are recounted and interpreted. In each case pure adaptive search is shown to require an expected search time which varies only linearly with the dimension of the feasible region. In Chapter 3 a generalisation of pure adaptive search is introduced under the name of hesitant adaptive search. This original algorithm retains the sample point generation mechanism of pure adaptive search, but allows for hesitation, in which an algorithm iteration passes without an improving sample being located. In this way hesitant adaptive search is intended to model more closely practically implementable algorithms. The analysis of the convergence of hesitant adaptive search is more thorough than the analyses already appearing in the literature, as it describes how hesitant adaptive search behaves when given more general objective functions than in previous studies. By specialising to the case of pure adaptive search we obtain a unification of the results appearing in those papers. Chapter 4 is the most applied of the chapters in this thesis. Here hesitant adaptive search is specialised to describe the convergence behaviour of localisation search schemes. A localisation search scheme produces a bracket of the current improving region at each iteration. The results of Chapter 3 are applied to find necessary and sufficient conditions on the 'tightness' of the brackets to ensure that the dependence of the expected search duration on the dimension of the feasible region is linear, quadratic, cubic, and so forth. Chapter 5 describes another original generalisation of pure adaptive search, known as fenestral adaptive search. This algorithm generates sample points from a region determined not merely by the previous sample, but by the previous w samples, where w is some prespecified positive integer. The expected search duration of fenestral adaptive search is greater than that of pure adaptive search, but still varies only linearly with the dimension of the feasible region. The sequence of objective function values obtained constitutes an interesting stochastic process, and Chapter 5 is devoted to understanding this process. Chapter 6 presents a theoretical comparison of the search durations of deterministic and stochastic global optimisation algorithms, together with some discussion of the implications. It is shown that to any stochastic algorithm, there corresponds a deterministic algorithm which requires no more iterations on average, but we discuss why stochastic algorithms may still be more efficient than their deterministic counterparts in practice.

We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between power-saving states of different energy consumption and wake-up costs. We develop a learning-augmented online algorithm that makes decisions based on (potentially inaccurate) predicted lengths of the idle periods. The algorithm's performance is near-optimal when predictions are accurate and degrades gracefully with increasing prediction error, with a worst-case guarantee almost identical to the optimal classical online algorithm for the problem. A key ingredient in our approach is a new algorithm for the online ski rental problem in the learning augmented setting with tight dependence on the prediction error. We support our theoretical findings with experiments.

We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between power-saving states of different energy consumption and wake-up costs. We develop a learning-augmented online algorithm that makes decisions based on (potentially inaccurate) predicted lengths of the idle periods. The algorithm's performance is near-optimal when predictions are accurate and degrades gracefully with increasing prediction error, with a worst-case guarantee almost identical to the optimal classical online algorithm for the problem. A key ingredient in our approach is a new algorithm for the online ski rental problem in the learning augmented setting with tight dependence on the prediction error. We support our theoretical findings with experiments.

Please cite as:* Handayani, A., Hegarty, B., Pillai, P., Spreadborough, K. (2021) The Cascade of Care: How data models shape understanding of “monitoring and evaluation”, and “surveillance and survey”. DOI: https://doi.org/10.26188/14784783 *Authors listed in alphabetical orderNote: Files changed on 23/11/2021 to update title (include HIV in the title). No other changes were made.Abstract:This paper sets up the context in which the Cascade of Care is applied to HIV prevention in the Indonesian context. The Cascade of Care, hence forth referred to as the cascade, is a component of the broader Continuum of Care which is focused on the process from being at risk of HIV through to HIV prevention. This paper first outlines the cascade as a data model, which is a core component of providing policy makers and funders a high-level picture of progress towards HIV prevention. The paper considers the implications of the 90/90/90 approach to HIV prevention - “90% of all persons living with HIV (PLHIV) are aware of their HIV status, 90% of all people who know their status are receiving antiretroviral therapy (ART), and 90% of those on ART are virally suppressed”.The paper then considers two main components required to supply data to the cascade. First, monitoring and evaluation which emphasises that data should be used to drive decisions is examined. Second, surveillance and survey is considered which are the tools by which this data is collected. Throughout the paper, consideration is given to the purpose of the cascade and how the cascade shapes conceptualisation of these key terms. This paper provides a critique of how the cascade provides the appearance of a standard of HIV treatment and the broader implications of this.

Please cite as:* Handayani, A., Hegarty, B., Pillai, P., Spreadborough, K. (2021) The Cascade of Care: How data models shape understanding of “monitoring and evaluation”, and “surveillance and survey”. Seminar Presentation. DOI: https://doi.org/10.26188/14883348*Authors listed in alphabetical orderA presentation given at UCoE - AIDS Research Center Atma Jaya Virtual International Seminar, 29 June, 2021, online. https://pph.atmajaya.ac.id/event/the-cascade-of-care-how-data-models-shape-understanding-of-monitoring-and-evaluation-and-surveillance-and-survey/ The HIV services cascade is a framework for identifying, measuring, and visualizing the magnitude of gaps in HIV services throughout the lifelong HIV care continuum. The cascade also becomes a data model which then becomes a component for policy makers and donors in seeing an overview of the progress of HIV prevention. There are two main elements required in cascade data collection. First, monitoring and evaluation which emphasizes the use of data for decision making. Second, surveillance and surveys that consider the use of data collection tools.UCoE - AIDS Research Center Atma Jaya in collaboration with the University of Melbourne will cordially invite you to a Virtual International Seminar entitled "The Cascade of Care: How Data Models Shape Understanding of 'Monitoring and Evaluation', and 'Surveillance and Survey' ". This seminar is expected to be able to convey a critique of how the cascade presents HIV care standards and their implications and accommodate an overview related to the use of the cascade data model in HIV programs that can be input into the HIV data infrastructure in Indonesia.Speakers: Benjamin Hegarty, Kristal Spreadborough, Priyanka PillaiModerator: Amalia HandayaniThis presentation is related to the following preprint: https://doi.org/10.26188/14784783

Fractional cascading is one of the influential and important techniques in data structures, as it provides a general framework for solving a common important problem: the iterative search problem. In the problem, the input is a graph $G$ with constant degree. Also as input, we are given a set of values for every vertex of $G$ . The goal is to preprocess $G$ such that when we are given a query value $q$ , and a connected subgraph $\pi$ of $G$ , we can find the predecessor of $q$ in all the sets associated with the vertices of $\pi$ . The fundamental result of fractional cascading, by Chazelle and Guibas, is that there exists a data structure that uses linear space and it can answer queries in $O(\log n+\vert \pi\vert)$ time, at essentially constant time per predecessor [15]. While this technique has received plenty of attention in the past decades, an almost quadratic space lower bound for “two-dimensional fractional cascading” by Chazelle and Liu in STOC 2001 [17] has convinced the researchers that fractional cascading is fundamentally a one-dimensional technique. In two-dimensional fractional cascading, the input includes a planar subdivision for every vertex of $G$ and the query is a point $q$ and a subgraph $\pi$ and the goal is to locate the cell containing $q$ in all the subdivisions associated with the vertices of $\pi$ . In this paper, we show that it is actually possible to circumvent the lower bound of Chazelle and Liu for axis-aligned planar subdivisions. We present a number of upper and lower bounds which reveal that in two-dimensions, the problem has a much richer structure. When $G$ is a tree and $\pi$ is a path, then queries can be answered in $O(\log n+\vert \pi\vert + \min\{\vert \pi\vert \sqrt{\log n},\alpha(n)\sqrt{\vert \pi\vert}\log n\})$ time using linear space where $\alpha$ is an inverse Ackermann function; surprisingly, we show both branches of this bound are tight, up to the inverse Ackermann factor. When $G$ is a general graph or when $\pi$ is a general subgraph, then the query bound becomes $O(\log n+\vert \pi\vert \sqrt{\log n})$ and this bound is once again tight in both cases.

U ovom radu objašnjeni su pojmovi algoritama, te je pobliže predočen programski jezik Scala. Definirane su najčešće tehnike oblikovanja algoritama, te prikazani su primjeri radi lakšeg poimanja. Također navedeni su algoritmi sortiranja i pretraživanja koji su elementarni kada se priča o računalnoj znanosti. Osim toga ponuđena su neka algoritamska rješenja u programskom jeziku Scala za neke od uobičajenih problema koji se javljaju u informatici. This bachelor thesis explains concepts of algorithms, and presents Scala programming language in more detail. The most common algorithm design techniques are defined, with presented examples for ease of understanding. Sorting and searching algorithms are also mentioned which are elementary when talking about computer science. In addition, some algorithmic solutions in the Scala programming language are offered for some of the common problems that occur in informatics.

Glavna zamisao ovog rada je da se pokuša spojiti algoritam roja čestica i grafička simulacija rada samog algoritma u 3D prostoru na primjeru jata ptica kako pretražuje prostor u potrazi za ribom. Simulacija je napravljena u programskom jeziku C++, grafičkom sučelju OpenGL i razvojnom okruženju Visual studio 2017. Primijenjeni su osnovni dijelovi i koncepti koji su potrebni da se napravi 3D prostor, koristi moderni OpenGL, primjenjuje sam algoritam i grafički 3D model galeba. The main idea of this work is to try to connect the algorithm of the particle swarm and the graphical simulation of the work of the algorithm itself in the 3D space on the example of birds searching the space in search of fish. The simulation was made in the C++ programming language, the graphical interface of OpenGL and the Visual Studio 2017 development environment. Basic parts and concepts that are needed to make 3D space are applied, using modern OpenGL, the algorithm itself and graphic 3D model of Seagull.

Computing learners may not master basic concepts, or forget them between courses or from infrequent use. Learners also often struggle with advanced computing courses, perhaps from weakness with prerequisite concepts. One underlying challenge for researchers and instructors is determining the reason why a learner gets an advanced question wrong. Was the wrong answer because the learner lacked prerequisite skills, has not mastered the advanced skill, or some combination of the two? We contribute a design investigation into how to create differentiated questions which diagnose prerequisite and advanced skills at the same time. We focused on tracing and related skills as prerequisites, and on advanced object-oriented programming, concurrency, algorithm and data structures as the advanced skills. We conducted an inductive qualitative analysis of existing assessment questions from instructors and from a concept inventory with a validity argument (the Basic Data Structures Inventory). We found dependencies on a variety of prerequisite knowledge and mixed potential for diagnosing difficulties with prerequisites. Inspired by this analysis, we developed examples of differentiated assessments and reflected on design principles for creating/modifying assessments to better assess both advanced and prerequisite skills. Our example differentiated assessment questions and methods help enable research into how prerequisites skills affect learning of advanced concepts. They also may help instructors better understand and help learners with varying prerequisite knowledge, which may improve equity of learning outcomes. Our work also raises theoretical questions about what assessments really assess and how separate advanced topics and prerequisite skills are.

The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets. A blocking set is a set of vertices such that no optimal vertex cover contains all vertices in the blocking set, and the study of minimal blocking sets played implicit and explicit roles in many existing results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class 𝒞, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is showed to allow an essentially tight efficient reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class 𝒞, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain non-hereditary classes 𝒞, including the class 𝒞_{LP} of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or 𝒞_{LP} graphs., LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 36:1-36:14

Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson [ 31 ] has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e.g., Max-Cut , for many others, e.g., Max-SAT and Max-DiCut , the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known. In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including Max-Cut , Max-2SAT , and Max-DiCut , and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for the Max-Cut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.

Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can be decreased by a popular $k$-opt move. Earlier work has shown that (i) assuming the Exponential Time Hypothesis, there is no algorithm to find an improving $k$-opt move in time $f(k)n^{o(k/\log k)}$ for any function $f$, while (ii) it is possible to improve on the brute-force running time of $O(n^k)$ and save linear factors in the exponent. Modern TSP heuristics show that very good global solutions can already be reached using only the top-$O(1)$ most promising edges incident to each vertex. Motivated by this, we study the problem of finding an improving $k$-move in bounded degree graphs, presenting new algorithms and conditional lower bounds. We show that the aforementioned ETH lower bound also holds for graphs of maximum degree three, but that in bounded-degree graphs the best improving $k$-move can be found in time $O(n^{23k/135+o(k)})$. This improves upon the best-known bounds for general graphs. Due to its practical importance, we devote special attention to the range of $k$ in which improving $k$-moves in bounded-degree graphs can be found in quasi-linear time. For $k\le 7$, we give quasi-linear time algorithms for general weights. For $k=8$ we obtain a quasi-linear time algorithm for polylogarithmic weights. On the other hand, based on established fine-grained complexity hypotheses, we prove that the $k=9$ case does not admit quasi-linear time algorithms. Hence we fully characterize the values of $k$ for which quasi-linear time algorithms exist for polylogarithmic weights on bounded-degree graphs. As a byproduct, we show a new bound on pathwidth of even graphs which results in improved running time bounds for counting $k$-vertex paths and cycles., A new running time bound for counting cycles and paths in graphs was added