[[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B201/public/html/predmety/46/85/p4685106.html|Timetable at FEE]] [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B201/public/html/paralelky/P46/85/par4685106.1.html|Students of ePAL]] [[https://cw.felk.cvut.cz/brute/|Upload system BRUTE]] [[https://cw.felk.cvut.cz/forum/forum-1682.html|Discussion board]] ---- ==== Practices ==== Problem sets with comments/solutions * 1. Asymptotic complexity (in preparation) * 2. Minimum spanning trees (in preparation) * 3. Directed graphs {{ :courses:be4m33pal:directed_gr_sol.pdf | with comments/solutions }} (Consultations 2) * 4. Heaps {{ :courses:be4m33pal:heaps_sol.pdf | with comments/solutions }} (Consultations 2) * 5. Isomorphism {{ :courses:be4m33pal:isomorphism_sol.pdf | with comments/solutions }} (Consultations 1) * 6. Combinatorial generation {{ :courses:be4m33pal:combinatorial_sol.pdf | with comments/solutions }} (Consultations 1) * 7. Finite automata and text search I {{ :courses:be4m33pal:automata1_sol.pdf | with comments/solutions }} * 8. Finite automata and text search II {{ :courses:be4m33pal:automata2_sol.pdf | with comments/solutions }} * 9. Finite automata and text search III {{ :courses:be4m33pal:automata3_sol.pdf | with comments/solutions }} Extra online consultations will be organized during semester weeks 10. - 14. to discuss presented solutions in problem set 1.-8. ==== Online consultations ==== **Consultation 1** Consultation date: **Tue 24.11., 16:15-17:45** The discussed topics of the consultation were topics 5. and 6. - Isomorphism and Combinatorial generation (see the documents above), those correspond to lectures 5. and 6. **Consultation 2** The discussed topics of the consultation will be topics 3. and 4. - Directed graphs and Heaps (see the documents above), those correspond to lectures 3. and 4. **Your course of action:** **1.** Note the consultation date: **Mon 30.11., 11:00-12:30** **2.** Check the solutions/comments of the given topics 3. and 4. above. Mark the solutions which, in your opinion, need more explanation or corrections and which you would like to understand better. **3.** Go to the poll [[https://forms.gle/jXrSikRZbcV5QUVS8|Advanced Algorithms Consultation 2]] and tick the boxes at the corresponding problems from topics 3. and 4. above, where you demand more explanation.\\ Complete this step before 10:00 PM Sunday 29.11. \\ The consultations will discuss primarily the problems in the highest demand. ---- ==== The Basics ==== **Introduction and repetitions**\\ * Asymptotic complexity recap. Training problems {{:courses:ae4m33pal:seminars:semComplexityNoSol.pdf| are here}}. Another set {{ :courses:b4m33pal:cv01_2019.pdf | in Czech}}. * Graphs and their representations, BFS, DFS. Solve {{:courses:ae4m33pal:seminars:cv01e.docx| example exam problems}}. Additional training problems {{:courses:ae4m33pal:seminars:2012cvGraphs.pdf| can be found here.}} * For more thorough or necessary basic acquaintance with the related topics consult the book **[[https://home.cse.ust.hk/~dekai/271/notes/L01a/poa.pdf| Problems on Algorithms]]**. Student are expected to be able to solve any problem marked by one cap in chapters 2. and 3. both during the semester and at the exam. We recommend problems 64. - 66., 144. - 148., 163. - 170. as an easy start. **Upload system**\\ * An introduction to Upload system, 0-th programming optional (not graded) task, its specification can be found [[http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=fence|here]].\\ Write a program that solves the task. Upload it and check how the system asseses it. Follow strictly the rules specified on page [[courses:be4m33pal:seminars:upload_system|Upload System.]]\\ **Training homework problem**\\ * The solution and submission is not mandatory and it is not graded if submitted. The problem itself is extremely simple, you can utilize it is to get acquainted with the. [[courses:be4m33pal:seminars:upload_system|Upload System BRUTE.]] \\ Training problem: [[https://cw.felk.cvut.cz/brute/data/ae/release/2020z_b4m33pal/pal2020/evaluation/input.php?task=fence|Problem statement and public data]] ---- === 1st week === * Spanning trees and minimum spanning trees of graphs: {{:courses:ae4m33pal:seminars:kostrye.doc| example problems}}. More problems for training {{:courses:ae4m33pal:seminars:2012cvSTree.pdf| here.}} **First homework problem**\\ [[https://cw.felk.cvut.cz/brute/data/ae/release/2020z_b4m33pal/pal2020/evaluation/input.php?task=laserhighways|Laser Highways]] **Exam topics**\\ * Asymptotic notations, asymptotic complexity, graph representations. * Boruvka's, Kruskal's, Prim's algorithms. Their implementation and data structures, ie. priority queues and Union-Find. * Prim's algorithm without a queue. * Union-Find implementations. ---- === 2nd week === **Note:**\\ Supplementary problems for missing online practices are available: {{ :courses:be4m33pal:practices02eextra.pdf | in pdf }}.\\ Solve problems 1-5 and one of problems 6-10 according to your choice. Send a photo of your solutions by 6.10., to berezovs@fel.cvut.cz with cc to varhaiho@fel.cvut.cz. **Additional**:\\ Problems for personal training: Directed graphs, strongly connected components, Eulerian graphs:\\ {{ :courses:be4m33pal:cvorigfye0.pdf |set 1}}, {{:courses:ae4m33pal:seminars:2012cvoriggfynosol.pdf| set 2}}. **Exam topics**\\ * Eulerian graph (directed and undirected), Eulerian path/cycle, method of finding them. * Strong and weak connectivity, strong and weak components, graph condensation. Algorithms which find strong components or produce a condensation. * Topological ordering of a graph using DFS or using gradual roots/leaves removal. ---- === 3rd week === * Binary, d-ary, binomial heaps. Fibonacci heaps. {{:courses:ae4m33pal:seminars:haldye.docx| Example problems}}. * Additional problems for training {{:courses:ae4m33pal:seminars:2012cvheapsnosol.pdf| here}} **Exam topics**\\ * The heap rule. Standard operations on heaps. Binary, d-ary and binomial heap. * Binary and d-ary heap implemented in an array. * Fibonacci heap, amortized complexity of its operations. ---- === 4th week === * Graph and tree isomorphism. {{:courses:ae4m33pal:seminars:cvisoe.doc| Example problems}}. * Additional problems for training {{:courses:ae4m33pal:seminars:2012cvgraphisonosol.pdf| here}} \\ **Exam topics**\\ * Graph isomorphism, definition, invariants, algorithm for finding all isomorphisms. * Isomorphism and certificates of undirected trees, computing the certificate for a tree and reconstructing a tree from a certificate. ----- === 5th week === * Combinatorial generation of subsets, permutations and their ranks. {{:courses:ae4m33pal:seminars:kombi1e.docx| Example problems}}. * Additional problems for training {{:courses:ae4m33pal:seminars:2012cvcombialgnosol.pdf|here}} \\ **Kreher, Stinson: Combinatorial Algorithms, notes:**\\ * {{:courses:ae4m33pal:seminars:kresti30.pdf| page 30, 31}} * {{:courses:ae4m33pal:seminars:kresti32.pdf| page 32, 33}} * {{:courses:ae4m33pal:seminars:kresti34.pdf| page 34, 35}} * {{:courses:ae4m33pal:seminars:kresti36.pdf| page 36, 37}} * {{:courses:ae4m33pal:seminars:kresti38.pdf| page 38, 39}} * {{:courses:ae4m33pal:seminars:kresti40.pdf| page 40, 41}} * {{:courses:ae4m33pal:seminars:kresti42.pdf| page 42, 43}} * {{:courses:ae4m33pal:seminars:kresti44.pdf| page 44, 45}} * {{:courses:ae4m33pal:seminars:kresti52.pdf| page 52, 53}} * {{:courses:ae4m33pal:seminars:kresti54.pdf| page 54, 55}} * {{:courses:ae4m33pal:seminars:kresti56.pdf| page 56, 67}} **Exam topics**\\ * Combinations, variations, permutations with or without repetition, definitions, formulas. Binomial coefficients, their basic relations, Pascal triangle. * Operations(functions) Rank and UnRank for ordered permutations and k-element subsets of given set. * Gray code - definition, properties, operations Rank and UnRank. ---- === 6th week === * Finite automata and regular expressions. {{:courses:ae4m33pal:seminars:ata1e.docx| Example problems}}. * Additional problems for training {{:courses:ae4m33pal:seminars:2012cvfautomatanosol.pdf| here}}\\ **Exam topics**\\ * Deterministic and non-deterministic finite automaton (DFA and NFA), definition. Languages accepted by finite automata. * Algorithm for transforming NFA to DFA, simulation of NFA work without transformation to DFA. Epsilon-transitions and their removal from an automaton. * Regular expressions. Definition, algorithm for transformation of regular expression to NFA. ---- === 7th week === * Approximate pattern matching and language operations. {{:courses:ae4m33pal:seminars:ata2e.docx|Example problems }} * Text Searching. Additional problems for training {{:courses:ae4m33pal:seminars:2012cvfautomatanosol.pdf| here}}\\ **Exam topics**\\ * Construction of NFA for pattern matching. Impelementation of NFA/DFA by a table or by code. * Hamming and Levenshtein distance. NFA/DFA for search of substrings which have nonzero distance from a given pattern. ---- === 8th week === * Approximate text searching {{:courses:ae4m33pal:seminars:ata3e.docx| example problems}}. * Additional problems for training {{:courses:ae4m33pal:seminars:2012cvapproxtextsearchingnosol.pdf| here}}. \\ **Exam topics**\\ * Finding dictionary entries in a text with the help of dictionary automaton. * Number of states of dictionary NFA, DFA. * Approximate text search based on previous methods. ---- === 9th week === Primes and pseudorandom numbers -- {{:courses:ae4m33pal:seminars:cvrndprimese.docx| Example problems }}. **Exam topics**\\ * Generation of random numbers and prime numbers. Their properties. Prime factorization, exact and randomized primality tests. ---- === 10th week === * Skip List, B and B+ trees {{:courses:ae4m33pal:seminars:cv11_2015e.docx| example problems}}. **Exam topics**\\ * Skip list * Search trees B and B+. Asymptotic complexity of particular search tree operations. ---- === 11th week === * 2-3-4 trees and B+ trees, splay trees. Additional problems for training {{:courses:ae4m33pal:seminars:2012cvb234treesnosol.pdf|here}} \\ **Exam topics**\\ 2-3-4 trees and B+ trees. Asymptotic complexity of particular search tree operations. ---- === 12th week === * KD trees, Nearest neighbours problem. {{ :courses:b4m33pal:stromy3e.docx | Example problems incl. previous week}}. **Exam topics**\\ KD trees, search for Nearest Neighbour in 2D. ---- === 13th week === **In preparation**\\ * Trie, suffix trie, binary trie **Exam topics**\\ * Trie, suffix trie, binary trie ---- === 14th week === **In preparation**\\ * Radix trie, Patricia trie, segment tree. **Exam topics**\\ * Radix trie, Patricia trie, segment tree. ---- ====== Search Trees Interactive Animations ====== * [[https://www.cs.usfca.edu/~galles/visualization/BST.html|Binary search tree]] * [[https://www.cs.usfca.edu/~galles/visualization/AVLtree.html|AVL tree]] * [[https://www.cs.usfca.edu/~galles/visualization/BTree.html|B tree]] * [[https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html|B+ tree]] * [[https://www.cs.usfca.edu/~galles/visualization/RedBlack.html|Red-black tree]] * [[https://www.cs.usfca.edu/~galles/visualization/SplayTree.html|Splay tree]] * [[https://yongdanielliang.github.io/animation/web/24Tree.html|2-3-4 tree]] ==== Problems in Czech ==== | Week | Topics | Problems | | 1. | Asymptotic complexity, graphs basics | {{:courses:a4m33pal:cviceni:cv01.docx|}} | | 2. | MST | {{:courses:a4m33pal:cviceni:kostry.doc| }} | | 3. | Strong connectivity, Eulerian path | {{:courses:a4m33pal:cviceni:cvorigfy.doc| }} | | 4. | Heaps | {{:courses:a4m33pal:cviceni:haldy.docx|}} | | 5. | Graph isomorphism | {{:courses:b4m33pal:cviso-1.doc|}} | | 6. | Ranking, combinatorial objects generators | {{:courses:a4m33pal:cviceni:kombi1.docx|}} | | 7. | DFA, NFA 1 | {{:courses:a4m33pal:cviceni:ata1.docx|}} | | 8. | DFA, NFA 2 | {{:courses:a4m33pal:cviceni:ata2.docx | }} | | 9. | DFA, NFA 3 | {{:courses:a4m33pal:cviceni:ata3.docx|}} | | 10. | Prime numbers and random generators | {{:courses:a4m33pal:cviceni:cvrndprimes.docx|}} | | 11. | Skip list, B/B+ tree | {{:courses:a4m33pal:cviceni:cv11_2015.docx|}} | | 12. | Splay, AVL, RB tree | {{:courses:a4m33pal:cviceni:stromy0.docx| opakování}}, {{:courses:a4m33pal:cviceni:cvbvsetsplay.docx| AVL, splay }}, {{:courses:a4m33pal:cviceni:cv13nyni.docx|B, splay.}} | | 13. | kD-trees | {{:courses:a4m33pal:cviceni:cv13mb.docx|}} | | 14. | Trie | {{:courses:b4m33pal:cv14_2017.docx|}} | {{ :courses:b4m33pal:datapub.zip | some data}}