Last Friday (January 20, 2012) marked the first Programming Team practice at the University of Akron this year. The topic was Solving Problems Quickly (link shows the problems we worked on and a couple sample solutions).

Background

If you’re not specifically interested in the UAkron Programming Team (or Programming Team coaching in general) jump down to Backseat Coding.

For the last several years we’ve really focused on algorithms and I think the team has benefitted greatly from that, taking 13th and 28th place out of 122 teams at the ACM ECNA Regional last semester. However, the actual scoreboard from the contest show something troubling:

  • Consider our team qUArk which took 13th place with 4 problems correctly solved. Their first correct solve was at 53 minutes, second correct solve not until 135 minutes….
    • The team in 14th place had all 3 of theirs by the time we only had 2.
    • The team in 11th place had 3 of theirs in just a bit longer than it took us to get 1.
    • We were the slowest team to solve 4 problems (ranging from a 1 minute delta against 11th place to a 272 minute delta against 9th place).
    • The 4th problem solved was, statistically, one of the harder problems. Problems C and E should have been easier.

What’s the takeaway? We have smart kids who can solve hard problems given enough time. The fact that they solved F proves this. But, imagine if they had solved the three “easy” problems ({B, D, I}) in the same amount of time as “Cowgorithms” (the fastest team to solve 4 problems, who were unable to solve F after 6 attempts) who were done with {B, D, I} at the 68 minute mark (versus our time of 194 minutes). I firmly believe we would have solved a 5th (and maybe even 6th) problem given that extra 126 minutes. We need to get better at solving the “easy” problems quickly. It’s not as fun as dynamic programming or as exciting as getting a complicated graph problem to work, but it’s essential to the continued improvement of our program.

Backseat Coding

(I’m purposely avoiding calling this Pair Programming because of the connotation that comes along with that term. While similar in implementation, our goal is different – we are not concerned with code maintainability, exception handling, usability, etc. – we are worried with getting a correct implementation in the absolute minimum amount of coding time possible while also thinking about upcoming problems in the background.)

When I started programming competitions, I was awful. I had problems with syntax, couldn’t visualize a solution to relatively easy problems until I had been coding for maybe 40-50 minutes. We had programming team practices (via a course called Competitive Programming) once a week, and simply showing up and solving problems eventually made me faster, but still not fast enough.

Then I met my eventual coding partner in crime, Corey. By the time I was a senior, we could solve easy problems fast as a pair. Check out these results from Denison’s 2006 Contest (we were team BW-CD) –problems solved at the 9, 24, 53, 98, 105, and 148 minute marks. I don’t think we were any smarter than team “UsII”, but we had 2 solved by the time they had 1 solved, 3 when they had 2, and 6 when they had 3. Problem C was arguably the only hard problem in the set (modified DFS), and the other teams at the top just didn’t have time to properly tackle it.

Why were we able to execute so fast? Because of our great communication and our willingness to be involved backseat coders.

Luckily, Corey and I were friends and we felt comfortable asking questions, requesting clarifications and, sometimes, telling each other they were just wrong. We also both enjoyed proving the other person wrong so we would both be constantly trying to think of edge cases or counterexamples that would break the other’s code. This is a great practice because the judges have spent many, many hours coming up with edge cases for the exact same purpose.

Because the programming team typically has 3 members and 1 terminal, it’s often a good strategy to have two developers at the computer at the same time. I almost always see the person typing quietly coding away while the other person watches and looks for syntax errors, copy/paste errors, etc. This is not good enough. The person typing has a lot of things going on in their brain. They’ve got their idea of the algorithm in their head. They’re making sure everything is tabbed in and braced correctly. They’re worried about loop bounds… Both team members need to worry about these things, but even more importantly, they both have to have a firm understanding of the algorithm and be on the same page.

Algorithms need to be conveyed using words:

  • “We need a loop to read the input, just make a while loop”
  • “If the input is 0, we quit.”
  • “We need to read in n nodes, so make another loop from 1 to n to read them in.”
  • “Now, we just need to make a recursive method to traverse the loop with a global list of visited nodes… Just call the method here and we’ll implement it in a minute”
  • Etc.

If there’s more than about 30 seconds of silence while two coders are at the computer together, I start to worry. At least one party should be conveying the algorithm in words, calling out syntax errors, asking questions, etc.

If the person not typing has a posture that is less engaged than the typist, I worry. The only excuses to not be leaning forward, reading code, talking about the algorithm are deep thought about potential counterexamples that will invalidate the entire approach and drawing out examples on paper.  Excepting these situations, the absolute minimum amount of communication otherwise is the non-typist saying “Yep, looks good, makes sense,” because even that lets the coder know that they’re both on the same page.

Want to solve the easy problems faster so that you can have more time for the hard problems?

  • Communicate while you type. Explain what you’re doing, walk through the algorithm.
  • Lead the way without a keyboard. Make sure you’re in sync with the coder. Walk through the algorithm, think about counterexamples & edge cases. Draw out example cases.
  • Use phrases like
    • Next, we need to loop through the…” This shows you both understand the overall approach to the algorithm.
    • Did you account for the case where…” You should be thinking of edge cases and counterexamples. Is it going to blow up when n = 2,000,000,000?
    • Why are you doing that?” If you don’t understand something the other types/says, you won’t be able to effectively help at all.
    • It’ll take half the time to code this if you… If you understand what they’re trying to accomplish and see them taking an approach that takes a long time to code or is highly error prone (picture a long list of if/else’s due to bounds checking that could be avoided by adding a buffer row/column to a table), you should step in and dictate the faster solution to them. This only works if every other bullet point has been accounted for and your teammate trusts you.
  • Do NOT use phrases like
    • It’s faster if you write ++i.”
    • You should never write while(true).”
    • You know you can decrease the size of tabs in the editor settings…
    • But you’re wasting like 65 array entries.” (More on this one in my next post…)
    • ” (That’s the sound of you being too passive.)

I realize that I’m making this sound easier than it is.  Well, actually, I do think it’s easy… but it requires practice. The amount of practice necessary really depends on personality type – some developers think they’ll never be the type of person who can effectively communicate ideas about programming in real time… I think those people just haven’t had enough practice or perhaps never had a safe environment in which to try without fear of failure.  I believe this is one of the main benefits students receive by participating in ACM Programming Teams, but most coaches (myself included) struggle with teaching this skill.

Any suggestions on teaching this skill, thoughts on Pair Programming, or other comments are welcome.

Posted in Pair Programming, Programming Contests | Leave a comment

The University of Akron competed in the ACM East Coast North America Regional last weekend. The ACM International Collegiate Programming Competition is held yearly, with Regional events taking place all across the world including 11 regionals in the United States. You can find all relevant information from the contest including the problem set here.

There were 122 teams from 60 schools at our regional competing to solve as many of the 9 problems as possible within the 5 hours provided, and Akron’s teams came in 13th and 28th place! Teams must contain 3 full time students and may contain at most one graduate student. The teams that represented Akron were:

qUArk: 13th place with 4 problems solved (1st place 46 at YSU location)
Jeff, Adam, and Nick

qUAck: 28th place with 3 problems solved (4th place of 46 at YSU location)
Alex, Eric, and Jarryd

Because our region is large, the contest is held simultaneously at 4 satellite locations, and our teams took 1st and 4th place at the Youngstown State University location which hosted 46 teams!

Only teams from 4 schools managed to solve more problems than team qUArk, including Waterloo, Toronto, Carnegie Mellon, and Michigan (with a couple other schools also solving 4 problems correctly but in less accumulated time).

Congratulations to both of our teams for their phenomenal performance this year! Achieving these ranks is the result of weeks and weeks of Friday night practices where these and other students spend their time learning new algorithmic techniques, honing their coding skills, and improving their teamwork.

In the coming weeks, I’ll be posting detailed explanations of the solutions to some of the harder problems in the set (skipping the 4 most solved problems ({B, C, D, I})). Stay tuned!

Posted in Programming Contests | Leave a comment

The 2nd Annual University of Akron Programming Competition took place on Saturday, April 30th, 2011. There were 6 teams in attendance made up of current UAkron students (although we’re considering opening up the event to other schools in the future). My responsibility for the event was writing the problem set and judging proposed solutions. The problem set can be found here:

Revised Contest Problem Set

I’ll give a bit of background on the problems here. This may contain spoilers, so if you want to work on the problems you may want to skip the rest of this post. These explanations assume you’ve read (or at least looked at) that problem.

Problem A: Overlapping 2D Barcodes

   Difficulty: 1/5, Solved by 6/6 teams

This problem is pretty straight forward, and mainly involves nested loops and checking individual characters within a string. This problem was solved by 6/6 teams.

Problem B: Randomly Evaluated Boolean Expressions

   Difficulty: 5/5, Solved by 0/6 teams

This is one of the hardest problems in the set. The root problem is considering all of the full parenthesizations of a boolean expression and figuring out how many of those parenthesizations return True. Here are a couple larger examples than the problem description provides:

Input: return T or F xor T and F xor T or F xor T and F and T xor F or T or T or F xor F and T xor F;
Output: 7161517 of 9694845

Input: return F xor T and T xor F or F or T xor T and T xor F xor T xor F and T or F and F xor T and F and T xor F or T and T xor F and F and T xor F and T xor F xor T and F and T xor F and F or T xor T xor F or F or T;
Output: 2288490719605020900 of 3116285494907301262

The problem also involves utilizing randomly evaluated local variables as part of the final return statement, rather than just returning a statement full of constant T / F values.

Input:
5
Boolean a = T xor F xor F xor F and T;
Boolean b = T and F or F;
Boolean c = T and T xor b and b xor T and F;
Boolean d = a or c or F or F xor b xor c;
return c and d or d and T and F;
Output:
197061645695975424 of 2591129315051569152

The efficient solution involves Dynamic Programming and is O(n^3) where n is the number of terms in the Boolean expression.

Problem C: Long Division

   Difficulty: 3/5, Solved by 1/6 teams

This problem mostly involves output formatting and bookkeeping as you must emulate the full process of long division, and there are many places that formatting errors can creep in if you aren’t careful.

Problem D: Heart Monitor

   Difficulty: 1/5, Solved by 6/6 teams

This is one of the two “easy” problems in the set (along with Problem A). The only real problem encountered by teams was not following the definitions of “impossible” and “concerning” heart rates precisely.

Problem E: Inverse Function Domains

   Difficulty: 4/5, Solved by 0/6 teams

This is an interesting problem, and a bit trickier than I thought when I was originally writing it. I originally thought you could just sort the incoming points by x value, then travel the function marking y values as hit every time a line segment went through that y value. This almost worked, except for the case of {(0, 1), (1, 0), (2, 3), (3, 2)} which results in the open interval (1, 2), but this is missed if only integer y values are tracked. Updating the solution to keep track of *.5 values solves this issue, at which point it becomes a matter of formatting the output with proper set notation.

Problem F: Late For the Final Exam

   Difficulty: 5/5, Solved by 0/6 teams

This is the other crazy problem in the set (along with Problem B). It’s a “shortest path” problem when driving between points on a directed graph (in the Cartesian plane). The catch is that there is a speed limit, rate of acceleration & rate of deceleration, and a maximum speed at which turns can be navigated (full speed at a <10 degree turn, full stop at a >90 degree turn, and a linear relation between 0 and full speed between 10 and 90 degree turns). Figuring out the minimum drive time between two points in the graph involves not only a graph traversal and calculation of maximum turning speed at various angles, but also the amount of time required to navigate a segment of road given the road length, starting speed and maximum ending speed (which may or may not be achieved). It ends up involving a reasonable amount of algebra and to calculate these times.

Problem G: N Degrees of Ashton Kutcher

   Difficulty: 2/5, Solved by 1/6 teams

This is a fairly simple graph problem. The only awkward part is input reading because people are introduced during the descriptions of other people, so they may not have an ID yet (depending on the implementation).

Posted in Programming Contests | Leave a comment

I’m back from MIX11 in Las Vegas, which was absolutely awesome. My talk about Windows Phone 7 App Analytics is linked above, but can also be found at its official home on the Channel 9 MIX Event site, where you can leave comments or rate the session.

Regarding MIX in general, I think the updates coming to Windows Phone 7 in the Mango update look really promising. The performance profiler coming in the dev tools update looks really, really cool. I also can’t wait to use the official Kinect SDK when it is released later this Spring.

Posted in .NET, Application Analytics, MIX, WinPhone7 | Leave a comment

I’ll be speaking at Microsoft’s MIX Event (April 12-14) in Las Vegas as one of 11 selected “Open Call” sessions. The session is titled “Who Would Pay For That Feature? Adding Analytics to Your Windows Phone 7 Applications.” I’ll be discussing a few things:

The world of mobile analytics
A lot of people associate “mobile analytics” with “web analytics,” particularly on Windows Phone 7 where most applications are written in Silverlight. However, you don’t have to settle for only knowing which pages of your app are being visited; the analytics available on WP7 are customizable and quite deep (gathering runtime strings, exception reports, etc.). As such, there may be privacy concerns when gathering such deep analytics, so you may want to consider surfacing an opt-in for your users (similar to how Visual Studio or Expression Blend ask you on their first launch if you want to participate in their Customer Experience Improvement Program). This may feel like a lot to think about, but it’s really just one large opportunity for you to gain unique insight into your application AND your users.

Analytics as a full-fleged part of your development cycle
I mentioned a lot of options in the previous section, but it’s not overwhelming if you consider analytics as truly part of your development cycle, starting with understanding requirements. You may only be interested in knowing how many unique users you have and how often they’re using your application. Or maybe you want to know more about which areas of your app users are interacting with. Maybe you actually want to know more about your users and how you can categorize & target them with content updates, new features, or bug fixes. Either way, you should come to the table knowing what questions you hope analytics will help you answer.

Once analytics are collected and analyzed (which I’ll discuss below), the next step is to use that information to decide how to improve your app. It may even make you realize you have a new question about your users that analytics could help you uncover, but you didn’t think of the first time through.

Practical demos on gathering analytics using Dotfuscator & Runtime Intelligence for Windows Phone 7
I’ll walk through the instrumentation of a sample app using Dotfuscator & Runtime Intelligence (which is free for Windows Phone 7 developers thanks to Microsoft), from the very basics (counting application runs and unique users) to the complex (tracking how long a web service call takes, and combining those timings with the type of network connection on the phone at that time).

Analyzing analytics results
Lastly, I’ll show the culmination of all of our efforts so far — the data! I’ll be showing off both default reports and the truly unique insights that can be gained by exporting custom runtime data and doing app-specific pivots on the data.

If you’re developing a Windows Phone 7 app and want to know precisely what to work on for your next release (whether to improve your user feedback ratings or earn more money through sales or adds), you should definitely see this session or watch it afterward on the MIX website.

Posted in .NET, Application Analytics, MIX, WinPhone7 | Leave a comment

The UAkron Programming Team had its first practice of the new year last night. I’m very excited for this semester — we have a number of first year competitors who are learning the ropes and a solid group of veterans who all seem energetic about the process. We’ve expanded our practices to 6-10 PM on Friday evenings (compared to the previous schedule of 7-10PM). This will give us more time to actually discuss techniques and algorithms rather than just chugging away on problems (which, don’t get me wrong, has tons of value).

There will hopefully be three main events for the team this spring: The Denison Spring Programming Contest, Ohio Wesleyan University Programming Contest, and hopefully the 2nd Annual UAkron Programming Contest (internal only as of now).

One of my personal goals is to write 5 or 6 new problems this semester and slip them in with the weekly practice problem sets.

For the first practice, I had taken the last 6 years of contest problems from the Denison Spring Programming Contest and organized them by difficulty level (as determined by percentage of teams that correctly solved them) and algorithm category (2D Array Manipulation, Graph Traversal, Dynamic Programming, etc.). The results were somewhat interesting. I’ll post my findings once I have a chance to better define the algorithm groups (currently Generating Permutations and Generating Subsets are distinct groups, but should probably be aggregated up into a Combinatorics group). Based on the most frequently occurring problem types, we spent the practice focusing on string manipulation & 2D array manipulation, and introducing graph problems. Next week we will talk about a few basic approaches to graph problems (sticking to simple BFS/DFS) and then tackle some related problems. I’ll also be posting the prep materials I create in the hopes that it is of use to someone.

Posted in Programming Contests | Leave a comment

I recently launched PointingAtThings.com, a pretty simple website that allows people to upload pictures of themselves or their friends pointing at things in pictures. Website viewers are presented with two images of people pointing at things and may choose which one they like more. They are then presented with new pairings until they get bored.

There are currently 27 live images of people pointing at things to vote between, depicting 15 distinct people in the act of pointing. We’ve had a total of 2474 votes from 105 unique IP addresses.

For me, the fun part of this project is coming up with interesting ways of ranking the images. Currently, after you vote between two images, you are presented with two sets of statistics. One set is based on the votes that were cast for that exact matchup. If you’re voting between image 5 and image 8, then these statistics will show you how many times 5 beat 8 (and vice versa) in direct, head to head competition.

I worry that if many images are added, we’d quickly get to the point where most matchups encountered by voters are new or have very few existing votes (the number of votes would have to grow quadratically versus the number of images available to vote on to prevent this), so I want a way to get a sense of which picture is more liked in a pair without having direct matchup votes.

A simple way of doing this is looking at the win/loss record for each image individually (against all opponents), and comparing their win percentages. This is a decent measurement, but it doesn’t take # of votes cast for that image into account (this would prefer an image with 2 votes and a 100% win percent over an image with 1000 votes and a 95% win percent).

Hence, one of my main goals will be to implement various other ranking algorithms, such as Elo and TrueSkill. Elo seems a lot more straightforward than TrueSkill, but I have a particular interest in TrueSkill from my addiction to the Rock Band 2 leaderboards, which are implemented on top of TrueSkill.

There are a number of planned improvements to the site. Since the original launch, we’ve added the creation of correctly sized thumbnail images to decrease page load times, as well as a full administrator console to provide moderators the ability to approve / remove submitted images. Future improvements include S3 image hosting, individual image pages, upload acceptance email notification, and an attribution field so we can use Creative Commons – Attribution licensed images. If you’re a graphic artist and you have an interest in helping us lay out the homepage awesomely, please let me know!

I’ll post here when we have major releases, or with occasional interesting statistical tidbits.

Posted in Pointing At Things | Leave a comment