One year ago, I started writing here on the topic of deliberate practice techniques for software developers. This is my 52nd weekly post for 2015. With the year coming to an end, let’s review the story so far.
Math Fluency for UVa 927
From time to time, I’ll run across a UVa problem description that makes liberal use of mathematical notation. UVa 927, the first starred problem in uHunt Chapter 3, is one of those. uHunt classifies it as a Level 4 problem, but most of the challenge is in interpreting the problem description. Once you figure out what it’s asking for, the problem itself is straightforward.
The Role of Questions and Answers in Learning
Here are two approaches you could take to learn something new:
Passive review: Consume an explanation of the topic you’re trying to learn. For example, read a textbook chapter, watch a video lecture, or read an online article on the topic.
Active recall: Do an activity that requires you to remember something that you know about the topic. For example, go through a set of flashcards, write an essay, or take a practice test.
It shouldn’t be hard to guess which of these approaches is more effective at reinforcing what you know about a topic. Although you have to consume new information at least once through a lecture or other means, continuing to passively consume the same information repeatedly doesn’t help you learn it much better. The brain seems to take retrieval more seriously than storage: neural connections are strongly reinforced when information is actively used, but information that merely arrives through the senses receives a comparatively weak boost.
Why Measure Your Productivity?
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.
The Competitive Programming Debate
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.
The Time Bank Productivity System
Earlier this year, I wrote a survey of the Productivity Habits that I’m using to keep my project moving along. This week, I’m going to focus on one habit, which I’m calling Time Bank. I’ll also share a handy spreadsheet that makes it easy to try out this system.
Java Lessons from uHunt Chapter 2
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.
Lessons from Competitive Programming 3, Chapter Two
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.
Lessons from uHunt Chapter Two
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.
Solving UVa 11402 with Segment Trees
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.
- « Previous Page
- 1
- …
- 43
- 44
- 45
- 46
- 47
- …
- 50
- Next Page »