Computer Sciences Commons^™

Cell Representations Of The Configuration Space For Planning Optimal Paths, Ajay Kannan

Dartmouth College Undergraduate Theses

This paper proposes sampling techniques to approximate the configuration space for optimal motion planning. We sample valid configurations in the workspace and construct path subconvex cells in the free configuration space. The radius of each cell is calculated using lower bounds on the robot’s minimum time to collision. Using theorems about path convexity, the shortest paths found between any two points in the decomposed space are guaranteed to be safe. Experimental results are provided for a planar arm.

Why Do Protein Structures Recur?, Rebecca G. Leong

Dartmouth College Undergraduate Theses

Protein tertiary structures exhibit an observable degeneracy in nature. This paper examines the connection between a protein motif's abundance in nature and its designability as measured by in silico methods. After generating a set of protein structures, we evaluated each structure's abundance in nature, ratio of possible contacts (contact degree) and in silico designability. Our results showed that any two or these metrics are moderately correlated. Together abundance and contact degree produced the strongest correlation with in silico designability. Our results suggest that abundance is indeed an indicator of designability. Furthermore, abundance and contact degree appear to correlate with some …

Two Algorithms For Finding Edge Colorings In Regular Bipartite Multigraphs, Patricia T. Neckowicz

Dartmouth College Undergraduate Theses

For a d-regular bipartite multigraph, an edge coloring is equivalent to a decomposition of the edge set into d perfect matchings. When d is a power of 2, we can recursively perform Euler partitions to find the perfect matchings. When d is not a power of 2, however, we eventually reach a subproblem graph of odd degree where we can no longer perform an Euler partition. We propose two different algorithms that address this case. Both algorithms make use of an auxiliary matching, called dummy edges, to make the degree of the graph even. In the first algorithm, dummy edges …

Frameshift: Shift Your Attention, Shift The Story, Tim Tregubov, Rukmini Goswami

Dartmouth College Master’s Theses

Attention is a limited resource that intrinsically dictates our perceptions, memories, and behaviors. Further, visuospatial attention correlates highly with user engagement, heart rate, and arousal. Artists and interactive game designers strive to capture and direct attention, yet even in the most carefully crafted graphic narratives viewer eye paths -- a proxy for attention -- vary up to 20 percent. Our aim is to use attentional measures to enrich graphic novel narratives.FrameShift uses eye tracking to measure reader attention and changes text and visual elements later on in the story accordingly. We have built an extensible framework for using attention to …

Trip: Tracking Rhythms In Plants, An Automated Leaf Movement Analysis Program For Circadian Period Estimation, Kathleen Greenham, Ping Lou, Sara E. Remsen, Hany Farid, C Robertson Mcclung

Dartmouth Scholarship

Background: A well characterized output of the circadian clock in plants is the daily rhythmic movement of leaves. This process has been used extensively in Arabidopsis to estimate circadian period in natural accessions as well as mutants with known defects in circadian clock function. Current methods for estimating circadian period by leaf movement involve manual steps throughout the analysis and are often limited to analyzing one leaf or cotyledon at a time.

Methods: In this study, we describe the development of TRiP (Tracking Rhythms in Plants), a new method for estimating circadian period using a motion estimation algorithm that can …

Course Insight: An Application Of Natural Language Processing In A Course Browser, Chuanqi Sun

Dartmouth College Undergraduate Theses

Course inSight integrates a course catalog with natural language processing and cloud database to provide recommendations based on the concepts extracted from a given course, revealing meaningful connections between courses that are not available through existing technologies. This paper justifies the rationale behind the project, narrates the design process, and discusses implementation details and possible improvements.

Communication Complexity Of Distributed Statistical Algorithms, James A. Brofos

Dartmouth College Undergraduate Theses

This paper constructs bounds on the minimax risk under loss functions when statistical estimation is performed in a distributed environment and with communication constraints. We treat this problem using techniques from information theory and communication complexity. In many cases our bounds rely crucially on metric entropy conditions and the classical reduction from estimation to testing. A number of examples exhibit how bounds on the minimax risk play out in practice. We also study distributed statistical estimation problems in the context of PAC-learnability and derive explicit algorithms for solving classical problems. We study the communication complexity of these algorithms.

Mcollector: Sensor-Enabled Health-Data Collection System For Rural Areas In The Developing World, Rima Narayana Murthy

Dartmouth College Master’s Theses

Health data collection poses unique challenges in rural areas of the developing world. mHealth systems that are used by health workers to collect data in remote rural regions should also record contextual information to increase confidence in the fidelity of the collected data. We built a user-friendly, mobile health-data collection system using wireless medical sensors that interface with an Android application. The data-collection system was designed to support minimally trained, non-clinical health workers to gather data about blood pressure and body weight using off-the-shelf medical sensors. This system comprises a blood-pressure cuff, a weighing scale and a portable point-of-sales printer. …

Mismorphism: A Semiotic Model Of Computer Security Circumvention (Extended Version), Sean W. Smith, R Koppel, J Blythe, V Kothari

Computer Science Technical Reports

In real world domains, from healthcare to power to finance, we deploy computer systems intended to streamline and improve the activities of human agents in the corresponding non-cyber worlds. However, talking to actual users (instead of just computer security experts) reveals endemic circumvention of the computer-embedded rules. Good-intentioned users, trying to get their jobs done, systematically work around security and other controls embedded in their IT systems. This paper reports on our work compiling a large corpus of such incidents and developing a model based on semiotic triads to examine security circumvention. This model suggests that mismorphisms---mappings that fail to …

Data Citation Practices In The Crawdad Wireless Network Data Archive, Tristan Henderson, David Kotz

Dartmouth Scholarship

CRAWDAD (Community Resource for Archiving Wireless Data At Dartmouth) is a popular research data archive for wireless network data, archiving over 100 datasets used by over 6,500 users. In this paper we examine citation behaviour amongst 1,281 papers that use CRAWDAD datasets. We find that (in general) paper authors cite datasets in a manner that is sufficient for providing credit to dataset authors and also provides access to the datasets that were used. Only 11.5% of papers did not do so; common problems included (1) citing the canonical papers rather than the dataset, (2) describing the dataset using unclear identifiers, …

Optimistic And Parallel Ising Model Estimation, James Brofos, Rui Shu

Computer Science Technical Reports

We consider a new method for estimating the structure of Ising graphical models from data. We assume that the data is observed with error, so that it is, in a sense, unreliable. We propose and investigate an ``optimistic'' estimator; that is, an approach that seeks to correct the log-likelihood objective function when some amount of the data is known to be mismeasured. We derive an interior point algorithm that constructs our estimator efficiently, and demonstrate that it leads naturally to a parallel procedure for recovering the graphical structure of Ising models. We show that the optimistic estimator has performance comparable …

Information-Theoretic Limits For Density Estimation, James Brofos

Computer Science Technical Reports

This paper is concerned with the information-theoretical limits of density estimation for Gaussian random variables with data drawn independently and with identical distributions. We apply Fano's inequality to the space of densities and an arbitrary estimator. We derive necessary conditions on the sample size for reliable density recovery and for reliable density estimation. These conditions are true simultaneously for both finitely and infinitely dimensional density spaces.

Amulet: A Secure Architecture For Mhealth Applications For Low-Power Wearable Devices, Andrés Molina-Markham, Ronald Peterson, Joseph Skinner, Tianlong Yun, Bhargav Golla, Kevin Freeman, Travis Peters, Jacob Sorber, Ryan Halter, David Kotz

Dartmouth Scholarship

Interest in using mobile technologies for health-related applications (mHealth) has increased. However, none of the available mobile platforms provide the essential properties that are needed by these applications. An mHealth platform must be (i) secure; (ii) provide high availability; and (iii) allow for the deployment of multiple third-party mHealth applications that share access to an individual's devices and data. Smartphones may not be able to provide property (ii) because there are activities and situations in which an individual may not be able to carry them (e.g., while in a contact sport). A low-power wearable device can provide higher availability, remaining …

An Assessment Of Single-Channel Emg Sensing For Gestural Input, Travis Peters

Computer Science Technical Reports

Wearable devices of all kinds are becoming increasingly popular. One problem that plagues wearable devices, however, is how to interact with them. In this paper we construct a prototype electromyography (EMG) sensing device that captures a single channel of EMG sensor data corresponding to user gestures. We also implement a machine learning pipeline to recognize gestural input received via our prototype sensing device. Our goal is to assess the feasibility of using a BITalino EMG sensor to recognize gestural input on a mobile health (mHealth) wearable device known as Amulet. We conduct three experiments in which we use the EMG …

Diagnosis-Specific Readmission Risk Prediction Using Electronic Health Data: A Retrospective Cohort Study, Courtney Hebert, Chaitanya Shivade, Randi Foraker, Jared Wasserman, Caryn Roth, Hagop Mekhjan, Stanley Lemeshow, Peter Embi

Dartmouth Scholarship

Background: Readmissions after hospital discharge are a common occurrence and are costly for both hospitals and patients. Previous attempts to create universal risk prediction models for readmission have not met with success. In this study we leveraged a comprehensive electronic health record to create readmission-risk models that were institution- and patient- specific in an attempt to improve our ability to predict readmission. Methods: This is a retrospective cohort study performed at a large midwestern tertiary care medical center. All patients with a primary discharge diagnosis of congestive heart failure, acute myocardial infarction or pneumonia over a two-year time period were …

On Opportunity Cost Bounds For The Knowledge Gradient, James Brofos

Computer Science Technical Reports

We prove an upper bound on the cumulative opportunity cost of the online knowledge gradient algorithm. We leverage the theory of martingales to yield a bound under the Gaussian assumption. Using results from information theory we are further able to provide asymptotic bounds on the cumulative opportunity cost with high probability.

Methods For Efficient Object Categorization, Detection, Scene Recognition, And Image Search, Alessandro Bergamo

Dartmouth College Ph.D Dissertations

In the past few years there has been a tremendous growth in the usage of digital images. Users can now access millions of photos, a fact that poses the need of having methods that can efficiently and effectively search the visual information of interest. In this thesis, we propose methods to learn image representations to compactly represent a large collection of images, enabling accurate image recognition with linear classification models which offer the advantage of being efficient to both train and test. The entries of our descriptors are the output of a set of basis classifiers evaluated on the image, …

Cutting Wi-Fi Scan Tax For Smart Devices, Tianxing Li

Dartmouth College Master’s Theses

Today most popular mobile apps and location-based services require near always-on Wi-Fi connectivity (e.g., Skype, Viber, Wi-Fi Finder). The Wi-Fi power drain resulting from frequent Wi-Fi active scans is undermining the battery performance of smart devices and causing users to remove apps or disable important services. We collectively call this the scan tax problem. The main reason for this problem is that the main processor has to be active during Wi-Fi active scans and hence consumes a significant and disproportionate amount of energy during scan periods. We propose a simple and effective architectural change, where the main processor periodically computes …

Shared Roots: Regularizing Deep Neural Networks Through Multitask Learning, Piotr Teterwak

Dartmouth College Undergraduate Theses

In this paper, we propose to regularize deep neural nets with a new type of multitask learning where the auxiliary task is formed by agglomerating classes into super-classes. As such, it is possible to jointly train the network on the class-based classification problem AND super-class based classification problem. We study this in settings where the training set is small and show that , concurrently with a regularization scheme of randomly reinitializing weights in deeper layers, this leads to competitive results on the ImageNet and Caltech-256 datasets and state-of-the-art results on CIFAR-100.

3dflow: Continuous Summarization Of Mesh Editing Workflows, Jonathan D. Denning, Fabio Pellacini

Computer Science Technical Reports

Mesh editing software is continually improving allowing more detailed meshes to be create efficiently by skilled artists. Many of these are interested in sharing not only the final mesh, but also their whole workflows both for creating tutorials as well as for showcasing the artist's talent, style, and expertise. Unfortunately, while creating meshes is improving quickly, sharing editing workflows remains cumbersome since time-lapsed or sped-up videos remain the most common medium. In this paper, we present 3DFlow, an algorithm that computes continuous summarizations of mesh editing workflows. 3DFlow takes as input a sequence of meshes and outputs a visualization of …

Crosscomp: Comparing Multiple Artists Performing Similar Modeling Tasks, Jonathan D. Denning, Fabio Pellacini

Computer Science Technical Reports

In two previous papers, we have focused on summarizing and visualizing the edits of a single workflow and visualizing and merging the edits of two independent workflows. In this paper, we focus on visualizing the similarities and dissimilarities of many workflows where digital artists perform similar tasks. The tasks have been chosen so each artist starts and ends with a common state. We show how to leverage the previous work to produce a visualization tool that allows for easy scanning through the workflows.

Sculptflow: Visualizing Sculpting Sequences By Continuous Summarization, Jonathan D. Denning, Fabio Pellacini, Jiawei Ou

Computer Science Technical Reports

Digital sculpting is becoming ubiquitous for modeling organic shapes like characters. Artists commonly show their sculpting sessions by producing timelapses or speedup videos. But the long length of these sessions make these visualizations either too long to remain interesting or too fast to be useful. In this paper, we present SculptFlow, an algorithm that summarizes sculpted mesh sequences by repeatedly merging pairs of subsequent edits taking into account the number of summarized strokes, the magnitude of the edits, and whether they overlap. Summaries of any length are generated by stopping the merging process when the desired length is reached. We …

A Wearable System That Knows Who Wears It, Cory Cornelius, Ronald Peterson, Joseph Skinner, Ryan Halter, David Kotz

Dartmouth Scholarship

Body-area networks of pervasive wearable devices are increasingly used for health monitoring, personal assistance, entertainment, and home automation. In an ideal world, a user would simply wear their desired set of devices with no configuration necessary: the devices would discover each other, recognize that they are on the same person, construct a secure communications channel, and recognize the user to which they are attached. In this paper we address a portion of this vision by offering a wearable system that unobtrusively recognizes the person wearing it. Because it can recognize the user, our system can properly label sensor data or …

Garden Of Eden: Software Packages For The Generation And Rendering Of Visually Realistic Trees And Forests, William B. Jackson

Computer Science Technical Reports

Garden of Eden is an exercise in procedural generation of lifelike worlds. It randomly generates a forest scene of realistically shaped and proportioned asymmetric trees on top of a simple topographical map. This map is then rendered in an HTML5 3D canvas, with support for user navigation. The end result of this project is a sort of game, though without any goal, narrative, or creative purpose. It is simply a static rendering of a natural environment, open for exploration, closed to manipulation, exploring how users find visual pleasure and meaning in virtual environments. The passive interaction of the user is …

Constant Rmr Transformation To Augment Reader-Writer Locks With Atomic Upgrade/Downgrade Support, Jake S. Leichtling

Dartmouth College Undergraduate Theses

The reader-writer problem [1] seeks to provide a lock that protects some critical section of code for two classes of processes: readers and writers. Multiple readers can have access to the critical section simultaneously, but only one writer can have access to the critical section to the exclusion of all other processes. The difficulties in solving the reader-writer problem lie not only in developing a correct and efficient algorithm, but also in rigorously formulating the desirable properties for such an algorithm to have. Bhatt and Jayanti accomplished both of these tasks for several priority variants of the standard reader-writer problem …

Chain Match: An Algorithm For Finding A Perfect Matching Of A Regular Bipartite Multigraph, Stefanie L. Ostrowski

Dartmouth College Undergraduate Theses

We consider the problem of performing an edge coloring of a d-regular bipartite multigraph G = (V, E). While an edge coloring can be found by repeatedly performing Euler partitions on G, doing so requires that the degree of G be a power of 2. One way to allow the Euler partitioning method to continue in cases where d is not a power of 2 is to remove a perfect matching from the graph after any partition that results in a graph with an odd degree. If this perfect matching can be identified in O(E) time, we can maintain the …

Stylecheck: An Automated Stylistic Analysis Tool, Alexander P. Welton

Dartmouth College Undergraduate Theses

StyleCheck is a user-friendly tool with multiple functions designed to aid in the production of quality writing. Its features include stylistic analysis (on both document-wide and individual-sentence scales) and spelling and grammar check, as well as generating suggested replacements for all types of errors. In addition, StyleCheck includes the capability to identify the famous author (out of a limited corpus) with the style most similar to the user's. The source code for StyleCheck is available online at: https://github.com/alexpwelton/StyleCheck

Zebra: Zero-Effort Bilateral Recurring Authentication (Companion Report), Shrirang Mare, Andres Molina-Markham, Cory Cornelius, Ronald Peterson, David Kotz

Computer Science Technical Reports

We describe and evaluate Zero-Effort Bilateral Recurring Authentication (ZEBRA) in our paper that appears in IEEE Symposium on Security and Privacy, May 2014. In this report we provide a more detailed comparative evaluation of ZEBRA against other related authentication schemes. The abstract of the paper follows. Common authentication methods based on passwords, tokens, or fingerprints perform one-time authentication and rely on users to log out from the computer terminal when they leave. Users often do not log out, however, which is a security risk. The most common solution, inactivity timeouts, inevitably fail security (too long a timeout) or usability (too …

Modflows: Methods For Studying And Managing Mesh Editing Workflows, Jonathan D. Denning

Dartmouth College Ph.D Dissertations

At the heart of computer games and computer generated films lies 3D content creation. A student wanting to learn how to create and edit 3D meshes can quickly find thousands of videos explaining the workflow process. These videos are a popular medium due to a simple setup that minimally interrupts the artist’s workflow, but video recordings can be quite challenging to watch. Typical mesh editing sessions involve several hours of work and thousands of operations, which means the video recording can be too long to stay interesting if played back at real-time speed or lose too much information when sped …

Zebra: Zero-Effort Bilateral Recurring Authentication, Shrirang Mare, Andrés Molina-Markham, Cory Cornelius, Ronald Peterson, David Kotz

Dartmouth Scholarship

Common authentication methods based on passwords, tokens, or fingerprints perform one-time authentication and rely on users to log out from the computer terminal when they leave. Users often do not log out, however, which is a security risk. The most common solution, inactivity timeouts, inevitably fail security (too long a timeout) or usability (too short a timeout) goals. One solution is to authenticate users continuously while they are using the terminal and automatically log them out when they leave. Several solutions are based on user proximity, but these are not sufficient: they only confirm whether the user is nearby but …