HW9. Search heuristics (November 11, 23:59)
EX1 (1p). Study the provided example graphs:
https://colab.research.google.com/drive/1WejPCLbKmxoFYHPBpTLc-qLTYFY9Zwr5#scrollTo=9z6jmTmv7krs
What is being calculated, how, which graphs are more interesting, and why? Which parameters describe the graphs the best in your opinion?
Add some characterization model - which? What does it add?
EX2 (1p). Study one of the chosen random graph generation models - describe what it does, why, and how the model parameters affect it. Use the simulator to generate (many) data sets using that model; and analyze them.
Vary the size, e.g. 10, 50, 100, 500, 1000, possibly more; as well as the other parameters.
Describe what happens to the graph? Can you “break” anything, can you identify which parameters describe the graphs the best?
EX3 (1p). Create an example graph data yourself. Either synthesize it from some real data as the (remember the word or image examples?) or create a totally randomized generator that creates an interesting (educational) graph (directed or undirected) randomly
Describe the chosen approach and the data set. Attempt to create a visually understandable and hopefully appealing graph, where the information on clusters and for example the PageRank becomes visually easy to understand (e.g. to be included in teaching materials).
Characterize the generated graph.
EX4 (1p). Let’s study the greedy set cover algorithm.
Code: https://colab.research.google.com/drive/1WcxfB0ZqEl_rSD-M98nouufG1j7R7o7m
Feel free to use all code from there.
Provide an analysis on “how frequently the greedy is worse than optimal”.
Create some instance of the set cover problem, where the Greedy is performing really poorly.
EX5 (1p). Continue on data generation for the set cover task - either randomly or from some data sets. Poke with that data both the greedy as well as optimal set cover algorithms. Can you identify the limits, when the optimal solution starts to be infeasible? How large data could be still analysed with no big problems using the greedy solution?
EX6 (Bonus 2p). There is a 3x3 puzzle - see the nine-card puzzle (look up the nine-card puzzle from App Store, Play Store). (We have also the physical card games/fridge magnets.)
Goal is to solve the puzzle so that all 9 cards fit together properly. There is exactly one solution (with 4 rotations). The solution can be done by a backtracking search.
First, we want to simply encode each card by what object and what part is on the card. We’ll use 2 letters: 1) the type of object (e.g. R for Red, G for green, P for Pink, etc) and 2) “which end” (L for Lighter, D for Darker) or (T for Top and B for Bottom). We can encode each card by four such codes clockwise. For example, the following codes [ BB, PT, RT, YT ] could represent the balloons of the card starting from top:
Another type of cards with colors and darkness could be represented as [BD, BL, GL, RL]. 
Here is one example coding (game with beans, not the above examples):
(number of) Beans color+length (Long, Short)
str = "GS GL WS RS, BS RL WL RS, WS BL RS GL, RL GS BS WL, WL GS RS BS, WL GS RL BL, BL WL BS GL, GL WL BS RS, BL RL WS GS"
You can split this string at ‘,’ and further, at space to get a short 4-string list to represent ea ch card. In addition, you need a rotation (0,1,2,3).
Your task is to find a placement of 3x3 cards, so that they fit with their partners. The cards could be laid from top row left to right. At every step the new card should match the card on the left (if it has left neighbor) and card on top (if it has a top neighbor).
We will systematically try all placements. The cards on “table” have been placed in specific order. All free cards are in waiting list. From them pick a candidate for next. And try all 4 rotations. If it fits (same object, but different end of the same object), move that card to the “table” (candidate solution). Next, you have one card less to choose from. Repeat the process recursively until you manage to fit the last, ninth card. Then report the placement on the table. It is a backtracking search.
EX7 (Bonus 1p). Create 4x4 puzzle(s). And 5x5 puzzle(s). How does the nr of elements and hardness of a solution compare? (If an element is only once, there is a single opportunity… - how many are desired for 4x4 and 5x5?)