fakrudeen-something

[fakrudeen-something]

Google Home vs Siri challenge!

In Christmas vacation we decided to do a google home vs siri challenge for fun.

We came up with 10 questions with each question worth 10 points:

What is the square of hundred?

Who is the first person on the moon?

Where is Kerala?

How do you say merry christmas in spanish?

What is the biggest animal?

How tall can a Sequoia tree grow?

Is a rocket or a plane faster?

Where am I?

Where is the nearest Lime bicycle?

Tell me a joke

Here are the results:

1. What is the square of hundred? This was one of the easiest questions. Surprisingly Google got this wrong and went on about squares in general. Siri got it perfectly right and said “10,000”.

Google - 0 and Siri - 10

2. Who is the first person on the moon?

Both of them got it right. Google explained a bit more about date and so on. Siri said “Neil Armstrong”.

Google - 10 and Siri - 10

3. Where is Kerala?

It is a state of Kerala and both of them got it and said it is in Kerala. Siri brought up the map as we used the Siri in Mac and Google can’t do it with a speaker anyway.

Google - 10 and Siri - 10

4. How do you say merry christmas in spanish?

Google said “Feliz Navidad” in beautiful Spanish voice. Siri didn’t understand the question and produced complete non-sense.

Google - 10 and Siri - 0

5. What is the biggest animal?

Both of them said Blue whale.

Google - 10 and Siri - 10

6. How tall can a Sequoia tree grow?

Google correctly said it can grow ~250 ft and added as bonus maximum diameter. Siri harped on about some “Sequoia tree girl”!

Google - 10 and Siri - 0

7. Is a rocket or a plane faster?

We had to repeat this once and Google got the answer correct. Siri again came up with some word salad after asking three times.

Google - 10 and Siri - 0

8. Where am I?

Google surprisingly got this wrong as their map is so good. Siri got this exactly right and gave our address.

Google - 0 and Siri - 10

9. Where is the nearest Lime bicycle?

This was one of the hardest questions and we knew it is very close to home near the corner. Both of them got it wrong as expected.

Google - 0 and Siri - 0

10. Tell me a joke

We gave each 3 chances as it was open ended question. 

Best from Google: “What do you call a Labrador when it turns into magician”?

Labracabdrador

Best from Siri:

“Where do whales go to listen to music”?

Orca-estra

We grudgingly gave both of them a pass!

Google - 10 and Siri - 10

image credit: https://www.inteligenciaartificial.me

And the winner is:

google home!

Final scores were: Google: 70% and Siri:60%

[fakrudeen-something]

Minimum Spanning Tree algorithm

Minimum spanning tree for an undirected weighted graph computes the spanning tree with minimum weight.

This code computes the minimum spanning tree for the graph:

public static MSTInfo computeMST(Graph graph) {    Map<Graph.Vertex, Boolean> vertexToProcessedMap = new HashMap<>();    Map<Graph.Vertex, Integer> vertexToMinimumEdgeMap = new HashMap<>();    Map<Graph.Vertex, Graph.Vertex> vertexToPredecessorMap = new HashMap<>();    PriorityQueue<Graph.Vertex> minimumEdgeQueue = new PriorityQueue<>((vertex1, vertex2) -> {        if(!vertexToMinimumEdgeMap.containsKey(vertex1)) {            return 1;        } else if(!vertexToMinimumEdgeMap.containsKey(vertex2)) {            return -1;        }        return (vertexToMinimumEdgeMap.get(vertex1)-vertexToMinimumEdgeMap.get(vertex2));    });    Optional<Graph.Vertex> firstOptional = graph.vertices().stream().findFirst();    if(!firstOptional.isPresent()) { // empty graph        return null;    }    Graph.Vertex start = firstOptional.get();    vertexToMinimumEdgeMap.put(start, 0);    vertexToPredecessorMap.put(start, null);    minimumEdgeQueue.add(start);    while (!minimumEdgeQueue.isEmpty()) {        Graph.Vertex current = minimumEdgeQueue.poll();        for(Graph.Vertex neighbor:graph.adjacencyList(current)) {            relax(graph, current, neighbor, minimumEdgeQueue, vertexToMinimumEdgeMap, vertexToPredecessorMap, vertexToProcessedMap);        }        vertexToProcessedMap.put(current, true);    }    Graph mstGraph = buildMSTGraph(graph, vertexToPredecessorMap);    return new MSTInfo(mstGraph); }

This java code computes the minimum spanning tree in Jave with randomized tests:

package com.fakrudeen; import java.util.*; import static com.fakrudeen.Graph.buildRandomGraph; /** * Minimum Spanning Tree Algorithm * Author: Fakrudeen Ali Ahmed * Date: 17 Sep 2017 */ public class MST {    public static void main(String[] args) throws InterruptedException {        for(int i = 0; i < 1000; ++i) {            runComputeMST();            Thread.sleep(3000);            System.out.println();        }    }    private static void runComputeMST() {        Graph graph = buildRandomGraph(true, true);        System.out.println(graph);        MSTInfo mstInfo = computeMST(graph);        System.out.println(mstInfo);    }    public static MSTInfo computeMST(Graph graph) {        Map<Graph.Vertex, Boolean> vertexToProcessedMap = new HashMap<>();        Map<Graph.Vertex, Integer> vertexToMinimumEdgeMap = new HashMap<>();        Map<Graph.Vertex, Graph.Vertex> vertexToPredecessorMap = new HashMap<>();        PriorityQueue<Graph.Vertex> minimumEdgeQueue = new PriorityQueue<>((vertex1, vertex2) -> {            if(!vertexToMinimumEdgeMap.containsKey(vertex1)) {                return 1;            } else if(!vertexToMinimumEdgeMap.containsKey(vertex2)) {                return -1;            }            return (vertexToMinimumEdgeMap.get(vertex1)-vertexToMinimumEdgeMap.get(vertex2));        });        Optional<Graph.Vertex> firstOptional = graph.vertices().stream().findFirst();        if(!firstOptional.isPresent()) { // empty graph            return null;        }        Graph.Vertex start = firstOptional.get();        vertexToMinimumEdgeMap.put(start, 0);        vertexToPredecessorMap.put(start, null);        minimumEdgeQueue.add(start);        while (!minimumEdgeQueue.isEmpty()) {            Graph.Vertex current = minimumEdgeQueue.poll();            for(Graph.Vertex neighbor:graph.adjacencyList(current)) {                relax(graph, current, neighbor, minimumEdgeQueue, vertexToMinimumEdgeMap, vertexToPredecessorMap, vertexToProcessedMap);            }            vertexToProcessedMap.put(current, true);        }        Graph mstGraph = buildMSTGraph(graph, vertexToPredecessorMap);        return new MSTInfo(mstGraph);    }    /**     * MST relax an edge     * @param graph Original graph     * @param current source of the edge     * @param neighbor destination of the edge     * @param minimumEdgeQueue Priority Queue with minimum edge weights as the key     * @param vertexToMinimumEdgeMap Vertex to Minimum Edge weight map     * @param vertexToPredecessorMap Vertex to Predecessor map     * @param vertexToProcessedMap Map showing whether a vertex has been processed already     */    private static void relax(Graph graph, Graph.Vertex current, Graph.Vertex neighbor, PriorityQueue<Graph.Vertex> minimumEdgeQueue, Map<Graph.Vertex, Integer> vertexToMinimumEdgeMap, Map<Graph.Vertex, Graph.Vertex> vertexToPredecessorMap, Map<Graph.Vertex, Boolean> vertexToProcessedMap) {        //skip already processed neighbours        if(vertexToProcessedMap.getOrDefault(neighbor, false)) {           return;        }        int edgeWeight = graph.getWeight(current, neighbor);        if(vertexToMinimumEdgeMap.getOrDefault(neighbor, Integer.MAX_VALUE) > edgeWeight) {            minimumEdgeQueue.remove(neighbor);            vertexToMinimumEdgeMap.put(neighbor, edgeWeight);            minimumEdgeQueue.add(neighbor);            vertexToPredecessorMap.put(neighbor, current);        }    }    /**     * Build MST graph from predecessor map and original graph     * @param graph original graph     * @param vertexToPredecessorMap predecessor map     * @return MST graph     */    private static Graph buildMSTGraph(Graph graph, Map<Graph.Vertex, Graph.Vertex> vertexToPredecessorMap) {        Map<Graph.Vertex, List<Graph.Vertex>> edges = new HashMap<>();        Map<Map.Entry<Graph.Vertex, Graph.Vertex>, Integer> edgeWeights = new HashMap<>();        for(Graph.Vertex vertex:vertexToPredecessorMap.keySet()) {            Graph.Vertex predecessor = vertexToPredecessorMap.get(vertex);            if(null == predecessor) { // ignore root vertex                continue;            }            if(!edges.containsKey(predecessor)) {                edges.put(predecessor, new ArrayList<>());            }            List<Graph.Vertex> neighbors = edges.get(predecessor);            neighbors.add(vertex);            edgeWeights.put(new AbstractMap.SimpleEntry<>(predecessor, vertex), graph.getWeight(predecessor, vertex));        }        return new Graph(edges, edgeWeights);    }    public static class MSTInfo {        Graph graph;        public MSTInfo(Graph graph) {            this.graph = graph;        }        @Override        public String toString() {            return "MSTInfo{" +                    "graph=" + graph +                    '}';        }    } }

[fakrudeen-something]

Murphy’s law

Murphy’s law says “if something can go wrong, it will go wrong.”

There is a technical version of this in probability.

If there are 1000 ways (events)  for a nuclear meltdown and all are mutually independent and each of them with probability 1/100, then the expectation value of the number of events is 10 and it is a virtual certainty that nuclear meltdown will occur.

In fact the probability for it to not meltdown is < e^-10. (~0.000045)

More details at: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap19.pdf

[fakrudeen-something]

Depth First Search (DFS)

Depth First Search of a Graph visits the graph by going as deep as one can go and then backtracking.

This code visits all reachable nodes by DFS starting with a source:

public static DFSInfo visit(Graph graph, Graph.Vertex start, Map<Graph.Vertex, Graph.Vertex> vertexToParentMap, Map<Graph.Vertex, Integer> vertexToFinishTimeMap, AtomicInteger finishTime) {    vertexToParentMap.put(start, null);    for(Graph.Vertex neighbor:graph.adjacencyList(start)) {        if (!vertexToParentMap.containsKey(neighbor)) {            visit(graph, neighbor, vertexToParentMap, vertexToFinishTimeMap, finishTime);            vertexToParentMap.put(neighbor, start);        }    }    vertexToFinishTimeMap.put(start, finishTime.incrementAndGet());    return new DFSInfo(vertexToParentMap, vertexToFinishTimeMap); }

This code in Java runs DFS on graph with randomized tests:

package com.fakrudeen; import java.util.HashMap; import java.util.Map; import java.util.concurrent.atomic.AtomicInteger; import static com.fakrudeen.Graph.buildRandomGraph; /** * Depth First Search (DFS) Algorithm * Author: Fakrudeen Ali Ahmed * Date: 3 Sep 2017 */ public class DFS {    public static void main(String[] args) throws InterruptedException {        for(int i = 0; i < 1000; ++i) {            runDFS();            Thread.sleep(3000);            System.out.println();        }    }    private static void runDFS() {        Graph graph = buildRandomGraph(false, false);        System.out.println(graph);        DFSInfo dfsInfo = visit(graph, new Graph.Vertex(1, 1), new HashMap<>(), new HashMap<>(), new AtomicInteger(0));        System.out.println(dfsInfo);        dfsInfo = visitAll(graph);        System.out.println(dfsInfo);    }    public static DFSInfo visitAll(Graph graph) {        Map<Graph.Vertex, Graph.Vertex> vertexToParentMap = new HashMap<>();        Map<Graph.Vertex, Integer> vertexToFinishTimeMap = new HashMap<>();        AtomicInteger finishTime = new AtomicInteger(0);        for(Graph.Vertex vertex:graph.vertices()) {            if(!vertexToParentMap.containsKey(vertex)) {                visit(graph, vertex, vertexToParentMap, vertexToFinishTimeMap, finishTime);            }        }        return new DFSInfo(vertexToParentMap, vertexToFinishTimeMap);    }    public static DFSInfo visit(Graph graph, Graph.Vertex start, Map<Graph.Vertex, Graph.Vertex> vertexToParentMap, Map<Graph.Vertex, Integer> vertexToFinishTimeMap, AtomicInteger finishTime) {        vertexToParentMap.put(start, null);        for(Graph.Vertex neighbor:graph.adjacencyList(start)) {            if (!vertexToParentMap.containsKey(neighbor)) {                visit(graph, neighbor, vertexToParentMap, vertexToFinishTimeMap, finishTime);                vertexToParentMap.put(neighbor, start);            }        }        vertexToFinishTimeMap.put(start, finishTime.incrementAndGet());        return new DFSInfo(vertexToParentMap, vertexToFinishTimeMap);    }    public static class DFSInfo {        Map<Graph.Vertex, Graph.Vertex> vertexToParentMap;        Map<Graph.Vertex, Integer> vertexToFinishTimeMap;        public DFSInfo(Map<Graph.Vertex, Graph.Vertex> vertexToParentMap, Map<Graph.Vertex, Integer> vertexToFinishTimeMap) {            this.vertexToParentMap = vertexToParentMap;            this.vertexToFinishTimeMap = vertexToFinishTimeMap;        }        @Override        public String toString() {            return "DFSInfo{" +                    "vertexToParentMap=" + vertexToParentMap +                    ", vertexToFinishTimeMap=" + vertexToFinishTimeMap +                    '}';        }    } }

[fakrudeen-something]

Graph class in Java

This is a Graph class in java including methods for building and printing graphs.

package com.fakrudeen; import java.util.*; /** * A Graph class * Author: Fakrudeen Ali Ahmed * Date: 3 Sep 2017 */ public class Graph {    private Map<Vertex, List<Vertex>> edges;    private Map<Map.Entry<Vertex, Vertex>, Integer> edgeWeights;    public Graph(Map<Vertex, List<Vertex>> edges) {        this.edges = edges;    }    public Graph(Map<Vertex, List<Vertex>> edges, Map<Map.Entry<Vertex, Vertex>, Integer> edgeWeights) {        this.edges = edges;        this.edgeWeights = edgeWeights;    }    public Set<Vertex> vertices() {        return edges.keySet();    }    public List<Vertex> adjacencyList(Vertex v) {        return edges.getOrDefault(v, null);    }    public int getWeight(Vertex source, Vertex destination) {        if(null == edgeWeights) { // unweighted graph            return (edges.get(source).contains(destination)? 1:Integer.MAX_VALUE);        }        return edgeWeights.getOrDefault(new AbstractMap.SimpleEntry<>(source, destination), Integer.MAX_VALUE);    }    @Override    public String toString() {        if(null == edgeWeights) {            return "Graph{" +                "edges=" + edges +                '}';        }        return "Graph{" +                "edges=" + edges +                ", edgeWeights=" + edgeWeights +                '}';    }    public static class Vertex {        public int id;        public int val;        public Vertex(int id, int val) {            this.id = id;            this.val = val;        }        @Override        public boolean equals(Object o) {            if (this == o) return true;            if (o == null || getClass() != o.getClass()) return false;            Vertex vertex = (Vertex) o;            return id == vertex.id;        }        @Override        public int hashCode() {            return id;        }        @Override        public String toString() {            return String.valueOf(id);        }    }    public static Graph buildRandomGraph(boolean withWeights, boolean isUndirected) {        int verticesCount = 10;        int edgesCount = verticesCount*2;        Map<Vertex, List<Vertex>> edges = new HashMap<>();        for(int i = 0; i < verticesCount; ++i) {            edges.put(new Vertex(i, 1), new ArrayList<>());        }        Random random1 = new Random();        Random random2 = new Random();        for(int i = 0; i < edgesCount; ++i) {            int source = random1.nextInt(verticesCount);            int destination = random2.nextInt(verticesCount);            if(source != destination) { // avoid self loop                addEdge(edges, source, destination);                if(isUndirected) {                    addEdge(edges, destination, source);                }            }        }        if(!withWeights) {            return new Graph(edges);        }        Random random3 = new Random();        Map<Map.Entry<Vertex, Vertex>, Integer> edgeWeights = new HashMap<>();        for(Vertex vertex:edges.keySet()) {            List<Vertex> neighbors = edges.get(vertex);            for(Vertex neighbor:neighbors) {                int edgeWeight = random3.nextInt(edgesCount * 10);                edgeWeights.put(new AbstractMap.SimpleEntry<>(vertex, neighbor), edgeWeight);                if(isUndirected) {                    edgeWeights.put(new AbstractMap.SimpleEntry<>(neighbor, vertex), edgeWeight);                }            }        }        return new Graph(edges, edgeWeights);    }    private static void addEdge(Map<Vertex, List<Vertex>> edges, int source, int destination) {        List<Vertex> neighbors = edges.get(new Vertex(source, 1));        Vertex destinationNode = new Vertex(destination, 1);        if(!neighbors.contains(destinationNode)) { // avoid duplicate elements in adjacency list            neighbors.add(destinationNode);        }    } }

[fakrudeen-something]

Breadth First Search (BFS)

BFS visits all the nodes in a graph starting from a source in the order of distance from the source.

This code computes BFS for a graph:

public static BFSInfo visit(Graph graph, Graph.Vertex start) {    Map<Graph.Vertex, Integer> vertexToLevelMap = new HashMap<>();    Map<Graph.Vertex, Graph.Vertex> vertexToParentMap = new HashMap<>();    vertexToLevelMap.put(start, 0);    vertexToParentMap.put(start, null);    // add start vertex to level 0 as well as the initial frontier    List<Graph.Vertex> frontier = Collections.singletonList(start);    int currentLevel = 1;    while(!frontier.isEmpty()) {        List<Graph.Vertex> next = new ArrayList<>();        for(Graph.Vertex currentNode:frontier) {            List<Graph.Vertex> adjacencyList = graph.adjacencyList(currentNode);            for(Graph.Vertex neighbor:adjacencyList) {                if(!vertexToLevelMap.containsKey(neighbor)) {                    vertexToLevelMap.put(neighbor, currentLevel);                    next.add(neighbor);                    vertexToParentMap.put(neighbor, currentNode);                }            }        }        frontier = next;        ++currentLevel;    }    return new BFSInfo(vertexToLevelMap, vertexToParentMap); }

The full java code for Graph class with some utility methods:

package com.fakrudeen; import java.util.*; /** * A Graph class * Author: Fakrudeen Ali Ahmed * Date: 3 Sep 2017 */ public class Graph {    private Map<Vertex, List<Vertex>> edges;    private Map<Map.Entry<Vertex, Vertex>, Integer> edgeWeights;    public Graph(Map<Vertex, List<Vertex>> edges) {        this.edges = edges;    }    public Graph(Map<Vertex, List<Vertex>> edges, Map<Map.Entry<Vertex, Vertex>, Integer> edgeWeights) {        this.edges = edges;        this.edgeWeights = edgeWeights;    }    public Set<Vertex> vertices() {        return edges.keySet();    }    public List<Vertex> adjacencyList(Vertex v) {        return edges.getOrDefault(v, null);    }    public int getWeight(Vertex source, Vertex destination) {        if(null == edgeWeights) { // unweighted graph            return (edges.get(source).contains(destination)? 1:Integer.MAX_VALUE);        }        return edgeWeights.getOrDefault(new AbstractMap.SimpleEntry<>(source, destination), Integer.MAX_VALUE);    }    @Override    public String toString() {        if(null == edgeWeights) {            return "Graph{" +                "edges=" + edges +                '}';        }        return "Graph{" +                "edges=" + edges +                ", edgeWeights=" + edgeWeights +                '}';    }    public static class Vertex {        public int id;        public int val;        public Vertex(int id, int val) {            this.id = id;            this.val = val;        }        @Override        public boolean equals(Object o) {            if (this == o) return true;            if (o == null || getClass() != o.getClass()) return false;            Vertex vertex = (Vertex) o;            return id == vertex.id;        }        @Override        public int hashCode() {            return id;        }        @Override        public String toString() {            return String.valueOf(id);        }    }    public static Graph buildRandomGraph(boolean withWeights, boolean isUndirected) {        int verticesCount = 10;        int edgesCount = verticesCount*2;        Map<Vertex, List<Vertex>> edges = new HashMap<>();        for(int i = 0; i < verticesCount; ++i) {            edges.put(new Vertex(i, 1), new ArrayList<>());        }        Random random1 = new Random();        Random random2 = new Random();        for(int i = 0; i < edgesCount; ++i) {            int source = random1.nextInt(verticesCount);            int destination = random2.nextInt(verticesCount);            if(source != destination) { // avoid self loop                addEdge(edges, source, destination);                if(isUndirected) {                    addEdge(edges, destination, source);                }            }        }        if(!withWeights) {            return new Graph(edges);        }        Random random3 = new Random();        Map<Map.Entry<Vertex, Vertex>, Integer> edgeWeights = new HashMap<>();        for(Vertex vertex:edges.keySet()) {            List<Vertex> neighbors = edges.get(vertex);            for(Vertex neighbor:neighbors) {                int edgeWeight = random3.nextInt(edgesCount * 10);                edgeWeights.put(new AbstractMap.SimpleEntry<>(vertex, neighbor), edgeWeight);                if(isUndirected) {                    edgeWeights.put(new AbstractMap.SimpleEntry<>(neighbor, vertex), edgeWeight);                }            }        }        return new Graph(edges, edgeWeights);    }    private static void addEdge(Map<Vertex, List<Vertex>> edges, int source, int destination) {        List<Vertex> neighbors = edges.get(new Vertex(source, 1));        Vertex destinationNode = new Vertex(destination, 1);        if(!neighbors.contains(destinationNode)) { // avoid duplicate elements in adjacency list            neighbors.add(destinationNode);        }    } }

Full java code for BFS using the above Graph with randomized tests:

package com.fakrudeen; import java.util.*; /** * Breadth First Search (BFS) Algorithm * Author: Fakrudeen Ali Ahmed * Date: 3 Sep 2017 */ public class BFS {    public static void main(String[] args) throws InterruptedException {        /*Graph graph = buildGraph();        BFSInfo bfsInfo = visit(graph, new Graph.Vertex(1, 1));        System.out.println(bfsInfo);        */        for(int i = 0; i < 1000; ++i) {            runBFS();            Thread.sleep(3000);            System.out.println();        }    }    private static void runBFS() {        Graph graph = Graph.buildRandomGraph(false, false);        System.out.println(graph);        BFSInfo bfsInfo = visit(graph, new Graph.Vertex(1, 1));        System.out.println(bfsInfo);    }    private static Graph buildGraph() {        Map<Graph.Vertex, List<Graph.Vertex>> edges = new HashMap<>();        Graph.Vertex first = new Graph.Vertex(1, 1);        Graph.Vertex second = new Graph.Vertex(2, 1);        Graph.Vertex third = new Graph.Vertex(3, 1);        Graph.Vertex fourth = new Graph.Vertex(4, 1);        edges.put(first, new ArrayList<>());        edges.put(second, new ArrayList<>());        edges.put(third, new ArrayList<>());        edges.put(fourth, new ArrayList<>());        edges.get(first).add(second);        edges.get(first).add(third);        edges.get(second).add(third);        edges.get(second).add(fourth);        edges.get(third).add(fourth);        return new Graph(edges);    }    public static BFSInfo visit(Graph graph, Graph.Vertex start) {        Map<Graph.Vertex, Integer> vertexToLevelMap = new HashMap<>();        Map<Graph.Vertex, Graph.Vertex> vertexToParentMap = new HashMap<>();        vertexToLevelMap.put(start, 0);        vertexToParentMap.put(start, null);        // add start vertex to level 0 as well as the initial frontier        List<Graph.Vertex> frontier = Collections.singletonList(start);        int currentLevel = 1;        while(!frontier.isEmpty()) {            List<Graph.Vertex> next = new ArrayList<>();            for(Graph.Vertex currentNode:frontier) {                List<Graph.Vertex> adjacencyList = graph.adjacencyList(currentNode);                for(Graph.Vertex neighbor:adjacencyList) {                    if(!vertexToLevelMap.containsKey(neighbor)) {                        vertexToLevelMap.put(neighbor, currentLevel);                        next.add(neighbor);                        vertexToParentMap.put(neighbor, currentNode);                    }                }            }            frontier = next;            ++currentLevel;        }        return new BFSInfo(vertexToLevelMap, vertexToParentMap);    }    public static class BFSInfo {        Map<Graph.Vertex, Integer> vertexToLevelMap;        Map<Graph.Vertex, Graph.Vertex> vertexToParentMap;        public BFSInfo(Map<Graph.Vertex, Integer> vertexToLevelMap, Map<Graph.Vertex, Graph.Vertex> vertexToParentMap) {            this.vertexToLevelMap = vertexToLevelMap;            this.vertexToParentMap = vertexToParentMap;        }        @Override        public String toString() {            return "BFSInfo{" +                    "vertexToLevelMap=" + vertexToLevelMap +                    ", vertexToParentMap=" + vertexToParentMap +                    '}';        }    } }

[fakrudeen-something]

Parking in a narrow parking space in parking lot

I had the problem of parking in a spot which has poles for roof support on one side [left] and another car at the other side [right] and space itself was narrow. The opposite side had the cars as well [in the parking lot] and the passage was not very wide to go to the other end and make a 90 degree turn into the space. My main problem was avoiding scratching or hitting the other car to my side. So I tended to go close to the pole and turn sharply in. I kept scratching my car against the pole. Suddenly the idea struck me.

Go past the spot and in front of the car to your side. turn in front of the car [of course, it is not possible to do 90 degree turn. If it were possible you may as well do it in front of your own spot] as much as you can and back up in front of your own slot making you turn 90 degrees in front of your own slot. Now you can go straight in. So the key idea: Turn not in front of your space but past the space in front of the next car and back up till you are perfectly aligned 90 degrees! Hope this helps someone in same situation!

[fakrudeen-something]

Top 3 places to visit in America

1. New York

It is one of the places which define America.

Statue of liberty, Wall st, Skyscrapers, Museum of Natural History, Metropolitan Museum of Art and Times Square to name few places.

2. Los Angeles

This is another place which defines America.

Disney land, Hollywood and Universal studios to name a few. It also comes with a lot of homeless!

3. San Francisco

Yet another place which uniquely defines America.

Silicon Valley, Golden Gate Bridge, Golden Gate Park and hippy places (Haight-Ashbury)  to name a few. It also has a lot of homeless showing America’s inequality in a land of tech billionaires.

[fakrudeen-something]

Top 3 English movies

1. Saving private Ryan

This movie shows the second world war in graphical detail with a strong underlying story which makes it a great movie instead of a documentary.

2. Bourne ultimatum

This movie is part of the Bourne trilogy and the best one in the series. Whole trilogy is great. This one stands out as the ultimate spy thriller with strong story and thrilling sequences.

3. 12 Angry Men

This is one of the greatest movies I watched. It has no special effects, no stunts and stands simply on the strength of its story. It shows jurers debating a black man who is accused of killing his father. One jurer who is not convinced slowly wins them over purely by logical arguments.

This is the kind of movie which elevate Cinema to more than entertainment.

[fakrudeen-something]

Binary search

Binary search is a natural algorithm to search for an element in a sorted array.

This code searches for an element in an array using binary search:

public static int binarySearch(int[] vals, int start, int length, int valueToSearch) {    if(null == vals || 0 == length) {        return -1;    }    int mid = length/2;    if(vals[start + mid] == valueToSearch) {        return start + mid;    }    if (vals[start + mid] > valueToSearch) {        return binarySearch(vals, start, mid, valueToSearch);    } else {        return binarySearch(vals, start + mid+1, length - mid -1, valueToSearch);    } }

This is a complete java program including randomized tests and computing the time taken:

package com.fakrudeen; import java.util.Arrays; import java.util.Random; import static com.fakrudeen.PeakFinder.generateRandomArray; /** * Binary search algorithm * Author: Fakrudeen Ali Ahmed * Date: 24 Aug 2017 */ public class BinarySearcher {    public static void main(String[] args) throws InterruptedException {        //int[] vals = PeakFinder.generateRandomArray(25, bound);        // 0  1  4  5  5  7  9  9  9  10  11  12  12  13  14  15  15  15  15  15  18  18  18  18  19        int[] vals = null;//PeakFinder.readArray(args);        for(int i = 0; i < 1000; ++i) {            runBinarySearch(vals);            Thread.sleep(3000);        }    }    private static void runBinarySearch(int[] vals) {        int bound = 125;        if(null == vals) {            vals = generateRandomArray(1000000, bound);        }        Arrays.sort(vals);        //System.out.println(Arrays.toString(vals));        Random random = new Random();        int valToSearch = random.nextInt(bound);        System.out.println(valToSearch);        long startTime = System.nanoTime();        int index = binarySearch(vals, 0, vals.length, valToSearch);        long duration = System.nanoTime() - startTime;        System.out.println(index);        System.out.println("micro seconds " + duration/1000.0);    }    public static int binarySearch(int[] vals, int start, int length, int valueToSearch) {        if(null == vals || 0 == length) {            return -1;        }        int mid = length/2;        if(vals[start + mid] == valueToSearch) {            return start + mid;        }        if (vals[start + mid] > valueToSearch) {            return binarySearch(vals, start, mid, valueToSearch);        } else {            return binarySearch(vals, start + mid+1, length - mid -1, valueToSearch);        }    } }

[fakrudeen-something]

Extended Euclid algorithm

Euclid algorithm  is one of the oldest algorithms known to humanity. It computes the Greatest common divisor of two integers.

Extended Euclid algorithm computes the GCD and the coefficients of the linear combination:

gcd = a M + b N, where gcd is the greatest common divisor of integers M and N.

It is for instance important in computing multiplicative inverse of numbers which is very important for instance in RSA algorithm for public key encryption which is behind all https sites.

This function computes the extended Euclid:

public static EuclidInfo computeExtendedEuclid(int m, int n) {    //sm+tn=gcd    int rprev = m;    int rcurr = n;    int sprev = 1;    int scurr = 0;    int tprev = 0;    int tcurr = 1;    while(0 != rcurr) {        int quotient = rprev / rcurr;        int temp = rprev%rcurr;        rprev = rcurr;        rcurr = temp;        temp = scurr;        scurr = sprev - scurr * quotient;        sprev = temp;        temp = tcurr;        tcurr = tprev - tcurr * quotient;        tprev = temp;    }    /*    if(sprev < 0) {        sprev += n;    }    if(tprev < 0) {        tprev += m;    }*/    return new EuclidInfo(rprev, sprev, tprev); }

This is the full java code with randomized tests:

package com.fakrudeen; import java.util.Random; /** * Extended Euclid algorithm * Author: Fakrudeen Ali Ahmed * Date: 16 Sep 2017 */ public class ExtendedEuclid {    public static void main(String[] args) throws InterruptedException {        System.out.println(computeExtendedEuclid(60, 13));        for(int i = 0; i < 1000; ++i) {            runExtendedEuclid();            Thread.sleep(3000);            System.out.println();        }    }    private static void runExtendedEuclid() {        int m = new Random().nextInt(100000);        int n = new Random().nextInt(100000);        System.out.println(m);        System.out.println(n);        System.out.println(computeExtendedEuclid(m, n));    }    public static EuclidInfo computeExtendedEuclid(int m, int n) {        //sm+tn=gcd        int rprev = m;        int rcurr = n;        int sprev = 1;        int scurr = 0;        int tprev = 0;        int tcurr = 1;        while(0 != rcurr) {            int quotient = rprev / rcurr;            int temp = rprev%rcurr;            rprev = rcurr;            rcurr = temp;            temp = scurr;            scurr = sprev - scurr * quotient;            sprev = temp;            temp = tcurr;            tcurr = tprev - tcurr * quotient;            tprev = temp;        }        /*        if(sprev < 0) {            sprev += n;        }        if(tprev < 0) {            tprev += m;        }*/        return new EuclidInfo(rprev, sprev, tprev);    }    public static class EuclidInfo {        // sm+tn=gcd(m, n)        int gcd;        int s;        int t;        public EuclidInfo(int gcd, int s, int t) {            this.gcd = gcd;            this.s = s;            this.t = t;        }        @Override        public String toString() {            return "EuclidInfo{" +                    "gcd=" + gcd +                    ", s=" + s +                    ", t=" + t +                    '}';        }    } }

[fakrudeen-something]

Edit Distance algorithm

Edit distance is a way of quantifying how similar two strings are. Edit distance allows insert, delete or replace as operations for converting one string to another with possibly differing costs for different operation and depending on the pair of characters.

This function computes edit distance assuming all costs are same and equal to 1.

public static EditDistanceInfo computeEditDistance(String string1, String string2) {    int length1 = string1.length();    int length2 = string2.length();    int[][] edit = new int[length1 +1][length2 +1];    edit[length1][length2] = 0;    for(int i = length1; i >= 0; --i) {        edit[i][length2] = length1-i;    }    for(int j = length2; j >= 0; --j) {        edit[length1][j] = length2-j;    }    //edit(i, j) = min(edit(i, j+1)+cost(insert), edit(i+1, j)+cost(delete), edit(i+1, j+1)+cost(replace)    // edit(0,0) is final edit distance    for(int i = length1 -1; i >= 0; --i) {        for(int j = length2 -1; j >= 0; --j) {            edit[i][j] = Integer.min(edit[i][j+1]+1, Integer.min(edit[i+1][j]+1, edit[i+1][j+1]+ ((string1.charAt(i) != string2.charAt(j))?1:0)));        }    }    // compute edit operations    List<Character> operations = new ArrayList<>();    if(0 == length2) {        return new EditDistanceInfo(edit[0][0], operations);    }    for(int i = 0; i < length1;) {        for(int j = 0; j < length2;) {            if(edit[i][j] == edit[i][j+1]+1) {                operations.add('i');                ++j;            } else if(edit[i][j] == edit[i+1][j]+1) {                operations.add('d');                ++i;            } else  {                if(string1.charAt(i) != string2.charAt(j)) {                    operations.add('r');                } else {                    operations.add('s');                }                ++i; ++j;            }        }    }    return new EditDistanceInfo(edit[0][0], operations); }

Here is the full working java code with randomized strings:

package com.fakrudeen; import java.util.ArrayList; import java.util.List; import java.util.Random; /** * Edit distance algorithm * Author: Fakrudeen Ali Ahmed * Date: 9 Sep 2017 */ public class EditDistance {    private static final String ALPHA = "abcdefghijklmnopqrstuvwxyz";    public static void main(String[] args) throws InterruptedException {        for(int i = 0; i < 1000; ++i) {            runComputeEditDistance();            Thread.sleep(3000);            System.out.println();        }    }    private static void runComputeEditDistance() {        //String string2 = "fakrudeen";        //String string1 = "nabeela";        String string1 = generateRandomString();        String string2 = generateRandomString();        System.out.println(string1);        System.out.println(string2);        System.out.println(computeEditDistance(string1, string2));    }    private static String generateRandomString() {        Random random1 = new Random();        Random random2 = new Random();        StringBuilder builder = new StringBuilder();        for(int i = 0; i < random1.nextInt(25);++i) {            builder.append(ALPHA.charAt(random2.nextInt(ALPHA.length())));        }        return builder.toString();    }    public static EditDistanceInfo computeEditDistance(String string1, String string2) {        int length1 = string1.length();        int length2 = string2.length();        int[][] edit = new int[length1 +1][length2 +1];        edit[length1][length2] = 0;        for(int i = length1; i >= 0; --i) {            edit[i][length2] = length1-i;        }        for(int j = length2; j >= 0; --j) {            edit[length1][j] = length2-j;        }        //edit(i, j) = min(edit(i, j+1)+cost(insert), edit(i+1, j)+cost(delete), edit(i+1, j+1)+cost(replace)        // edit(0,0) is final edit distance        for(int i = length1 -1; i >= 0; --i) {            for(int j = length2 -1; j >= 0; --j) {                edit[i][j] = Integer.min(edit[i][j+1]+1, Integer.min(edit[i+1][j]+1, edit[i+1][j+1]+ ((string1.charAt(i) != string2.charAt(j))?1:0)));            }        }        // compute edit operations        List<Character> operations = new ArrayList<>();        if(0 == length2) {            return new EditDistanceInfo(edit[0][0], operations);        }        for(int i = 0; i < length1;) {            for(int j = 0; j < length2;) {                if(edit[i][j] == edit[i][j+1]+1) {                    operations.add('i');                    ++j;                } else if(edit[i][j] == edit[i+1][j]+1) {                    operations.add('d');                    ++i;                } else  {                    if(string1.charAt(i) != string2.charAt(j)) {                        operations.add('r');                    } else {                        operations.add('s');                    }                    ++i; ++j;                }            }        }        return new EditDistanceInfo(edit[0][0], operations);    }    public static class EditDistanceInfo {        int distance;        List<Character> operations;        public EditDistanceInfo(int distance, List<Character> operations) {            this.distance = distance;            this.operations = operations;        }        @Override        public String toString() {            return "EditDistanceInfo{" +                    "distance=" + distance +                    ", operations=" + operations +                    '}';        }    } }

[fakrudeen-something]

Knapsack algorithm

Knapsack problem solves the maximum value you can pack while keeping the weight of the items under some maximum weight W.

A solution to this is as follows:

public static KnapsackInfo computeKnapSack(int[] weights, int[] values, int max) {    //knapsack array    int[][] k = new int[weights.length+1][max+1];    for(int i = 0; i <= max;++i) {        k[0][i] = 0;    }    // k[i, m] = max(k[i-1, m], k[i-1, m-weights[i-1]]+values[i-1])    for(int i = 1; i <= weights.length; ++i) {        for(int currentWeight = 0; currentWeight <=max;++currentWeight) {            if(weights[i-1] > currentWeight) {                k[i][currentWeight] = k[i-1][currentWeight];            } else {                k[i][currentWeight] = Integer.max(k[i - 1][currentWeight], k[i-1][currentWeight-weights[i-1]]+values[i-1]);            }        }    }    //compute included elements    boolean[] included = new boolean[weights.length];    for(int i = 0; i < included.length; ++i) {        included[i] = false;    }    for(int i = weights.length-1,currentWeight = max;i >= 0 && currentWeight > 0;--i) {        if(k[i+1][currentWeight] != k[i][currentWeight]) {            included[i] = true;            currentWeight -= weights[i];        }    }    return new KnapsackInfo(k[weights.length][max], included); }

And full working solution in java including randomized tests:

package com.fakrudeen; import java.util.Arrays; import java.util.Random; /** * Knapsack algorithm * Author: Fakrudeen Ali Ahmed * Date: 6 Sep 2017 */ public class Knapsack {    public static void main(String[] args) throws InterruptedException {        for(int i = 0; i < 1000; ++i) {            runKnapSack();            Thread.sleep(3000);            System.out.println();        }    }    private static void runKnapSack() {        int length = 10;        int bound = 1000;        int[] weights = generateRandomArray(length, bound);        int[] values =  generateRandomArray(length, 10*bound);        System.out.println(Arrays.toString(weights));        System.out.println(Arrays.toString(values));        int max = new Random().nextInt((length/2)*bound);        System.out.println(max);        System.out.println(computeKnapSack(weights, values, max));    }    public static KnapsackInfo computeKnapSack(int[] weights, int[] values, int max) {        //knapsack array        int[][] k = new int[weights.length+1][max+1];        for(int i = 0; i <= max;++i) {            k[0][i] = 0;        }        // k[i, m] = max(k[i-1, m], k[i-1, m-weights[i-1]]+values[i-1])        for(int i = 1; i <= weights.length; ++i) {            for(int currentWeight = 0; currentWeight <=max;++currentWeight) {                if(weights[i-1] > currentWeight) {                    k[i][currentWeight] = k[i-1][currentWeight];                } else {                    k[i][currentWeight] = Integer.max(k[i - 1][currentWeight], k[i-1][currentWeight-weights[i-1]]+values[i-1]);                }            }        }        //compute included elements        boolean[] included = new boolean[weights.length];        for(int i = 0; i < included.length; ++i) {            included[i] = false;        }        for(int i = weights.length-1,currentWeight = max;i >= 0 && currentWeight > 0;--i) {            if(k[i+1][currentWeight] != k[i][currentWeight]) {                included[i] = true;                currentWeight -= weights[i];            }        }        return new KnapsackInfo(k[weights.length][max], included);    } public static int[] generateRandomArray(int length, int bound) {     int[] vals = new int[length];     Random random = new Random();     for(int i = 0; i < length; ++i) {         vals[i] = random.nextInt(bound);     }     return vals; }    public static class KnapsackInfo {        int maxValue;        boolean[] included;        public KnapsackInfo(int maxValue, boolean[] included) {            this.maxValue = maxValue;            this.included = included;        }        @Override        public String toString() {            return "KnapsackInfo{" +                    "maxValue=" + maxValue +                    ", included=" + Arrays.toString(included) +                    '}';        }    } }

[fakrudeen-something]

My current courses

I am currently watching two courses:

1. Gravity

This course also explains Manifolds, Tensors and so on.

2. Probability Excellent course on probability and random variables.

[fakrudeen-something]

Top 10 books

Selfish Gene by Richard Dawkins

Great book - Richard dawkins explaining gene’s eye view of evolution truly explaining why we are survival machines of genes. It completely changed my view of life and finally freed me away from all religious non-sense.

Blind watchmaker by Richard Dawkins

Another great book by Dawkins explaining how evolution can build the complex organs like eye or flying.

Brief history of time by Stephen Hawking

Book explaining big bang and evolution of time.

Origin of the species by Charles Darwin

Hope no need for an explanation here!

Road to reality by Roger Penrose

Great book explaining all the known physics so far. Hard read but worth it.

Packing for Mars by Mary Roach

Very funny and entertaining book explaining the science of space travel.

Naked Economics by Charles Wheelan

Excellent book explaining economic fundamentals for layman.

Collapse by Jared Diamond

Excellent book about collapse of human societies and the reasons behind them. Particularly the description of Montana is lovely.

Blank Slate by Steven Pinker

Book on human mind explaining why it is an organ pre-wired in a specific way for specific purpose and not a blank slate on which anything can be written.

God Delusion by Richard Dawkins

Hard hitting book by the master debunking all the religious non-sense

[fakrudeen-something]

Babai’s Graph isomorphism result for layman

University of Chicago professor  Laszlo Babai announced in last November that Graph isomorphism is ‘almost’ in P.

Whether P = NP is one of the hardest unsolved problems in Computer science with great practical importance.

Babai’s result proves that one of the problems generally though to be NP-complete [hardest problems in NP] is actually not so hard [in this sense it is similar to PRIMES in P - checking for primality can be done in polynomial time but PRIMES in P is actually a stronger result as it has no ‘almost’].

Note that it doesn’t do much to solve the P=? NP debate itself. It only means we used to have a wrong intuition about a particular problem just as in the case of PRIMES.

Prof. Babai proves that Graph isomorphism is ‘almost’ in P. That is it is quasi-polynomial, 2^((logn)^c) for c > 1

c=1 means it is in P.

I have a feeling someone will shortly prove that it is in P. It is only a matter of time. 

image courtesy: http://www.sciencemag.org

Graph isomorphism means given two graphs they are different arrangements of ‘same’ graph - i.e. it has same vertices connected the same way.

[fakrudeen-something]

Euclid’s parallel axiom and human stupidity

Great mathematician of 2000 years ago, Euclid wrote a classic mathematical text called Elements.

As is typical for mathematics, he listed some axioms and decided to prove many interesting theorems like pythogores theorem or algorithm for GCD.

One of Euclid’s axiom was called parallel postulate or parallel axiom and it said:

Given a line and a point not on the line there is exactly one line parallel to the first line and passing through the given point.

It looks very uncontroversial, right?

But many mathematicians of later centuries were uncomfortable with it for a reason. This additional postulate looks superfluous and they thought it could be derived from Euclid’s other simpler axioms. Many mathematicians spent years trying to ‘prove’ this from other axioms.

The problem was unsolved for many many years and mathematicians kept working on it for years.

Then one day someone [well at least 3 including Gauss] came up  with a geometry where all the other Euclid’s axioms are true but parallel postulate is false! This means this postulate is logically independent of others. These are called hyperbolic geometry, elliptic geometry and so on.

The interesting question is why didn’t anyone think of such a simple idea as constructing a different geometry with other axioms for 2000 years?

Our strong beliefs/biases affect our judgement heavily despite our best intentions and the price we pay for it is sometime high!

All those years mathematicians were trapped in to Euclidean geometry they couldn’t even think of anything else. They simply couldn’t think of postulate being false at all.

I think there is a large lesson here for humanity. Don’t respect tradition and authority way too much?