For the third year in a row, BCA has qualified in at least one division of the ACSL All-Stars, a national computer science contest. The first year, when I was a sophomore, we were all ecstatic to have made a national competition. (well who wouldn't be?) The three of us, Kamran, Pavel, and I, were to somehow get to Maryland on Friday, stay there for a night, and get back Saturday after the competition by ourselves because Mr. Tyndall, the ACSL advisor, couldn't make it. Balls.
I decided to take things into my own hands. I recruited my parents as drivers, since I had close connections to them and they were wiling to go to the competition. We found a relatively inexpensive hotel in the area and booked two rooms, one for the guys and one for my family. (It had free wifi, too :D) With some reviewing, but no formal programming practice or problem sets, we managed 4th place overall. Nice.
The next year, Mr. Tyndall decided to sign up two teams, one in the intermediate division and one in the senior division. Both teams qualified for All-Stars, to be held in Alabama. Unlike before, this trip was school sponsored (Dr. Mayers chaperoned!), but we had to pay a lot more than if we went by ourselves. Again, there was no formal practice except for a cursory review of the topics for the written contest the night before. This yielded mixed results: the powerhouse of a senior team (Sam, Kamran, and I) easily claimed second place, while the intermediate team managed sixth. What was worse was that the individual round scores for the intermediate team was absolutely horrendous, with one person getting a measly 4 out of 12. Seriously?!
Upon witnessing the utter massacre, I vowed to make sure it doesn't happen again. I decided that, since I got a perfect 40/40 on the monthly contests and a near perfect 11/12 on the All Stars written contest, there wasn't really a point to go to All Stars again, so I just participated in the seasonal contests to help the school's team score. I made sure that after both teams were invited to All Stars, optimal teams were chosen as soon as possible to maximize training time.
As expected, both teams were invited. I decided to implement a team selection test for additional data gathering. It covered all material on the seasonal contests and had two parts; the first part was a speed test with ten short-answer questions to be done in ten minutes and the second part was five All Star questions (open-ended!) to be done in thirty minutes. The scores were more or less what I expected; but I was highly disappointed that no one got the internal path length question correct on the speed section and only Andrew Cai got the pre/in/postorder traversal question right on the accuracy section. Now I had a better sense of everyone's skill level and collective strengths (bit string flicking) and weaknesses (trees).
The next step was to pick teams. Mr. Tyndall, Dr. Nevard, and I sat down during my lunch time to discuss teams. With everyone's seasonal contest and TST scores in hand, we debated for about forty-five minutes on everyone's qualifications. We focused on people's teamwork skills, motivation to prepare for the contest and reason for going, and ability to supply a driver. Finally, we decided that Alex K. Andrew H., and Mark M. should represent the intermediate team and Yumi S., Andrew C., and Jonathan S. should represent the senior team.
With the team selection out of the way, I quickly whipped up a problem set on trees. It had two sections; the first section had three parts; each required building a binary search tree out of the string (ABCDEFFEDCBA, BERGENACADEMIES, PRINCETONUNIVERSITY), find the internal and external path lengths, and do preorder, inorder, and postorder traversals on the tree. The second part consisted of building a max-heap out of the word SCHOLARSHIP and doing preorder, inorder, and postorder traversals. Time limits were given so that the contestants could pace themselves. The results were generally good; most of the six were able to do the heap question, but about half stumbled on the longer strings in part one.
The weekend before the competition, I emailed everyone a programming problem set. I couldn't find any `good' ACSL problems (this is where you rofl), so I stole one from Project Euler (find the sum of the digits in $$N^M$$), one from USACO (preface numbering), and made two up (sudoku solver and shortest path). I was plenty surprised to have seen a shortest path problem on last year's All Stars, given that ACSL was mostly about brute force and super annoying problems. I am not sure if anyone attempted the problems, since I did not receive any emails with programs. Oh well.
The second pset was on Finite State Automata and ACSL Assembly and the third was a speed test on bit string flicking. Again, the psets had two parts each. On pset 2, the first part consisted of drawing some finite state automata from regexes and the second part consisted of not reading, but writing assembly code given a task. The third pset had two sections of bit string flicking. I got responses from most of the All Starrers. They did well on the third one, but got pretty raped on the second one. One person said that ``his eyes bled'' when he wrote the assembly code. Since it was just days before the competition, I decided, at 23:30 the day before their departure, to type up and send them my solutions to the problems so not only could they check themselves, but also see how I attempt the problems.
During all of this writing problems and giving feedback fun stuff, I also had to maintain clear communication with Arlan Dietrich, the ACSL coordinator, Mr. Tyndall, and the driving parents. There was lots to be done logistics-wise, such as registering for the competition, placing lunch orders for the competition, and telling parents about the schedule of the competition and the times that they have to get to places. Although it was very overwhelming, I somehow got through everything fine…
I was really happy to hear that the competition went smoothly, and even more so when they said that they pwned the individual round :D I breathed a sigh of relief, now knowing that I have considerably mitigated our biggest weakness. Three people got 11/12s, one got 10, and two got 8s. Much much better than 11/11/10/9/7/4. The senior team did respectably well on programming, with 37 out of 40, but the intermediate team got absolutely annihilated, scraping up only six points out of forty. This resulted in a fourth place finish for senior team and sixth place for intermediate team. At least four of them got books for doing well on the individual round. Well done, guys :)
30 May 2010
18 May 2010
Rolfcopter
Enjoy :)
Direct link:
Video 1
Video 2
Other notes: The white thing in the background on the top-left is the back of my Math Prize for Girls check with my shitton of iPods. (Actually not quite the whole lot; I am currently using my iPhone and iPod 20GB 4th Generation) :D
This post is dedicated to my project partner Dan A., who failed at spelling `roflcopter' on his SEN10R shirt.
Direct link:
Video 1
Video 2
Other notes: The white thing in the background on the top-left is the back of my Math Prize for Girls check with my shitton of iPods. (Actually not quite the whole lot; I am currently using my iPhone and iPod 20GB 4th Generation) :D
This post is dedicated to my project partner Dan A., who failed at spelling `roflcopter' on his SEN10R shirt.
17 May 2010
16 May 2010
Yay Internship Paper
Good morning. We are here to tell you about our eight months of internship experience in approximately twenty minutes.
As two of the top programmers at the Academies, we set sights on a computer science related internship. We chose to intern with AltLaw because we wanted to work for a small scale open source project to get firsthand experience on working with a team of people all over the country and to be recognized as not just an intern, but also a contributor of the project. We also liked that it was going to be on-campus, so we did not have to arrange transportation to the city or elsewhere.
AltLaw is a free and open source legal search engine. The project was started by Stuart Sierra, Paul Ohm, Tom Bruce, Carl Malamud, and Tim Stanley in hopes of creating a searchable database of law cases and such that is accessible to everyone, not just paid subscribers. However, in November, Google Scholar added legal cases to its vast collection of scholarly documents, so AltLaw is no longer needed. The developers did not see this as a complete disappointment; they were happy to see that a large corporation has taken on this initiative to provide the general public with a searchable collection of legal documents.
We interacted with Stuart for most part of the project. He has a bachelors of arts in theatre from the New York University and a masters of sciences in computer science from Columbia University. He works for the Program on Law & Technology at the Columbia Law School, where he spends his day hacking on AltLaw.
The branch of computer science in which AltLaw belonged is known as Information Retrieval. It is the science of searching for documents, for information within documents, and for metadata about documents, as well as that of searching relational databases and the World Wide Web. The three branches on which we focused are scraping or getting data, processing data (usually with mathematical or algorithmic means), and displaying data, usually with a web interface. At AltLaw, this was done with a variety of tools and languages.
Working for AltLaw required us to learn a Lisp-like programming language called Clojure, among other things. It is radically different from languages one might be accustomed to; it forces one to think recursively instead of imperatively. The biggest omission that newcomers will notice and lament is the lack of `for' and `while' loops. This is a bigger part to data immutability, or the inability to modify the value of a variable once it has been set. Immutability allows for much simpler concurrency implementation because there will not be any discrepancies in variable values in multithreaded applications and such.
To practice coding with a functional programming mindset and to learn the Clojure API, we started out with little programs, such as factorial (which, surprisingly, can be written a bunch of different ways). There is the standard tail recursion method, loop-recur method, and a clean, one-liner map-reduce method. We were surprised that there was a rather large time discrepancy when we tested the different ways with a large test case.
In the meantime, the ATCS parent organization, Computer Science Families, was generous enough to donate two Sun Fire rack servers for us to use. Unfortunately, we were not allowed to keep the servers in school without handing them over. We tried to find another permanent home for them, but that proved to be difficult as well. They, now along with nine other machines, are sitting in the basement of the house of the CSFamilies' president.
We wrote a program similar to the UNIX wc (wordcount) program to test Clojure's performance. The test results showed that the Clojure program was consistently more than twice as slow as wc, which reinforced the notion that interpreted programs are slow (augh this wording is terribad -Sherry Wu 5/16/10 3:11 PM)
After we were relatively fluent with the basic syntax, Stuart taught us about how Clojure and any functional language was deeply intertwined with lists and its siblings, such as maps, sequences, and vectors. To practice with these, we wrote a sentence validator. This program takes a grammar and a collection of sentences and returns whether each sentence is valid with respect to the grammar. (darn i don't think this wording is good either -Sherry Wu 5/16/10 3:16 PM)
As an aside, we were asked to write a regex (regular expression) to parse Java-style floating point numbers. Regexes were quite easy to pick up; and this assignment showed us an application of using regexes. (lol this paragraph seems relatively useless -Sherry Wu 5/16/10 3:20 PM)
Now that we had a hang of working with the data structures, Stuart taught us about the basic infrastructure of search engines. They stored keywords into a table-like data structures, such as a Document Term Matrix or an Inverted Index. The inverted index is essentially a map used to count occurrences of words in a set of sentences and to keep track of which sentences had what words. One of our assignments, which turned out to be a mini-project, was to write an inverted index.
Stuart decided to shift from programming to learning about Hadoop. Unfortunately, our efforts were impeded by a variety of things, including a lack of 32-bit J2SE 6 for Mac OS X, restricted user rights on school computers, and a terribadly craptastic implementation of the school's network. Therefore, we were left with only three laptops to work with. It took quite a bit to get the software configured, and finally, when all three machines were up and running, we got the sample distributed wordcount program to run! Unfortunately, that was all for Hadoop.
On the bright side, we still continued discussing concurrent programming. Stuart introduced us to the meat of Clojure, starting with agents and refs and reinforcing immutability. It was more of a watch-and-learn session instead of hands-on coding. Stuart wrote a program to test the fairness of the random boolean generator, except this time, we could see the proportion of true booleans in real time. As a final example, we played with a prewritten ant farm simulator as a demonstration of concurrent programming.
Stuart also showed us some testing techniques, such as unit testing and applications of agents. He showed us his rapid testing library, in which a program watches several files and runs tests against them every time a change is made. This is done by having the operating system push changes to the program (instead of it asking the file system if the files in question have been changed). A question that still remains is whether it can be used to develop itself. Yay metatesting?
As a final `unit', Stuart introduced us to "better object-oriented programming" in Clojure, which involved message passing, similar to a practice in Objective C. This is radically different from object oriented programming in Java, where every class has a predefined set of messages. We messed with some Protocols (Interfaces in Java speak) and Structures (Classes in Java).
In the middle of working with Stuart, we decided to do some basic Monte Carlo. This is a technique for numerical integration and heavily involves randomness. The canonical example is computing the area of pi by throwing darts in a circle inscribed in a square and finding the proportion of darts that land within the circle. We just implemented this in Clojure for fun and ran increasing numbers of trials in each test to see how the value in question would converge.
To wrap up the end of the year, we did discussions of current technology, the industry, and the future. Our most interesting discussion was about cloud computing, in which we debated the effect of the iPad and Android devices and current development tools. We talked about HTML5 and its open source buddies against the rest of interactive development tools, such as Flash, Silverlight, and even Cocoa. One of the big points in discussion was whether many people would continue to support native iPhone development now that Apple has banned using all but Apple-approved languages.
As a last activity, Stuart told us about different uses of programming languages in industry and upcoming revolutions. Although he lamented that he wasn't part of the PC revolution, he is happy that he is able to see functional programming, massive data processing, and virtualization go mainstream. He showed us the enterprise hardware Java accelerator (essentially a massive server powered by a custom chip with fifty-some cores and oodles of gigabytes of memory). We did an exercise in which we had to write the GCD function in Clojure, Python, and Ruby and benchmark all three. We were surprised that Clojure was fastest (by quite a wide margin), followed by Python and then Ruby.
Overall, we highly recommend this internship to anyone up for a challenge. Picking up Clojure is not recommended for the incompetent, as it requires thinking and persistence to master it. We got a full exposure to a new (and very different!) language and were able to work with someone from the open source community. It is also a big advantage if you are able to push yourself to work in an unsupervised environment or have a superb problem solving skill; if you have either, you will be able to accomplish the assignments easily.
As two of the top programmers at the Academies, we set sights on a computer science related internship. We chose to intern with AltLaw because we wanted to work for a small scale open source project to get firsthand experience on working with a team of people all over the country and to be recognized as not just an intern, but also a contributor of the project. We also liked that it was going to be on-campus, so we did not have to arrange transportation to the city or elsewhere.
AltLaw is a free and open source legal search engine. The project was started by Stuart Sierra, Paul Ohm, Tom Bruce, Carl Malamud, and Tim Stanley in hopes of creating a searchable database of law cases and such that is accessible to everyone, not just paid subscribers. However, in November, Google Scholar added legal cases to its vast collection of scholarly documents, so AltLaw is no longer needed. The developers did not see this as a complete disappointment; they were happy to see that a large corporation has taken on this initiative to provide the general public with a searchable collection of legal documents.
We interacted with Stuart for most part of the project. He has a bachelors of arts in theatre from the New York University and a masters of sciences in computer science from Columbia University. He works for the Program on Law & Technology at the Columbia Law School, where he spends his day hacking on AltLaw.
The branch of computer science in which AltLaw belonged is known as Information Retrieval. It is the science of searching for documents, for information within documents, and for metadata about documents, as well as that of searching relational databases and the World Wide Web. The three branches on which we focused are scraping or getting data, processing data (usually with mathematical or algorithmic means), and displaying data, usually with a web interface. At AltLaw, this was done with a variety of tools and languages.
Working for AltLaw required us to learn a Lisp-like programming language called Clojure, among other things. It is radically different from languages one might be accustomed to; it forces one to think recursively instead of imperatively. The biggest omission that newcomers will notice and lament is the lack of `for' and `while' loops. This is a bigger part to data immutability, or the inability to modify the value of a variable once it has been set. Immutability allows for much simpler concurrency implementation because there will not be any discrepancies in variable values in multithreaded applications and such.
To practice coding with a functional programming mindset and to learn the Clojure API, we started out with little programs, such as factorial (which, surprisingly, can be written a bunch of different ways). There is the standard tail recursion method, loop-recur method, and a clean, one-liner map-reduce method. We were surprised that there was a rather large time discrepancy when we tested the different ways with a large test case.
In the meantime, the ATCS parent organization, Computer Science Families, was generous enough to donate two Sun Fire rack servers for us to use. Unfortunately, we were not allowed to keep the servers in school without handing them over. We tried to find another permanent home for them, but that proved to be difficult as well. They, now along with nine other machines, are sitting in the basement of the house of the CSFamilies' president.
We wrote a program similar to the UNIX wc (wordcount) program to test Clojure's performance. The test results showed that the Clojure program was consistently more than twice as slow as wc, which reinforced the notion that interpreted programs are slow (augh this wording is terribad -Sherry Wu 5/16/10 3:11 PM)
After we were relatively fluent with the basic syntax, Stuart taught us about how Clojure and any functional language was deeply intertwined with lists and its siblings, such as maps, sequences, and vectors. To practice with these, we wrote a sentence validator. This program takes a grammar and a collection of sentences and returns whether each sentence is valid with respect to the grammar. (darn i don't think this wording is good either -Sherry Wu 5/16/10 3:16 PM)
As an aside, we were asked to write a regex (regular expression) to parse Java-style floating point numbers. Regexes were quite easy to pick up; and this assignment showed us an application of using regexes. (lol this paragraph seems relatively useless -Sherry Wu 5/16/10 3:20 PM)
Now that we had a hang of working with the data structures, Stuart taught us about the basic infrastructure of search engines. They stored keywords into a table-like data structures, such as a Document Term Matrix or an Inverted Index. The inverted index is essentially a map used to count occurrences of words in a set of sentences and to keep track of which sentences had what words. One of our assignments, which turned out to be a mini-project, was to write an inverted index.
Stuart decided to shift from programming to learning about Hadoop. Unfortunately, our efforts were impeded by a variety of things, including a lack of 32-bit J2SE 6 for Mac OS X, restricted user rights on school computers, and a terribadly craptastic implementation of the school's network. Therefore, we were left with only three laptops to work with. It took quite a bit to get the software configured, and finally, when all three machines were up and running, we got the sample distributed wordcount program to run! Unfortunately, that was all for Hadoop.
On the bright side, we still continued discussing concurrent programming. Stuart introduced us to the meat of Clojure, starting with agents and refs and reinforcing immutability. It was more of a watch-and-learn session instead of hands-on coding. Stuart wrote a program to test the fairness of the random boolean generator, except this time, we could see the proportion of true booleans in real time. As a final example, we played with a prewritten ant farm simulator as a demonstration of concurrent programming.
Stuart also showed us some testing techniques, such as unit testing and applications of agents. He showed us his rapid testing library, in which a program watches several files and runs tests against them every time a change is made. This is done by having the operating system push changes to the program (instead of it asking the file system if the files in question have been changed). A question that still remains is whether it can be used to develop itself. Yay metatesting?
As a final `unit', Stuart introduced us to "better object-oriented programming" in Clojure, which involved message passing, similar to a practice in Objective C. This is radically different from object oriented programming in Java, where every class has a predefined set of messages. We messed with some Protocols (Interfaces in Java speak) and Structures (Classes in Java).
In the middle of working with Stuart, we decided to do some basic Monte Carlo. This is a technique for numerical integration and heavily involves randomness. The canonical example is computing the area of pi by throwing darts in a circle inscribed in a square and finding the proportion of darts that land within the circle. We just implemented this in Clojure for fun and ran increasing numbers of trials in each test to see how the value in question would converge.
To wrap up the end of the year, we did discussions of current technology, the industry, and the future. Our most interesting discussion was about cloud computing, in which we debated the effect of the iPad and Android devices and current development tools. We talked about HTML5 and its open source buddies against the rest of interactive development tools, such as Flash, Silverlight, and even Cocoa. One of the big points in discussion was whether many people would continue to support native iPhone development now that Apple has banned using all but Apple-approved languages.
As a last activity, Stuart told us about different uses of programming languages in industry and upcoming revolutions. Although he lamented that he wasn't part of the PC revolution, he is happy that he is able to see functional programming, massive data processing, and virtualization go mainstream. He showed us the enterprise hardware Java accelerator (essentially a massive server powered by a custom chip with fifty-some cores and oodles of gigabytes of memory). We did an exercise in which we had to write the GCD function in Clojure, Python, and Ruby and benchmark all three. We were surprised that Clojure was fastest (by quite a wide margin), followed by Python and then Ruby.
Overall, we highly recommend this internship to anyone up for a challenge. Picking up Clojure is not recommended for the incompetent, as it requires thinking and persistence to master it. We got a full exposure to a new (and very different!) language and were able to work with someone from the open source community. It is also a big advantage if you are able to push yourself to work in an unsupervised environment or have a superb problem solving skill; if you have either, you will be able to accomplish the assignments easily.
05 May 2010
Happeh happeh happeh 17+1!
Yes, today is a nice day that is alternatively known as my birthday! It's been an awesome eighteen years thinking different, and only more is going to come. Lots have changed (and not changed), so let's see:
Changed:
Academic Focus: I thought I would enjoy math and physics (just like Dad) and would get a PhD and be a near exact replica, but I turned out not to be one of the theoretical people. Though I do find theory helpful in understanding applications, I find it pretty boring and useless by itself. This reflects my newborn interest in economics and applications of computer science and math. I probably will end up getting an MBA or something like that.
Computing and involvement with technology: One of the things I am really happy that I did early was get involved in technology. When I was in sixth grade, my parents said that they would buy me my own box to use (so I wouldn't have to take over their system), so I looked online at various manufacturer and review websites. I was enthralled by Apple's artwork, but was silly enough to fall for the Megahertz (gigahertz) myth, so I pretty much discounted its machines. So I ended up with a little noisy Dell tower, which I used for the first twoish years of middle school.
As I kept reading C|Net (mainly for reviews), I started following technology (and Apple). I remember the one time when I was reading initial reviews about the $49 Apple Mighty Mouse (debuted August 2005), and I predicted that Apple was going to release a Bluetooth one with Laser tracking for $20 more, the price delta between the wireless mouse and the former wired mouse. And holy crap, I was right! XD
My computing style had shifted quite a bit; I started out on Dad's Macintosh Classic when I was really little, then used several Windows boxes for quite a bit of time, got my first computer (a Dell Dimension 4600C which I am using as a webserver today), got a Mac mini for my 13th birthday, tried Ubuntu and Hackintoshed my Dell a year later, got a MacBook Pro (which I love and am still using it today) for my 14th birthday, and built my own box in sophomore year (with the intention of Hackintoshing, but that was never realized and it's now a Ubuntu box).
Unchanged:
`Thinking' Different: I have always been `different' (i.e. odd one out in `normal' people's language) ever since...I dunno...elementary school? preschool? Known as the `brainiac' or the `math whiz', the other kids basically ignored me because, well, I didn't play sports and was interested in academics. During the award ceremonies in middle school, most of the crowd booed when I got up to claim my certificate of honor or excellence. In another situation, when I was talking with someone from my homeroom who plays sports, I told him about getting money or a free laptop at a math competition (Mathcounts Nationals, in particular) and his reaction was like, ``nawwww, get out of here! you're kidding!''
In BCA, I am pretty much the same, except there's a much wider range of people interested in academics. However, I still remain the odd one out in that I am the only female in my class to be interested in and dedicated to both math and compsci. XD
Being different has been fruitful for me. I followed through with compsci and math and have won many prestigious awards (USACO Gold and Math Prize 6th place) and am Captain of both teams. I am the first female from BCA to make Gold. Pursuing these usually `guys-only' subjects has allowed me to make some wonderful connections
Being different has just made me plain bizarre. I am one of few people who has cracked all my joints at least once (cracking my neck freaks my mom out XD). I know all of the first generation Pokemon (only the first 80 or so in order, though) and 97% of second generation. I skipped junior prom to go to a compsci competition (ACSL All-Stars). Now that was pretty epic. Oh, also, I do not approve of makeup/any of that girly garbage.
Expanding on that last note: I probably do it for the hell of it, but it is also for economic reasons: with limited resources, I cannot possibly feed my gadget impulsion and buying silly stuff at the same time. Therefore, I forgo most (if not all) makeup, jewelry, etc. and save my budget for buying computers, circuits, hardware, and the like. A $500 prom dress?! I'd take an NVidia GTX 480 over that any day (or an iPad; either one is nice)! Also, I can be different! Unlike pretty much everyone else, I wear khaki-like pants and a BCA/Math Team t-shirt most of the time, but now I pretty much wear black-and-gold apparel every day to remember Mr. Holbrook's passing.
Well, that's pretty much all I have to say. I suppose I'll end this with something more informal...
I'm a beaver,
You're a beaver,
We are beavers all.
And when we get together,
We do the beaver call.
e to the u, du / dx
e to the x, dx
Cosine, secant, tangent, sine
3.14159
Integral, radical, mu dv
Slipstick, slide rule, MIT!
GOOOOOO TECH!
Hello, MIT!
Subscribe to:
Posts (Atom)