Abstract: When representing a sequence in a data structure,
it seems we might need O(k) time to reverse a substring of length k.
However, by encoding our sequence in a "Boustrophedon" linked list (a
doubly linked list in which each node cannot distinguish between its
forward and backward pointers), we allow substring reversals in O(1)
time. I will discuss the operation and some interesting applications
of this approach (e.g., enumerating permutations in constant
worst-case time each), based on an original paper by Aaron Williams.
| SPRING 2012 | ||
|---|---|---|
| Date | Speaker | Topic |
| 4/20/2012 | Aditya Sriram | Modeling Causality and Making Predictions |
| 4/13/2012 | Brian Dean | How to Hang a Picture in Polynomial Time |
| 4/6/2012 | Rommel Jalasutram | Aggregating Inconsistent Information. Ranking and Clustering |
| 3/30/2012 | Brian Dean | Simple Algorithms for Approximate Order Statistics |
| 3/9/2012 | Brian Dean | Feature Selection via Linear Programming |
| 3/2/2012 | Brian Dean | Introduction to Streaming Algorithms |
| 2/24/2012 | Brian Dean | Sparse Fourier Transforms |
| 2/17/2012 | Brian Dean | Parametric Search |
| 2/10/2012 | Rommel Jalasutram | Popular Matchings |
| 2/3/2012 | Brian Dean | High-Multiplicity Scheduling Problems |
| 1/27/2012 | Brian Dean | The Benefit of Doing Tasks in Random Order |
| 1/20/2012 | Sam Bryfczynski | Using Clustering and Visualizations to Analyze Student Work |
| FALL 2011 | ||
| Date | Speaker | Topic |
| 12/02/2011 | Sumod Mohan | Gomory-Hu Clustering and Application to Image Segmentation |
| 11/18/2011 | Rommel Jalasutram | Building the Cactus of a Graph |
| 11/11/2011 | Brian Dean | Estimating Network Reliability |
| 11/4/2011 | Brian Dean | Maximum Adjacency Orderings and Minimum Cuts |
| 10/21/2011 | Brian Dean | Realistic 3D Cell Cytoskeletal Reconstruction from Machine Vision Analysis of Confocal Microscopy Images |
| 10/14/2011 | Rommel Jalasutram | Very Simple Methods for All Pair Network Flow Analysis |
| 10/07/2011 | Brian Dean | Global Minimum Cuts in Planar Graphs |
| 9/30/2011 | Brian Dean | Algorithms for Sports |
| 9/23/2011 | Brian Dean | Clustering with Parametric Minimum Cuts |
| 9/16/2011 | Brian Dean | On-Line Load Balancing |
| 9/9/2011 | Brian Dean | Community Structure in Signed Networks |
| 9/2/2011 | Brian Dean | Computing the Girth of a Graph |
| 8/26/2011 | Brian Dean | Selected Problems from Recent Informatics Olypiads |
| SPRING 2011 | ||
| Date | Speaker | Topic |
| 4/29/2011 | Elizabeth Matthews | Procedural Generation of Story-Driven Maps |
| 4/22/2011 | Brian Dean | Fully-Dynamic Graph Connectivity |
| 4/15/2011 | Aditya Sriram | Learning Topologies of Graphical Models using Parallel Interactive Markov Chain Monte Carlo methods |
| 4/8/2011 | Ben Cousins | Jane: A New Tool for the Cophylogeny Reconstruction Problem |
| 4/1/2011 | Brian Dean | Maintaining Dynamic Strongly-Connected Components and Transitive Closure in Directed Graphs |
| 3/11/2011 | Chad Waters | Randomized Reduction |
| 3/4/2011 | Gift Kositwattanarerk | Modern Algorithms for the Decoding Problem |
| 2/25/2011 | Rommel Jalasutram | Weighted On-Line Bipartite Matching |
| 2/18/2011 | Raghuveer Mohan | 2D Van Emde Boas Structures |
| 2/11/2011 | Chad Waters | Optimal Pattern Matching in LZW-Compressed Strings |
| 2/4/2011 | Matt Dabney | Approximating the Highway Problem |
| 1/28/2011 | Brian Dean | Heuristics for Large-Scale Assignment Problems |
| 1/21/2011 | Brian Dean | Matching a Million Points |
| 1/14/2011 | Brian Dean | Auction Algorithms for Optimal Matchings |
| FALL 2010 | ||
| Date | Speaker | Topic |
| 12/3/2010 | Brian Dean | Approximation and Compression in Shortest Path Computation |
| 11/19/2010 | Shelby Darnell | A Genetic Algorithm for Feature Reduction on Finger Shape and Dorsum Surface Features |
| 11/5/2010 | Rommel Jalasutram | Multiple-Source Shortest Paths in Planar Graphs |
| 10/29/2010 | Raghuveer Mohan | A Simpler Implementation and Analysis of Chazelle’s Soft Heaps |
| 10/22/2010 | Brian Dean | Parabolic Lifting, Etc. |
| 10/15/2010 | Brian Dean | Encoding Numbers in Binary without Wasting Space |
| 10/1/2010 | Brian Dean | Double Displacement and Deterministic Perfect Hash Table Construction |
| 9/24/2010 | Rommel Jalasutram | Better and Simpler Approximation Algorithms for the Stable Matching Problem |
| 9/17/2010 | Brad Paynter | An Optimization Approach to a Geometric Packing Problem |
| 9/10/2010 | Brian Dean | Maximum Flows in Planar Graphs II |
| 9/3/2010 | Brian Dean | Maximum Flows in Planar Graphs I |
| 8/27/2010 | Brian Dean | Eulerian Augmentation |
| SPRING 2010 | ||
| Date | Speaker | Topic |
| 4/23/2010 | Brian Dean | Binary Search |
| 4/16/2010 | Brian Dean | Algorithms for the Optimal Staying up Late Problem |
| 4/9/2010 | Rommel Jalasutram | Self-Stabilizing Depth-First Search |
| 4/2/2010 | Shelby Darnell | Reducing 3D Finger Surface Features Using Computational Intelligence |
| 3/26/2010 | Brian Dean | Path Packing, Covering, and Cutting in Trees |
| 3/12/2010 | Brian Dean | Splay Trees, Dynamic Trees, and Tango Trees |
| 3/5/2010 | Brian Dean | Random Walks, Sampling, and Approximate Counting |
| 2/26/2010 | Sumod Mohan | Computer Vision and Graph Cuts |
| 2/19/2010 | Rommel Jalasutram | The Complexity of Computing a Nash Equilibrium |
| 2/12/2010 | Brian Dean | System-Optimal Versus User-Optimal Network Routing |
| 2/5/2010 | Raghuveer Mohan | New Algorithms for Building Cartesian Trees |
| 1/29/2010 | Brian Dean | Optimal Stable Marriage Algorithms |
| 1/22/2010 | Brian Dean | Adaptive Stable Marriage Algorithms |
| 1/15/2010 | Wayne Goddard | Master-Slave Self-Stabilizing Algorithms |
| 1/8/2010 | Brian Dean | Parametric Maximum Flows and Graph Clustering |
| FALL 2009 | ||
| Date | Speaker | Topic |
| 12/4/2009 | Brian Dean | Algorithmic Games |
| 11/20/2009 | Pradip Srimani | Recent Results in Self-Stabilizing Algorithms |
| 11/13/2009 | Brian Dean | Fair and Unfair Flow Allocations |
| 11/6/2009 | Brian Dean | My Favorite Algorithmic Programming Competition Problems |
| 10/30/2009 | Brian Dean | Algorithms for Problems on Regular Bipartite Graphs |
| 10/16/2009 | Brian Dean | A Simple Method for Analyzing Randomized Divide-and-Conquer Algorithms |
| 10/2/2009 | David Jacobs | A Self-Stabilizing Algorithm for Maximal Matching |
| 9/18/2009 | Steve Hedetniemi | A New Look at an Old Self-Stabilizing Algorithm for {2}-Domination |
| 9/11/2009 | Brian Dean | Encoding Connectivity in Graphs |
| 9/4/2009 | Brian Dean | Reconstructing Edge-Disjoint Paths |
| 8/28/2009 | Brian Dean | Shortest Path Computation in Planar Graphs |
| SPRING 2009 | ||
| Date | Speaker | Topic |
| 4/17/2009 | Brian Dean | Time-Dependent Shortest Path and Network Flow Problems |
| 4/10/2009 | Brian Dean | Approximating Shortest Path Distances and Diameter |
| 4/3/2009 | Brian Dean | New Approaches for Learning Greedy Orderings |
| 3/27/2009 | Wayne Goddard | Self-Stabilizing Algorithms for Domination with a Distributed Daemon |
| 3/13/2009 | Brian Dean | Shortest Paths and Matrix Multiplication |
| 3/6/2009 | Steve Hedetniemi | NP-completeness Methods of Alice McRae: A Tutorial on NP-completeness |
| 2/27/2009 | Brad Paynter | An Optimization Approach to a Geometric Packing Problem |
| 2/20/2009 | John Dabney | An Efficient Algorithm for Verifying Stable Matchings |
| 2/13/2009 | Brian Dean | Stable Allocation Problems and Algorithms |
| 2/6/2009 | Brian Dean | Similarity Computation Based on Connectivity |
| 1/30/2009 | Brian Dean | Approximating the Bounded-Degree Minimum Spanning Tree Problem |
| 1/23/2009 | Brian Dean | Minimum-Degree Spanning Trees |
| 1/16/2009 | Brian Dean | Rank-Sensitive Priority Queues |
| 1/9/2009 | Brian Dean | Min-Max Theorems in Discrete Optimization |
| FALL 2008 | ||
| Date | Speaker | Topic |
| 12/5/2008 | Jeremy Carter | Folding and Cutting Paper |
| 11/21/2008 | Brian Dean | Using Linear Programming to Find Bugs in Computer Programs and Humans |
| 11/14/2008 | Brian Dean | Semidefinite Programming and Approximation Algorithms |
| 11/7/2008 | Brian Dean | Finding a Central Element |
| 10/31/2008 | Daniela Ferrero | Directed Hypergraphs as Interconnection Networks Models |
| 10/24/2008 | Brian Dean | Lagrangian Relaxation, Parametric Optimization, and Spanning Tree Problems |
| 10/17/2008 | David Jacobs | Three Ways to Compute the Characteristic Polynomial of a Tree |
| 10/10/2008 | Brian Dean | Parametric Search and Ratio Objectives |
| 9/26/2008 | Pradip Srimani | Introduction to Distributed Localized Graph Algorithms |
| 9/19/2008 | Brian Dean | Unsplittable Bipartite Matchings |
| 9/12/2008 | Brian Dean | Convex Bipartite Matchings |
| 9/5/2008 | Brian Dean | On-Line Bipartite Matching |
| 8/29/2008 | Brian Dean | Popular Matchings |