9 months since my last post! It’s definitely time to give the birth to the new one. Let’s recollect what happened since last August.
First of all I completed another year of my studies in Computer Science Department at Purdue University. During the Fall’08 semester I took Computer Architecture, Data Structures, Web Search and Management, Discrete Math, and Abstract Algebra (Honors). 3 CS + 2 Math, nice combo, no doubt.
In September and October we met twice a week with my teammates for 5-hour simulated ACM ICPC contest in preparation for the East Central North America Regional. And on the first day of November at 10:00am the actual contest kicked off. 45 minutes before the start of the competition we had zero problems solved, as everyone else (smiling). But 45 minutes before the end we had already three, which was definitely not enough to qualify. And then in this last magic 45-minute period we got “Yes” on 3 problems, with the last one (problem H, in particular) accepted on the last 300th minute! This catapulted us from the 10th place to the 4th after two teams from Carnegie Mellon University (The Tartans & The Dragons), and Waterloo Black (University of Waterloo, Canada). Wildcards, and we’re going to World Finals in Stockholm, yay!
Purdue Taekwondo Club… another extracurricular activity I enjoy didn’t get much of my attention in the fall, I missed most of practices and ended up missing the promotion test in December. Looks like school and programming competitions totally occupied my thoughts and actions, thus, leaving no space for something else.
During the October break we made an adventurous trip to Boston, mostly to visit Harvard and MIT campuses (on our way we actually visited RIT as well). 5 days of driving across the northern part of the US!
On December, 25 thanks to the kind invitation from our good friend and teammate Nathan we went to our first Christmas dinner in the US. Several days later, winter break including New Year – 10 days in Hawaii!!! Some of the memorable impressions and emotions are partially reflected in my albums in the Russian social networking website – vkontakte.ru. I got cold in the Aloha island, and it took me about a week to recover. On January, 12, the first day of Spring’09 semester, I had to attend classes with my swollen right eye covered like a Tom Cruise’s character from ‘Valkyrie’.
Spring 2009! My coursework included Operating Systems, Database Management System, Applied Statistics for Scientists and Engineers, and Algorithms. The latter was taught by one of greatest professors I have ever encountered – Mike Atallah. Despite 12 credits (minimum requirement for the full-time student), the semester was quite intense: two project-based courses (namely, OS and DBMS) are the main reasons. OS projects included shell scripting, whole month was on spent on huge Shell project, in April we did multithreading, interprocess RPC and implemented Linux version of malloc (segregated free list, fence posts, boundary tags, coalescing). In CS448 (Intro to Relational DBMS) projects we wrote almost all the aspects of the DBMS including Disk Manager, Buffer Manager, Heap Files, Iterators, Join Methods, Hash Index, Executors, Planner, Optimizer, etc. CS381 was really enjoyable, being brilliant computer scientist, Mike Atallah is wonderful at explaining the algorithms with most attention spent on concept, key idea, the steps which led to its invention rather than on cumbersome notation as in many math classes I took before. As every CS student @ Purdue knows apart from the theory of algorithms with Mike Atallah you can also gain some knowledge in motivation, success and practical wisdom. There’s a Facebook group which collects his most memorable quotes. Check it out, I occasionally contribute some of the aphorisms from the notes.
10 days of the Spring break I spent in Peru. It was my first trip to South America. Machu Picchu, El Lago Titicaca, Puno, Lima, Cuzco… As usual, all the photos are available in corresponding albums in vkontakte.ru.
Taekwondo! I was much regular this spring, than last fall, and on one of the April Saturdays was promoted to blue belt. Movies? Most of them I watched on plane, not much time during the semester. From the ones watched, I would like to note ‘Yip Man’, ‘Yes man’, ‘The Terminal’.
But the quintessence of the whole semester was for sure the ACM ICPC World Finals in Stockholm, Sweden. I enjoyed the whole trip, the royal organization, accommodation, except the last 3.5 hours of the actual competition when we could not solve any problems. The start was OK, we solved two rather easy problems (binary search for each permutation & convex hull). The remaining time was spent hopelessly thinking more about other competitors getting balloons for correct submissions and not concentrating on ourselves. Other two teams from our regional (Waterloo & CMU) were in Top 12 winning bronze medals. After the contest I tried to find the objective reasons of our knockout. Not to discourage ourselves, but on contrary to motivate the continuous growth. The first reason, no matter how broad and vague this sounds, is the lack of preparation. We could not get in to Petrozavodsk programming camp and started regular practices for WF only in the beginning of April, three Mondays in a row we wrote 5-hour contests together with CMU team (remotely via PC^2). The last Monday before the trip to Sweden the team from Duke University joined our training. As a side note, to make this kind of practices nationwide would be beneficial for all the teams going to World Finals. The reason # 2 is that we are not honed to think clearly under major stress circumstances. Another aspect we can improve is the team strategy: for 3.5 hours independently solving 3 different problems w/o luck in the end is definitely no good… Anyway, there are no big victories without defeats, and we are looking forward to compete in the upcoming regional to deserve the next chance in Harbin next February.
Now the short-term goal for the summer is to solve as many problems in Saratov State University Online Judge as possible & compete in all the major contests from this or this list. That’s it for now. Stay tuned. My plans include covering the problems from different contests & archives on which I worked on. And by the way don’t exclude all the remaining topics!