HW8. Graphs (28 October, 23.59)
EX1. (1p) Word-word graph - basics
Let’s use words of length 5. These are vertices in the graph. There shall be an edge if the two words differ in one character position only.
Words: https://drive.google.com/drive/folders/1K-__ajBGyy3ltONfwJnBTjjSMN6bVREJ
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.
- Calculate or estimate the diameter of the (largest) connected component.
EX2. (1p) Weighted word-word graph. We’ll use the same word-word graph but add weights (2 x #differences - 1).
Calculate the shortest distances between two (random or distant) words. \\
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 only one letter at any time only? Maybe the 1-letter changes were not even possible and 2-3 letter change was necessary? Note that changing 2 letters yields a cost of 3 and 3 letter change costs 5. While a single-letter change would be one every time.
Find some interesting tasks (word game puzzle) 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
Look at the examples of graphs constructed from images and the provided code.
Images: https://drive.google.com/drive/folders/1Hi7UY4I9qgOdoHS18Z71ioaKdgOXdTJ8
Code: https://colab.research.google.com/drive/18tebLlWm7z6x9NzoX7-9cDugMV_dSD-K
Nodes are selected pixels on the image by a RxC grid (can be dense or sparse representation). With that, every graph node has a precise location on the 2D plane, allowing to overlay the graph over the photo. You can choose the images from the folder provided, create your own image (AI), google image search, or pick some from your own photo library. Pick something that allows you to make the point on the spanning tree or path-finding algorithms.
Visualise on these images the trees - BFS, DFS, Random order. (BFS is provided)
Visualise the Dijkstra shortest path tree. And the A* algorithm for the shortest path (code is there).
Play with inputs; modify the weighted distance function - speed per pixel = f( RGB color) - calculate_edge_weights() ; DIstance = distance (# pixels/ speed). E.g. make speed higher for Red or Green pixels; make speed dependent on the difference from some specific color.
Pick two different images where two different distances/weights/speeds are calculated for edges, that yield nice visualizations (you can change everything!). E.g. “prefer the paths that follow a similar color”, prefer “red” paths, prefer “dark” paths or “light” paths.
In the report include the source image and the illustrations that you obtain. Comment, what can be observed from the representations and why.
EX4. (1p) Make an explicit Dijkstra/A*/priority queue based implementation. All these would follow the same logic of selecting from the priority queue the most promising nodes to be opened next. Dijkstra fetches the closest to source; A* the closest by distance from source + estimate to the target. You can propose some other heuristic, e.g. prioritize certain color (or function on the color) first or “speed” (speed to reach previous node+speed to extend it). E.g. follow primarily the white paths (e.g. on the city maps).
Visualize the search front after some select stages (e.g. every 20% of nodes traversed).
You can play with random source and target (like in task 3) or fix the points manually in code to make comparisons easier.
EX5. (1p) Calculate the Minimum Spanning tree. Make an explicit implementation of the chosen MST algorithm (Prim, Kruskal, Boruvka, …). Visualize the same images and distance measures as from the EX4.
EX6. (Bonus 1p) Choose an article for an Essay, and provide reasoning, why you preferred that choice. Make a schedule for the reading and writing the summary of the paper.
https://courses.cs.ut.ee/2024/algorithmics/fall/Main/Essays -> and \\
https://drive.google.com/drive/u/1/folders/1x-LWavGuxZWwCJWXy9E0dvBViq70KBfy