Exam tasks for Algorithmics course 2023/24 Fall Period: From Write on the report 1) your full name and study book number, a 2) statement, that you completed the exam on

your own and cited/reported all materials that you consulted and used in your solutions. Keep track of time spent and report 3) the used hours for each task. Submission: via courses.cs.ut.ee - the PDF and code (zip, tar, gz, ...) Rules Exam is personal, no collaborations or discussions are allowed with any other people - students, parents, colleagues, etc. But you can use Internet and Al assistants! However, you must describe which resources and assistants you have used. You may get half of the points by properly describing theoretically working solutions even if you do not implement them. But you may not know if they would work without trying out, hence you might lose points. Describe concisely (briefly and sufficiently) how you went about solving the tasks; and high-level description of practical implementation and experimentation. Minimum no of points to pass the exam is 20. Exam was supposed to give up to 40 points. It is your choice to see how many you need or want to achieve. Hint: There is no need to complete all programming tasks to perfection. Think carefully through and choose wisely. Same algorithm may or may not work on all test cases (describe if and why this may happen). Focus on the most obvious solutions and essential things first to get a baseline working for each task. Later you can improve, add layers of perfection. Goal is to demonstrate independent thinking. No need to optimize for maximal speed. Measure code execution times but do not worry about whether you have achieved a new world record, fitting in overnight and exam time frame is more important than saving 10% time off the fast solution. Shorter code is preferred over the complex solutions. Keep descriptions of your solutions of each task to 1-2 pages of textual explanations, pseudocode, discussion and main illustrations. Statistics. tables and (e.g. reconstructed images, etc) may perhaps add additional 3-4 pages. Ideally, the entire exam report should not exceed 10-12 pages. Upload also the code. A link to download all relevant questions and task data from https://drive.google.com/drive/folders/1NViHx_zsgvkGvZ9txOgtaXWBRQFm_08V Please, first read through all tasks and fill in the preliminary form to share your first thoughts. https://forms.gle/u4jtYm767AUDXUs1A This may help give guidance to all, if needed. T1 (15p): Image reconstruction from scrambled versions. We have shuffled rows and/or columns of original images. The scripts of generating them and the directories with data for your exam tasks are provided. Every image has its own folder. https://drive.google.com/drive/folders/1XegE0bVWV35pr3VxGmiJWH1_nPjZEuye Input data consists of PNG images shuffled in different ways. They can be by rows; or by columns; or by both; also grayscale or coloured. Sometimes color channels are even mixed making it more challenging to reconstruct also RGB values¹. Hint: probably each color channel correlates better with its own color channel, rather than other colors. 3color refers to a situation where 3 RGB values are kept next to each other even when columns are reorganized. Start from simpler examples or tasks first; gradually build up more complex solutions for more challenging examples. Discuss what may need to be done differently in each case. The small examples - 3 colors creating different shades in 16x16 image; and the illustration of A are there to serve as small examples that were generated by the same scripts. In making the scripts ChatGPT has been helpful. But they are not optimized or commented much. Only the PNG versions are left as main input. The scripts have tons of examples of how to read in the image and process them to get RGB valued matrices, converted into different channels, BW, etc. There is also a principal component analysis (PCA) script. Some images could be easier, some harder to reconstruct. Explain why. Techniques to try: sorting by some criteria, nearest neighbor search; or maybe TSP optimisation; There is also a PCA plotting code, you should see the structure in there as well. 1 Mixing up all RGB channels independently across the entire image may turn out to be too challenging. You may try but it could also fail. Treat this as an interesting bonus curiosity question to be discussed theoretically, how to approach it and why it may possibly fail. -> <- ??? T2 (15p): Find similar patterns on the images The inputs for this task are in this folder: https://drive.google.com/drive/folders/1x8Syehq1MCgi4dFD-vHWbXTBpiLlou86 Basic task: Find similar structures and shapes - lines or areas in images. Select a specific or arbitrary random line within an image, find similar sequences within the same image or other images. Nearby original image the similarity is likely the highest. Expand and try to find similarities in different regions or other images. Explain your thought process and give examples. You will most likely benefit from dynamic time warping. But you can also start with simpler edit distance like measures (use numeric differences instead of equal or not). Inputs - images of sand dunes and pyramids from DALLE. Some of them scaled to much smaller shapes, see how to match thumbnail to larger original image. Work with pyramids "horizontally". Take a line through all pyramids and find similar lines in the original image and other thumbnails. Can you find "most of the pyramid" by just starting from one line? Report the distribution of the distance measure found values (density plot) and visualize the most similar lines as a result to query. Original:. Smaller versions with few rows only - identify same rows from above image. From those "thumbnail” size images you should be able to extract some individual rows spanning all three pyramids and match those to the top full-scale image. Report some 20-50 closest lines at least. You can also revisit the reconstructed images from the first task, if those provide alternative good examples for your methods. Especially the various structured examples like chess boards. If you generate other test images that turn out to be more interesting, surprising, and useful, please feel free to add in the report. We will value creativity, novelty and ideas over yes/no answers. Provide sufficient illustrations to make your point(s). The second example set is more complex - with several different generated images of sand dunes. Try to find similar shapes or regions across the provided images. The similarity may not need to be across the entire image but be more local, yet spanning large enough areas and of possibly different sizes.