Portfolio of Projects on Computer Networks & Algorithms


Design of a Ripple Type algorithm to find Transitive Closure in graphs

posted Dec 21, 2010, 11:21 PM by Unknown user   [ updated Feb 25, 2012, 12:01 AM by Unknown user ]


Designed an algorithm to find the transitive closure in graphs. The algorithm has a unique property where time complexity is inversely proportional to the average branching factor of a graph. In fact it challenges the optimality of Warshall's O(n3) algorithm which is used in most books on algorithms. 

The time complexity of my algorithm is O(N3/E3). Where N is the number of nodes and E is the number of edges. The developed algorithm was initially hypothesized using flow charts and then it was tested by formally proving the hypothesis using running code. The input test case was varied from 10 to 500 nodes and at max n2 edges (i.e. 100 to 250,000 edges). The branching factor varied from 2 to 143 in these randomly generated graphs


It was found out that the total time taken to calculate the transitive closure in a single source graph is proportional to b-3 (branching factor = Total-Edges/Total-Nodes). A graph of the result is provided below. 


The graph below shows the big-oh complexity (upper limit) and theeta complexity (lower limit) of the algorithm. 



The graph below shows the variation of total-time and the branching factor of a graph. 



The graph below shows the variation of the b3 with total-time. 



Journal paper being sent for review by TALG, ACM. 

Please contact me for explanation of this algorithm. 


Image-o-encrypt

posted Dec 21, 2010, 10:32 AM by Unknown user   [ updated Jan 3, 2011, 7:30 AM ]

Self Initiated Project. 

Designed an algorithm on pattern recognition to encrypt messages in images. The code was written in Matlab and encryption and decryption of messages was performed. The resultant images have been shown below. 


Here two images were used. Image-2 had the message stored in it and image-1 had to store the message. The original images are shown below - 


Image-1 

This image has to store the message.


Message to be stored in Image-1.



Image-1 after message is Encrypted.


Now the message is decrypted from Image-1. The images below show the final images - 



Image-1 after message is decrypted/extracted.



Decrypted Message from the image.




Also, apart from this project, I applied different image processing & pattern recognition algorithms as a part of the course. Some of the important features learnt and implemented are: 


  • Digital Image data structures
  • Image enhancement in Spatial Domain 
    • Gray level transformations - Log, Power-law, Piecewise-Linear, Image-Negatives
    • Sampling and Quantization
    • Resizing Digital Images
    • Histogram Processing
    • Smoothing using spatial filters - lowpass, average, weighted average, median filters. 
    • Sharpening using spatial filters - Laplace, Sobel operators. 
  • Image enhancement in Frequency Domain
    • 2-D DFT and its inverse
    • Gaussian Low pass filters
    • Gaussian High pass filters
    • Padding 
    • Homomorphic Filtering
    • FFT
    • Convolution 
  • Color Image Processing
    • HSI color model
    • Intensity Slicing
    • Histogram Processing
    • Color & Tone correction
    • Smoothing & Sharpening
  • Image Compression
    • Redundancies
    • Encoder and decoder models
    • Variable length coding
    • LZW coding
    • Bit-Plane coding
    • Lossless predictive coding
    • Lossy Compression
    • Wavelet coding
    • Video Compression stadards
  • Morphological Operations
    • Dilation & Erosion
    • Hit-Miss Transformations
    • Opening & Closing
    • Boundary Extraction
    • Region Filling
    • Connected Components
    • Convex Hull
    • Thinning
    • Thickening
    • Skeletons
  • Segmentation
    • Point & Line detection
    • Edge detection
    • Hough Transform
    • Graph-Theoretic Techniques for Global Processing
    • Thresholding
    • Adaptive Thresholding
    • Region Growing
    • Watershed Segmentation
    • Motion in segmentation
  • Representation & Descriptions
    • Signatures
    • Chain Codes
    • Polygonal Approximations
    • Boundary Segments
    • Skeletons
    • Boundary Descriptors
    • Regional Descriptors
    • PCA for description
  • Object Recognition
    • Pattern Classes
    • Neural Networks
    • Fuzzy Systems
    • Syntactic pattern recognition
    • Graph Matching
    • Optimization Techniques
    • Finger Print recognition, 
    • IRIS recognition
    • Handwriting recognition &
    • Face recognition


Message Oriented Middleware (MOM)

posted Dec 21, 2010, 10:31 AM by Unknown user   [ updated Oct 10, 2011, 4:17 PM ]

Guide: Mr. Sandeep K. Mitra, Project Leader, Middle East Business Unit, Nucleus Software Exports Ltd., Noida, INDIA. 

I along with my team designed a proof of concept of a message oriented Middleware using Java Messaging Service (JMS) specifications.  The proof of concept was developed with synchronous and asynchronous messaging. 


The flow chart is shown below - 




A video which captures most of the features of a MOM, is shown below. 


Message Oriented Middleware



This project was developed independently by me and my team as a part of the practice school 1 program (of BITS Pilani) at Nucleus Software Exports Ltd, Noida. 

Credits: Arpit Agarwal, Ashutosh Singh, Ganesh Kumar & Naman Rastogi.

Journal Server Freeware Digital Library Project

posted Dec 21, 2010, 10:27 AM by Unknown user   [ updated Jan 1, 2011, 12:57 AM ]

Guide: Prof. Dr. Rahul Banerjee, SDETU Chief, BITS Pilani, Pilani Campus. 


Studied the various Search Engine Optimization Algorithms as a part of the Journal Server Freeware Digital Library Project, initiated by the Oxford-based JournalServer Trust. 


Google search engine algorithms were studied and exposure was gained in the same region. 


The major areas of algorithmic study was - 

  • Information Retrieval
  • Page Rank 
  • Query Parsing
  • Web Crawling
  • Hashing
  • Meta-Data/Meta-Text formation
Some algorithms: 
  • Non-Negative Matrix Factorization
  • Principle Component Analysis
  • Finding Global and Local minima
  • Document Term Matrix
  • Self-Organizing Maps
  • Distributed Search Algorithms
  • Centralized Search Algorithms
The Wikipedia page of the project is - http://en.wikipedia.org/wiki/JournalServer

Compiler

posted Dec 20, 2010, 3:10 AM by Unknown user   [ updated Oct 13, 2011, 12:15 AM ]

Guide: Mr. S. P. Vimal, Lecturer BITS Pilani, Pilani Campus. 

Designed a complete compiler for a language, as a part of the Programming Languages and Compiler Construction course at BITS Pilani. Applied and learnt the concepts of: 

  • Deterministic Finite Automata
  • Non-Deterministic Finite Automata
  • Push Down Automata
  • Single Tape Turing Machine
  • Double Tape Turing Machine
  • Multi Tape Turing Machine
  • Lambda Calculus
  • Parsing Techniques
  • Register Allocation
  • Liveness Analysis
  • Garbage Collection
  • Scope and binding of parameters
  • Activation Records
  • Call Stacks
  • Summary & Data organization
  • Machine language translation
The intermediate steps of the compiler development used were:
  • Lexical Analyzer
  • Syntax Analyzer
  • Parser
  • Symbol Table
  • Type Checker
  • Intermediate Code Generation
  • Code Optimization
  • Register Allocator
  • Instruction Scheduler
  • Code Generation in Target Language
  • ASM generation

The entire code built by me can be obtained from here

A Soda Dispenser

posted Oct 21, 2009, 8:58 AM by Unknown user   [ updated Oct 13, 2011, 12:15 AM ]

Guide: Prof. Sudeept Mohan, Group Leader, CSIS BITS Pilani, Pilani Campus. 

Designed a soda vending machine on concepts of embedded system as a part of the course project for the Microprocessors course. Applied concepts of Microprocessor memory & peripheral interfacing, with programming. 


The picture below shows the complete hardware design of the soda dispenser developed. 


The connections from the microprocessor..


The album below shows all the parts.. 


Soda Vending Machine



The code was developed in Embedded C and Assembly. 


The entire report can be found here: Report


1-6 of 6