Wednesday, March 24, 2010

Simple C Calculator



Code is compilable for basic integer operations:

x + y

x - y

x * y

x / y

(space reqd between mainline arguments)



Though this code is too simple to share with computer science enthusiasts, but lets build C concepts over a simple snippet:

Code:


#include <stdio.h>
typedef struct {
    int operand1;
    int operand2;
    char inp_operator;   
    
} operation;
void parse_user_input(int arg_index, operation *a, char * mainline_arg);
int string_to_int_conversion(char * string);
int main(int argc, char* argv[])
{
    
    int loop_index;
    operation calc; 
    
    //Extract input digits and end-user's desired operation
    for(loop_index = 1; loop_index <argc; loop_index++)
    {
        //printf(" loop index is %d\n", loop_index);
        //printf("%s\n", argv[loop_index]);
        parse_user_input(loop_index, &calc, argv[loop_index]);
    }
        
    switch (calc.inp_operator)
    {
    case '+':
        printf("%d\n", (calc.operand1 + calc.operand2));
        break;
    case '-':
        printf("%d\n", (calc.operand1 - calc.operand2));
        break;
    case '*':
        printf("%d\n", (calc.operand1 * calc.operand2));
        break;
    case '/':
        printf("%d\n", (calc.operand1 / calc.operand2));
        break;
    default:
        printf("Invalid operands entered as %d, %d, %c, exiting without calculation", calc.operand1, calc.operand2, calc.inp_operator);
    }
    return 0;
}
//Logic for parsing user input storing basic arithmetic operands and operations
void parse_user_input(int arg_index, operation *a, char * mainline_arg)
{
  
  if (arg_index == 1)
  {
     a->operand1 = string_to_int_conversion(mainline_arg); 
     //printf("%d\n", a->operand1);
  }
  
  if (arg_index == 2)
  {
     
     a->inp_operator = mainline_arg[0]; 
     
  }
  if (arg_index == 3)
  {
     a->operand2 = string_to_int_conversion(mainline_arg); 
     //printf("%d\n", a->operand2);
  }
}

//Logic for converting string to decimal if 
//each element entered between 0-9 
int string_to_int_conversion(char * string)
{
    int converted_integer = 0;
    while ((*string != '\0') && (*string >='0') && (*string <='9') )
    {
        converted_integer = (converted_integer * 10) + (*string -'0');
        *string++;
        
    }
 

    return converted_integer;
  
}
Quiz:

1.Use Function polymorphism in above C program
2. Introduce floating point arithmetic in the above code

Monday, March 15, 2010

Multi-Threading

As user's run-time needs keeps on increasing, it becomes imperative to design effective models where multiple concurrent tasks can be successfully accomplished. One set of possibilities already exists in terms of creating multiple processes running at the same time. Withn 1 process, multiple threads are used to used to devise parallelism. This phenomenon is highly applied in case of network processors. One good link:

http://www.wedevblog.com/posix-threads-threading-with-c.html


As previous posts have already emphasized on these concepts, today's post focusses on testing multithreaded applications.

Reference for this post is:
Object-Oriented Multithreading Using C++ by Cameron Hughes and Tracey Highes
http://www.amazon.com/gp/product/0471180122/ref=cm_li_v_cs_d?tag=linkedin-20


 2 important testing guidelines shared by them:
 -Don't wait until a software system gets complex before testing it
 -Categorize the types of defects to which the software is subject

Unit Testing - Requires that SW be tested one component or unit at a time

Stress Testing - Designed to push a component or a system up to and sometimes beyond its limits

Integration Testing - Used to test the assembly of components. The components are combined into logical groups, and each group is tested as a unit

Regression Testing - Used to retest modules that have changed.Regression tests ensure that the changes to the component do not cause it to lose any functionality

Operational Testing - Used to test the system in its full operation. The operation tests also serve to determine how the component will behave in a totally foreign environment.

Specification Testing - The component is audited against the original specification, used as part of the software verification process.

Acceptance Testing - Used by the end user of the module, component or system to determine performance.

Lets also try to understand several typical categories of software defects that are specific to programs that contain multithreading, concurrency, parallelism or asynchronous process:

Race Condition - Occurs when two or more threads or processes are attempting to modify the same block of shared modifiable data simultaneously.

Deadlock - A thread or process is waiting for an event that will not occur.

Priority Inversion - Occurs when a lower priority thread blocks the execution of a higher priority thread when synchronization variables are being used or when competing for resources.

Performance Degradation - Occurs when a system's performance lowers or degrades in terms of responsiveness, execution time, calculation of results, and so on.

Indefinite Postponement - Occure when a system indefinitely delays the scheduling of processes or threads while other processes or threads receive the attention and the allocation of resources.

Mutex Exhaustion - Occurs when a system has reached its maximum number of mutexes that can be created.

Thread Exhaustion - Occurs when a system has reached its maximum number of threads that can be allocated.


Quiz:
http://testertested.qualityfrog.com/
http://www.informit.com/articles/article.aspx?p=412922&seqNum=4

I scored pretty bad  in the first!

Saturday, March 6, 2010

Sorting Algorithms

Today's post talks of various sorting algortihms already in place to sort unsorted sequence of numbers or infact any list where based on some logic the entities can be compared. To name a few that are commonly heard:





Insertion Sort


Bubble Sort


Quick Sort


Selection Sort


Heap Sort


Merge Sort


Bucket Sort


Radix Sort





Wikipedia provides a good insight into various sorting algorithms.


http://en.wikipedia.org/wiki/sorting_algorithm





Another good reference is available in Data Structures and Algorithms book by Bruno R. Preiss.

Inserion sort implies a linear search starting from either left or right direction and inserting the element at a sorted position w.r.t. all the elements from the sorted direction



and it continues as:

4 7 11 13 15 17 35 45 12 19 3 22

4 7 11 13 15 17 35 45 12 19 3 22

4 7 11 12 13 15 17 35 45 19 3 22

4 7 11 12 13 15 17 19 35 45 3 22

3 4 7 11 12 13 15 17 19 35 45 22

3 4 7 11 12 13 15 17 19 22 35 45

While insertion sort looks easy to implement, its disdvantage is large running time for big unsorted arrays.Check out his interesting animation to understand the disadvange more precisely:

http://www.sorting-algorithms.com/insertion-sort

One good thing about insertion sort is that it does not need any scratch space apart from the sequence being sorted

2 . Bubble Sort

Check out the same animation to figure out the difference yourself:

http://www.sorting-algorithms.com/bubble-sort

3. Merge Sort

Merge Sort needs space in which to merge the elements of its sub-lists.

4. Quick Sort

Quick Sort simply swaps elements around to get them on the correct side of the pivot, as a result equal elements may not be in the same relative order as they were when the sort began.

Again check out the same animation for quick sort to figure out the difference yourself:

http://www.sorting-algorithms.com/quick-sort

Quiz:

1. Can recursion algorithm be effectively applied to insertion sort?

2. How do computers sort data internally?

3. Should bubble sort be taught to beginners?

4. Is quick sort a stable sort?

5. http://www.funtrivia.com/playquiz/quiz2710061f06f18.html

Monday, March 1, 2010

Binary Arithmetic







Boolean variables 0 and 1 form the basis of many complex IC on any of our electronic devices. This post starts with their basics leading to understanding of some basic digital circuits.



Rules of binary addition:

0 + 0 =0
0 + 1 = 1
1+ 0 = 1
1 + 1 = 0 (with a carry of 1)
1+ 1 + 1 = 10 + 1 = 11
Rules of binary subtraction:

0- 0 =0
1 - 0 = 1






1 -1 = 0



0 -1 = 1 (with a borrow of 1)











Rules of binary multiplication:




Repeated addition of one number by times equal to other number





Rules of binary division:



x / y implies count the number of times y can be subtracted from x with positive or zero remainder.


Multiplication of two given floating point numbers is carried out by multiplying their mantissas and adding the exponent values on a common base.






Division of two given floating point numbers is carried out by dividing the dividend mantissa by the divisor mantissa and subtracting their common base exponent values. Normalize the result if required.


Combination of different binary variables gives rise to LOGIC Gates. Each of the basic logic gates is a piece of hardware or an electronic circuit that can be used to implement the most basic logical expressions. 3 basic self explanatory logic gates are AND OR NOT



.



For Ex-OR gate, output equals 0 for equal inputs and 1 for unequal inputs.






The output of NAND gate is 0 when all the inputs are 1.



The output of NOR gate equals 1 when all its inputs are 0.


NAND and NOR gates have a special property that these gates can individually be used to construct logic circuit for any boolean expression making them universal gates.


Quiz:
1. How many binary digits can be added using a half adder circuit?

2. A logic gate with 4 inputs can give how many possible input combinations?

3. NOT gate can have how many input variables?

4. What is the resultant gate f ormed by shorting all the inputs of a NOR gate?

5. Is 10110001 necessarily a binary number?

Mindbox