C++ Next

Design NoSQL tables for Activity Stream

2013-02-07T00:11:00.003+05:30

Most of the social networks now-a-days have activity stream, a stream of events for a particular object with very large number of such objects. Facebook has timeline, twitter has its updates, etc... The company I am working in came up with a product similar to Dropbox and we were supposed to implement a similar design pattern in our application. In the future posts I will discuss several designs and compare each of them based on following criteria:

Correctness
Access Time
Storage requirements

See that every object's activity stream can be subscribed. In our application, every shared folder has an activity stream. When a folder is shared with multiple users, every one of them needs to get update on that shared folder. When the user is removed from collaborating on a shared folder, he should stop getting updates on that folder. Joining and leaving a shared folder also constitutes activities in the stream.

Create a word cloud from source code of an application

2012-04-24T12:58:00.001+05:30

I am currently working at Druva Software. I wanted to create word-cloud from the source of the application I was working on. Here is the command I used:

find ./ -type f -print0 | xargs -0 cat | tr '[:space:]' '\n' | tr -c '[:alnum:]' '\n' | sort | uniq -c

This will generate a text file in a format " 'occurence count' 'word' " on each line. The top word would be empty space or new line which you can simply ignore. Since the command searches in binary files too, I got some non-relevant words too which I removed. I converted the file in comma-separated values and uploaded it to wordle and below is what I got. The application seem to be very 'self'ish.

Find formula for coordinates : Solution

2011-11-07T18:46:00.001+05:30

The problem statement is here. Observe that the $ (x, y) $ coordinate appears in the $ (x + y) ^{th} $ solid line. The $ n^{th} $ diagonal has $ 1 + 2 + 3 + ... + n $ elements before it, i.e. $ (x + y) ^{th} $ diagonal has $ \frac{(x+y)(x+y+1)}{2} $ elements before it. Add the $ x $ elements to it to get the point at coordinate $ (x+y) $. So the answer is $ \frac{(x+y)(x+y+1)}{2} + x $.

IIT Delhi MTech Interview Question: Find formula for coordinates

2011-11-04T22:55:00.002+05:30

On a grid, the numbering is done as shown in the image below. Dotted lines go up and solid lines go down.

Find out the formula to describe number on grid given the standard $ (x, y) $ coordinate. Credit goes to my colleague Jignesh Parsana for the problem.

Update: I found that this is Cantor's Pairing Function as given at http://szudzik.com/ElegantPairing.pdf

Design a cache replacement policy for a hard-disk if the stream of sector requests is already known : Solution 1

2011-10-15T17:39:00.001+05:30

Problem statement is here.

For the first $ k $ requests, all the sectors are cached. For every request $ s_i, k < i <= R $, we have $ k + 1 $ sectors to put in $ k $ cache location. To discard one of the sectors, we can give weight to every sector which is equal to the difference between the index of next request for that sector and the index of the current request. So if the next request for sector $ m $ is appearing at index $ j $ then the weight of that sector is $ j - i $. Choose the $ k $ sectors with the minimum weight.

Google Interview Question : Design a cache replacement policy for a hard-disk if the stream of sector requests is already known

2011-10-15T17:19:00.004+05:30

Problem statement: You are given a hard-disk with large number of sectors say $ N $ and that has a facility to store $ k $-sectors in cache such that read time for cache is very less compared to the time to read sector from a hard-disk and $ N >> k $. Assume the seek time is negligible compared to read-time. You are given a stream of requests $ s_i \text{ such that } 0 <= i <= R, k << R << N $.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Chapter 11

2011-09-11T16:56:00.001+05:30

The author discusses about working in team and the reasons for doing so such as:

Large projects with thousands of classes cannot be handled by a single person
Creating a whole application by a single person may miss the deadline
Creating a software involves not just developing an application but documentation, help files, installer, graphics, a website and many more things so it is better to have a team with different skills

The author then discusses about team management and the 'soft' issues involved in managing the team such as:

Choosing a structure: There are two alternatives to deciding a team structure

Community of equals: Each member on the team is recognised of being equally capable.
Hierarchy:

Tracking progress: The author suggests email-notification tool from source code control module or web page refresh from build tools. The author suggests 3 x 3 approach where each member regularly sends a report to other members of the team or just the project manager containing:

Three accomplishments for the previous week
Three obstacles to progress from the previous week
Three plans for the coming week

Avoiding your incompetence: The author discusses the Peter Principle, i.e. In a hierarchy, every employee tends to rise to his or her level of incompetence. In most organizations, people are promoted when they do their job well but never demoted. The author gives following tips to become a competent manager:

Start with a small team
Spend some time on management chores
Pay attention to everybody's ideas
Read literature on software project management

The author then discusses tools for distributed teams such as:

E-mail:

Use spam protection
Keep project related emails organized
Read emails in a batch
Instead of sharing every email with everyone, try sharing items through public folders or a news server

Instant Messages:

Read messages in a batch
Keep everybody on the same service
Keep an archive of conversations

Online Workspaces: The author discusses use of online workspaces like GotDotNet or SourceForge and their pros and cons.
Wikis: The author provides several wikis available and what their benefits and disadvantages are.
Microsoft Sharepoint: The author discusses advantages and disadvantages of Microsoft sharepoint and groove.
Programmer's tools: The author discusses CodeWright and CodeReview.

Find depth of a k-ary tree given a parent array : Solution 3

2011-09-08T11:39:00.001+05:30

The problem statement is mentioned here. The first solution is here. The second solution is here.

While traversing up the tree from a leaf node, we can avoid the whole path till root if we can utilize the depth already found for nodes that were traversed earlier. This will reduce the problem to $ O(N) $ as below with extra space of $ O(N) $.

Let DEPTH be an array of length N
Initialize all elements of DEPTH to -1
FINDDEPTH(i)
    if DEPTH[i] == -1
        if P[i] == -1
            DEPTH[i] = 0
        else
            pDepth = FINDDEPTH(P[i])
           DEPTH[i] = pDepth + 1
    return DEPTH[i]

Let L be an array of length N
Initialize all elements of L to true
for each node i from 0 to N-1
   if P[i] is not -1
       set L[P[i]] to false
   end if
end for
initialize maxDepth to 0
for each node i from 0 to N-1
    if L[i] is false, continue next node
    depth = FINDDEPTH(i)
    if maxDepth < depth
       set maxDepth = depth
    end if
end for

As can be seen, the time complexity of the algorithm is $O(N)$ where $N$ is the number of nodes. The space complexity is $O(N)$. Thanks to my colleague Jignesh Parsana to help point to this solution.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Chapter 10

2011-09-04T17:57:00.001+05:30

The author discusses importance of logging application activity both during development and after shipping and methods of logging. The logging during development is required since

Log allows you to understand actions that led to a bug
Log helps clarify the order of events
Some bugs only reproduce when running without a debugger
Some bugs occur after thousands of calls of a function

The author suggests to make it easy for end user to turn logging on or off. The author advises to include following in the logs:

Error messages and information including stack trace
The state of internal data structures
User actions
The timings of significant actions
Important environment information

The author then discusses about logging tools including:

The Trace and Debug classes of .Net framework -
The EventLog class - This is used to log events to Windows Event Log
Enterprise Instrumentation Framework
Logging Application Block
log4net

If there is no logging included in application, the author discusses about diagnostic tools like System Information to collect information from user machine.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Chapter 9

2011-09-04T17:53:00.003+05:30

The author discusses about how to manage risk and bugs in software development. The author divides risk management in following

Risk Assessment: The author suggests to brainstorm a list of things that might go wrong for risk assessment including things that might impact the cost, schedule or quality of the product. The author then asks the reader to order the list of risks based on importance. This is achieved by assigning probability and cost to each risk and multiplying them to get the impact.
Risk Control: After the risks have been identified and prioritized, the author advises to create a risk management plan where the reader needs to specify what he is going to do to mitigate the risk.
Top Five Risks List: The author advises the reader to maintain top five risk list including its previous rank and how long the risk is on the list.

The author then discusses about Bug Triage, a term that refers to prioritizing bugs based on their criticality and decide on what to do about them. The author then provides following list of resolutions that can be applied to bugs:

By design
Duplicate
Postponed
Not reproducible
Won't fix
Reassigned
Fixed

The author then discusses different types of software testing such as:

Unit Testing - This is done by developers to ensure a function or unit is bug-free.
Functional Testing - This is is carried out by testers to make sure the application confirms to the requirements and specifications.
Conformance Testing - This ensures the application confirms the industry standards.
Compatibility Testing - This ensures that the application runs in different environments including hardware, operating systems, browsers etc...
Performance Testing - The goal of this testing is to identify performance issues and creating benchmarks.
Stress Testing - The goal is to identify how the application fails when it is subjected to excessive stress. It involves simulating large number of users, low RAM, CPU contention etc... to make sure the application failure doesn't result in damage to operating system or data loss.
Regression Testing - This involves making sure that new features didn't break the existing functionality.
Smoke Testing - This involves running quick tests to verify that major features work.
Black-box Testing - The testing of components is done based solely on their interfaces.
White-box Testing - Internal behaviour of the components is tested with full knowledge of the implementation.

The author provides some tips to effectively test the application when there is no separate quality assurance department. The author also suggest to take every bug as a learning experience rather than as a deficiency in coding skills of a developer.

The author then provides following tips to create a test network:

Buy pre-assembled machines
Buy name brands
Buy serious development hardware
Store data separately
Keep drive images
Use virtual machines
Use KVM switches
Get your own domain
Use a firewall
Set aside test machines
Set aside a build machine
Use a mix of machines for testing

The author then discusses about bug-tracking tools. The author then provides a list of issues to consider while deciding on a bug-tracking tool:

Price
License Fee structure
Cross-platform availability
E-mail notification
Allow outside access
Allow custom information
Differentiation between bugs and feature requests
Integration with source code control and requirements tool
Flexible workflow
Storage Format

The author then provides an example bug-tracking tool and how he used it to track one of the bugs for his own application.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Chapter 8

2011-09-04T17:50:00.001+05:30

The author discusses that code generation is the core activity of any developer and his focus in this chapter will be on code generation tools. The author suggests to spend time on thinking about automating a repetitive task instead of doing it. The author then gives an example of generating stored procedures using a tool. The code generation tools are classified in two categories:

Passive that dumps the code and forgets
Active which are then classified in several other categories

Code munger
Inline-code expander
Mixed-code generator
Partial-class generator
Tier generator
Full-domain language

The author clarifies that code-generation is not just restricted to code but a variety of end products can be developed using the technology such as:

Database access code
User interface code
Documentation
Unit tests
Web services
DLL wrappers for legacy code
Configuration files or initialization files
Scripting files
Installation files

The author then discuss a specific example of generating code directly from a database table using MSDataSetGenerator tool in .NET. The author then also provide a list of other tools available and briefly mentions their functionality. The author then provides an example of how he uses one of the code generation tool to help create code for his DownloadTracker application. The author then provides a list of pros and cons of using code generation tools.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Chapter 7

2011-08-02T13:43:00.000+05:30

The author discusses about reusing the code in such a manner as to increase efficiency. The author then talks about following tools:

Ildasm: This tool is intermediate language disassembler. The author then provides an example of disassembling an assembly.
Reflector: This tool translates the MSIL code to C# or VB.NET code.
Nogoop: This tool allows to inspect and use a .NET component or class.
Snippet compiler: This tool allows you to write code to exercise a new component.

The author then discusses about several sources of reusable code including .NET framework class library, Microsoft application blocks, logidex .NET library and free sources like CodeProject and GetDotNet.

The author then discusses a tool FxCop which can be used to check if a class library confirms to design guidelines suggested by Microsoft.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Chapter 6

2011-08-02T13:37:00.002+05:30

The author discusses the importance of IDE (Integrated Development Environment) in this chapter. It is not possible to create an IDE that suits every developer and that's why customisation is required. The author then provides some of the customisation that can be used in Visual Studio.NET environment. The author then talks about using macros in Visual Studio environment. The author provides examples of visual studio add-ins that analyzes source-code and provides useful information such as lines of code in each module that helps distinguish simple and complex modules, lines of comments that provides information about under-documented or over-documented module, easy reference to different classes/methods in the source code, suggestions to improve performance of the code, etc...

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Introduction and Chapter 5

2011-07-27T18:27:00.001+05:30

The author talks about integrating testing into development process using the techniques of test-driven-development and refactoring. The author discusses different kinds of testing such as:

Unit Testing
Integration Testing
System Testing
Stress Testing
Beta Testing
Acceptance Testing

The author then provides a typical set of steps followed by developers in a team and suggests to have system testing done by somebody other than the one who has written the code.

The author provides a list of unit testing tools available. The author then uses one of the tools and write unit test cases for his Download Tracker application. The author then discusses Test Driven Development and provides two easy steps followed in the process:

Write a failing automated test before any code
Remove duplication

The author then applies the methodology to his own Download Tracker application to provide example.

The author then introduces the concept of refactoring, the process of changing a software system in such a way that it does not alter the external behaviour of the code yet improves its internal structure. The author then provides a list of tools that can be used for automated refactoring.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Introduction and Chapter 4

2011-07-27T18:10:00.000+05:30

The author talks about defensive coding in this chapter whose goal is to write code that makes it easy to find problems and make modifications.

The author discuss about usage of assertions to detect errors in code. The author provides following two guidelines:

Assertions should not have side effects.
Avoid assertions to test compiler/language issues

The author then talks about exceptions, the exception mechanism in C#, the reason for creating custom exceptions and the guidelines for creating custom exceptions in C#. The author then implements his own custom exception for Download Tracker application. The author then provides following guidelines for good exceptions:

Exceptions are for exceptional situations
Don't create unnecessary custom exceptions
Constructors with a string value should be used
Pass exception from low level routine to higher level routine with enough information

The author then examines the debate of whether to use comments or have self-documenting code. The author likes the first approach better and classifies comments in following different categories:

Noise comments: They just repeat what the code says and does not increase the readability and should be avoided.
Placeholder comments: They are note to your future self.
Summary and Intent comments: Summary comments summarize a lot of code in short English statements. Intent comments do not explain what the code does, it explains why it does it in a particular manner.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Introduction and Chapter 3

2011-07-27T18:06:00.000+05:30

In this chapter the author talks about how to use source code control tool effectively. The author provides following list of commands for a novice user to learn:

Create Project
Add
Get
Checkout
Revert
Check In

The author then enlists following commands for level 2 user:

Label
Merge
Branch
Share

The author then specifies following commands to be used by an expert user:

Cloak
Delete
Move
Rename
Pin
Rollback

The author then specifies a list of source code control tools and their pros and cons. The author provides following list of characteristics to look at when deciding on a source-code control system:

Price
Concurrent Development Style (checkout-edit-checkin vs edit-merge-commit).
Repository
Internet Friendliness
IDE Integration
Cross-platform support

The author then talks about best practices that needs to be followed including:

What to put under source code control
Checking out as less files as possible
Putting comments at the time of check-in
Proper use of labels
Maintaining discipline in branching
Integrate bug-tracking tool with source code control tool

The author then provides the source code control created for his Download Tracker tool.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Chapter 2

2011-07-20T21:19:00.000+05:30

The author talks about how to organize project in three different ways:

Architectural perspective addresses the overall shape of the application
Project perspective addresses the construction of the application
The staged delivery perspective addresses the release of the application

The author then provides definition of architecture with two common elements:

Highest level breakdown of a system into parts
Decisions that are hard to change

The author then provides three stages of software construction:

Architectural stage involves important decisions
Design stage involves detailed plans for writing the application
Implementation stage involves writing code

The author then draws architecture of its Download Tracker application. The author then talks about UML and tools that can be used to model architecture in form of UML.

The author talks about design patterns and how they help at architecture level. The author then talks about three methods of coding a large project:

Breadth-First: In this method, the entire skeleton of the application is built without any details. The author enlists following advantages and disadvantages of the approach:

This method ensures that everything in architecture is covered.
It demonstrates overall flow of application early in coding cycle.
Looking at the skeleton, customer's expectation for schedule may become unrealistic.
A team of developers are difficult to manage in this approach.

Depth-First: In this approach, one part of the application is completely developed before moving on to anything else. The author enlists following advantages and disadvantages for the approach:

The developer can focus on just one piece of code for its issues.
A team of developers can work on separate components.
Architecture will not be tested till late in the development cycle.
The complete application flow cannot be determined till the end of the development.

Mixed Models: The author suggests to take a mixed approach since most products have some UI component which can be developed using breadth-first approach and the rest of the components can be developed using depth-first approach.

The author then talks about three cornered trade-off representing product, cost and time. The author then discusses several approaches such as:

The Beta-Test approach: This is used by Microsoft where there are several targets like

Alpha
Beta 1
Beta 2
Release Candidate
Release

The XP approach: This involves making a series of small releases with high quality bar. Releases are spaced close to one another with very small functionality added above the previous release.

The author emphasizes the fact that product in three cornered trade-off represents not just features but quality too. Releasing a product full of bugs is a sure-shot way to lose customers.

Coder to Developer: Tools and Strategies for Delivering Your Software by Mike Gunderloy : Introduction and Chapter 1

2011-07-19T20:46:00.001+05:30

Introduction

The author distinguishes between coders, who know syntax and semantics of computer language and developers, who can apply that knowledge to turning out a working application with all the supporting details. The book is targetted to help a coder become a developer.

The author then provides an outline of how the book is organized into a sensible order of chapters so that the reader completes the task to ship a successful software product although every chapter is organized as a stand alone one.

Chapter 1
The author emphasizes on requirements management and choosing a methodology before starting to write a single line of code. The author then provides a list of questions to do brainstorming to start software development process. The author then discusses two concepts:

The elevator pitch: The idea was popularized in dot-com era when instead of 15-minute presentation, entrepreneurs were told to explain their ideas to a VC in an elevator ride to 87th floor in 30-seconds. Based on this, the author provides a rule to write a short statement describing what the software will do and why. The author warns the developer to refrain away from feature creep - the continuing addition of new functionality when the old ones are still being coded. The author provides some points to keep in mind while coming up with elevator pitch and creates one for his own software.
The mind map: Mind-map is a form of diagram for free-form brainstorming. The author then provides a list of softwares to use mind-map on Windows. The author also provides mind-map of the software he is going to create in the book called Document Tracker.

The author then classifies the requirements in four sets:

Business requirements: These are high-level objectives of the organization.
User requirements: The goals the user must be able to perform.
Functional requirements: Software functionality that must be built for the user to accomplish their tasks.
System requirements:

The author then provides a checklist to help elicit requirements at the time of working with external customer. The author then discuss about ways to capture requirements and describes use case as one of them. The author then enlists use cases of the tool Document Tracker. The author then provides a list of items that should be present in the use case document.

Instead of focusing on major milestones, the author advises the developers and managers to focus on small tasks, e.g. instead of defining a target date for user interface, set target date for individual dialog boxes and forms. The author then provides some examples of project tracking and billing tools.

The author provides a list of issues in using Microsoft Project for software project management such as it is overkill, designed for huge software projects etc... The author then talks about different methodologies of software development such as:

Waterfall Approach: The method is like a waterfall which starts from requirements analysis and then flow downhill through preliminary design, detailed design, implementation and system testing and acceptance testing.
Iterative Approach: All the project phases like development testing and planning are repeated many times in the course of the project. The author provides two examples Rational Unified Process (RUP) and Microsoft Solutions Framework (MSF) of iterative approaches.
Agile Approach: The author lists methodologies such as Extreme Programming (XP), Scrum, and Crystal for rapid application development.

The author finally recommends to use what works and leave the rest. Both waterfall and iterative approaches measure the cost of an entire project upfront while agile methodologies keep delivering small chunks until time or money runs out. The author also mentions test-driven-development method which resulted from extreme programming.

The author then provides a checklist while planning the software to make sure you are building the right thing.

The Art of Software Testing by Glenford Myers : My Opinion

2011-07-16T22:50:00.000+05:30

I would give this book 5 out of 5. It is a must read book for both programmers and quality assurance engineers. It should be included in colleges as a textbook along with Code Complete that I described earlier.
To make it easy to browse, I am putting links to all the chapters below:

The Art of Software Testing by Glenford Myers : Chapter 8

2011-07-16T22:34:00.000+05:30

The author discusses about testing tools and other techniques in this chapter. The test case design has not been automated but significant advancements have been made in automating other aspects of the testing process. Some of the tools are:

Module driver tools: It provides a language to express test cases to test a module. The author mentions three advantages of such tool:

The language reduces the effort required and standardizes the form of test cases.
Rerun of test cases is easy when a correction is made to the module
The automatic verification of results forces the programmer to state explicitly the expected output.

The author mentions AUT (Automated Unit Test), MTS and TESTMASTER as examples.

Static flow analysis tools: They analyze control flow and data flow of the program, they can detect following errors:

Variable with an undefined value
Variables with assigned values that are never used
Unreachable code
Inconsistent interfaces among modules

ACES, FACES, AUDIT, RXVP and DAVE are examples of this kind of tools.

Test coverage monitors: Coverage monitors are tools that monitor the subject program during execution to provide statistics to determine whether the statement-coverage and decision-coverage criteria have been met.
Mathematical proof of program correctness: The proof of program correctness tries to demonstrate that the program is error free. The author provides references to method of inductive assertions, predicate transformers, subgoal induction, computation induction, structural induction and intermittent assertions.
Program correctness provers: The goal is to create a program that, takes as input another program and its input and output assertions, attempt to prove the subject program correct.
Symbolic Execution: It is a hybrid between program testing and correctness provers. The subject program is executed symbolically.
Test Data Generators: The author talks about several tools that generate test data to meet a specific criterion by analyzing a program's logic flow.
Environmental Simulators: These are useful when testing in actual environment cannot be done, test conditions are hard to create in real environment etc...
Sneak Circuit Analysis:
Virtual Machines: They provide multiple programs impression that each is executing in separate standalone machine.
Testing Mathematical Software:
Interactive Debugging Tools: The author discuss about EXDAMS, ISMS and CAPS.
Compiler Debugging Aids: Compilers can contain debugging features added to the language such as

Ability to designate any arbitrary statements as debugging statements and to activate and deactivate at compilation or run time.

Program State Monitors: It monitors a program during execution, watching for the arrival of a certain predefined conditions and/or collecting data that would be useful during debugging such as first, last, minimum and maximum of each assignment statement, minimum and maximum values of each do-loop control variable etc...

The author then discusses about software error studies, software error data-collection and predictive models. The author then provides some statistics on testing experiments and the results. The author then provides some findings on debugging experiments.

The author discusses how computer architecture or hardware design can help debugging by providing features not present in the current computer design.

The Art of Software Testing by Glenford Myers : Chapter 7

2011-07-14T17:02:00.000+05:30

Debugging is defined as determining the exact nature and location of the suspected error within the program and fixing or repairing the error.

The author then discusses debugging methods:

Brute-force debugging: It is the most inefficient and unsuccessful method and advises to use this only when all other method fails. The author discusses three methods of brute-force debugging.

Debugging with a storage dump: This is the most efficient method and the author provides a list of problems associated with this method including static nature of the dump, massive amounts of irrelevant data, etc...
Debugging with scattered print statements: The author also enlists the shortcomings of this technique such as massive amount of data, require to change program, etc...
Debugging with automated debugging tools: The author compares debugging with solving a homicide and emphasizes the use of brain over a set of aids.

Debugging by Induction: The author provides steps in the induction process as follows:

Locate the pertinent data
Organize the data
Find relationship among data
Devise a hypothesis
Prove the hypothesis

Debugging by Deduction: The author provides steps in the deduction process as follows:

Enumerate the possible causes
Use the data to eliminate the possible causes
Refine the remaining hypothesis
Prove the remaining hypothesis

Debugging by Backtracking: In this method, mental reverse execution of the program is performed in which values of variables and state of the program is deduced by looking at the wrong output and the process is continued till the origin of the first unexpected state.
Debugging by Testing: Separate set of "slim" test cases are developed to provide information useful in locating a suspected error.

The author then provides two set of principles:

Error locating principles
Error repairing principles

When there is one bug, there is likely to be another.
Fix the error, not just the symptom of it.
The probability of fix being correct is not 100%.
The probability of the fix being correct drops as the size of the program grows.
Beware of the possibility that an error correction creates a new error.
The process of error repair should put one back temporarily in design phase.
Change the source code, not the object code.

The author then discusses about improvement that can be achieved by careful analysis of software errors:

When was the error made?
Who made the error?
What was done incorrectly?
How could the error have be prevented?
Why wasn't the error detected earlier?
How could the error have been detected earlier?
How was the error found?

The Art of Software Testing by Glenford Myers : Chapter 6

2011-07-11T23:12:00.000+05:30

In this chapter, the author focuses on the part of testing that starts when human-testing ends. The author talks about origination of errors in software programming. Since software development is a process of communicating information about the program and translating it from one form to another, the vast majority of software errors are attributable to breakdowns, noise and mistakes in communication. The author then describes the flow of the software development process. The author suggests to include more precision into the development process and having a separate verification step at the end of each process. The author also suggests having distinct testing processes toward distinct development processes i.e. focus each testing process on a particular translation step. The author then discusses testing at different stage of development cycle:

Function Testing: It is a process of finding discrepancies between the program and its external specification.
System Testing:

System testing is the process of attempting to demonstrate how the program does not meet its objectives.
System testing is impossible if the project has not produced a written set of measurable objectives for its product.

The author then mentions following categories of test cases:

Facility Testing: It is the determination of whether each facility mentioned in the objectives was actually implemented.
Volume Testing: The program is subjected to heavy volume of data.
Stress Testing: It involves testing a program under heavy load in a short span of time.
Usability Testing: The author provides following aspects of usability testing

Does system contain excessive number of options ?
Does system return acknowledgment to all inputs?
Is the program easy to use?
Where accuracy is vital, is sufficient redundancy present?
Are the outputs of the program meaningful?

Security Testing: It is a process of attempting to devise test cases to subvert the program's security checks.
Performance Testing: Test cases should be designed to show that the program does not meet its performance objectives like response times and throughput rates.
Storage Testing: Test cases should be designed to show that the program does not meet storage objectives in terms of main and secondary storage and spill/temporary files.
Configuration Testing: The program should be tested with each kind of hardware device and with the minimum and maximum configuration. Each possible configuration of the program should also be tested.
Compatibility/Conversion Testing: Test cases should be designed to make sure the program meets the objectives of compatibility with and conversion procedures from, the existing system.
Installability Testing: Testing of installation procedures should be part of this testing.
Reliability Testing: If the objective of the program contain specific statements about reliability, tests should be devised to
Recovery Testing: Tests should be designed to see the system's recovery from programming errors, hardware failures and data errors.
Serviceability Testing: Serviceability objectives defined in terms of service aids, mean time to debug a problem, maintenance procedures, and quality of internal-logic documentation.
Documentation Testing: User documentation should be subject to an inspection for accuracy and clarity. Examples in the documentation should be part of test cases used to test the program.
Procedure Testing: Any human procedures involved in large programs should be tested.

The author clearly specifies not performing system test by programmers who have written the program as well as not within the organization developing the program.

Acceptance Testing: This is carried out by conducting tests to show that the program does not do what it is contracted to do.
Installation Testing: This may include test cases to check that all the files have been created and have necessary contents, all parts of the system exists and is working.

The author then discusses about test planning and enlists following components of a good test plan:

Objectives: Each testing phase should have an objective.
Completion criteria: Criteria for specifying the completion of each test phase needs to be specified.
Schedules: The schedules for when the test cases will be designed, written and executed should be created.
Responsibilities: The responsibilities of people regarding testing and fixing of errors should be clearly defined.
Test-case libraries and standards: Systematic methods of identifying, writing and storing test cases are necessary.
Tools: The required test tools must be identified including the owner for their development or acquisition and how to use them or when they are needed.
Computer time: Each testing phase's required computer time should be calculated.
Hardware configuration:
Integration: System integration plan should be in place that defines the order of integration and the functional capability of each version of the system.
Tracking procedures: There should be tracking of errors and the estimation of progress with respect to schedule, resources and completion criteria.
Debugging procedures: Mechanisms must be in place to track the progress of corrections and adding them to the system.
Regression testing: Regression testing is important because changes and error corrections tend to be more error-prone than the original code. The purpose of the regression testing is to determine if the change has regressed other aspects of the program.

The author then discusses about test completion criteria which can be two of the following:

Scheduled time for testing expires.
When all the test cases execute without detecting any errors.

The author describes how both the criteria are useless. The author provides three criteria

The first one is based on use of testing methodologies:

Completion of module testing can be achieved if the test cases are derived from multi-condition coverage criterion or boundary value analysis of interface specification and all the test cases are unsuccessful.

Completion of function testing can be achieved if the test cases are derived from cause-effect graphing, boundary value analysis and error guessing and all the test cases are unsuccessful.

The second criteria is to state the completion requirements in positive terms, i.e. test of a module is not complete till x errors are found or an elapsed time of y months. The author discuss the problem of estimating the number of errors in a program and provides several ways like

Experience with previous programs
Apply predictive models
Use industry-wide averages

The third criteria is to plot the number of errors found per unit time during test phase. By examining the shape of the curve, it can be determined whether to finish or continue the testing.

The author again emphasizes on hiring an independent test agency to test the program.

The Art of Software Testing by Glenford Myers : Chapter 5

2011-07-11T23:04:00.000+05:30

The author discusses about unit testing in this chapter and enlists following advantages of module testing:

It makes combinatorics of managing testing easier.
It makes debugging easier.
It speeds up testing since multiple modules can be tested simultaneously.

The author then takes an example and generates test cases for it.

The author then discusses incremental testing where one module at a time is integrated with already tested modules and then tested. In non-incremental testing, all the modules are first tested and then integrated to create a program. The author then provides following observations for incremental testing:

Non-incremental testing requires more work.
Programming errors related to mismatching interfaces or incorrect assumptions among modules will be detected earlier if incremental testing is used.
Debugging becomes easier.
Incremental testing results in thorough testing.
Non-incremental approach uses less machine-time.
Non-incremental testing can be more parallelized in the earlier phase.

The author then discuss two approaches of incremental testing:

Top-down approach: The author points out following shortcomings of this approach:

When a new module is introduced, it is impossible to test some predefined situations.
If the newly introduced module is at a distance from the module doing I/O operations, it is difficult to decide the set of inputs that allows to execute all tests on the newly introduced module.
Since displayed output is from a module large distance away from the module being tested, correlation between output and behaviour of the module is difficult to establish.
Even though it seems possible, it cannot be combined with top-down design.
Sometimes, a module may remain untested before moving to the other module.

Bottom-up approach: The author points out following advantages/disadvantages of this approach:

The working program does not get created till the last module is added.

The author then provides a list of guidelines to perform the actual test:

The set of test cases needs to be reviewed or inspected before the test is performed.
Use automated test tools.
Look at the side effects of a module.
Testing of a module should be done by programmer of a calling module.
Debugging should always be done by the programmer.
If a high number of errors are found in a subset of the modules, such modules should be subjected to further module testing.

The Art of Software Testing by Glenford Myers : Chapter 4

2011-07-11T01:04:00.000+05:30

The author discuss about how to design test cases in this chapter. The problem is to determine what subset of the possible test cases has the highest probability of detecting the most errors. The author then tries to develop a strategy which uses black-box-oriented test-case-design methodologies combined with testing the logic of the program using white-box testing.

The author then discusses following methods of test-case design:

Logic-Coverage testing: The author discusses about designing a testing strategy such that every code path is executed exactly once. The author provides an example program and shows that it is a very weak criterion. The stronger criterion for logic coverage is called decision coverage or branch coverage. The criterion states that every decision has true or false outcome at least once. Decision coverage generally satisfies the statement coverage except when

The program has multiple entry points
The program has no decisions
The author then discusses a stronger method called condition coverage where each condition in a decision takes on all possible outcomes at least once.

Equivalence partitioning: Since exhaustive-input test of a program is impossible, selecting the subset of test cases with the highest probability of finding the most errors is required. Test case design by equivalence classes proceed in two steps:

Identifying the equivalence classes: Each input condition is partitioned into two or more groups such as valid equivalence class, invalid equivalence class and external condition. The author then provides some guidelines for finding equivalence classes:

If an input condition specifies a range of values, identify one valid equivalence class and two invalid equivalence classes.
If an input condition specifies the number of values, identify one valid equivalence class and two invalid equivalence classes.
If an input condition specifies a set of input values, identify one valid equivalence class for each value and one invalid equivalence class.
If a condition specifies a "must be" situation, identify one valid equivalence class and one invalid equivalence class.

Defining the test cases: This follows following process:

Assign a unique number to each equivalence class.
Until all valid equivalence classes have been covered by test cases, write a new test case covering as many of the covered valid equivalence classes as possible.
Until all invalid equivalence classes have been covered by test cases, write a test case that covers one and only one of the uncovered invalid equivalence classes.

Boundary value analysis: Boundary conditions are those situations directly on, above or beneath the edges of input equivalence classes and output equivalence classes. The author then gives guidelines for boundary value analysis:

If an input condition specifies a range of values, write test cases for valid ends of the range and invalid-input test cases for situations just beyond ends.
If an input condition specifies a number of values, write test cases for the minimum and maximum number of values and one beneath and beyond these values.
Try to create input conditions that test boundaries of output range and beyond.
Try to create input conditions that test boundaries of output values and beyond.

Cause Effect Graphing: This technique can explore combinations of input circumstances. The author then describe a process to derive test cases using this method. The author then take an example and apply the method to derive test cases.
Error Guessing: it is not possible to give exact procedure for this technique since it is intuition based or ad-hoc. The author then provides an example of how to guess errors.

The author then provides a final strategy which is a combination of the methods provided earlier as follows:

Use Cause Effect Graphing from specification of input conditions.
Use Boundary Value Analysis
Identify valid and invalid equivalence classes for the input and output.
Use error-guessing techniques to add additional test cases.
Use decision coverage, condition coverage, multiple-condition coverage to meet coverage criterion.

The Art of Software Testing by Glenford Myers : Chapter 3

2011-07-11T00:49:00.000+05:30

The author introduces non-computer based or human testing in this chapter. Methods related to this kind of testing are applied between the time the program is coded and the time the computer-based testing begins. This provides two advantages:

The errors are found earlier in the development cycle and the cost of correcting them is lesser and the probability of correcting the error correctly is higher.
While correcting the errors found during computer-based testing, the programmers are under immense pressure forcing them to make more mistakes.

The author then discusses about similarities and differences between code inspections and walkthroughs. The author provides several points that work in favour of this processes:

They involve people including the author and so the program is tested not just by the author but by others.
The errors found using these processes result in lower debugging costs since the precise nature of the error is located while computer-based testing only exposes symptom of an error.

The authors specifies that modifying a program is a more error-prone process than writing a new program and so program modifications should also be subjected to these testing processes.

The author then discusses about code inspections, the breakup of the team, the roles people play and the general procedure. There are two main parts:

The programmer is requested to narrate statement by statement the logic of the program.
The program is analyzed with respect to a checklist of historically common programming errors.

The author provides the ideal time for the sessions to be between 90-120 minutes. The author emphasizes on the programmer being open-minded to make the whole process effective. Code inspection identifies the error-prone sections of the code and allow to focus more on that area when computer based testing begins.

The author then provides a common checklist for code-inspection:

Is an uninitialized variable referenced?
Is array subscript value within the defined bounds?
Is array subscript an integer value?
Is the lifetime of reference variable within the lifetime of referenced storage?
If a data structure is referenced in multiple procedures or functions, is the structure defined identically in each procedure.
When indexing into a string, are the limits of the string exceeded?
Are there any "off by one" errors in indexing operations or in subscript references to arrays?
Are there any variables with similar names?
Verify mixed-mode arithmetic correctly.
Verify different size same data type arithmetic correctly, i.e. long with short.
Verify divisor not becoming zero in division operation.
For expressions with more than one operator, are the assumptions about precedence of operators and order of evaluation correct?
Are operands of a boolean operator boolean?
Will every loop always terminate?
Have all files been opened before use?
Are end-of-file conditions detected and handled correctly?
Are I/O error conditions handled correctly?

The author then discusses code walkthrough. The author describes the participants and their role in walkthrough process. The author then describes the difference in walkthrough from code inspection, i.e. the participants execute the set of paper test cases mentally. The comments of code walkthrough should be targeted towards the program and not the programmer. The rest of the process follows that similar to code inspection.

The author then discuss about desk checking and tells that it is not as effective as code-inspection of walkthrough.

The author then talks about peer ratings. The participants are told to evaluate anonymous programs in terms of their overall quality, maintainability, extensibility, clarity and readability. The participants are asked to rate the programs on a scale of 1 to 7 in terms of different questions such as:

Was the program easy to understand?
Would it be easy to modify this program?
Would you be proud to have written this program?