|Berry, Daniel (University of Waterloo)
Requirements Analysis in Real Life:
Why for sure, there will never be a
|An examination of the difficulties determining the requirements for some real-life systems, some with software and some without, makes it clear why there will never be a software engineering silver bullet.|
|Fill, James Allen (John Hopkins)
Probabilistic Analysis of QuickSort:
|We will begin by reviewing the operation of the ubiquitous randomized sorting algorithm QuickSort, invented by Tony Hoare in the early 1960s. We will then survey the probabilistic analysis of QuickSort, from the solution of a simple divide-and-conquer recurrence relation for the expected value of the number of key comparisons K_n needed to sort n distinct keys (items), to three techniques for establishing and characterizing a limit distribution for normalized K_n, to rates of convergence to the limit distribution, to a recent more realistic analysis that treats keys as symbol strings and measures the execution cost of QuickSort as the number of symbol comparisons. If time permits, we will also discuss the closely related QuickSelect selection (order-statistic finding) algorithm.
| Plaisted, David (University of North Carolina)
Survey of Instance-Based Theorem
|Since Robinson's 1965 paper, resolution has dominated theorem proving in
first-order logic. However, now there is a shift towards propositional type
techniques such as those used in modern high-performance satisfiability
testers, and these techniques are being applied to first-order logic, with a
significant increase in power. These developments will be discussed.
| Dershowitz, Nachum (Tel-Aviv University)
|I will describe some of the highlights of Ed's and my adventures with
calendrical algorithms over the past twenty-five years.
| Kuszmaul, Chris (Palo Alto High School)
Binary Heaps Implement
Efficient Mergable Priority Queues,
And other Stories
|A small modification to a standard Binary Heap decreases the amortized
merge operation time from O(n) to O(log^2 n). Meanwhile, high school
students stand to learn computer science, but there are some barriers to this that are not solved with curriculum design or even recruitment of talented teachers.
| Wong, Martin (University of Illinois,
Algorithmic Aspects of VLSI Physical
|In the early 1980s, Prof. Ed Reingold briefly worked in the area of physical
design of VLSI when the field was still in its infancy. Although significant
progresses have been made in the past 30+ years, challenges still lie ahead due to the rapid advances of integrated circuit technologies. In this talk, I will present some recent challenges and solutions in VLSI physical design.
|Roberto Tamassia (Brown University)
Secure Tree Drawin in the Cloud: Privately Analyzing and Visualizing Hierarchical Datasets
|The problem of constructing drawings of trees that satisfy layout properties and constraints associated with effective visualizations has been extensively studied. Early work on this subject includes two seminal papers by Edward M. Reingold: “Tidier Drawing of Trees” (with John S. Tilford, 1981) and “The Complexity of Drawing Trees Nicely” (with Kenneth J. Supowit, 1982). We study the problem of drawing trees in a cloud-computing context where a client outsources the storage of the tree and computation of the drawing to a cloud server. We show that a number of classic drawing algorithms can be implemented in a privacy-preserving manner in such a cloud framework. Namely, we present data-oblivious drawing algorithms that enable the server to efficiently construct the drawing of a tree and yet learn nothing about the tree besides the number of nodes.|
Picking up the Pieces
|We consider the problem of uniquely putting together a string from its overlapping substrings, a problem with diverse applications to synchronization of networking metadata, DNA sequencing, and encryption of biometric data. We will briefly discuss this problem's connections to the set reconciliation problem and Reingold’s hidden hand in its solution. If time allows, we will also conduct a post-mortem on some victims of the "Reingold axe". The talk will be conducted in "Reingold style".|
On the Distance Between Labelled Triangulations
|A Diagonal Flip in a triangulated planar graph removes an edge from the graph, and adds a new one in such a way that the result is still triangulated and planar. The question we consider in this talk is: Given two such triangulations of n vertices (labeled 1, 2, ... n) how many such diagonal flips does it take to convert one into the other? We give an algorightm for this problem that does O(n log n) flips. We also prove that there exists pairs of triangulations that require Omega(n log n) flips. This is joint work with Robert Tarjan and William Thurston.|
Matchings, Random Walks and
|The maximum matching problem is among the most well-studied problems in combinatorial optimization with many applications. The matching problem is well-known to be solvable in polynomial time. However, as large data sets become more prevalent, there is a growing interest in sublinear algorithms --- these are algorithms whose resource requirements are substantially smaller than the size of the input on which they operate. In this talk, we will describe some results that illustrate surprising effectiveness of randomization in solving exact and approximate matching problems in sublinear space or time.|
The Fast Marching Algorithm for Image Segmentation
|The fast marching algorithm allows to solve efficiently the so called Eikonal partial differential equation. This algorithm, equivalent to the Tsitsiklis
algorithm can be seen as a continuous extension of the well known Dijkstra Algorithm. It allows to find minimal cost path drawn on an image. We will show various applications, like vessel extraction in medical images.
Dynamic Social Network Analysis of Zebras and other Animals
|Every network analysis software package has a Fruchterman-Reingold (1991) network layout option for static networks. But what about networks that change over time? Not only we don't know how to draw them, we know very few ways to analyze them. Over the last 15 years, methods for analysis of dynamic networks have started to be developed. I will describe out contribution to the field and the applications of dynamic network analysis to understanding social behavior of zebras, baboons, humans, and other animals.|
|Sanjiv Kapoor (Illinois Tech)||In this talk we discuss the behavior of selfish routing in networks where traffic
is heterogenous and when traffic is differentiated. While the nature of selfish routing has been studied in homogenous traffic and the Price of Anarchy has been shown to be bounded, we show that these bounds worsen when traffic is heterogenous. This has applications in transportation studies as well. We also illustrate the inefficiencies of bandwidth partitioning. The analysis of the models has implications in the debate on net-neutrality.