Red-Green-Code

Deliberate practice techniques for software developers

Why Measure Your Productivity?

By Leave a Comment 0

Office Space

It’s impossible to measure developer productivity. At least, that’s what the experts say. Martin Fowler came to that conclusion over 10 years ago in a classic article, and the consensus hasn’t changed since then. My favorite recent article on the subject is by Jim Bird, a development manager and CTO.

So let’s take that as a given: Measuring developer productivity reliably and objectively is a hard problem, maybe an impossible one. But rather than rehash the standard arguments, I’m going to change the rules a bit.

« Continue »

The Competitive Programming Debate

By Leave a Comment 0

Which of the following statements best describes your opinion of competitive programming?

  • -2: It is harmful to the software industry, and should be abolished.
  • -1: It’s no worse than any other form of entertainment, but it has no educational value.
  • 0: It may help some people get better at programming, but it’s a niche hobby.
  • 1: It’s a good way to get better at programming. Every programmer should try it out a few times to see what they think.
  • 2: It should be a required part of all college algorithms classes.

I’m not conducting a survey. These are just statements representing the range of opinions that I have seen while reading the Competitive Programming topic on Quora. (Actually I’m not sure if I have ever seen (2)).

As with any controversial topic, it’s common for people to talk past each other when discussing the pros and cons of competitive programming. In this post, my goal is to express the various arguments as clearly as I can.

That’s not to say that I am neutral on the matter. My opinion is closest to (1). I have written a post about reasons to study competitive programming, and of course much of the content on this blog deals with using competitive programming puzzles for learning. However, I’m always interested to hear differing opinions, especially when they have good arguments to back them up.

With that framework in mind, let’s take a look at what people are saying about competitive programming.

« Continue »

Java Lessons from uHunt Chapter 2

By Leave a Comment 0

Reference2

This post is part of a series on Java syntax and libraries for solving the problems in each chapter of uHunt, a tool for competitive programming practice. You can find the rest of the posts in the series by visiting my uHunt Java post category.

In the previous post in this series, a review of Java for uHunt Chapter 1 problems, I covered Java basics. This time around, I’ll be discussing the additional Java features required to solve the Chapter 2 problems. The problems in this chaper focus on data structures, so we’ll be looking at data structures supported by the Java Class Library.

As before, I have put full examples of all of these topics in my Reference.java reference class. You can look there to find sample code to try out.

« Continue »

Lessons from Competitive Programming 3, Chapter Two

By Leave a Comment 3

CP3Chapter2

This post is part of a series of commentaries covering each chapter of Competitive Programming 3 by Steven and Felix Halim. You can find the rest of the posts in the series by visiting my CP3 post category.

Competitive Programming 3 (CP3) Chapter 2 covers a selection of data structures that are useful for solving competitive programming problems. These data structures are used in the Chapter 2 uHunt problems, and in subsequent chapters in the book. In some cases, Chapter 2 just provides a brief introduction to topics that are covered extensively elsewhere. For example, Section 2.4.1 covers some basic information about representing a graph, while Chapter 4 contains the book’s full treatment of graph algorithms. And Section 2.2 devotes a paragraph each to common data structures like arrays, stacks and queues, which readers are expected to know about already. In other cases, Chapter 2 goes into more depth. For example, it’s harder to find information about the Segment Tree data structure in other sources, so it is covered in more detail in this chapter.

As in the rest of the book, each section in this chapter ends with a list of recommended UVa Online Judge problems. The same list can be found on uHunt, where you can also track your progress.

In addition to UVa OJ problems, each section also has written problems. For example, a question in the section on stacks and arrays asks the reader how to implement a stack using an array. Answers are supplied for some of these problems at the end of the chapter. I have just been skimming these written problems. The appeal for me of the CP3/uHunt approach is that problems are “graded” automatically by a computer. Solving problems and then looking up answers at the end of the chapter is the traditional textbook self-study approach. While that can be useful, especially you have a peer or instructor to review your written answers, my goal in using this book is learning through coding. I found plenty of opportunities to learn about the Chapter 2 data structures while I was solving the corresponding uHunt problems.

« Continue »

Lessons from uHunt Chapter Two

By Leave a Comment 0

uHunt Chapter 2

This post is part of a series that considers what can be learned from the problems in each chapter of uHunt, a tool for competitive programming practice. You can find the rest of the posts in the series by visiting my uHunt post category.

I recently finished the last of the 37 starred problems in uHunt Chapter 2. I’m solving these problems as part of a learning project that I’m calling Project 462, after the 462 uHunt starred problems.

Chapter 2 highlights problems that require more specific data structures than the ad-hoc problems in Chapter 1. The chapter starts out with arrays, covers familiar data structures like stacks and queues, and ends with problems that use Segment Trees and Fenwick Trees, data structures that you may not have heard about in college.

The uHunt approach is to categorize problems by the algorithm, data structure or technique that the authors recommend using to solve them. In addition to the category, each problem has a level — generally 1 through 4 — indicating its difficulty level. The Chapter 2 problems mostly use the same range of levels as the Chapter 1 problems. But for each Chapter 2 problem, there is an extra step of learning or reviewing the appropriate data structure. Although they start with a data structure recommendation, most Chapter 2 problems still require problem-solving techniques and creative thinking.

In many competitive programming situations, you won’t know which data structure to use in advance. The goal of the uHunt style of practice is to get familiar with the range of problems that you’ll come across, so that you know which data structure, algorithm, or technique to use when you see a similar problem in the future.

« Continue »

Solving UVa 11402 with Segment Trees

By Leave a Comment 5

Pirate

UVa 11402: Ahoy, Pirates! is one of the most challenging of the uHunt starred problems I have come across so far, for a few reasons:

  • The problem is designed to be solved using a segment tree. This is a data structure that comes up in competitive programming, but isn’t covered in the standard algorithms textbooks (e.g., Sedgewick or CLRS). So I studied it for the first time in preparation for solving this problem.
  • A static segment tree like the one described in Wikipedia, is not sufficient. Solving this problem requires a segment tree that implements lazy propagation so that updates can be made efficiently.
  • As an extra challenge, the problem author added the requirement for an “invert” operation. This adds some implementation complexity and means a generic segment tree implementation won’t work.
  • Java solutions seem to run very close to the time limit, which is a generous five seconds for this problem. Even an efficient solution that addresses the previous points may nevertheless need some additional performance tweaking to run fast enough.

Read on for solutions to these issues, and an explanation of how to go about coding a solution.

« Continue »

Cal and Scott’s Top Performer Course

By Leave a Comment 0

Bubble

In an earlier post, I mentioned a pilot course I took a couple of years ago on applying deliberate practice to various types of jobs. Well that original pilot, and a subsequent pilot in 2014, has resulted in a course called Top Performer (not an affiliate link). As part of the homework for the second pilot, I came up with the idea for Project 462 and this blog. So as people are considering the course this week, I thought I would add my thoughts to the mix.

« Continue »

Software Methodologies for Very Small Teams

By Leave a Comment 0

Bootstrap DNA

When I was working on my undergraduate degree in Computing and Software Systems, I took a class in software engineering. The purpose of this class was to introduce us to the range of real-world processes that professionals use to develop software, processes that didn’t often come up in our academic work. That goal turned out to be a tall order for a three-month class, given the scope it tried to cover. It might have been more effective to pick one process and use it for a group project. Nevertheless, one exercise I remember from the class is matching software development processes to types of projects.

Here’s the type of question I’m talking about, from a University of New Brunswick class assignment:

Giving reasons for your answer based on the type of system being developed, suggest the most appropriate generic software process model that might be used as a basis for managing the development of the following systems:

a) A system to control anti-lock braking in a car

b) A virtual reality system to support software maintenance

c) A university accounting system that replaces an existing system

d) An interactive travel planning system that helps users plan a journey with the lowest environment impact

« Continue »