English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we consider the problem of finding a regression in a versioncontrol system (VCS), such as \texttt{git}. The set of versions is modelled bya Directed Acyclic Graph (DAG) where vertices represent versions of thesoftware, and arcs are the changes between different versions. We assume thatsomewhere in the DAG, a bug was introduced, which persists in all of itssubsequent versions. It is possible to query a vertex to check whether thecorresponding version carries the bug. Given a DAG and a bugged vertex, theRegression Search Problem consists in finding the first vertex containing thebug in a minimum number of queries in the worst-case scenario. This problem isknown to be NP-complete. We study the algorithm used in \texttt{git} to addressthis problem, known as \texttt{git bisect}. We prove that in a general setting,\texttt{git bisect} can use an exponentially larger number of queries than anoptimal algorithm. We also consider the restriction where all vertices haveindegree at most 2 (i.e. where merges are made between at most two branches ata time in the VCS), and prove that in this case, \texttt{git bisect} is a$\frac{1}{\log_2(3/2)}$-approximation algorithm, and that this bound is tight.We also provide a better approximation algorithm for this case. Finally, wegive an alternative proof of the NP-completeness of the Regression SearchProblem, via a variation with bounded indegree.

Theoretical analysis of git bisect