Research Experiences

MSc Thesis in Computing Science

Title: Average sensitivity of breadth-first search algorithm on grids

  • Abstract: The average sensitivity of a graph algorithm is a measure that calculates the stability of the algorithm when the input graph undergoes perturbations. The perturbation is represented by removing some of the edges of the input graph, and the stability is quantified using the Earth mover’s distance between the algorithm’s outputs on the original and perturbed graphs. In this thesis, we investigate the average sensitivity of the Breadth-first search(BFS) algorithm with BFS trees as outputs. It is known that for an arbitrary graph G(V, E), the average sensitivity of the BFS algorithm is Θ(|V(G)|). We prove that when the input graph G is an m × n grid graph, there is a BFS algorithm with an average sensitivity of at most 2. We also prove that for specific starting nodes, the randomization of the BFS algorithm reduces its average sensitivity. Click here to see more.

BSc Thesis in Computer Engineering

Graph sampling from distance matrices using Spanning Trees (minimum spanning tree, maximum spanning tree, low weighted and high weighted random walk spanning trees) and visualization of closeness centrality and betweenness centrality in these graphs. Click here to see more.

Selected Projects

A Genetic Algorithm

Devising a genetic algorithm for regression of third degree polynomial

Graph Sampling Project

Graph sampling from distance matrices using Spanning trees and visualization of closeness and betweenness in graph

CamScanner

A simple CamScanner

Pacman

A 2D Pacman game implemented with java.

The Dodger

A fun 2D game implemented with java.

The Sliding Puzzle

solving sliding puzzle problem using different algorithms

Fun

A new evergreen chess game just dropped!!

Although I don't play chess that often and I am not a professional chess player, I believe I have played a perfect game of chess with the black pieces which lasted 72 moves. Look at the accuracy of my game! It is 99%. And no! It wasn't like my opponent blundered a heavy piece early on at the beginning of the game and that most of my moves until the end of the game would be winning. In fact, my opponent didn't blunder or make any inaccurate moves until the last move!! And in an attempt to flag me (I had only 3 seconds on the clock) my opponent blundered mate in one! Unbelievable right?

Chess Game Image View Game Details