Category Archives: Computer Science

Boys Like to Break Things

Boys Like to Break Things.txt

by Richard White

2014-09-10

It’s no secret that Technology Education has something of a gender problem. For reasons that are still unknown (at least to me), I have far fewer female students in my Computer Science courses than in my Physics classes, where the ratio is close to 50-50. I encourage young women to join my classes, and even had the honor of advising an all-girl group of “Technovators” in an app-design competition the year before.

It’s a curious thing, and although I’d like to find a way to improve the girl:boy ratio, it’s not entirely clear what I should do to do so.

An interesting thing happened in the AP Computer Science class the other day however, and it broke down along gender lines. We’d taken a few moments earlier in the period to examine an old PC running Linux that I’d placed at the front of the room. I’d taken one side of the tower off, and we were looking at the motherboard, graphics card, disk drive, CPU, etc.

And a bit later in the class we were going over shell commands that students might find useful, and after introducing the “remove” command (rm), I mentioned the dangers of inadvertently typing sudo rm -rf /, a command which will recursively remove every file on the computer… usually not something that one intends to do.

it’s an interesting concept, and the thrill of a dangerous command like that holds some inherent appeal, perhaps, to geeks. And then one of the boys raised his hand and asked, “How long will it take before the rm command eventually removes some critical file that is necessary to the ongoing operation of the computer?”

It was an interesting question and one that I hadn’t given much thought to up to this point. The rm command is working on the hard drive, while the operating system mostly resides in RAM, but there are swap operations in which the OS interacts with the hard drive, so… this was a great thing to ponder. At what point does the snake eating its own tail become unable to continue?

You know where this is going. “That’s a great question, Cyril. Let’s find out.” So I had one of the students type the requisite command on the computer that, moments ago, we’d used to demonstrate hardware. They hit the Enter key and took great delight in the list of files scrolling by on the screen, a live-action view of what was being deleted as the rm command slowly destroyed the OS.

This singular opportunity was of such interest that the students crowded around the machine to watch the spectacle, and one young man recorded the event on his phone…

Here’s the other part that you can almost certainly guess. Of the four young women in the class, not a single one came up to the front to watch the event up close. Were they intimidated by the gathered crowd? Was the destruction just less interesting to them? Were they thinking about heading off to their next class? Are boys just more interested than girls in testing things, even (especially!) to the point of breaking them?

I don’t have the answer, but I think about these things. We all need to be thinking about these things, and encouraging women who express interest to explore the idea of learning more technology.

Daniel’s Search Hack

DANIEL’S SEARCH HACK

by Richard White

2014-05-24

ap_comp_sci

On one of the last days of the AP Computer Science class, I met with a few students who had been participating in the High School Capture the Flag hacking contest. A high school in New Jersey had created a competition that would allow teams of high school students using digital tools to solve various types of puzzles.

One of the problems involved a text file with just two lines in it. The first line explaining that students would need to search the file for a series of English words in sequence, although those words wouldn’t be separated by spaces. The second line consisted of over 10 million letters, mostly scrambled, but with words occasionally found within them.

Here are 200 letters from that file:

nhisseokenphoncecrgoeemmoedkihrhobufiiripsthituhelttiytftihweaihurmadarwwesrfeehstetpiaiiendyeogeallrrrescihslhyorsdccalloaaoeyrotlnnstuovdhreshapmmrennaaehtprsedtlsciaemtggsriedencsneihassskusosekhci

You can see the word “hiss” in there, as well as “rips”, “fee”, “call”, “has”, as well as a number of 1- and 2-letter words, but clearly nothing identifiable as a sequential series of words.

So how do you go about looking those needles in that haystack?

I had some ideas, and I’d been working on the problem for a day or two. I wrote a Python program to read all 10 million characters into a string so that I could search through it. I Googled and found a couple of lists of English words, arranged in order of popularity, and inserted those into my program as a list of words.

But now what? How do you start trying to find a sequence of words in a line of ten million letters?

My first algorithm looked liked this:

  1. Get a word (call if word1) from the word list, and another word (word2) from the word list.
  2. Look in the text for an occurrence of the first word.
  3. If you find that word, look to see if the second word is near it. It it is print it out. If not…
  4. Keep looking for additional occurrences of the first word and the second word, until you can’t find anymore.
  5. Get a different word2 from the list and check that against word1.
  6. Repeat this until you’ve tried ever word in the list as word2.
  7. Set word1 to the next word in the list and repeat the whole process.

It didn’t work. It was a first attempt at trying to work through the file, and this particular strategy was much too slow—my search was going nowhere fast.

Time to alter the strategy.

My second try concentrated on reducing the number of text interactions that had to take place. This time, I would:

  1. Take the first word in the word list identify all the locations (indexes) where that word existed in the string.
  2. Do this again with every word in the word list until I had a “dictionary” of word locations.
  3. Now start at the first word, and look at its first location. Go through the other words and their locations, and if a second word was found withing 10 characters of this one…
  4. Look for a third word with a location with 10 characters of this one…
  5. … and then a fourth word. If I could find four words all within 30 characters or so, perhaps this would identify the flag phrase.

Here’s what the results look like for that strategy:

It didn’t work. I mean, the program worked fine, producing a seemingly endless string of lines that matched the specifications I had, but none of the lines produced were what I was looking for. Here’s the partial output from that second algorithm.

alludcgytsooiahitaonoayhlfcdseheieytreee
alludcgytsooiahitaonoayhlfcdseheieytreee
alludcgytsooiahitaonoayhlfcdseheieytreee
alloswvgtwousmipohivteceyihrugitdrttsinu
allesettupslasweoovnsetlbiaerietmntadnea
allesettupslasweoovnsetlbiaerietmntadnea
allesettupslasweoovnsetlbiaerietmntadnea
allechslaashtwnonhhsirewteoaeadmoiitlrhi
alloiarlfeyedacusoemtniohneegsaailaennso
alloiarlfeyedacusoemtniohneegsaailaennso
alloiarlfeyedacusoemtniohneegsaailaennso
allswhybrnastsoetedotwilnrmollhtieeterol
allpeinnucctdanyedrtsittadhhnldvsiniedln
alladhlasgdeaeihownaotoroeemhaueailoenwh
allihyhcinnchpbsoileowidsupredhnpywoweyh
allihyhcinnchpbsoileowidsupredhnpywoweyh
allmhmsfoodieutreethktevkevfaieehvtlhaii
allvcniaionoeuwesthiontnebedneehgecetlts
allvcniaionoeuwesthiontnebedneehgecetlts
allacohohhssoraaehylesooyfeeithseiioatrm
alllaseeatholnsttochtiwrlsridtwodrefvneo
alleeoninshrhugdnewizdeydtepnrartsossrtl

I still was getting “words” in each of those lines that didn’t correspond to the flag I was searching for. This was starting to get frustrating.

I went into class the next day and explained to the students my frustrations, and they were happy to brainstorm different strategies. At one point, Daniel said, “Why don’t you just look through each line in the file and count the number of words in it? Maybe the line with the most words will be the one we’re looking for.”

“That’s a good idea, Daniel, but the file isn’t split up into lines. It’s just one long line of characters.”

He thought about it for a minute, and his partner Ezra said, “Well, let’s just split it up into lines. 140 character lines. That’s good enough for Twitter.”

So that’s what we did. The students have been studying Java for this past year and I was coding in Python, so they watched while I coded their strategy:

    for line in lines:
    num_of_words = 0
        for word in searchTerms:            
            if line.find(word) != -1:          
                num_of_words += 1
                if num_of_words > 25:
                    print num_of_words, line

Because it was a relatively simple strategy, the two decided that they could afford to search for any words contained in 10,000-word dictionary. We watched as the results appeared on the screen:

Last login: Sat May 24 18:03:42 on ttys002
MotteRouge:~ rwhite$ /var/folders/6x/vklj_pls5215szrp_k2qcjcc0000gn/T/Cleanup\ At\ Startup/find3-422672661.132.py.command ; exit;
File has been split into lines! Proceeding…

26 netenivgdyblduenehttihaaoshasnoadhigdateilnoteanabinmstaruceoarasuleedpnhtgeoendtgedeeincodolropthei
26 deeeeepraosderwfsrerepimnsinaosutttnoeytvrvtheterthistollagtitnhsminewitcecnlrsbgeoeddiorwadanartell
27 chaoomelohdanamtgswsbtroddtapmcfhlewasalnewasisscelapostnecstotvstviiiederectunoauwjleeddicbsigesnem
27 ailmavbfngdfawdigcrseentatoueiefrdrnorfkersrutccamemdireaeiedsleoauieiaitmlsitemhiapropenhbutworfson
27 tnatrsirvsprosaeseebatoniwrtaptranuinetdsyraheroenattphweelilnhopedelrudolbiaimoioiaahlttonesoucoduy
26 thahksvrtetentnaanyosmyclekrmrnotestadrtslonuisnproncedpesaehietidethereheionmcbalasaeriantrsrheteeh
26 odicelerussltltmerehsoaeebaotruettanarfdereunecgtsnsnatllasteakitnngodrsuseerthdfaisirnswaudcsvwhvie
27 akyoeaaptebheaeasetrrsdairnslegstensnhhtirepysuxxthseelesnetfdaniknsethaiarsoslutsperaegotedibnnlids
27 hidsrdaedoiltdetoeiepdscencairdstheeovrncwaaihstnthtnebemochthestyaahiseperateanhistseaoneeyntareade
26 edlotetwlettdtstfdnseovnrpamatelfroltsmahliassseaueeeamihnhgavepaadatrglettanitoleeenlredramdhoyaddt
30 latecwhoodehderowtaesitfeflantenvweosrehonsethlaerateeeersiosrlesuaidpeutdineacetzrthrchbhrideeafsat
26 tvanodeaosomidhonatnusidispithscvhsnhsoilesacciraeenycielaehoallooldamwrneirwcfamotntrdataoeenogleeb
33 ntevnaaureakltyashtbosutheselettersrepresenttheclothmarkerthatunlocksrewardsehegcceremuahwtmknnflswa
29 bandosytrctanoyearenonajrnpasrlgaohisnhunetnsielistdoecdpeehenaasshecisiojersydataelpsheeulhesvfonli
28 nargelrhendedtoidlteauuvtihsursaioptehetclbnigeauhoneystolheatbsantrwmsctipsslagedsehieahsadoacscihn

And there it is, on the line with 33 matches, just a few moments after starting the program running:

these letters represent the cloth marker that unlocks rewards

We submitted the flag to the contest and saw out score total immediately jump up 400 points—it was our single biggest success of the competition to that point.

I like this story because it reminds me of a few things that we sometimes forget. Working on digital problems like this is not always about coding— sometimes it’s about strategies. Also, there are trade-offs in strategies that require considering constraints: how much memory, power, time, and data do you have? How do your solution results vary based on the trade-offs you make?

Computer Science teachers talk about these things, but I’m always pleased to see a situation where the students get to actually experience that exploratory process themselves.

Thanks to Daniel, Ezra, Adam, and Stephanie for being willing to play with this problem on the last day of school!

Computer Science in Schools

Computer Science in Schools

by Richard White

2013-12-26

Happy Holidays everybody!

The holidays are no time to get any rest. Oh, no, there’s too much going on–parties, holiday shopping, out-of-town visitors–to actually get any down time. No, to actually get a chance to relax, you have to resort to more drastic measures… like getting sick.

That’s my genius plan, and it’s working just great.

While I’m sitting around waiting for my body’s defense mechanisms to do their thing, I’ll just include a quick year-end pointer here to one of Audrey Watters’s year-end Trend posts, this one on Computer Science in schools:

Despite the proliferation of these learn-to-code efforts, computer science is still not taught in the vast majority of K–12 schools, making home, college, after-school programs, and/or libraries places where students are more likely to be first exposed to the field.

There are many barriers to expanding CS education, least of which is that the curriculum is already pretty damn full. If we add more computer science, do we cut something else out? Or is CS simply another elective? To address this particular issue, the state of Washington did pass a bill this year that makes CS classes count as a math or science requirement towards high school graduation. Should computer science – specifically computer science – be required to graduate? In a Google Hangout in February, President Obama said that that “made sense.” In the UK, computing became part of the national curriculum.

She has a bit more to say on the subject, but her thoughts echo many of my own. Does everyone really need to “Learn to Code”? How important is Computer Science in the midst of an already bulging academic curriculum? How can educators and the tech industry best reach out inclusively to students on behalf of an industry that is not only famously non-inclusive, but downright hostile to some demographics?

It’s a problem that merits discussion at all levels, and there are certainly institutional responses that might be pursued. As I expand my role as a computer science educator I may even become involved in some of those—that’s certainly my intention.

In the meantime, I consider myself on the ground doing the front-line work without which nothing else matters. “For this assignment, students, we’re going to…”

“Oh, cool…!”

If you’re not doing something cool with your computer science, well… what’s the point, really? ;)

Merry Christmas and Happy Holidays, everybody. See you in the New Year!

Hour of Code

HOUR OF CODE

by Richard White

2013-12-14

You may have heard about the Hour of Code this past week, a 5-day educational technology event sponsored by Code.org that is meant to inspire future generations of computer scientists and computational thinkers: by spending just an hour working on a computer science related project—playing with a coding simulation, building a game, solving an algorithmic puzzle—students of any age level will have a better understanding of the topic of computer science, and perhaps be inspired to study it further, either in school or on their own. As a computer science teacher it had popped up onto my radar a few months ago, and it sounded like an intriguing idea so I proposed the idea to our school directors, who were immediately excited about the possibilities.

Fast forward two months, lots of meetings, some curriculum development, and a website, and I’m happy to report that Hour of Code was a rousing success at Poly. We decided early on to target fifth and seventh grades at the school, and I decided early on to create a curriculum—part coding, part computational thinking discussion—that would work with our students. It certainly helps that we had an entire Apple iMac computer lab that I was free to install a user-friendly text editor on.

As I write this, we’ve finished working with the two classes of fifth graders, who thoroughly enjoyed the experience. We talked, we coded, and they walked away with an official and personalized Code.org Certificate of Completion as well as a printout of their code and corresponding Python turtle-graphics art. (Little Marco enjoyed the experience so much that he was quite put out when the lab had to be vacated before he’d put the finishing touches on his masterpiece. I learned later that the first thing he did when he got home from school that day was to plop down in front of the computer and finish his program.)

hour_of_code

Crucial to the success of the day was the support of a large number of people, including our division Ed Tech coordinators, our Director of IT, the teachers who gave us class time to work with their students, and three of my own Upper School students who came down to assist the younger students. We had teacher visitors from other schools in attendance as well, including a professor from Caltech’s Center for Advanced Computing Research. (I don’t think he was scouting our fifth graders for prospective students, but you never know…)

The participation of all these people was vital: advancing technology use in schools is not just about getting new hardware. As a gentle reminder of this fact, our seventh grade sessions—tentatively scheduled for this week—had to be postponed due to some scheduling conflicts. All is well, though, and we’ll be running a more sophisticated Hour of Code session—one that delves into recursion—with our seventh graders at the end of January.

For futher information about Poly’s Hour of Code, including code examples, the presentation slides, or a zipped file containing both, see Polytechnic Hour of Code.