TDD By Example

TDD (Test Driven Development) By Example

What is Test driven development?
Write code only to fix a failing test case. That is the gist of test driven development (TDD). This is a cyclic process- You first write a test for a requirement, and then you write some real code to pass the test, then you refactor the code for best possible design using various design principle for example SOLID , GRASP etc. The benefit here is that you already have a safety net as tests before refactoring the code. Whatever refactoring you are doing, your tests should not fail.
TDD is an evolving process. You evolve your software design by simply following above steps for each and every requirements of your software. It keeps you away from verbose code, over engineering and making unnecessary assumption.
The Test->Code->Refactor cycle also known as red-green-blue. You can understand the significance of these colours from below diagram.
TDD-By-Example
Since the title of this post is TDD by example, let’s do an example using TDD to understand the concepts better.

We will follow the same cycle
Write a failing test – make it pass – refactor the code.

The problem is:
Create a simple shopping cart

We will add different requirements to our current problem and we evolve our design and code accordingly.

Create a simple java project ShoppingCartApp in Eclipse, add JUnit4 library dependency to it. First create a test folder and a class ShoppingCartAppTest.
TDD-By-Example1
Requirement: Create an empty shopping cart
When: An empty shopping cart created.
Then: the product count of cart should be 0.

Add a test to create an empty shopping cart in ShoppingCartAppTest class. Make an assertion to product count 0.

Now it is giving compilation error since we don’t have ShoppingCart class. Let’s create a ShoppingCart class in src folder and a method getProductCount() in it.

Now run the test case. It should pass. We have completed our first requirement using TDD.
TDD-By-Example4
Requirement: Add Product to shopping cart
When: Add 1 unit of ‘Gatsby hair cream’, unit price 30 Rupees.
Then:
– The product count of the cart should be 1.
– The total value of cart should be 30 rupees.

Add a test to add a Product to ShoppingCart. Make assertion for product count 1 and then later make the assertion for the total cart value should be 30.

It will give you compilation error since we don’t have Product class and also there is no addProduct() method to our ShoppingCart class.

Let’s create the Product class as per our requirement.

Add ‘addProduct()’ method to ShoppingCart class.

Now you have failing test since in reality there is no product added to ShoppingCart.
TDD-By-Example8

It’s time to refactor our ShoppingCart class. Let’s add a product holder to ShoppingCart class and add products to it.

Run your test again. You can see your test is passing now.
TDD-By-Example10
We have completed the first part of the requirement. Now add an assertion for the second requirement- the total cart value should be 30.0.

This will give you compilation error since we don’t have the getTotalCartValue() method in ShoppingCart class. Add this method to ShoppingCart.

Now run the test. You will have failing test case.
TDD-By-Example11
Its time to refactor our ShoppingCart class. Add some real logic to calculate cart value.

Now run the test again. You test is passing now.
TDD-By-Example12
We have completed the two requirements.

Requirement: Add different Products to shopping cart
When:
– Add 1 unit of ‘Gatsby hair cream’, unit price 30 Rupees.
– Add 1 unit of ‘Bvlgiri Soap’, unit price 100 Rupees.

Then:
– The product count of the cart should be 2.
– The total value of cart should be 130 rupees.

Add a test to add different Products to ShoppingCart. Make assertion for product count 2 and the total cart value 130.

Run the test, it will pass without any refactoring.

It’s time to add more requirements to our Shopping Cart application Let’s move to the next requirement (on second page).
Go to the next page – Click on the below red circle with page number.

Analysis of algorithms

Analysis of Algorithms

  • “Analysis of Algorithms” is concerned primarily with determining the memory (space) and time requirements (complexity) of an algorithm.
  • The time complexity (or simply, complexity) of an algorithm is measured as a function of the problem size.

Some examples are given below.

  1. The complexity of an algorithm to sort n elements may be given as a function of n.
  2. The complexity of an algorithm to multiply an m*n matrix and an n*p matrix may be given as a function of m , n , and p.

How efficient is an algorithm or piece of code depends on a lots of resources, including:

  • CPU (time) usage
  • memory usage
  • disk usage
  • network usage

All are important but we will mostly talk about time complexity (CPU usage).
when analyzing an algorithm, one might find that the time (or the number of steps) it takes to complete a problem of size n

Units for measuring an algorithm’s running time

Identify the most important operation of the algorithm, called the basic operation , the operation contributing the most to the total running time, and compute the number of times the basic operation is executed.

  • Assigning a value to a variable
  • Calling a method
  • Performing an arithmetic operation (for example, adding two numbers)
  • Comparing two numbers
  • Indexing into an array
  • Following an object reference
  • Returning from a method.

The time required by a function/procedure is proportional to the number of “basic operations” that it performs. Here are some examples of basic operations:

  • one arithmetic operation (e.g., +, *).
  • one assignment (e.g. x = 0)
  • one test (e.g., x == 0)
  • one read (of a primitive type: integer, float, character, boolean)
  • one write (of a primitive type: integer, float, character, boolean)

Orders of Growth
Order of growth

Worst-Case, Best-Case, and Average-Case Efficiencies
there are many algorithms for which running time depends not only on an input size but also on the specifics of a particular input.

  • The worst-case complexity of the algorithm is the function defined by the maximum number of steps taken in any instance of size n. This represents the curve passing through the highest point in each column.
  • The best-case complexity of the algorithm is the function defined by the minimum number of steps taken in any instance of size n. This represents the curve passing through the lowest point of each column.
  • The average-case complexity of the algorithm, with is the function defined by the average number of steps over all instances of size n.

Consider, as an example, sequential search.

Best Case
Best case sequential search
Worst Case
worst case sequential search
Average Case
sequential search average case

Clearly, the worst-case analysis provides very important information about an algorithm’s efficiency by bounding its running time from above.
best-worst-average case graph
The important thing to realize is that each of these time complexities define a numerical function, representing time versus problem size. Time complexities are complicated functions and we need to simplify that to work with them For this, we need the “Big Oh” notation.

The Big Oh Notation

when analyzing some algorithm, one might find that the time (or the number of steps)it takes to complete a problem of size n is given by T(n)=4n2 -2n+2. If we ignore constants (which makes sense because those depend on the particular hardware the program is run on) and slower growing terms, we could say “T(n) grows at the order of n ” and write: T(n) = O(n2).

  • It proves to be much easier to talk in terms of simple upper and lower bounds of time-complexity functions using the Big Oh notation. The Big Oh simplifies our analysis by ignoring levels of detail that do not impact our comparison of algorithms.
  • The Big Oh notation ignores the difference between multiplicative constants. The functions f(n) = 2n and g(n) = n are identical in Big Oh analysis.
  • For a problem of size N:

    • a constant-time algorithm is “order 1” : O(1)
    • a linear-time algorithm is “order N” : O(N)
    • a quadratic-time algorithm is “order N squared” : O(N2)

    Note that the big-O expressions do not have constants or low-order terms. This is because, when N gets large enough, constants and low-order terms don’t matter

    f(n) = 2n2 + 3n + 1 = O(n2)

    big-o

    big-o-1

    big-oh

    Example Big-O calculation
    big-oh
    Example Big-Omega calculation
    big-omega
    Example Big-Theta calculation
    big-theta

    Relationship
    screen-shot-2016-12-18-at-1-49-23-pm

    More example on Big(O)
    f(n) = 3n + 8 <= 4n for all n0 = 8 and c=4 O(n) f(n) = n2 + 1 <= 2n2 for all n0 = 1 and c=2 O(n2 )
    f(n) = n4 + 100n2 + 50 <= 2n4 for all n0 = 11 and c=2 O(n4)
    f(n) = 2n3+ 22 <= 2n3 for all n0 = 1 and c=2 O(n3 )
    f(n) = n <= n2 for all n0 = 1 and c=1 O(n )
    f(n) = 410 < = 410 for all n0 = 1 and c=1 O(1)

    There are no unique set of values for n0 and c in proving the asymptotic bounds. Lets Consider, 100n + 5 = O(n)

    Sol 1 : 100n + 5 <= 100n + n = 101n , for all n >= 5 and c =101
    Sol 2 : 100n + 5 <= 100n + 5n = 105n , for all n >= 1 and c =105

    References
    Algorithm Design Manual – Steven S. Skiena
    Design and Analysis of Algorithm – Anany Levitin
    Beginning Algorithm – Simon Harris, James Ross
    Data Structure And Algorithm with javaScript – Michael McMillan
    Data Structures and Algorithms Made Easy – Narasimha Karumanchi