Lecture notes pdf

Lecture notes in PDF

Exercise sheet 8 pdf

Exercises and solutions in PDF

Lecture notes

Lecture notes in LaTex

Maximum induced subgraph of a recursive circulant

The recursive circulant RC(2(n), 4) enjoys several attractive topological properties. Let max_epsilon(G) (m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that max_epsilon(RC(2n,4))(m) = Sigma(i)(r)=(0)(p(i)/2 + i)2(Pi), where p(0) > p(1) > ... > p(r) are nonnegative integers defined by m = Sigma(i)(r)=(0)2(Pi). We then apply this formula to find the bisection width of RC(2(n), 4). The conclusion shows that, as n-dimensional cube, RC(2(n), 4) enjoys a linear bisection width. (c) 2005 Elsevier B.V. All rights reserved.

Ω-results for Beurling's zeta function and lower bounds for the generalised Dirichlet divisor problem

In this paper we study generalised prime systems for which the integer counting function NP(x) is asymptotically well behaved, in the sense that NP(x)=ρx+O(xβ), where ρ is a positive constant and . For such systems, the associated zeta function ζP(s) is holomorphic for . We prove that for , for any ε>0, and also for ε=0 for all such σ except possibly one value. The Dirichlet divisor problem for generalised integers concerns the size of the error term in NkP(x)−Ress=1(ζPk(s)xs/s), which is O(xθ) for some θ<1. Letting αk denote the infimum of such θ, we show that .

Fast median calculation method

The ever increasing demand for high image quality requires fast and efficient methods for noise reduction. The best-known order-statistics filter is the median filter. A method is presented to calculate the median on a set of N W-bit integers in W/B time steps. Blocks containing B-bit slices are used to find B-bits of the median; using a novel quantum-like representation allowing the median to be computed in an accelerated manner compared to the best-known method (W time steps). The general method allows a variety of designs to be synthesised systematically. A further novel architecture to calculate the median for a moving set of N integers is also discussed.

Software-based study of a non-sorting method for median calculation on a set of integer numbers

This paper presents a software-based study of a hardware-based non-sorting median calculation method on a set of integer numbers. The method divides the binary representation of each integer element in the set into bit slices in order to find the element located in the middle position. The method exhibits a linear complexity order and our analysis shows that the best performance in execution time is obtained when slices of 4-bit in size are used for 8-bit and 16-bit integers, in mostly any data set size. Results suggest that software implementation of bit slice method for median calculation outperforms sorting-based methods with increasing improvement for larger data set size. For data set sizes of N > 5, our simulations show an improvement of at least 40%.

Median architecture by accumulative parallel counters

The time to process each of W/B processing blocks of a median calculation method on a set of N W-bit integers is improved here by a factor of three compared to the literature. Parallelism uncovered in blocks containing B-bit slices are exploited by independent accumulative parallel counters so that the median is calculated faster than any known previous method for any N, W values. The improvements to the method are discussed in the context of calculating the median for a moving set of N integers for which a pipelined architecture is developed. An extra benefit of smaller area for the architecture is also reported.

Bit-index sort: a fast non-comparison integer sorting algorithm for permutations

This paper describes a fast integer sorting algorithm, herein referred as Bit-index sort, which is a non-comparison sorting algorithm for partial per-mutations, with linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers supported by machine hardware to retrieve the ordered output sequence. Results show that Bit-index sort outperforms in execution time to quicksort and counting sort algorithms. A parallel approach for Bit-index sort using two simultaneous threads is included, which obtains speedups up to 1.6.

Pipelined median architecture

The core processing step of the noise reduction median filter technique is to find the median within a window of integers. A four-step procedure method to compute the running median of the last N W-bit stream of integers showing area and time benefits is proposed. The method slices integers into groups of B-bit using a pipeline of W/B blocks. From the method, an architecture is developed giving a designer the flexibility to exchange area gains for faster frequency of operation, or vice versa, by adjusting N, W and B parameter values. Gains in area of around 40%, or in frequency of operation of around 20%, are clearly observed by FPGA circuit implementations compared to latest methods in the literature.

Generalised golden ratios over integer alphabets

It is a well known result that for β ∈ (1,1+√52) and x ∈ (0,1β−1) there exists uncountably many (ǫi)∞i=1 ∈ {0,1}N such that x = P∞i=1ǫiβ−i. When β ∈ (1+√52,2] there exists x ∈ (0,1β−1) for which there exists a unique (ǫi)∞i=1 ∈ {0,1}N such that x=P∞i=1ǫiβ−i. In this paper we consider the more general case when our sequences are elements of {0, . . . , m}N. We show that an analogue of the golden ratio exists and give an explicit formula for it.

Transcendental Brauer groups of products of CM elliptic curves

Let L be a number field and let E/L be an elliptic curve with complex multiplication by the ring of integers O_K of an imaginary quadratic field K. We use class field theory and results of Skorobogatov and Zarhin to compute the transcendental part of the Brauer group of the abelian surface ExE. The results for the odd order torsion also apply to the Brauer group of the K3 surface Kum(ExE). We describe explicitly the elliptic curves E/Q with complex multiplication by O_K such that the Brauer group of ExE contains a transcendental element of odd order. We show that such an element gives rise to a Brauer-Manin obstruction to weak approximation on Kum(ExE), while there is no obstruction coming from the algebraic part of the Brauer group.

Gál-type GCD sums beyond the critical line

We prove that ∑k,ℓ=1N(nk,nℓ)2α(nknℓ)α≪N2−2α(logN)b(α) holds for arbitrary integers 1≤n1<⋯

Weak hypergraph regularity and linear hypergraphs

We consider conditions which allow the embedding of linear hypergraphs of fixed size. In particular, we prove that any k-uniform hypergraph H of positive uniform density contains all linear k-uniform hypergraphs of a given size. More precisely, we show that for all integers l >= k >= 2 and every d > 0 there exists Q > 0 for which the following holds: if His a sufficiently large k-uniform hypergraph with the property that the density of H induced on every vertex subset of size on is at least d, then H contains every linear k-uniform hypergraph F with l vertices. The main ingredient in the proof of this result is a counting lemma for linear hypergraphs, which establishes that the straightforward extension of graph epsilon-regularity to hypergraphs suffices for counting linear hypergraphs. We also consider some related problems. (C) 2009 Elsevier Inc. All rights reserved.