HW9. Graphs, choosing essays (5th of Nov, 23.59)
EX1. Developing reading and writing skills are essential part of the course. The idea is to read at least one paper and write a 2-page essay/summary about that paper aiming at describing that content to your fellow coursemates. We have selected 11 papers for you to choose from. Your first task is to choose a paper that you will write an essay about. First, skim all them through (do it quickly). Write in the report which article you are choosing. Attempt to summarise in few sentences why you think it will be the most interesting article for you to choose. Note, that you may still change the article later, if you wish - but usually, it is better to stick to the choice.
The guidelines and articles can be found via https://courses.cs.ut.ee/2018/algorithmics/fall/Main/Essays and PDF-s downloadable via https://drive.google.com/drive/folders/1mxzFfIgdb9fMlZ_hbbbXEddfBWqx0_F-
Note, that your first submission will be read by two co-students who will give a feedback about your writing. Based on that feedback you should improve your essay and submit a final version for grading. Giving a constructive feedback to other students that will help them improve their writing shall be also an important skill. You can find the essay timeline on the HW page.
EX2. Recall graphs that you had analyzed from the last week’s HW8. Implement a BFS algorithm for the very same graphs (considering graphs unweighted, undirected).
- Measure or estimate time for 1000 BFS searches from random start vertices; reporting also the "depth of the component" starting from different vertices.
- Estimate the diameter of the graphs (based on 1000 searches). Draw the distribution of lengths of longest shortest paths you encountered.
Hint: if it takes too much time to run 1000 searches opt for less, but explain the reason.
EX3. When doing the BFS in the previous exercise, also test for the bipartiteness of the graph. Most of them aren't clearly. For those that are not bipartite - report how quickly do you detect that based on BFS, e.g. for X2 searches it was already when going to "2 hop" neighbourhood when you discovered it; for X3 searches within 3 hops, etc…
EX4. Use directed graph below - the direction is indicated by blue dot at the target of the edge. For this graph calculate the strongly connected components and the topological sort order of the components. Always apply the lexicographic ordering (in outer cycle generating a DFS forest; as well as selecting edges for expansion).
Visualisation hint: above graph has been rendered using SWOG language and server http://biit.cs.ut.ee/swog with the following "SWOG code" that can be uploaded on that server. That SWOG code can be modified if you want to automate the illustration of the search. E.g. to make a darker black line between nodes A and P, you can append "connect A.r P.r" to the end of file. As well as override the red text values as appropriate text, e.g. d[u] and f[u] times, next to each vertex. However, feel free to draw or render using any other visualisation schemes.
EX5. Use graph from the lecture - below. From this graph create and visualise a corresponding line graph. Formulate the Euler and Hamilton path tasks on original graph and line graph. How do these relate to the Euler and Hamilton paths in the original graph? Note, there is no need to find actual Euler and Hamilton paths, just formulate corresponding problems and compare the formulations.
EX6 (Bonus 2p). Scan the article you have chosen in EX1. If you try to read the article from start to finish by googling all unknown words, you can easily get stuck in the infinite depth of wikipedia articles. Instead, try to identify main points. Briefly look at each section and try to figure out:
- What is the research question and the reason for the study (usually stated in the Introduction)
- The hypothesis or hypotheses tested (Introduction)
- How these hypotheses were tested (Methods)
- What are the main findings (look for Results section, including tables and figures)
- How the findings were interpreted (Discussion)
In your report try to briefly (in a few sentences) summarise each of these points and be ready to present them during the practice session.