HW8. Graphs (27 October, 23.59)
EX1. (1p) Word-word graph - basics
Let’s use words of length 5 as vertices in the graph. There shall be an edge iff the two words differ in one character position only.
Words: https://drive.google.com/drive/folders/1K-__ajBGyy3ltONfwJnBTjjSMN6bVREJ
Test and characterise each of the three files.
Code to start from:
https://colab.research.google.com/drive/1sOY44Mymxjzb1gnDOiHcM1WEmXAlLD-O#scrollTo=CiGxyzGdBd8q
Do you get a connected graph? If not, how many components?
Characterize the largest component(s).
- Perform depth first search. What is the longest branch you can find using DFS? What is the width of that DFS tree?
- Perform a breadth-first search - same questions as for DFS.
- Find the path between 'sport' and 'spice'
EX2. (1p) Weighted word-word graph. We’ll use the same word-word graph but add weights ( 0.8 x #differences + 0.5).
Calculate the shortest distances between two (random or distant) words. \\
Provide examples in your report.
Think of it as a word game on how to convert a word in the smallest nr of operations into another one.
Can you find any example, where the more costly 2 or 3-letter changes would be cheaper than a path of changing one letter at any time only? Maybe the 1-letter changes were not even possible and 2-3 letter change was necessary? With the proposed scheme, the cost for 1 letter change is 1.3, 2 letters 2.1 and 3 letters 2.9, thus it might be more beneficial to go for larger changes in a single step.
Find some interesting word game tasks that you could give out during a party to other people. E.g. change “shore -> skirt” with only a few steps (3), changing exactly one letter at a time! Solve that puzzle yourself as well.
EX3. (1p) Graph data from image. Basic algorithms
We will now use an image as the basis for making a graph. Use this input image input_image_2.png :
We will overlay a random grid (graph) over this image. Selected positions are nodes, and there shall be connections to nearby other nodes.
There are three shortest paths: smallest nr of "hops", shortest path where weights are random, and by "speed" that is defined using pixel colors on each edge:
Last, there is a BFS tree overlayed:
In this task:
- Make sure to get it running (use the above input_image_2.png as input file to the Colab script): https://colab.research.google.com/drive/1NpsTAOjLr-0TqgaURij3a7pW9xHOrzO5#scrollTo=NYX1c6rgwxl9
- Describe, how the graph was obtained (node sampling (Poisson-disk), neighbor rule (graph construction), etc), also experiment with A, B, C options/modes.
- Describe how the distance was calculated for color based method.
- Coding: modify the BFS tree by writing an explicit version of a Dijkstra all sortest paths tree using the color based weight method
- Coding - Experiment with distances: Play even more with the distance/weight - to avoid dark areas, avoid blue and green areas, and to prefer the light pagths and gray streets as much as possible. Describe the proposed distance measure/weight calculation and provide a visual proof (images) - both for the shortest path (currently three paths using that distance), as well as the Dijkstra single-source shortest paths.
EX4. (1p) Make an explicit A* implementation. Use the same example and your best distance measure-based weights. Visualise both the shortest path found, but also the search tree that was needed to run the A* method (e.g. yellow tree, but dark blue shortest path).
EX5. (1p) Calculate the Minimum Spanning tree. Make an explicit implementation of the chosen MST algorithm (Prim, Kruskal, Boruvka, …). Visualise the same images and distance measures as from the EX3 and EX4.
EX6. (Bonus 2p)** Study the A* method in more details (your EX4). Vary distancew measures (e.g. the simple Euclidean distance vs the "speed" based time from EX3,4. Study also cases when start node is not "leftmost" but somewhere more in the middle. Identify first, when does A* seem to waste time by exploring too large an area? (Fix the random nr generator seed for easier experimentation when you fix "bad examples"). Include the bad example(s) in the report and state, what seems to be an issue. (Clearly demonstrating a case when there might be good basis for improvement, should earn you 1p).
Now try to improve it: What would be needed to narrow down the "wasted search space"? Experiment with some ideas - describe the idea and run an experiment to validate if you can narrow don the search space. E.g. try to run an optimistic path first; or precalculate some index first (to be used by many searches later). Demonstrate an improvement. Only worry/concern about the explored area, not the speed of the method. (1p)
EX7. (Bonus 1p) Choose an article for an Essay from the provided list, and provide reasoning, why you preferred that choice.
- For double-blind review your first submission shopuld not reveal your name, we will use either the courses-based pseudonyms or some other random ID-s. These guidelines will be shared later.
- Make a schedule for the reading the article and writing the summary. Moreover, you need to make a schedule to prepare slides (Microsoft PowerPoint, latex beamer, etc) for the presentation about the paper.
- Guidelines for writing a review to another person (we will set up a double-blind review).