6th Undergraduate Research Symposium (2012)

Held 25 April 2012 in 011 Sitterson Hall

Voronoi Diagrams and Geometric Transformations

Steven Love, supervised by Jack Snoeyink and Dave Millman

We illustrate the power of transforming one problem into another, specifically in creating a Voronoi diagram, through solving the nearest-neighbor problem. We are able to meet restrictions on time, space, and arithmetic precision by transforming the nearest-neighbor problem into computing a series of discrete upper envelopes. Our algorithm is faster than the de facto standard algorithm used by MATLAB, and we can guarantee correctness, because we only rely on two degrees of arithmetic precision. Voronoi diagrams have applications in path planning, database queries, wireless network distribution, art and more. Due to the transformable nature of the Voronoi diagram, our algorithm has implications for other similar geometric problems like Delaunay triangulation.

Steven Love is an industrious sophomore computer science major. He enjoys working all the time, magnets, interior design, sandwich crafting, bike riding, group showers, receipt collecting, mirrors, and public speaking.

Yet Another Animation System (YAAS)

William Hipschman, supervised by Prasun Dewan

We present Yet Another Animation System (YAAS), a framework that automatically generates pattern-based algorithm animations. By defining key methods of observable data structures as interesting events, we can respond to any change in the data structure by handling fired events, and so create animations for any algorithm comprised of such operations. Pairing the handling of these events with graphical manipulation, we are able to create useful animations based solely off of algorithm code. Our system improves programmer tools by providing fully-reversible animation, user-defined data support, and high levels of customizability, while maintaining strict separation of concern between components.

William Hipschman is a senior computer science major from Waupaca, Wisconsin. He has worked under Prasun Dewan for the past three years. In his spare time, William enjoys playing racket sports, ultimate Frisbee, and soccer. He has been known to guffaw heartily at a good pun.

SIML – A template language for an extensible data driven decision support system to support policy making

Ren Bauer, supervised by Hye-chung Kum

Social policy continues to be an area in which changes are expensive to implement and difficult to evaluate. Fortunately, the increased aggregation of data in this and similar fields provides an opportunity to create dynamic decision support systems (DSS) to guide policy makers when designing potential solutions. However, the majority of these systems utilize complex model-based designs, which can be difficult to transfer from one precise scenario to another. Due to constantly changing environments and unclear goals, light weight systems that can be easily extended is an important feature of decision support systems that support policy making. In this paper, we discuss the design and implementation of a dynamic data-driven decision support system, and compare this method to that of designing and implementing a model-driven system. We propose a model that makes use of templates and code generation in order to be optimized for extensibility. Finally, we provide an overview of the differences between using such a system and a typical model driven system, and suggest directions for future work with the goal of providing a more active decision support functionality.

Ren Bauer is a junior computer science major from Fayetteville, NC. He’s had the pleasure of working under the mentorship of Dr. Hye-Chung Kum since the Summer after his sophomore year, and is looking forward to an internship at Verisign this summer. Ren likes to play ultimate frisbee and just chill with his dog, and he’s probably going to fail all his classes this semester! So, go check him out!

Modeling UDP Traffic for Fun & Profit

Rebecca Crabb, supervised by Jay Aikat and Kevin Jeffay

In previous work at UNC, the full TCP application workload was modeled and regenerated in the lab. In this previous analysis, the UDP traffic was ignored. I defined a model to represent the full UDP application workload captured on any production network link. Being able to model a UDP application workload will allow experiments to be run on different networks with consistant, realistic application workloads.

Rebecca Crabb is a senior from Omaha, NE, majoring in CS and minoring in Entrepreneurship. This past summer, Rebecca interned at Google where she will return next year as a product manager. Rebecca played for the Women’s Soccer team here at UNC. Is it time for the free food yet?

Revisiting TCP Round-Trip Times

Wai Yau, supervised by Jay Aikat and Kevin Jeffay

TCP Round-trip time (RTT) plays an important role in communication between network applications. Simplistically speaking, RTT is a constant factor in network traffic that can be expressed as 2 times propagation delay. However, past research shows that there is a significant amount of variability for RTTs. In my research, I analyzed packet traces collected at the ISP link of UNC from 2004 and 2008 and compared with the findings from “Variability in TCP Round-trip Times,” a 2003 paper that highlights the existence of variability in TCP RTTs. It turns out that both the magnitude and variability in RTTs have been decreasing over the years, possibly the outcome of advancement in networking technologies.

I’m Wai Yau, a senior in the department. I’m a fairly simple person, and it doesn’t take much for me to be happy in life. The more I learn, the more I thrive.

Characterizing Modern Web Traffic

Stephanie Zolayvar, supervised by Jay Aikat and Kevin Jeffay

The web and how we use it have changed dramatically in the last decade, and a modern picture of web traffic is necessary for the effective networking testbeds, application development, and network management. This study provides a characterization of modern web traffic through statistical analysis of TCP headers, with specific attention to different web protocols.

Stephanie Zolayvar is a senior from Burlington, NC, going to Google in Seattle after graduation. She broke two cinder blocks at her black belt test and recommends steak cooked over a campfire.