Bloom fillers are considered an application of hash tables. Bloom filters are us
ID: 3692361 • Letter: B
Question
Bloom fillers are considered an application of hash tables. Bloom filters are used for proactive password cracking - to identify whether a password entered by a user at the time of registration is vulnerable for cracking or not. To do so. the Bloom filter maintains the hash values for a potentially vulnerable list of passwords (commonly used passwords, words from dictionary, etc) and if the hash value of the user entered password matches to those in the Bloom filter, the user password is not accepted as part of the registration process anti the user is forced to choose a password whose hash value does not match to the one in the Bloom filter. For the purpose of this project, you could envision a Bloom filter that calculates the hash value for a word as the sum of the ascii values of the characters in the word divided by a prime number; the size of the Bloom filter (hash table) is the magnitude of the divisor prime number. You can assume either a closed or open hash table. A false positive scenario is one wherein the user entered password is not vulnerable; but a Bloom filter flags the password as vulnerable. A false negative scenario is one wherein the user entered password is vulnerable; but a Bloom filter docs not flag the password as vulnerable. Given the above description of Bloom filters, prove that the Bloom filters cannot have a false negative scenario, but could have a false positive scenario. You could show your proof with examples and record a video. Prove that when Breadth First Search (BFS) is conducted on a graph starting from a particular vertex s. we are guaranteed to find the minimum hop path (paths with the minimum number of intermediate edges) from s to every other vertex in the graph.Explanation / Answer
Task 2
while using BFS for finding shortest path in a graph what we do is
We discover all the connected vertices, add them in the queue and also maintain the distance from source to that vertex. Now if we find a path from source to that vertex with still less distance then we update it!
As we are trying to find out the shortest path in the graph we will choose the hop path ie path with minimum number of intermediate edges .and we will traverse through all vertices in the graph so we can find out the hop path to all vertices in the graph from the starting vertex.
And following code will try to implement bfs traversal in a graph using c++:
// Program to print BFS traversal from a given source vertex. BFS(int s)
// traverses vertices reachable from s.
#include<iostream>
#include <list>
using namespace std;
// This class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void BFS(int s); // prints BFS traversal from a given source s
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// 'i' will be used to get all adjacent vertices of a vertex
list<int>::iterator i;
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
for(i = adj[s].begin(); i != adj[s].end(); ++i)
{
if(!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Breadth First Traversal (starting from vertex 2) ";
g.BFS(2);
return 0;
}