Project presentations for CSI5165 Combinatorial Algorithms
Room: LPR 285 (Louis Pasteur) - Thursday April 9, 8:50am-12:05

Coffee and donuts will be served.

Abstracts


Title: A tabu search for Costas arrays
Speaker: Yiorgos Tzanakis

A Costas Array of order n is a subset C of size n of the n^2 lattice points (i,j) with 1<=i,j<=n such that no two of the n lattice points in C are in the same row and column and such that no two of the (n choose 2) line segments between pairs of points agree on both magnitude and slope. These are useful in applications such as radar and sonar. Generation methods exist and produce Costas Arrays of order n for infinitely many n, but not for all n. Finding Costas Arrays has proven to be a remarkably difficult task. We propose a tabu search algorithm to search for Costas Arrays of order 32 and 33, for which no Costas Array is currently known.
Title: Heuristic search for low complexity normal bases.
Speaker: David Thomson

The efficient implementation of binary arithmetic is highly required in such areas as cryptography and signal processing. In a normal basis the operation of squaring has negligible cost, and so exponentiation can be performed very quickly using the square-and-multiply method. For efficient communications it is desirable to use normal bases with low complexity. We present a heuristic search for low complexity normal bases and compare this to a naive random method. We use a previous algorithm by the authors (and others) based on a binary Gray code to efficiently iterate the search.
Title : Cycle Enumeration for LDPC codes
Speaker: Mehdi Karimi

Low Density Parity Check (LDPC) codes are one of the best current channel codes. The finite-length analysis of LDPC codes is an active area of research with many open problems. One method to estimate the performance of finite length LDPC codes is to enumerate all short cycles and check if these cycles can cause the problem to the decoder. We will present a cycle enumeration algorithm for enumerating cycles in the graph of a LDPC code. Our algorithm is based on backtracking algorithm and we have used a minimum distance criterion to prune it. The results show that this criterion can improve the efficiency of backtracking algorithm for many LDPC codes.
Title: Solving the Subset Sum Problem Using Basis Reduction
Speaker: Katherine Jarvis

Basis reduction can be used as an alternative to backtracking or heuristic searches for solving various combinatorial search problems. We will look at how basis reduction can be applied to solve combinatorial problems. In 1982 Lenstra et al. introduced the LLL basis reduction algorithm. The LLL algorithm can be used to devise polynomial time solutions to classical problems in computer science. For instance the LLL algorithm played a major role in breaking knapsack based cryptosystems which are based on the NP-hard subset sum problem. We will see an implementation of LLL to solve certain instances the subset sum (or knapsack) problem.
Title: Minimal Change Ordering for Binary Trees and Triangulations
Speaker: John Howat

Binary trees are ubiquitous in data structuring problems and are often structurally manipulated through the use of rotations. We will review the work of Lucas et al., which provides a minimal change ordering on the binary trees on n nodes such that two adjacent trees differ by a single rotation. This ordering will be introduced, discussed, and an implementation of the ordering will be demonstrated. We will also show how to use this minimal change ordering to produce a minimal change ordering on the triangulations of convex (n+2)-gons, where two adjacent triangulations differ by a single edge-flip. An implementation of this will also be demonstrated.
Title: Simulated Annealing for a Max-k-weighted max-clique on a Genome Network with DCJ Distance
Speaker: Maryam Haghighi

Double-cut-and-join (DCJ) is a rearrangement operation on the order of genes in two genomes. The minimum number of such operations that converts one genome to another is called the DCJ distance. Our goal is to identify clusters of genomes that are of maximum distance k from each other. We review the DCJ operation and an algorithm for finding the DCJ distance. Then we introduce some common clustering approaches. We define a graph based on the DCJ distance of genomes, and show that finding the clusters is equivalent to finding a maximum k-weighted maximum clique in this graph. We study a simulated annealing approach for this problem, and propose two different heuristic searches. After the implementation, we compare the efficiency of these methods.
Title: Genetic Algorithm approach for Channel Assignment problem in Wireless Mesh Networks.
Speaker: Jose Andres Gonzalez Barrameda

A wireless Mesh Network is a mesh topology network of nodes interconnected using wireless links. Because the physical medium is shared, interference between near links which use a common radio frequency is a common problem. This interference can highly degrade the network performance. Thus, in order to increase the network throughput, it is proposed to equip each node with several network interfaces, and set them to different channels, so simultaneous non-interfering communication may be carried out. We propose a Genetic Algorithm approach for this NP-hard problem, believing that a good solution is composed by good solutions to network sub-sections.
Title: Solving The Exact Cover Problem Using Dancing Links
Speaker: David Forrester

An exact cover of a set is a set of subsets such that each element in the original set appears exactly once in exactly one of the subsets. Many computational problems can be reduced to an exact cover problem. I will demonstrate an algorithm known as "Algorithm X", which solves the exact cover problem using recursive, nondeterministic, depth-first, backtracking. I will also discuss an efficient implementation of this algorithm, known as "Dancing Links". Finally, I will show how Sudoku puzzles can be reduced to an exact cover problem, and how Dancing Links can be used to efficiently solve them.