Bryce Boe

Warning: This post contains pictures most people would never want to see of me, and a few vulgarities.

If you asked me just six months ago if I liked to run, I would have said “Hell no!” I have hated running for as long as I can remember, aside from the bit of running required in the sports I played. Running in PE up until tenth grade was a requirement to receive an ‘A’ in the class, and running was occasionally required training for volleyball. Running was never something I would have chose to do, thus as I drank more and exercised less throughout college I became terrifically out of shape.

Now if you ask me if I like to run, I would say, “Why yes I do”. Furthermore, if you ask if I liked to run for beer, I would respond, “Hell yes! I love running for beer!” Not only has my opinion of running changed, but also I am in the best shape of my life; well at least since starting College. So what changed?

Well, on June 27, 2009 I was introduced to a running club by the name of the Hash House Harriers, or more specifically the Santa Barbara kennel, H3SoB, which is short for the Hash House Harriers of Sant’o Barbara. A quick read through the Wikipedia entry on the Hash House Harriers will inform you the club started in 1938, Kuala Lumpur by a guy named ‘G’ in which the runners would celebrate completing the run with beer. Thankfully that tradition continued on, and I am now part of it.

Let me tell you, I was initially skeptical about the idea of running and drinking. After all, it sounds kind of counterintuitive. However, after just one run, I knew this was something exactly for me. Before I started running with the Hash House Harriers I drink quite a bit on a weekly basis and I could hardly run. After just a few weeks running with the Hash House Harriers I drank about the same however could noticeably run much further distances without tiring. Now, after nearly 6 months of running I not only can run even further distances, but believe it or not, I actually drink less on a weekly basis. I’ve become more health conscious, and further more I gained the desire to wake up on a Saturday to simply go for a run, sans beer. Running with the Hash House Harriers has changed my life.

I want to give you a little more insight on this club I am now part of as aside from the beer aspect, we are not a run-of-the-mill running club. Those that have been to what we refer to as a hash run, or simply a hash, know we don’t usually stay on well-defined trails. Rather, we often run off trail through storm drains, or through what we like to call the “shiggy stuff” which usually means low brush, weeds, or for those who are not careful, poison oak. The three things nearly every run calls for are flashlights, vessels (cups), and virgins (first time hashers).

Additionally, despite having never been part of a normal running group I would wager we are much more vulgar and thus much more fun. For instance, when the virgin’s are initiated in the club, they are informed, “After consuming your drink, you must place your vessel over your head“, at which point everyone joins in for our “Head! Who said head? I’ll take some of that, and I did” chant which goes on to talk about uprooting trees and shrubs and flowers with viking horns on our head. Wait, who said head?

Furthermore, after a runner has been with us for a decent period of time they are awarded with a sufficiently vulgar and maybe not so relevant name. Those that brought me to the hash were named Pre Med Head, who is now in medical school, and Try This Tip who cuts meat. Some other names in our group are PokeHer, Spread Eagle, Maxlode, and Picassol. After my 8th, or so, run I was given the name Cunt Cockulust because I was slightly mistaken for liking calculus. Many people in the hash just call me The Count so I go around doing my impressions of The Count from Sesame Street which usually is, “I love to count, things. Ah ah ah ah.”

Finally, we fairly often run in themes such as the bikini run, the toga run and the miniskirt run. Of those, I’ve only taken place in the bikini run as pictured below. Additionally everyone dressed up for the Halloween run, which happened to be my Virgin Lay also known as the first time I hared, or led the run; I dressed up as Super Hare which is also pictured below. The hare(s) are those that leave the pack about fifteen minutes early and using chalk and flour mark the trail everyone else runs. Hares often leave what are called checks to deceive the runners into following a false trail if they don’t pick up the real trail.

I encourage you all to seek out your local Hash House Harrier kennel and get a first hand experience. If you need more convincing check out the Washington Post article titled, “Making a Hash of Exercise“. On-On!

As a member of the Security Lab at UCSB I had the privilege to help create and run this year’s iCTF Hacking Competition. The six-year-old competition was very unique this year. Unlike CTFs seen before in which teams try to protect their services whilst attacking other teams’ services, our competition had teams deliver drive-by downloads to users for the purpose of stealing money from the users’ bank accounts.

In order to deliver drive-by downloads, the teams had to bring users to their webpage by boosting their search result on the search server for desired search terms. The users’ browsing pattern was they would search for a random word from a news site and then visit one of the resulting pages chosen according a Pareto distribution, meaning the top search result would have the highest probability of being picked with the last result the lowest.

The challenge there was to figure out how to boost the search results for particular keywords, unfortunately most of the teams simply duplicated the news site; this definitely was the safest strategy though slightly disappointing to me as I wrote the search engine code. I can claim that neither the search engine, nor the index server broke during the competition. The crawler had a few issues with some team’s pages, which I quickly fixed. I have made the search engine code available that was used in iCTF09.

In addition to writing the search engine, I wrote three challenges for the competition. The first challenge I wrote was called “The Difference”, or Forensics 4. The only information people were given was the title and the following image. The first step to solve this challenge is recognizing the image is the xkcd comic “The Difference“.

After downloading the original image one should notice the two files are different sizes with the original being 32KB and my image 46K. At this point a pixel-by-pixel comparison is required which reveals that 60 of the pixels differ and the values of the differing pixels are always larger in my image. This is where “The Difference” first comes into play by subtracting the value in my image from that of the original.

Doing so produces the results shown in the_difference_values.txt. Each line contains the difference value and the index of the pixel. The values in this list range from 33 to 41 with exceptions 10, 12 and 15. Additionally the numbers appear in groups of three where last number in the group is sometimes larger. After a bit of pondering the realization sets in that ASCII lowercase values range from 97 to 122 with space being 32 and hyphen 45. It should hit you like a ton of bricks that you need to sum the groups of three together and then convert the number to its ASCII value.

The string “sixty-four seventeen” now appears and you think you’ve solved the challenge, but no, it’s not quite done. This is where “The Difference” comes back into play in that you have to subtract these two numbers to get forty-seven. There were 596 submissions for this challenge of which 2 were correct. I’ve made the source to both generate and verify this challenge available.

The second challenge I wrote had 75 submissions and 0 correct solutions. This challenge was one of the Trivia 3 problems that had a text file and the following blurb associated with it:

Rummaging through the attic one afternoon Sally found a notebook which on the cover read ‘What happened in 95?’. On one of the pages she found the following two paragraphs of text which appeared as gibberish to her. She copied the two paragraphs down as best she could, however there were forty-five characters which she couldn’t make out from the first paragraph, which she simply neglected. What are those 45 characters?

The concept behind this problem is a one-time pad, where a completely random sequence of characters the same length as the original text is generated and then XORed with the original text to create the cipher text. At this point the original text can be discarded and recovered by XORing the cipher text with the one-time pad.

The challenge to this problem is finding where the 45 missing characters go, and what they are. One additional difficulty is figuring out that the ASCII values need to be subtracted by 95 prior to XORing so the numbers being XORed fit within 32 bits. This can be discovered by taking the min value that appears in the paragraphs which is 95 corresponding to ‘_’ and additionally the max value that appears which is 126 corresponding to ‘~’. The ‘95′ that appears in the blurb was to hint at this.

Finding the places where the characters should go requires XORing the current one-time pad with the cipher text. Plain text English with no punctuation or spaces will result at the beginning of the output until nonsense text is output. This is the point in which a character needs to be added to the one-time pad. This process needs to be repeated for all 45 characters.

At this point, XORing the one-time pad character with the desired character will result in the missing character. The solution is the concatenation of all the missing characters. This is “sdnalsilennahcehtdnuoradnuofebnacsehcnarbidun” which is “nudibranchescanbefoundaroundthechannelislands” reversed.

I’ve made the code to generate this challenge available. You’ll notice it loops until the one-time pad contains the characters of the solution. The original text is a passage from Joyce’s Dubliners that contains the oldest reference I know of to the phrase, “how goes it“. I did not write a solution for this problem.

The third and final problem I wrote was called 0xDEAFBABE or Trivia 2. A binary file (renamed to include .mid to resolve content type issues) was provided which the program file correctly informs that it is a midi audio file. By playing the file one hears about one note a second. Many teams tried to figure out what the notes were as they would be on a musical scale, such as c sharp or b flat, however that was a bit over thinking it. The solution was simply to print the ASCII character that corresponds to each midi note number. These numbers range from 0 to 127, thus they’re perfect for text. The solution to this was “does this not sound super cool?” There were 207 submissions of which 21 were correct. I have made my source to generate and verify this challenge available.

If you competed in the iCTF and attempted or completed any of these challenges let me know what you thought and how long you spent on them. I recall someone in the chat yesterday saying they were losing their sanity trying to solve “The Difference”; that gave me a good laugh

Last year I was a teaching assistant for two quarters giving me two opportunities to see how well I could share my knowledge with students. Aside from my knowledge of the material, and my ability to relate to many of the undergrads at UCSB (having previously been one myself) I had almost no preparation of how to be a TA. Our CS department requires that all TAs do three things: attend a department TA orientation, attend the campus TA orientation, and take a seminar specifically for training TAs in the CS department.

Both orientations occur the week before school starts, and cover topics such as what UCSB students are like, sexual harassment, time management, and whom to contact if […]. Our department’s required TA training seminar takes place in fall quarter, thus not prior to when TAs might have to teach, and was strictly presentation based. In none of these three requirements was there any discussion of pedagogy, the study of being a teacher.

I went into my first discussion section with no idea on how to lead an effective discussion section, other than what I personally saw in my undergraduate Computer Science discussion sections, most of which I did not attend. Those that I had attended were not discussion sections, but rather mini-lectures with a question and answer session, thus this was the model I followed. Rather than trying to help students make real world connections with what they were learning, I simply presented material and answered questions they had about assigned projects.

Despite how I now believe I could had a much bigger impact, I was given Outstanding Teaching Assistant awards both quarters I TAed based on my end of quarter reviews by the students, and professor recommendations. I am not attempting to brag here, but rather show that my instruction as a TA is representative of our department’s best TA instruction and that’s sad. It can be so much better.

Undergraduates coming to UCSB for Computer Science, benefit from being taught by some of the brightest minds in the country. However, if you think these professors are much different when it comes to pedagogy than our TAs, you are sadly mistaken. Our professors are not hired based on their teaching ability, but rather their ability to bring in research money through grants.

I’ve confirmed this through discussion with faculty involved in the hiring of new faculty. I asked one of our faculty members, “Suppose two candidates were identical in research experience, but one had more teaching experience. Would that give the candidate an edge?” The response I received was that no two candidates are ever identical in research experience, and that any teaching experience is completely neglected.

In my opinion this is unacceptable. At UCSB undergraduates are paying more than they should to receive a college education. At the very least they should be taught by professors who not only know what they’re teaching, but know how to teach it as effectively as possible. Teaching shouldn’t be a requirement, as many faculty members see it, but rather an opportunity to share knowledge.

Before I conclude, I want to mention that we have some incredible faculty in UCSB’s Computer Science department, many of who are not only excellent researchers, but also excellent instructors. Of those I’ve discussed this with, none of them had any formal teacher training, therefore are solely relying on past experience and observer feedback. Those that are excellent instructors have done incredibly well, but they could do so much better. As can I.

I assisted in hosting the UCSB Programming Competition again this year. Doing so rekindled my love for dynamic programming algorithms, thus why I prepared an example similar to this one for my class and why I wrote this post.

In my own words, dynamic programming is a technique to solve a problem in which previous solutions are used in the computation of later solutions. The generic coin change problem is, given coins of a specified denomination and a number N what are minimum number of coins needed to make change for N? If you don’t like my definitions see wikipedia for dynamic programming and coin problem.

You might be asking yourself, why is this even difficult; don’t I always just take the largest coin possible, as is done when making change with US coins? You’re right, that approach works with US coins and this approach is called a greedy approach. However, if the coins are of value 1, 3, and 4 then the greedy approach would say the best way to make change of 6 is with three coins: 4, 1 and 1. As you’ve probably figured out the correct, or optimal solution is with two coins: 3 and 3.

As I’m very fond of python I coded up a solution which should work in any circumstance so long as 1 is one of the coin denominations. The solution works as follows: Calculate the minimum number of coins to make 1, 2, 3, …, all the way up to the number we want to make change for. At any given point, i, the minimum number of coins to make i is dependent upon previous solutions.

I’m going to be kind of lazy and not actually explain the process as the code is pretty self explanatory, with one addition: The code doesn’t just calculate the minimum number of coins, but rather calculates what coins were used to make the minimum at each point. See the code below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#!/usr/bin/env python
import os, sys
 
def solve_coin_change(coins, value):
    """A dynamic solution to the coin change problem"""
 
    table = [None for x in range(value + 1)]
    table[0] = []
    for i in range(1, value + 1):
        for coin in coins:
            if coin > i: continue
            elif not table[i] or len(table[i - coin]) + 1 < len(table[i]):
                table[i] = table[i - coin][:]
                table[i].append(coin)
 
    print '%d coins: %s' % (len(table[-1]), table[-1])
 
 
if __name__ == '__main__':
    def usage():
        sys.stderr.write('Usage: %s value\n' % os.path.basename(sys.argv[0]))
        sys.exit(1)
 
    # Modify this to alter the denominations of coins
    coins = [1, 3, 4]
 
    if len(sys.argv) != 2:
        usage()
    try:
        value = int(sys.argv[1])
    except ValueError:
        usage()
    solve_coin_change(coins, value)

Wow, where has the time gone? In my absence a great deal has happened in my life so I’m going to break it up into a few chunks starting with stuff prior to the summer.

As I briefly mentioned in Flat Stanley’s Adventures, winter quarter I TAed the Compilers course for Tim Sherwood, one of my favorite Professors. As a TA I was primarily responsible for the course projects. I decided to write automatic grading utilities, which despite the occasional bug were quite beneficial to the students as they received immediate feedback when submitting their project. Additionally they were able to submit projects multiple times, thus allowing them to fix problems they might have overlooked. As my end of quarter reviews were pretty good, I was selected as one of four Outstanding TAs for the quarter in our department.

In addition to TAing winter quarter, I took two courses. One was a security related course on malware and reverse engineering lead by my soon to be adviser Chris Kruegel. The projects in the course had us write a simple Windows root kit, a ELF virus, a crack and a keygen for contrived programs, among a few others.

The second course I took was taught by Klaus Schauser and was on scalable web services. Klaus previously was a Comptuer Science professor at UCSB however, he left to found Expert City which later was bought by Citrix thus becoming Citrix Online. He now is the Chief Strategist for Appfolio a Santa Barbara company that provides an online solution to Property Management. This particular course interested me as it is seldom offered and web related topics fascinate me. A group consisting of myself, Adam, Jeff, Jon, Krithika, and Shashank created the website torrentphobe which was a torrent tracking service that utilized social networks. It worked wonderfully, however after the course ended, and the money for the servers was no more, we decided to shutdown our service.

During winter quarter I applied for summer internships. Naturally I reapplied with Google, applied to Microsoft and a few other companies, however I never would have thought of applying to AppFolio if I hadn’t taken Klaus’s scalable web services class. I had little knowledge of AppFolio prior to interviewing, however I wanted to interview simply to catch a glimpse of a pair programming company in addition to gaining interview experience. The interview went quite well, and to my surprise I was given an offer equivalent to that which Google would offer. After careful consideration and discussion about finding an appropriately challenging project, I was sold, and accepted before Google even got back to me on my application. I must quickly say that I’m over halfway through my internship and Appfolio is a fantastic company to work for. I only have a few weeks left; it will be sad to leave.

Spring quarter I took a single course, Advanced Computer Architecture with the same Tim Sherwood I TAed for. On a quick side note Tim is the Professor that held the Programming Battle Adam and I won in the spring quarter of our freshmen year in addition to taking us to Riverside for the ACM Programming Competition the following four falls. Thus I knew this class would be amazing even if the material weren’t the most enticing. The papers were definitely dense but I learned some damn cool stuff. Therefore I’m glad I took the class.

My main focus spring quarter was with my TA responsibilities for the Operating Systems course. I again gained a great deal of valuable experience, however grading for these projects was not as straightforward as the grading the previous quarter. The projects had very little area between doesn’t work at all, and works perfectly. Thus in attempt to accurately grade the students’ understanding of material the projects were designed to convey, I had the groups demo their projects. I think it worked out quite well, however as one student pointed out in their written review it, the demoing process is not a perfect method. They wrote, “[P]lease grade more harshly. People who BS’d the assignments got the same grade as people who did them right.” Nonetheless whomever they were comparing against must have done a good job at BSing.

Toward the end of the quarter notification came out that the graduating seniors elected me as the Computer Science Outstanding TA of the year. That quickly became a topic of toast when I was out with friends at a bar. I recall a few times Adam or Scott would introduce me as Bryce, the TA of the year. I attempted to not let it go to my head; sometimes I succeeded and others I failed. Such is life.

On the Scotty and Adam topic I attended their Master’s graduation ceremony, which was oh so boring. However, as with our undergraduate graduation, this one naturally came the mimosas in the morning and much other celebration so it was worth the hours in the sun. As all good things must come to an end, the celebrations didn’t last too much longer. A few days later we all moved out of our place on Sesame Tree. I moved down the road to Storke Ranch, and Adam and Scott temporarily moved home to Sacramento prior to their big move to Washington to work for Microsoft. The move marked the end of an era: the end of the Three Musketeers. However, the move also marked the start of a new life for me, which has been great so far. Nonetheless Scotty and Adam are missed.

I was just watching the keynote for Google I/O in which Google’s CEO, Eric Schmidt said, “I’m one of these people who believes Computer Science is at the center of the Universe.” I think this is one of my new favorite quotes. Quote at 4:34 in the video below.

It’s very exciting to read about the latest and greatest technology. Sometimes, however, I stop and wonder if all this technology really for the better? I was reading a blog post by Michael Zimmer titled Amusing Ourselves to Death: The Comic. His posts are mostly about online privacy, however, this particular post brought attention to a comparison between Orwell’s 1984, which I’ve started reading, and Huxley’s Brave New World, which I’ve now added to my reading list. I don’t have time to provide my thoughts on the matter, nonetheless I thought it was worth sharing. I’ll end by saying that if this technology wasn’t for the better, then I’d be out of a job

I previously mentioned that I was the Teaching Assistant (TA) for the Operating Systems class this quarter. It’s going quite well, though just as I remember, this class is a lot of work for the students, and a hell of a lot of work for the TA. I recently finished grading the third project in the class, and am now continuing my preparation for tomorrow’s lecture.

Tomorrow’s lecture is super exciting for me because not only do I get to lead it, it is my first time talking to a mostly full class for an hour and fifteen minutes. I teach discussion sections each week, however these differ in that roughly only half the class shows up, and additionally I don’t have to prepare much material since discussion sections go in the direction that the students desire. Tomorrow, however, this is not the case. I was given lecture slides from which it is my responsibility to impart knowledge onto the students about a specific topic, and that is exactly what I intend on doing.

I’ve read the relevant sections in the book from which the slides were prepared and I have even thought up some questions students might ask. To top it off, I’ve even planned some stupid jokes, such has how I am planning to say, “It’s a trap!” when the kernel traps due to an invalid memory access. I don’t want to give away too many of my tricks, but hopefully you get the impression that I’m excited and ready for tomorrow’s lecture.

Am I nervous? Absolutely not. I was nervous to prior to teaching my first few discussion sections last quarter, however talking in front of Computer Science students has simply become part of what I do. I’d probably be nervous if I had to instruct a class for a different department, but I’m always nervous the first time I do something new.

To end this I want to write that I’ve finally updated my CV on my Computer Science home page. If you’re interested in what academic and professional things I’ve been up to check it out.

Connor Pitching

This past weekend my littlest brother pitched for the first time. Word has it that he pitched 3 consecutive strikeouts! Go Connor. However, this word needs to be taken with a grain of salt as it comes from our mom, who as most moms do, occasionally neglect unfavorable details.

My past weekend involved getting scuba certified with Adam, Daria, and Margaux as we did our four beach dives. We now can rent scuba tanks and are _allowed_ to dive down to 60 feet. I must say that scuba is awesome, though I’d much prefer having gills to wearing ~75 pounds worth of gear. Gillyweed would be sweet too. Unfortunately it doesn’t exist… yet.

I turned my computer on this morning and to my dismay my 9 month old 1TB harddrive could no longer be detected. It is still under warranty so it’s no big deal about the hardware going bad, however it is a big deal that I didn’t have a backup of anything on the drive. Fortunately it only consisted of replaceable content, however it will take quite some time and bandwidth to regain that content.

This drive failure emphasizes the importance of backing up my unrecoverable data, and I’m curious as to what methods other people use for backup. A few months ago I backed up a good amount of information to Amazon S3, however doing that on a regular basis is not the simplest task, and probably isn’t the best place to store sensitive information unless it’s encrypted. The other thing that’s important to me is synchronization between my desktop and laptop, of which the challenge is my laptop runs OS X and my desktop runs Ubuntu Linux. I currently use rsync to move files back and forth, however it’s not a good solution when I wish to delete or rename files. I also am considering using GIT to store version information which so long as only 1 is considered the master there should be no issues.

Also on a semi-related note, if you want to run make clean on any folder under your current one which contains a makefile for archiving purposes try the following command:
find . -iname Makefile -exec dirname {} \; | while read i; do make clean -C $i; done

The following is my python implementation of choosing N random lines with equal probability from a file. This implementation is both memory and time efficient unlike other solutions. This problem was originally brought to my attention after a friend was asked a similar problem at a Google interview. Additionally a few weeks ago I was catching up on Jonathan’s blog and came across his March 2008 post about this problem. I submitted a similar solution to the one below in his comments.

Anyway, a naïve solution to this problem involves calculating a random position in the file, with the file size being the max. However this solution does not give equal probability to each line as longer lines will more likely be selected.

The simple solution involves counting the number of lines in the file and then choosing N random lines. However this requires a scan over the entire file to count the number of lines, and then in the worst case an entire scan over the file to print each random line. This is time inefficient if the file is massive in size.

One optimization is to store the seek position of all the line indexes in memory, thus avoiding the scanning to print out each random line. However this requires storing a number for all the lines in the file, which is memory inefficient if the file has a ton of lines.

By choosing whether to keep or replace the selected lines at each step in a single scan, one simply needs to store N positions into the file thus being both time and memory efficient. I’ll leave the exercise of proving that each line is selected with equal probability up to you.

Edited: Added prev so that the first line would be included, and replaced file.readline()[:-1] with file.readline().strip() to remove trailing whitespace properly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#!/usr/bin/env python                                                          
import os, random, sys
 
if __name__ == '__main__':
    def error_exit(msg):
        sys.stderr.write(msg)
        sys.exit(1)
 
    # Verify arguments                                                         
    if len(sys.argv) != 3: error_exit('Usage: %s FILE NUM_LINES\n' %
                                      os.path.basename(sys.argv[0]))
    text_file = sys.argv[1]
    if not os.path.isfile(text_file):
        error_exit('%s does not exist, or is not a file\n' % text_file)
    try:
        num_lines = int(sys.argv[2])
    except ValueError:
        error_exit('%s is not a number\n' % sys.argv[2])
 
    seeks = [0 for x in range(num_lines)]
    file = open(text_file)
    count = 0
    prev = 0
 
    # Calculate Random Lines                                                   
    while file.readline():
        for i in range(num_lines):
            if random.randint(0, count) == 0:
                seeks[i] = prev
        prev = file.tell()
        count += 1
 
    # Print Random Lines                                                       
    for i, pos in enumerate(seeks):
        file.seek(pos)
        print '%d: %s' % (i, file.readline().strip())
 
    file.close()