Binary Search

Searching

Given an arbitrary collection of n keys, the only way to determine if a search key is present by examining each element which yields O(n) complexity.
If the collection is organized, searching can be speed up dramatically.

Binary Search

Binary search is a natural divide-and conquer strategy for searching. The idea is to eliminate half the keys from consideration by keeping the keys in a sorted array. If the search key is not equal to the middle element of the array, one of the two sets of keys to the left and to the right of the middle element can be eliminated from further consideration.

Below is the working code in C Language.

#include<stdio.h>
int bsearch(int a[],int size,int elem)
{
        int low=0;
        int up=size-1;
        int mid;
        while(low <= up) {
                mid=(low+up)/2;
                if(a[mid]==elem)
                        return mid;
                else if(a[mid]<elem)
                        low=mid+1;
                else
                        up=mid-1;
        }
        return -1;
}
int main()
{
        int arr[10]={1,2,3,4,5,6,7,8,9,10};
        int pos,srch_elem;
        printf("Enter element to search : ");
        scanf("%d",&srch_elem);
        pos=bsearch(arr,10,srch_elem);
        if(pos == -1)
                printf("%d is not in array\n",srch_elem);
        else
                printf("%d is at location %d\n",srch_elem,pos+1);
        return 0;
}

Here in the above program of binary search there is a bug. The error is in assignment mid = (low+up)/2; it can lead to overflow (in case of array size large approx equal to size of int) and hence should be replaced by mid = low + (up-low)/2 .

The time complexity of binary search is equal to O(logn), which is superior to O(n) approach needed when the keys are unsorted.

Free Online Learning

Here are few site links which provide on line learning for free. They distribute lectures and notes for free.
You can see lectures of your interest and increase your knowledge.

NPTEL provides E-learning through online Web and Video courses in Engineering, Science and humanities streams.
http://nptel.iitm.ac.in/

MIT OpenCourseware - contains lectures and notes provided by MIT professors.
http://ocw.mit.edu/index.htm

Coursera contains lectures provided by prof of some of the good university of US.
https://www.coursera.org

You can also find a large set of video lectures shared on you tube.
Below are few you tube links.
http://www.youtube.com/user/StanfordUniversity
http://www.youtube.com/user/Harvard
http://www.youtube.com/user/UCBerkeley
http://www.youtube.com/user/nptelhrd

Security tube- contains lectures and demo related to hacking, information security, wireless security, hacking tools etc.
http://www.securitytube.net/

videolectures.net

learnerstv.com

Khan Academy - contains teaching materials related to  mathematics, history, healthcare and medicine, finance, physics, chemistry, biology, astronomy, economics, cosmology, organic chemistry, American civics, art history, microeconomics and computer science
http://www.khanacademy.org/

Google also provides learning tutorials that are present at site mentioned below. These contains lectures, presentations, assignments shared by some US Grad College Professors and some Google employees.
http://code.google.com/edu/


itunes U

Itunes U is an application provided by apple for your your iphone, ipads, ipod touch using which allow you can download lectures and read it on your iphone, ipads, ipod. you can gain access to these lectures on your personal computers too via installing itunes on your computer.

Using Valgrind Part 2

Using Memcheck tool of valgrind to detect memory leaks and other memory errors

Here is the demo program. You can try that. I have also attached it.

#include<stdio.h>
#include<stdlib.h>
void func()
{
int *f=(int *)malloc(sizeof(int)*10); ////Memory Leak
}
int main()
{
int *k;
int c;
int *p=(int *)malloc(sizeof(int));
free(p);
func();
c=*k;//use of uninitialized valirable
free(p);//double free
k=NULL;
printf("%d\n",*k);//accessing a null pointer
return 0;
}

Below is the valgrind memcheck tool output. I have added command also to use valgrind memcheck tool.
root@bt:~/Desktop# valgrind --tool=memcheck -v --leak-check=full --track-origins=yes ./a.out
==2230== Memcheck, a memory error detector
==2230== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==2230== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==2230== Command: ./a.out
==2230==
--2230-- Valgrind options:
--2230--    --tool=memcheck
--2230--    -v
--2230--    --leak-check=full
--2230--    --track-origins=yes
--2230-- Contents of /proc/version:
--2230--   Linux version 3.2.6 (root@bt) (gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) ) #1 SMP Fri Feb 17 10:40:05 EST 2012
--2230-- Arch and hwcaps: X86, x86-sse1-sse2
--2230-- Page sizes: currently 4096, max supported 4096
--2230-- Valgrind library directory: /usr/local/lib/valgrind
--2230-- Reading syms from /lib/ld-2.11.1.so (0x4000000)
--2230--   Considering /lib/ld-2.11.1.so ..
--2230--   .. CRC mismatch (computed 45f50ae1 wanted 137bc614)
--2230--    object doesn't have a symbol table
--2230-- Reading syms from /root/Desktop/a.out (0x8048000)
--2230-- Reading syms from /usr/local/lib/valgrind/memcheck-x86-linux (0x38000000)
--2230--    object doesn't have a dynamic symbol table
--2230-- Reading suppressions file: /usr/local/lib/valgrind/default.supp
==2230== embedded gdbserver: reading from /tmp/vgdb-pipe-from-vgdb-to-2230-by-root-on-???
==2230== embedded gdbserver: writing to   /tmp/vgdb-pipe-to-vgdb-from-2230-by-root-on-???
==2230== embedded gdbserver: shared mem   /tmp/vgdb-pipe-shared-mem-vgdb-2230-by-root-on-???
==2230==
==2230== TO CONTROL THIS PROCESS USING vgdb (which you probably
==2230== don't want to do, unless you know exactly what you're doing,
==2230== or are doing some strange experiment):
==2230==   /usr/local/lib/valgrind/../../bin/vgdb --pid=2230 ...command...
==2230==
==2230== TO DEBUG THIS PROCESS USING GDB: start GDB like this
==2230==   /path/to/gdb ./a.out
==2230== and then give GDB the following command
==2230==   target remote | /usr/local/lib/valgrind/../../bin/vgdb --pid=2230
==2230== --pid is optional if only one valgrind process is running
==2230==
--2230-- Reading syms from /usr/local/lib/valgrind/vgpreload_core-x86-linux.so (0x4020000)
--2230-- Reading syms from /usr/local/lib/valgrind/vgpreload_memcheck-x86-linux.so (0x4023000)
--2230-- Reading syms from /lib/tls/i686/cmov/libc-2.11.1.so (0x4042000)
--2230--   Considering /lib/tls/i686/cmov/libc-2.11.1.so ..
--2230--   .. CRC mismatch (computed 2236eb0a wanted a071c0c3)
--2230--    object doesn't have a symbol table
--2230-- REDIR: 0x40b5b10 (rindex) redirected to 0x4027050 (rindex)
--2230-- REDIR: 0x40b1f40 (malloc) redirected to 0x40263bf (malloc)
--2230-- REDIR: 0x40b1e60 (free) redirected to 0x4025fd9 (free)
==2230== Use of uninitialised value of size 4
==2230==    at 0x8048499: main (hell1.c:14)
==2230==  Uninitialised value was created by a stack allocation
==2230==    at 0x8048471: main (hell1.c:8)
==2230==
==2230== Invalid free() / delete / delete[] / realloc()
==2230==    at 0x402605E: free (vg_replace_malloc.c:427)
==2230==    by 0x80484AA: main (hell1.c:15)
==2230==  Address 0x419d028 is 0 bytes inside a block of size 4 free'd
==2230==    at 0x402605E: free (vg_replace_malloc.c:427)
==2230==    by 0x804848F: main (hell1.c:12)
==2230==
==2230== Invalid read of size 4
==2230==    at 0x80484B7: main (hell1.c:17)
==2230==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==2230==
==2230==
==2230== Process terminating with default action of signal 11 (SIGSEGV)
==2230==  Access not within mapped region at address 0x0
==2230==    at 0x80484B7: main (hell1.c:17)
==2230==  If you believe this happened as a result of a stack
==2230==  overflow in your program's main thread (unlikely but
==2230==  possible), you can try to increase the size of the
==2230==  main thread stack using the --main-stacksize= flag.
==2230==  The main thread stack size used in this run was 8388608.
==2230==
==2230== HEAP SUMMARY:
==2230==     in use at exit: 40 bytes in 1 blocks
==2230==   total heap usage: 2 allocs, 2 frees, 44 bytes allocated
==2230==
==2230== Searching for pointers to 1 not-freed blocks
==2230== Checked 56,076 bytes
==2230==
==2230== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==2230==    at 0x4026444: malloc (vg_replace_malloc.c:263)
==2230==    by 0x8048465: func (hell1.c:5)
==2230==    by 0x8048494: main (hell1.c:13)
==2230==
==2230== LEAK SUMMARY:
==2230==    definitely lost: 40 bytes in 1 blocks
==2230==    indirectly lost: 0 bytes in 0 blocks
==2230==      possibly lost: 0 bytes in 0 blocks
==2230==    still reachable: 0 bytes in 0 blocks
==2230==         suppressed: 0 bytes in 0 blocks
==2230==
==2230== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 11 from 6)
==2230==
==2230== 1 errors in context 1 of 4:
==2230== Invalid read of size 4
==2230==    at 0x80484B7: main (hell1.c:17)
==2230==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==2230==
==2230==
==2230== 1 errors in context 2 of 4:
==2230== Invalid free() / delete / delete[] / realloc()
==2230==    at 0x402605E: free (vg_replace_malloc.c:427)
==2230==    by 0x80484AA: main (hell1.c:15)
==2230==  Address 0x419d028 is 0 bytes inside a block of size 4 free'd
==2230==    at 0x402605E: free (vg_replace_malloc.c:427)
==2230==    by 0x804848F: main (hell1.c:12)
==2230==
==2230==
==2230== 1 errors in context 3 of 4:
==2230== Use of uninitialised value of size 4
==2230==    at 0x8048499: main (hell1.c:14)
==2230==  Uninitialised value was created by a stack allocation
==2230==    at 0x8048471: main (hell1.c:8)
==2230==
--2230--
--2230-- used_suppression:     11 dl-hack3-cond-1
==2230==
==2230== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 11 from 6)
Segmentation fault
root@bt:~/Desktop#

You can clearly see that valgrind has pointed out commented errors and also display the detail description about that error.
Valgrind options     -     uses
--tool=memcheck        - using valgrind memcheck tool
--leak-check=full     - to see details of leaked memory
--track-origins=yes    - to see where uninitialised values come from
-v             - For counts of detected and suppressed errors

Memory Pools: describing and working with custom allocators

There are many different sorts of custom allocator, so Memcheck attempts to reason about them using a loose, abstract model. We use the following terminology when describing custom allocation systems:
• Custom allocation involves a set of independent "memory pools".
• Memcheck’s notion of a memory pool consists of a single "anchor address" and a set of non-overlapping "chunks" associated with the anchor address.
• Typically a pool’s anchor address is the address of a book-keeping "header" structure.
• Typically the pool’s chunks are drawn from a contiguous "superblock" acquired through the system malloc or mmap.

The Valgrind mempool client request API is intentionally vague about the exact structure of a mempool. There is no specific mention made of headers or superblocks.

Typically, before making client requests related to mempools, a client program will have allocated such a header and superblock for their mempool, and marked the superblock NOACCESS using the VALGRIND_MAKE_MEM_NOACCESS client request.
When dealing with mempools, the goal is to maintain a particular invariant condition: that Memcheck believes the unallocated portions of the pool’s superblock (including redzones) are NOACCESS. To maintain this invariant, the client program must ensure that the superblock starts out in that state; Memcheck cannot make it so, since Memcheck never explicitly learns about the superblock of a pool, only the allocated chunks within the pool.

Once the header and superblock for a pool are established and properly marked, there are a number of client requests programs can use to inform Memcheck about changes to the state of a mempool. e.g - VALGRIND_CREATE_MEMPOOL,VALGRIND_DESTROY_MEMPOOL,VALGRIND_MEMPOOL_ALLOC,VALGRIND_MEMPOOL_FREE, etc.

For details refer Valgrind Manual Page.

Debugging MPI Parallel Programs with Valgrind

Memcheck supports debugging of distributed-memory applications which use the MPI message passing standard. This support consists of a library of wrapper functions for the PMPI_* interface. When incorporated into the application’s address space, either by direct linking or by LD_PRELOAD, the wrappers intercept calls to PMPI_Send, PMPI_Recv, etc. They then use client requests to inform Memcheck of memory state changes caused by the function being wrapped.

For details refer valgrind Manual Page.

EUCLID Algorithm - Greatest Common Divisor

Given two integers a and b, it finds the largest integer that divides both of them, known as their greatest common divisor (gcd).Algorithm for gcd was discovered well over 2000 years ago by the mathematician Euclid, in ancient Greece.

Euclid's rule
If x and y are positive integers with x >= y,then gcd(x,y) = gcd(x mod y,y).

pseudo code
function Euclid(ab)
Input: Two integers a and b with a b 0
Output: gcd(ab)
if b = 0: return a
return Euclid(b,amod b)

Fibonacci Series

Fibonacci Series is famous sequence of numbers each the sum of its two immediate predecessors. It was developed by Italian mathematician Leonardo Fibonacci.

Fn    =      Fn-1+Fn-2     if n>1
                1                   if n=1
                0                   if n=0

In fact, the Fibonacci numbers grow almost as fast as powers of 2: e.g. F30 is over a million, and F100 is already 21 digits longs. In general, Fn=2(0.694n)

Recursive algorithm.

pseudo code

function fib1(n)
if n=0: return 0
if n=1: return 1
return fib1(n-1) + fib1(n-2)

Time Complexity

Let Tn be the number of computer steps needed to compute fib1(n). so if n is less than 2, the procedure halts immediately.
therefore, T(n) <=2 for n<=1

For larger values of n, there are two recursive invocation of fib1, taking time, T(n-1) and T(n-2) respectively, plus three computer steps.
therfore, T(n)=T(n-1)+T(n-2)+3 for n>1

comparing this to the recurrence relation for Fn, we see T(n)>=Fn.
Hence, the running time of the algorithm grows as fast as the Fibonacci numbers! T(n) is exponential in n, which implies that the algorithm is impractically slow except for very small values of n.

Can we do better?

Iterative algorithm

A more sensible scheme would store the intermediate results — the values F0,F1,...,Fn-1 soon as they become known.
pseudo code

function fib2(n)
if n = 0 return 0
create an array f[0...n]
f[0] = 0, f[1] = 1
for i = 2...n:
f[i] = f[i-1] + f[i-2]
return f[n]

Time Complexity

The inner loop consists of a single computer step and n is executed n1 times. Therefore the number of computer steps used by fib2 is linear in n.

Can we do better?

One idea involves matrices.
we start by writing the equations F1=F1 and F2=F0+F1 in matrix notation:

Here, calculation of matrix coefficient will take approx log(n) complexity.

Applications of Fibonacci Numbers

The Fibonacci numbers are important in the run-time analysis of Euclid's algorithm to determine the greatest common divisor of two integers.

The Fibonacci numbers occur in a formula about the diagonals of Pascal's triangle.

In music Fibonacci numbers are sometimes used to determine tunings, and, as in visual art, to determine the length or size of content or formal elements.

Even more amazing is a surprising relationship to magic squares. Magic squares are arrangements of numbers in a square pattern in which all the rows, columns, and diagonals add up to the same number. The simplest is the 3x3 pattern shown below:

2	7	6
9	5	1
4	3	8

If one substitutes for these numbers the corresponding Fibonacci number, a new "magic square" is produced in which the sum of the products of the three rows is equal to the sum of the products of the three columns.

For More applications refer link:

http://library.thinkquest.org/27890/applications5.html

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

Introduction To Algorithms

Changes in Introduction to Algorithm, 3rd Edition (CLRS)

• It contains technique-based chapters on divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, NP-Completeness, and approximation algorithms.
• New chapters on van Emde Boas trees and multithreaded algorithms.
• Two chapters binomial heaps and sorting networks are removed.
• The material on flow networks now bases flows entirely on edges.
• 100 new exercises and 28 new problems are added.
• Revised treatment of dynamic programming and greedy algorithms. Dynamic programming now leads off with a more interesting problem, rod cutting,than the assembly-line scheduling problem.
• Introduced the notion of the subproblem graph as a way to understand the running time of a dynamic-programming algorithm.
• Delete a node from binary search trees (which includes red-black trees) now guarantees that the node requested for deletion is the node that is actually deleted.
• Modified treatment of the Knuth-Morris-Pratt string-matching algorithm.

You can download the ebook from below link

http://www.eazyupload.net/download/wKd0MC9p/0262033844.zip.htm

You can purchase online books from site
http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_5?ie=UTF8&qid=1335291985&sr=8-5

http://www.flipkart.com/introduction-algorithms-8120340078/p/itmczynzhyhxv2gs?pid=9788120340077&_l=j9Xfifej1tnSUjNow6B3Vw--&_r=+tjvyTjc+kHE2zbZyVojuQ--&ref=1f8f0b03-5641-4c04-805d-aa261ccae61e

The Web site(http://mitpress.mit.edu/algorithms/) links to a list of known errors, solutions to selected exercises and problems.

Using Valgrind Part 1

What Valgrind does with your program

You can invoke valgrind  using command

valgrind [valgrind-options] your-prog [your-prog-options]

The most important option is --tool which dictates which Valgrind tool to run. The default tool is memcheck. 

Regardless of which tool is in use, Valgrind takes control of your program before it starts. Debugging information is read from the executable and associated libraries, so that error messages and other outputs can be phrased in terms of source code locations, when appropriate.

Your program is then run on a synthetic CPU provided by the Valgrind core. As new code is executed for the first time, the core hands the code to the selected tool. The tool adds its own instrumentation code to this and hands the result back to the core, which coordinates the continued execution of this instrumented code.

First off, consider whether it might be beneficial to recompile your application and supporting libraries with debugging info enabled (the -g option). Without debugging info, the best Valgrind tools will be able to do is guess which function a particular piece of code belongs to, which makes both error messages and profiling output nearly useless. With -g, you'll get messages which point directly to the relevant source code lines.

 Another option you might like to consider, if you are working with C++, is -fno-inline. That makes it easier to see the function-call chain, which can help reduce confusion when navigating around large C++ apps.

If you are planning to use Memcheck: On rare occasions, compiler optimisations (at -O2 and above, and sometimes -O1) have been observed to generate code which fools Memcheck into wrongly reporting uninitialised value errors, or missing uninitialised value errors. So the best solution is to turn off optimisation altogether

Memcheck: a memory error detector

To use this tool, you may specify --tool=memcheck on the Valgrind command line.

It can detect the following problems that are common in C and C++ programs.

• Accessing memory you shouldn't, e.g. overrunning and underrunning heap blocks, overrunning the top of the stack, and accessing memory after it has been freed.
• Using undefined values, i.e. values that have not been initialised, or that have been derived from other undefined values.
• Incorrect freeing of heap memory, such as double-freeing heap blocks, or mismatched use of malloc/new/new[] versus free/delete/delete[] 
• Overlapping src and dst pointers in memcpy and related functions.
• Memory leaks.

The Function Stack

For getting the knowledge about function call stack you should be aware of some general purpose registers used during program execution especially related to stack.

Some of the general purpose register used during program execution are:

• AX/EAX/RAX: Accumulator
• BX/EBX/RBX: Base index (for use with arrays)
• CX/ECX/RCX: Counter
• DX/EDX/RDX: Data/general
• SI/ESI/RSI: Source index for string operations.
• DI/EDI/RDI: Destination index for string operations.
• SP/ESP/RSP: Stack pointer for top address of the stack.
• BP/EBP/RBP: Stack base pointer for holding the address of the current stack frame.
• IP/EIP/RIP: Instruction pointer. Holds the program counter, the current instruction address.

Segment registers:

• CS: Code
• DS: Data
• SS: Stack
• ES: Extra
• FS
• GS

So what happens when function call take place?

When the function call takes place, data elements are stored on the stack in the following way

• The function parameters are pushed on the stack before the function is called.  The parameters are pushed from right to left.
• The function return address is placed on the stack by the x86 CALL instruction, which stores the current value of the RIP register.
• Then, the frame pointer that is the previous value of the RBP register is placed on the stack.
• The callee save registers such as ESI, EDI, and EBX are stored if they are used at any point during the functions execution.
• Next, the locally declared variables.
• Then the buffers are allocated for temporary data storage.  

I will illustrate you by simple add program regarding function call.

sample program:

#include<stdio.h>
int add(int a,int b)
{
int c;
c=a+b;
return c;
}
int main()
{
int k=add(2,3);
printf("%d\n",k);
return 0;
}

compile program using gcc. 

gcc hello.c

objdump in linux is a good tool for getting information related to object file. it can be used to display assembler context of object file.

objdump -d a.out

it display a lot of information but i am displaying only of our concern.

0000000000400498 <add>:
  400498:       55                      push   %rbp
  400499:       48 89 e5             mov    %rsp,%rbp
  40049c:       89 7d ec                mov    %edi,0xffffffffffffffec(%rbp)
  40049f:       89 75 e8                mov    %esi,0xffffffffffffffe8(%rbp)
  4004a2:       8b 45 e8                mov    0xffffffffffffffe8(%rbp),%eax
  4004a5:       03 45 ec                add    0xffffffffffffffec(%rbp),%eax
  4004a8:       89 45 fc                mov    %eax,0xfffffffffffffffc(%rbp)
  4004ab:       8b 45 fc                mov    0xfffffffffffffffc(%rbp),%eax
  4004ae:       c9                      leaveq
  4004af:       c3                      retq

00000000004004b0 <main>:
  4004b0:       55                      push   %rbp
  4004b1:       48 89 e5                mov    %rsp,%rbp
  4004b4:       48 83 ec 10             sub    $0x10,%rsp
  4004b8:       be 03 00 00 00          mov    $0x3,%esi
  4004bd:       bf 02 00 00 00          mov    $0x2,%edi
  4004c2:       e8 d1 ff ff ff          callq  400498 <add>
  4004c7:       89 45 fc                mov    %eax,0xfffffffffffffffc(%rbp)
  4004ca:       8b 75 fc                mov    0xfffffffffffffffc(%rbp),%esi
  4004cd:       bf e8 05 40 00          mov    $0x4005e8,%edi
  4004d2:       b8 00 00 00 00          mov    $0x0,%eax
  4004d7:       e8 bc fe ff ff          callq  400398 <printf@plt>
  4004dc:       b8 00 00 00 00          mov    $0x0,%eax
  4004e1:       c9                      leaveq
  4004e2:       c3                      retq

you can also use disas to get the assembly code of function while using gdb.

gdb a.out

(gdb) disas main
Dump of assembler code for function main:
0x00000000004004b0 <main+0>:    push   %rbp
0x00000000004004b1 <main+1>:    mov    %rsp,%rbp
0x00000000004004b4 <main+4>:    sub    $0x10,%rsp
0x00000000004004b8 <main+8>:    mov    $0x3,%esi
0x00000000004004bd <main+13>:   mov    $0x2,%edi
0x00000000004004c2 <main+18>:   callq  0x400498 <add>
0x00000000004004c7 <main+23>:   mov    %eax,-0x4(%rbp)
0x00000000004004ca <main+26>:   mov    -0x4(%rbp),%esi
0x00000000004004cd <main+29>:   mov    $0x4005e8,%edi
0x00000000004004d2 <main+34>:   mov    $0x0,%eax
0x00000000004004d7 <main+39>:   callq  0x400398 <printf@plt>
0x00000000004004dc <main+44>:   mov    $0x0,%eax
0x00000000004004e1 <main+49>:   leaveq
0x00000000004004e2 <main+50>:   retq
End of assembler dump.
(gdb) disas add
Dump of assembler code for function add:
0x0000000000400498 <add+0>:     push   %rbp
0x0000000000400499 <add+1>:     mov    %rsp,%rbp
0x000000000040049c <add+4>:     mov    %edi,-0x14(%rbp)
0x000000000040049f <add+7>:     mov    %esi,-0x18(%rbp)
0x00000000004004a2 <add+10>:    mov    -0x18(%rbp),%eax
0x00000000004004a5 <add+13>:    add    -0x14(%rbp),%eax
0x00000000004004a8 <add+16>:    mov    %eax,-0x4(%rbp)
0x00000000004004ab <add+19>:    mov    -0x4(%rbp),%eax
0x00000000004004ae <add+22>:    leaveq
0x00000000004004af <add+23>:    retq
End of assembler dump.

To get the information about current values in registers you can use info command in gdb.
(gdb) info reg
rax            0x3810753a60     240794286688
rbx            0x380f61bbc0     240776231872
rcx            0x400500 4195584
rdx            0x7fff417a37b8   140734291916728
rsi            0x3      3
rdi            0x2      2
rbp            0x7fff417a36a0   0x7fff417a36a0
rsp            0x7fff417a36a0   0x7fff417a36a0
r8             0x38107522d0     240794280656
r9             0x380f40d620     240774075936
r10            0x0      0
r11            0x381041d8a0     240790919328
r12            0x0      0
r13            0x7fff417a37a0   140734291916704
r14            0x0      0
r15            0x0      0
rip            0x4004a2 0x4004a2 <add+10>
eflags         0x202    [ IF ]
cs             0x33     51
ss             0x2b     43
ds             0x0      0
es             0x0      0
fs             0x0      0
gs             0x0      0
fctrl          0x37f    895
fstat          0x0      0
ftag           0xffff   65535
fiseg          0x0      0
fioff          0x0      0
foseg          0x0      0
fooff          0x0      0
fop            0x0      0
mxcsr          0x1f80   [ IM DM ZM OM UM PM ]

These all registers are hardware architecture dependent.

Gdb(GNU Debugger)

A debugger for several languages, including C and C++. It allows you to inspect what the program is doing at a certain point during execution.Errors like segmentation faults may be easier to find with the help of gdb.

You need to build program with -g option to enable built-in debugging support.

gcc [other flags] -g <source files> -o <output file>

  

gdb commands

• getting help - you can get help of gdb commands
  (gdb)help CommandName
  (gdb)help
  will list classes of commands.
• Invoking gdb -Once your executable has been generated by the compiler, it is run under the control of gdb by typing.

  >gdb program 

  if you have not specified filename with gdb you can specify later using command file.
  (gdb) file program
  where program is the name of the executable. it loads the debugging information of this file.
  You can also start with both an executable program and a core file
  

  >gdb program core

  You can, instead, specify a process ID as a second argument, if you want to debug a running process:
  

  >gdb program 1234 

• Quiting gdb - you can exit gdb by using quit command.
  (gdb)quit
• Running the program - When gdb starts, your program is not actually running. It won't run until you tell gdb how to run it.To run the program, just use:
  (gdb) run
  if there is no issue it runs normally, else you (should) get some useful information like the line number where it crashed, and parameters to the function that caused the error.
• Setting breakpoints - Breakpoints can be used to stop the program run in the middle, at a some point. you can use “break” command.
  (gdb) break prog1.c:6
  sets a breakpoint at line 6, of prog1.c.
  You can also tell gdb to break at a particular function.Suppose you have a function my func:
  int func(int a);
  you can apply breakpoint to this function using command
  (gdb) break func
  Once you’ve set a breakpoint, you can try using the run command again. This time, it should stop where you placed breakpoint.
• You can proceed onto the next breakpoint by typing “continue”. because typing run will restart the program from beginnning.
  (gdb) continue
• You can single-step (execute just the next line of code) by typing “step.”
  (gdb) step
• Similar to “step,” the “next” command single-steps as well, except this one doesn’t execute each line of a sub-routine, it just treats it as one instruction.
  (gdb) next
• Removing breakpoints - you can use delete command to remove breakpoint.
  (gdb) delete N
  deletes Nth breakpoint. you can get that using command
  (gdb)info break.
• Passing arguments - you can specify arguments using set args command.
• Examining variables - The print command prints the value of the specified variables.
  (gdb) print var
• backtrace - produces a stack trace of the function calls that lead to a seg fault.
  (gdb)backtrace

For quick reference of gdb commands refer link http://users.ece.utexas.edu/~adnan/gdb-refcard.pdf