|
|
Given the proper amount of time, there would be a large number of things that I would research. Because time is limited, I have not been able to properly research very many topics to the degree that they deserve. Below is a listing of papers and or research that I've done since I started college in the fall of 1998, in reverse-chronological order. A large portion of the papers and/or research done was for courses that I have taken.
2006:
* Accepted to Graph Drawing 2006, "Trees with Convex Faces and Optimal Angles" (preprint available): We consider drawings of trees in which all edges incident to leaves can be extended to infinite rays without crossing, partitioning the plane into infinite convex polygons. Among all such drawings we seek the one maximizing the angular resolution of the drawing. We find linear time algorithms for solving this problem, both for plane trees and for trees without a fixed embedding. In any such drawing, the edge lengths may be set independently of the angles, without crossing; we describe multiple strategies for setting these lengths.
* Accepted to SWAT 2006, "The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems" (preprint available, conference version available, pp 400-410) : We consider problems where we are given a rooted tree as input, and must find a subtree with the same root, optimizing some objective function of the nodes in the subtree. When the objective is the sum of linear function weights of a parameter, we show how to list all optima for all parameter values in O(nlogn) time. This can be used to solve many bicriterion optimizations problems in which each node has two values xi and yi associated with it, and the objective function is a bivariate function f(Σxi,Σyi) of the sums of these two values. When f is the ratio of the two sums, we have the Weighted Maximum-Mean Subtree Problem, or equivalently the Fractional Prize-Collecting Steiner Tree Problem on Trees; we provide a linear time algorithm when all values are positive, improving a previous O(nlogn) solution, and prove NP-completeness when certain negative values are allowed.
2004:
* Added memory simulation with OS-level virtual-memory paging to the SimpleSim 3.0c processor simulator for Modern Microprocessors (ICS 241B, Alex Viedenbaum). Includes LRU, FIFO and Random page replacement strategies, main memory and disk access delays, memory and page size options, and memory hit/miss statistics.
2003:
* Designed and built a variant of Lempel-Ziv and Huffman coding for Data Compression. Findings: Dynamically growing a dictionary like Lempel-Ziv, but coding like huffman is a good beginning, but choosing codes in a locally optimal way (rather than greedy) is slow. More research is needed.
* Term paper for Parallel Computing, wrote about the current trends in high-performance computing. Findings: Custom-designed processors cannot be beat for special purpose computations, standard general-purpose processors are good for designing other processors, but the future lies in reconfigurable processors, similar to those produced by Xilinx. If/when you can compile C/C++ to be used on a reconfigurable processor with little to no changes, the "problem" of insufficient processing power will be gone.
* Research project for Ubiquitous Computing. Findings: Having augmented reality does not require that people lose their privacy. With a minimal investment in currently-available off-the-shelf hardware, it is possible for organizations and people to have secure augmented reality for pennies per day without having to trust a third party.
2002:
* Senior Capstone Project. I developed an MPI work-alike for Python, in Python, using asynchronous socket communication. Findings: algorithms can be sped up using a pure Python Multi-Processor programming library. The library has not been released due the poor quality of the code. When time allows, it will be rewritten and released.
* Project for Computer Networks. Findings: Randomly distributing packets across equivalent or near-equivalent paths on a network is a reasonable way to keep traffic flows balanced on certain sparse networks.
* Paper for Computer Networks. Findings: There are a handful of IP-level security features that could go a long ways toward making various flood attacks impossible to execute (none are currently in use on the internet).
* Project for Databases, designed and built a database using the Python programming language. Findings: A simple record-based database is very easy to design and build using Python, even ones that include modifiable schemas. Database (and/or hard-disk) defragmentation is trivially (and near-optimally) solved using simple algorithms.
2001:
* Paper for International Perspectives of Gender, Race and Class. Findings: There are few, if any, positive words for 'woman' in the English language, which may be either the result or cause of women being relative second class citizens in our culture.
2000:
* Project for Theory of Computation, wrote a prime number enumerating turing machine.
* Research Project for Intro to Lesbian and Gay Studies, wrote a paper examining the trends in crimes against GLBTQ individuals in the last 10 years. Findings: While the quantity of crimes against GLBTQ individuals is on a decline, the extremity of the crimes have increased. Conclusion: People are becoming more accepting of GLBTQ people, but those who aren't accepting, are feeling threatened and lashing out with more violence.
* Project for Intro to Artificial Intelligence, wrote some software and a paper on discovering lines in images. A simple mask was used and found to work fairly well. Perhaps a Radon Transform on the resulting masked image would provide decent vector-lined output.
1999:
* Project for Computer Architecture, a simple looping assembly language instruction for the Integer Java Virtual Machine simulator. My instruction was 5 cycles, other students' were 20+. Findings: If you are willing to lose generality for the sake of speed, much can be gained.
1998:
* Term Paper for Philosophy of Psychology, a summary of ideas and methods that defined psychology from Socrates and Plato to Gestalt. Findings: 7 chapters written by a first-quarter undergrad is too damn much.
|
|