COMBINATORIAL ALGORITHMS PROJECT TALKS (Friday, Dec 3, 9:00-12:00, CBY A605) 9:00-9:20 François de Bellefeuille, "Supervision Scheduling by Heuristic Algorithm" 9:25-9:45 Samuel Cormier-Iijima, "Alternative Combinatorial Gray Codes" 9:50-10:10 Behnan Hajian, "Finding the Most Influential Person Across The Network–Behavioral-­Based Algorithm Using Heuristic Search" 10:15-10:35 Ahmed Jedda, "Application of covering arrays in practical combinatorial testing" 10:40-11:00 Dana Jansens, "Counterexample by Exhaustive Search" 11:10-11:30 Elizabeth Maltais, "Graph homomorphisms by backtracking" 11:35-11:55 Andrew Schoenrock, "Identification of Novel Protein Complexes through Pseudo Clique Enumeration" ABSTRACTS SUBMITTED SO FAR: "Counterexample by Exhaustive Search", Dana Jansens Abstract: A thirty-year-old conjecture states that no Gray code can be created which has dimension n, with 2^n unique strings, by a successor function that always reads less than O(n) bits. Generally, it has been thought that a successor function must read exactly n bits in the worst case. This has been known for n <= 4. I show my attempts to extend the proof to some small dimensions > 4, and the surprising result that I uncovered. "Identification of Novel Protein Complexes through Pseudo Clique Enumeration", Andrew Schoenrock Protein complexes are made up of groups of proteins who interact with one another to perform some biological function. These complexes form a cornerstone of many biological processes and are of interest to many biologists and bioinformaticians. It is the aim of this project to identify novel protein complexes based on new proteome-wide protein- protein interaction prediction graphs in the Homo Sapiens organism produced by the latest implementation of the Protein-protein Interaction Prediction Engine (PIPE3). Complexes can be identified as dense subgraphs (also known as pseudo cliques) in this graph. A brief discussion of the method of reverse search for enumerating discrete objects will lead into a description of an efficient algorithm used to enumerate all pseudo cliques of a given graph, based on reverse search. The ideas behind the algorithm will be detailed and supplemented with an example. The talk will end with a discussion of the last steps of the project that still need to be completed as well as a brief discussion of what will happen with the data afterwards. "Alternative Combinatorial Gray Codes", Samuel Cormier-Iijima Gray codes have numerous applications in a variety of fields, including error correction, encryption, databases, and puzzles. The standard Gray code is the Binary Reflected Gray Code (BRGC), but there are many other possible minimal change orderings on binary tuples as well as other combinatorial objects. These include long-run (maximal run-lengths), balanced, monotonic, and single-track Gray codes. This talk will present an overview of each of these types of codes along with the motivation behind using them. The relation of these Gray codes with certain open combinatorial problems will also be discussed.