When you’re designing or writing software, one issue that can often be glossed over is the matter of efficiency. It’s so easy at the beginning of a project to just concentrate on getting something working, so you can demonstrate progress, and then worry about making it fast later on. The unfortunate fact is though optimisation can only take you so far, the true efficiency issues are going to lie in your algorithm design. Most IT professionals have learned the basics at some point in their career, but in case you’re a little rusty read on and we’ll refresh your memory.

The first thing to consider is what kind of complexity you’re looking to reduce. The two major complexity areas are time — that is, how long an operation will take to complete — and space, or how much memory is needed. When talking complexity, we tend to rate speed in terms of how many steps (or blocks of memory for space complexity) are taken per input variable, rather than in absolutes, since they are so dependent on the specifics of the hardware. Likewise, the length of time an individual step will take is largely disregarded since for large inputs this time will be dominated by the complexity class.

To make comparing two algorithms easier we group them into classes by using a special kind of notation. There are a number of different ways to do this, based upon the best case, average case and worst case input scenario. I like to use the worst case most of the time, since that’s the time it’s going to make the most difference to how you perceive performance. To express this we use what’s called big O notation, which expresses the number of steps an algorithm will take for an input of size “n” in the worst case. So, take the following example, which simply sums the numbers in a list.

sum(a) {
final_sum = 0
n = length(a)
for (i = 0; i < n; i++) {
sum += a[i]
}
return final_sum
}

Treating each line as a single step, we can see that calling sum on a list of size n will take n+4 steps to complete, two for the initialisation of final_sum and n, one to set up the for loop, one for the return statement and then n times one for the loop body.

The problem has changed, and now you need to multiply each number by how many times it occurs in the list before adding it to the running total. Take the following implementation:

sum_multiple(a) {
final_sum = 0
n = length(a)
for (i = 0; i < n; i++) {
num = 0
for (j = 0; j < n; j++) {
if (a[j] == a[i]) {
num++
}
}
final_sum += a[i] * num
}
return final_sum
}

This does similarly to the last function, with the exception that before adding the current value to the running total, it goes through the list and counts the number of occurrences of each value. Calling this function of a list of size n means that 4 + n * (1 + n * 2) steps are carried out since the outer loop now contains 2n + 1 steps. In total this means that calling this function “costs” 2n2 + n + 4 steps. For a list of 10 numbers it takes 214 steps, but for a list of 100 numbers it will need more than 20,000 steps to complete. That’s quite an increase. When we rewrite it in another way, however, this changes:

sum_multiple2(a) {
final_sum = 0
n = length(a)
numbers = dict()
for (i = 0; i < n; i++) {
if (numbers.has(a[i])) {
numbers[a[i]]++
} else {
numbers[a[i]] = 1
}
}
for (j = 0; j < n; j++) {
final_sum += a[j] * numbers[a[j]]
}
return final_sum
}

In this example we precompute the number of times each value occurs in the list. To do this we use a new data type which can store these values. It’s not particularly important how this is implemented so long as we can be sure that we can insert and retrieve values in constant time. In languages that support them as standard this could be a hash or a dictionary, or if you’re not that lucky (say you’re using C) then you can think of it as an integer array of size max(a). The method simply returns true if this type contains a the given value.

Anyhow, you can see how rather than work out how many times each number occurs as we reach it we can do it all at the beginning and store it. Let’s look at how this helps — sum_multiple2 takes 3n + 6 steps: the usual initialisation steps, plus two for each input to build the dictionary of number occurrences, and then one for each input to sum them. For 10 inputs this will take 36 steps, for one hundred: 306. That’s more than 65 times faster for the second version when dealing with 100 inputs. If say, we had one million inputs it becomes two trillion vs three million and the second version is more than 650,000 times faster.

Now we’ve been taking a fairly casual view of the number of steps in each algorithm, treating each line as one step, when a statement like “sum += a[j] * numbers[a[j]]” contains multiple lookups and could be compiled into as many as 10 individual instructions on a hardware level. This is not really that important though, when you think about it, even if we assume that every step we’ve counted in the second example really takes 10, and the first program is unchanged then it still represents more than a 60,000 times improvement.

Really what we’re interested in is the order of the algorithm, for convenience, we reduce it to the size of the largest part. For example, sum_multiples we say is O(n2) whereas sum_multiples2 is O(n). This is often all you really need to know, for large enough values of n, O(n) algorithms will always beat O(n2) algorithms, regardless of the details.

Waterfall development is a software development model involving a phased progression of activities, marked by feedback loops, leading to the release of a software product. This article provides a quick and dirty introduction to the model, explaining what it is, how it’s supposed to work, describing the six phases, and why the model can fail.

Say the words “waterfall development” to most people and chances are they’re going to be thinking of a bunch of condos under Niagara Falls. Imagine their surprise, then, when you tell them that waterfall development is actually a software development model which involves a phased progression of activities leading to the release of a software product. This article provides a quick and dirty introduction to the model, explaining what it is, how it’s supposed to work, and why it can fail.

Overview

Waterfall development isn’t new — it’s been around since 1970 — but most developers still only have a vague idea of what it means. Essentially, it’s a framework for software development in which development proceeds sequentially through a series of phases, starting with system requirements analysis and leading up to product release and maintenance. Feedback loops exist between each phase, so that as new information is uncovered or problems are discovered, it is possible to “go back” a phase and make appropriate modification. Progress “flows” from one stage to the next, much like the waterfall that gives the model its name.

A number of variants of this model exist, with each one quoting slightly different labels for the various stages. In general, however, the model may be considered as having six distinct phases, described below:

1. Requirements analysis: This first step is also the most important, because it involves gathering information about what the customer needs and defining, in the clearest possible terms, the problem that the product is expected to solve. Analysis includes understanding the customer’s business context and constraints, the functions the product must perform, the performance levels it must adhere to, and the external systems it must be compatible with. Techniques used to obtain this understanding include customer interviews, use cases, and “shopping lists” of software features. The results of the analysis are typically captured in a formal requirements specification, which serves as input to the next step.
2. Design: This step consists of “defining the hardware and software architecture, components, modules, interfaces, and data…to satisfy specified requirements” (Wikipedia). It involves defining the hardware and software architecture, specifying performance and security parameters, designing data storage containers and constraints, choosing the IDE and programming language, and indicating strategies to deal with issues such as exception handling, resource management and interface connectivity. This is also the stage at which user interface design is addressed, including issues relating to navigation and accessibility. The output of this stage is one or more design specifications, which are used in the next stage of implementation.
3. Implementation: This step consists of actually constructing the product as per the design specification(s) developed in the previous step. Typically, this step is performed by a development team consisting of programmers, interface designers and other specialists, using tools such as compilers, debuggers, interpreters and media editors. The output of this step is one or more product components, built according to a pre-defined coding standard and debugged, tested and integrated to satisfy the system architecture requirements. For projects involving a large team, version control is recommended to track changes to the code tree and revert to previous snapshots in case of problems.
4. Testing: In this stage, both individual components and the integrated whole are methodically verified to ensure that they are error-free and fully meet the requirements outlined in the first step. An independent quality assurance team defines “test cases” to evaluate whether the product fully or partially satisfies the requirements outlined in the first step. Three types of testing typically take place: unit testing of individual code modules; system testing of the integrated product; and acceptance testing, formally conducted by or on behalf of the customer. Defects, if found, are logged and feedback provided to the implementation team to enable correction. This is also the stage at which product documentation, such as a user manual, is prepared, reviewed and published.
5. Installation: This step occurs once the product has been tested and certified as fit for use, and involves preparing the system or product for installation and use at the customer site. Delivery may take place via the Internet or physical media, and the deliverable is typically tagged with a formal revision number to facilitate updates at a later date.
6. Maintenance: This step occurs after installation, and involves making modifications to the system or an individual component to alter attributes or improve performance. These modifications arise either due to change requests initiated by the customer, or defects uncovered during live use of the system. Typically, every change made to the product during the maintenance cycle is recorded and a new product release (called a “maintenance release” and exhibiting an updated revision number) is performed to enable the customer to gain the benefit of the update.

Advantages

The waterfall model, as described above, offers numerous advantages for software developers. First, the staged development cycle enforces discipline: every phase has a defined start and end point, and progress can be conclusively identified (through the use of milestones) by both vendor and client. The emphasis on requirements and design before writing a single line of code ensures minimal wastage of time and effort and reduces the risk of schedule slippage, or of customer expectations not being met.

Getting the requirements and design out of the way first also improves quality; it’s much easier to catch and correct possible flaws at the design stage than at the testing stage, after all the components have been integrated and tracking down specific errors is more complex. Finally, because the first two phases end in the production of a formal specification, the waterfall model can aid efficient knowledge transfer when team members are dispersed in different locations.

Criticisms

Despite the seemingly obvious advantages, the waterfall model has come in for a fair share of criticism in recent times. The most prominent criticism revolves around the fact that very often, customers don’t really know what they want up-front; rather, what they want emerges out of repeated two-way interactions over the course of the project. In this situation, the waterfall model, with its emphasis on up-front requirements capture and design, is seen as somewhat unrealistic and unsuitable for the vagaries of the real world. Further, given the uncertain nature of customer needs, estimating time and costs with any degree of accuracy (as the model suggests) is often extremely difficult. In general, therefore, the model is recommended for use only in projects which are relatively stable and where customer needs can be clearly identified at an early stage.

Another criticism revolves around the model’s implicit assumption that designs can be feasibly translated into real products; this sometimes runs into roadblocks when developers actually begin implementation. Often, designs that look feasible on paper turn out to be expensive or difficult in practice, requiring a re-design and hence destroying the clear distinctions between phases of the traditional waterfall model. Some criticisms also center on the fact that the waterfall model implies a clear division of labor between, say, “designers”, “programmers” and “testers”; in reality, such a division of labor in most software firms is neither realistic nor efficient.

Customer needs

While the model does have critics, it still remains useful for certain types of projects and can, when properly implemented, produce significant cost and time savings. Whether you should use it or not depends largely on how well you believe you understand your customer’s needs, and how much volatility you expect in those needs as the project progresses. It’s worth noting that for more volatile projects, other frameworks exists for thinking about project management, notably the so-called spiral model…but that’s a story for another day!

There are many ways to gather requirements. Interviewing — where you talk to the people who will define the new solution to determine what they need — is probably the default technique for most projects.

Interviewing can be an easy process if the person you’re talking to is organised and logical in their thought process. Since that’s not always the case, however, you have to employ good interviewing techniques in order to start and guide the interview.

There are a number of formal interviewing techniques that will make the requirements gathering process go more smoothly. Here they are.

Start off with general questions.

Typically, you don’t start the discussion by asking narrow, targeted questions. You’ll want to start more high-level and general questions. These questions should be open-ended, in that they require the interviewee to explain or describe something and can’t be answered with a "yes" or a "no". Your goal is to gather as much information as possible with the fewest number of questions.

Ask probing questions.

After you ask general, open-ended questions, you should then start to probe for details. Probing questions are probably the most valuable type of questions, since they tend to result in the detailed requirement statements you’re looking for.

Be persistent.

If you experience any difficulty understanding the interviewee’s point, ask follow-up questions. You can also ask for examples that will illustrate the points the interviewee is making.

Ask direction questions when you need additional information.

Direction questions start to take the discussion in a certain direction. They’re used to provide context and background. For example, "Why is that important to you?" or "Why do you care about that?" are questions that can provide direction.

Ask indirect questions to gain better understanding. Indirect questions are used to follow up on specific points that were raised previously. These questions are used to gain more clarity so that you can ask better questions next. For example, "Is that important because of …" or "You said everything needs to be secure because …"

Ask questions that validate your understanding.

A good interviewing technique is to restate what you just heard back to the interviewee to validate that you understood him/her correctly. For example, after hearing an answer, you could say "If I understand you correctly …"

Paraphrase.

This is similar to the prior technique except that you would take a large amount of information from the receiver and simplify it in your own words. For instance, after hearing the interviewee give a five-minute answer on how a process works today, you could paraphrase the basic points of what he/she said in a quick bulleted list of process steps. For example "So, in other words, the process you use today is basically 1,2,3,4 …"

Ask for examples.

In many (or most) cases of gathering requirements, the interviewer is not totally familiar with all of the information provided by the interviewee. Therefore, one effective way to gain more understanding is to ask for examples. This can also be utilised when the interviewee provides feedback that does not sound totally valid or totally believable. Asking the interviewee for an example helps lend a concrete and specific instance that may help make the requirements clearer. For example, "Can you give me an example of how that affects you?" can help make a statement more clear.

Keep the discussion back on track.

Sometimes the interviewee starts to talk about things that are outside the scope of the specific information you’re trying to gather. This is sometimes caused by a misunderstanding of the question you asked. Other times it’s caused by a lack of focus or a desire to talk about things that are of more interest to the interviewee. When the discussion gets off track, the interviewer must get back on track. An example of this technique would be "That’s a good point. However, can you describe how that relates to (…restate your original question…)?"

Try to stimulate ideas.

Sometimes the interviewee gives the obvious answers but isn’t thinking about other areas that may not be as obvious. The interviewer should try to get the interviewee to stretch a little and think about things that are not quite as obvious. For instance, you can ask "Can you think of a couple options for this situation?" or "Are there other ways to solve this?"

After yet more research into the various species that inhabit this working world of ours, I return with a new set of taxonomic classifications. This time, we concern ourselves with the team leader, in all his or her many guises.

As ever, there are many competent and sociable team leaders in IT departments; but they don’t make for great storytelling. Picking the worst and most dangerous types can help us recognise the signs and maybe even glean a little entertainment from them.

1: Dux Timeris

Fearful Leader

This team leader was persuaded to take the leadership job for two reasons: First, the powers that be decided that there should be a team leader so they could devolve some of their duties to someone who can’t answer back. They picked the least confident team member and tailored the promotion process to ensure that the correct candidate was appointed.

Second, this person was the last to get through the door when the call for volunteers went out. He may have been trampled underfoot in the rush and was slightly concussed when the job offer was made.

Now that this new leader is hooked, he’s too timid to ask to be re-graded and spends a lot of his free time worrying about the job. This is completely unfair, as this type is usually a good person trying to do a good job.

Favourite saying: "Can somebody help me please? Anybody?"

2: Dux Fulvus Nasus

I will leave you to translate the Latin for yourself

This leader does not think for himself but hangs on every word passed down to him from on high. If the boss told him that the sun was inhabited by pixies he would send Christmas cards to them.

He cannot believe what he is hearing when somebody on the team disagrees with a management decision; more worryingly, every critical word uttered within his earshot is reported back directly. Once aware of this, a team can make good use of it for propaganda purposes.

Consider the day of the Christmas party, for instance, when our help desk team was told that it was not permitted to attend. We weren’t expecting any calls, as virtually the whole company was at the bash. We decided, within the hearing of the Dux FN, that we would wait for the party to start and then go home. An hour later, our invite to the party had arrived, with an instruction to switch the phones over to voicemail.

Favourite saying: "I was talking to the boss this morning. Wonderful man!"

3: Dux Magnifica

The Paragon of all the Virtues

This person is under the misapprehension that he has arrived, that he or she is "Look on my works, ye Mighty, and despair!"

Yes, this jerk is full of himself. You would think he had just been appointed World President instead of a glorified tea boy. He took to wearing a pin-striped suit on appointment to the position.

He refers to the senior directors of the company as his colleagues or "fellow members of the management team." He is not a tattle-tale. The views of those under him are far too inconsequential to be listened to, much less acted upon.

Favourite saying: "Follow me lads; I know what I am doing!"

4: Dux Trogloditica

Cave Man

This leader is a technical expert who lives, eats, and breathes computers. He leaves the office at the end of the day and goes home to a techno cave where he spends his off-duty hours making his stock of computers, one that NASA would be proud to own, do things that they were never deigned to do.

When he is not thus engaged, he attends conventions dressed as his favourite character from a variety of science fiction films. D Trog is the first person to talk to about a technical problem and the last person to ask about any leadership or personal hygiene issue.

Favourite saying: "I think you’ll find that James T. Kirk never said, ‘Beam me up Scotty.’ The nearest he got was, ‘Scotty beam me up!’"

5: Dux Dictatorialis

The Dictator

You can say what you like about Dux Dictatorialis, but under him all the calls were logged on time. He (and it usually is a he) is an obnoxious person who can’t understand that people have a life outside of work and wants the world to know that HE is in charge. People who disagree with him usually disappear and are never seen again, although a trip to the media library or any other dark and dusty storage facility may give a clue as to their fate.

The worst thing about any dictatorship is that the weaker members of the team find themselves siding with the bully and become bullies themselves. Fortunately, this species is becoming rare in the wild, as there are many predators and few allies.

Favourite saying: "Come on, get with the program!"

6: Dux Nihilistica

Leader of Nothing and Nobody

D Nihilistica is an unhappy and lonely leader. He was made team leader, but the snag is that his team consists of just one person: himself. He has been doing the same job for a number of years and generally speaking, he does a pretty good job. A year ago, he was surfing a recruitment Web site and was spotted by his boss. They don’t want to lose him, as they would have great trouble in replacing him, especially at the paltry salary they currently offer.

Luckily, they persuaded him to stay by awarding him an upgrade in his status, a move that cost nothing.

Favourite saying: He doesn’t have one; there’s nobody to talk to.

7: Dux Amicus Bonissimus

The Best Mate

The Best Mate wants to please everybody all the time. Nobody ever explained the impossibility of this, so he continues trying, even though experience should tell him that he’s on a hiding to nothing. These leaders are known to go home at night wondering why everybody hates them. This is not true. We don’t hate them, we worry about them. In the futile commotion of trying to be all things to all people, they are in dire peril of going quietly mad.

Promotion is a double-edged sword that cuts both ways. When you are pleasing the bosses, you will upset the team. Stick up for the team and the bosses will blame you for not communicating their message properly.

Favourite saying: "Why does everybody hate me?"

8: Dux Reluctantis

The Reluctant Leader

The team had functioned well for a number of years, but there was a review and the question was asked, "Who is the team leader?" The answer was not what the big boss wanted to hear.

"You must have a team leader on every team." End of discussion.

People were invited to apply for the post, but nobody was keen. It was clear that the team dynamic was at risk and nobody wanted to rock the boat. Eventually, a person was picked, interviewed, and appointed. Even when the inevitable interview question was asked: "Why do you want this job?" the answer, "I don’t really want it," was not enough to put them off.

Sometimes, a D. Reluctantis is appointed because HR feels he needs a challenge to reveal his full potential.

Favourite saying: "If that’s okay with you…"

9: Dux Minoris

The Lesser Leader

This team leader is perfectly illustrated by Simon Travaglia’s Pimply Faced Youth (PFY) in his celebrated BOFH series of comic IT spoofs.

He is keen but has been led astray by a scheming and manipulative section manager. He is drawn into the various scams and schemes to do down the bean counters and is not above using the Argon-based fire systems to discretely dispose of those who stand in the way.

In reality, this character is easily diverted from his true path and finds himself in a tight corner when the schemes inevitably go wrong. He is great fun to work for, but you should always make sure that you take the key to the server room door with you if you enter alone.

Favourite saying: "Illegitimi non carborundum…" and he has the T-shirt to prove it.

10. Dux Severus

The Serious Team Leader

When some members of the team get promoted it goes to their heads.

Gone is the sociable, easy-going friend you worked with and out comes the martinet. The person who used to take 30-minute bathroom breaks suddenly starts to time your breaks and make scathing comments when you take more than four minutes. Having an upset stomach is no excuse because he knows that the loo break is often used as an unofficial break and an opportunity to catch up on office gossip with help desk colleagues.

Favourite saying: "We run a tight ship here."

This typifies the arrogance of the breed. Adopting the "Royal We" is always a sign that things are going to the bad.