Current Projects

My current projects list is out of control. I have replicated it below, with project statuses.

Internet Topology: It got me a PhD, and now its just sitting there. I haven’t touched it since my talk @Google, but it needs to get (re)written up and submitted to an actual journal. Status: only barely able to look at it without flashbacks. Let it sit for a bit longer.
Calculus Data Mining: I stole an idea from Titus Winters and used data mining techniques on student assessment data to build decision trees to discover “key concepts” that distinguish bad students from good students. This needs to get written up into a small note and sent … somewhere. Next step: Figure out where to send this, so that the writing can be tuned to the audience.
Whole program animation: Work with Sandro Badame (former student). We have built 90% of a system which can animate the execution of entire programs. It looks like we managed to do it in such a way that you get algoviz for free! But the system needs the last 10% which will take 90% of the work. Next step: CODE
Model for programs under memory pressure: Have an idea for how to model program behavior in the presence of large problems and virtual memory. The model is simple, but like all models it needs experimental validation. Experiments are being run, and the results will be submitted to ALENEX. Working on this (occasionally with Greg Rae). Next step: Run current experiments to completion and analyze the data. Build up the MergeSort experiment.
Growing Programs: An introduction to programming being written by me (and possibly others) with the idea in mind that programs are not written, they are not built, they are instead grown. I came up with this independently, but then read that Fred Brooks likes this metaphor as well, which made me feel like I was on the right track. This project has been stalled for quite some time. Next step: Figure out if there is demand for yet another CS1 book, albeit one with a different (and unique) approach.
24 Game: Turn the website into a little note about combinatorial enumeration and the 24 game. Initially for Math Magazine, but their acceptance rate is dismally low, so first try there and then see where else might want it. Next step: more writing.

Projects in stasis/completed:

Tree Animation: Did work with student Sandro Badame, presented it at Boca, and it is now under review. Could use some code cleanup.
Optimizing T-9 keyboards: Found out that optimizing cell phone keyboard usage is NP-complete sometimes and polynomial other times. Submitted to FUN2010, was accepted, was presented, has been published in the proceedings (and right here) Project is on GitHub.

Published 6 July 2010

Filed in

http://www.barsoom.org/ Daniel Stutzbach

Your “Growing Programs” idea could also make a good children's or high school intro-to-programming book.
http://home.manhattan.edu/~peter.boothe/ Peter Boothe

There seem to be no good HS textbooks. We have good calc textbooks, but somehow not for CS.
http://twitter.com/mathzorro Chris Hanusa

I always thought that 3 3 7 7 was one of the hardest 24 puzzles.
PS. Happy late birthday! I guess you got an Orange present.
F. Carr

pls can has “Model for programs under memory pressure” ?? kthxbye
http://home.manhattan.edu/~peter.boothe/ Peter Boothe

The model, currently undergoing experimental validation, attempts to estimate the number of page faults an algorithm will have. The basic idea is that you count the number of times in which a pointer is accessed that is not adjacent to an existing pointer. In this model, Heapsort has O(n lg n) page faults and Mergesort only has O(n). Thus, we have (possibly) figured out an easy way of assessing “cache friendliness” or “works well in the presence of virtual memory”. There's lots of algorithms that have this designed in – see streaming algorithms and cache oblivious algorithms – but I know of no ex-post-facto way of analyzing an algorithm to assess its friendliness. And certainly not with such an easy-to-analyze model.
http://www.barsoom.org/ Daniel Stutzbach

I look forward to reading this paper after you've written it. I typically have plenty of physical memory to work with, but essentially the same reasoning applies to CPU cache which is a much scarcer resource.

I am not sure I understand your adjacent-pointer heuristic. If I make a linear scan through an array, all of my pointer accesses are adjacent but wouldn't I still incur O(n) page faults?

As a minor caveat, if the list being sorted contains pointers to objects then Mergesort is also O(n log n), since the dereference points to an essentially random piece of memory.
http://home.manhattan.edu/~peter.boothe/ Peter Boothe

Replying to Dan, you've just pointed out the big flaw in the model. I don't see an easy way of dealing with your concern, but I agree it exists. The big hope is mostly that this new model will be “less wrong” than simply ignoring the problem.
http://www.barsoom.org/ Daniel Stutzbach

What if you assume that the operating system will keep in memory the most recently used p pages each of which is k bytes, where p and k are constants (i.e., not a function of n)?

Then a linear scan is O(n) page faults, Heapsort is O(n log n) page faults, and Mergesort is …

I guess Mergesort would work out to be O(n log n) page faults as well, but it'd be closer to O(n log_k n) page faults compared to Heapsort's O(n log_2 n) page faults. I see now your dilemma.
Lindsey Kuper

You gave a talk about your Ph.D. work at Google? Are there slides or a video?
http://home.manhattan.edu/~peter.boothe/ Peter Boothe

No video as far as I know, but my slides may be found at http://home.manhattan.edu/~peter.boothe/2010-03...

blog comments powered by Disqus

« BSD Heapsort is busted

Impromptus

Current Projects

About Peter

Photostream

Bookmarks feed

Twitter

Meta