{"id":250,"date":"2025-01-17T23:04:47","date_gmt":"2025-01-17T22:04:47","guid":{"rendered":"https:\/\/home.agh.edu.pl\/~kkulak\/?page_id=250"},"modified":"2025-01-18T15:38:58","modified_gmt":"2025-01-18T14:38:58","slug":"algorithms-and-data-structures","status":"publish","type":"page","link":"https:\/\/home.agh.edu.pl\/~kkulak\/algorithms-and-data-structures\/","title":{"rendered":"Algorithms and Data Structures"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Literature<\/h2>\n\n\n<div class=\"teachpress_pub_list\"><form name=\"tppublistform\" method=\"get\"><a name=\"tppubs\" id=\"tppubs\"><\/a><\/form><div class=\"teachpress_publication_list\"><h3 class=\"tp_h3\" id=\"tp_h3_2022\">2022<\/h3><div class=\"tp_publication tp_publication_book\"><div class=\"tp_pub_info\"><p class=\"tp_pub_author\"> Cormen, T. H.;  Leiserson, C. E.;  Rivest, R. L.;  Stein, C.<\/p><p class=\"tp_pub_title\"><a class=\"tp_title_link\" onclick=\"teachpress_pub_showhide('94','tp_links')\" style=\"cursor:pointer;\">Introduction to Algorithms, fourth edition<\/a> <span class=\"tp_pub_type tp_  book\">Book<\/span> <\/p><p class=\"tp_pub_additional\"><span class=\"tp_pub_additional_publisher\">MIT Press, <\/span><span class=\"tp_pub_additional_year\">2022<\/span>, <span class=\"tp_pub_additional_isbn\">ISBN: 9780262367509<\/span>.<\/p><p class=\"tp_pub_menu\"><span class=\"tp_resource_link\"><a id=\"tp_links_sh_94\" class=\"tp_show\" onclick=\"teachpress_pub_showhide('94','tp_links')\" title=\"Show links and resources\" style=\"cursor:pointer;\">Links<\/a><\/span> | <span class=\"tp_bibtex_link\"><a id=\"tp_bibtex_sh_94\" class=\"tp_show\" onclick=\"teachpress_pub_showhide('94','tp_bibtex')\" title=\"Show BibTeX entry\" style=\"cursor:pointer;\">BibTeX<\/a><\/span><\/p><div class=\"tp_bibtex\" id=\"tp_bibtex_94\" style=\"display:none;\"><div class=\"tp_bibtex_entry\"><pre>@book{Cormen2022ita,<br \/>\r\ntitle = {Introduction to Algorithms, fourth edition},<br \/>\r\nauthor = {T. H. Cormen and C. E. Leiserson and R. L. Rivest and C. Stein},<br \/>\r\nurl = {https:\/\/books.google.pl\/books?id=RSMuEAAAQBAJ},<br \/>\r\nisbn = {9780262367509},<br \/>\r\nyear  = {2022},<br \/>\r\ndate = {2022-01-01},<br \/>\r\npublisher = {MIT Press},<br \/>\r\nkeywords = {},<br \/>\r\npubstate = {published},<br \/>\r\ntppubtype = {book}<br \/>\r\n}<br \/>\r\n<\/pre><\/div><p class=\"tp_close_menu\"><a class=\"tp_close\" onclick=\"teachpress_pub_showhide('94','tp_bibtex')\">Close<\/a><\/p><\/div><div class=\"tp_links\" id=\"tp_links_94\" style=\"display:none;\"><div class=\"tp_links_entry\"><ul class=\"tp_pub_list\"><li><i class=\"fas fa-globe\"><\/i><a class=\"tp_pub_list\" href=\"https:\/\/books.google.pl\/books?id=RSMuEAAAQBAJ\" title=\"https:\/\/books.google.pl\/books?id=RSMuEAAAQBAJ\" target=\"_blank\">https:\/\/books.google.pl\/books?id=RSMuEAAAQBAJ<\/a><\/li><\/ul><\/div><p class=\"tp_close_menu\"><a class=\"tp_close\" onclick=\"teachpress_pub_showhide('94','tp_links')\">Close<\/a><\/p><\/div><\/div><\/div><h3 class=\"tp_h3\" id=\"tp_h3_2009\">2009<\/h3><div class=\"tp_publication tp_publication_book\"><div class=\"tp_pub_info\"><p class=\"tp_pub_author\"> Soltys, M.<\/p><p class=\"tp_pub_title\"><a class=\"tp_title_link\" onclick=\"teachpress_pub_showhide('96','tp_links')\" style=\"cursor:pointer;\">An Introduction to the Analysis of Algorithms<\/a> <span class=\"tp_pub_type tp_  book\">Book<\/span> <\/p><p class=\"tp_pub_additional\"><span class=\"tp_pub_additional_publisher\">WORLD SCIENTIFIC, <\/span><span class=\"tp_pub_additional_year\">2009<\/span>.<\/p><p class=\"tp_pub_menu\"><span class=\"tp_resource_link\"><a id=\"tp_links_sh_96\" class=\"tp_show\" onclick=\"teachpress_pub_showhide('96','tp_links')\" title=\"Show links and resources\" style=\"cursor:pointer;\">Links<\/a><\/span> | <span class=\"tp_bibtex_link\"><a id=\"tp_bibtex_sh_96\" class=\"tp_show\" onclick=\"teachpress_pub_showhide('96','tp_bibtex')\" title=\"Show BibTeX entry\" style=\"cursor:pointer;\">BibTeX<\/a><\/span><\/p><div class=\"tp_bibtex\" id=\"tp_bibtex_96\" style=\"display:none;\"><div class=\"tp_bibtex_entry\"><pre>@book{Soltys2009iott,<br \/>\r\ntitle = {An Introduction to the Analysis of Algorithms},<br \/>\r\nauthor = {M. Soltys},<br \/>\r\nurl = {https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/7254},<br \/>\r\ndoi = {10.1142\/7254},<br \/>\r\nyear  = {2009},<br \/>\r\ndate = {2009-01-01},<br \/>\r\npublisher = {WORLD SCIENTIFIC},<br \/>\r\nkeywords = {},<br \/>\r\npubstate = {published},<br \/>\r\ntppubtype = {book}<br \/>\r\n}<br \/>\r\n<\/pre><\/div><p class=\"tp_close_menu\"><a class=\"tp_close\" onclick=\"teachpress_pub_showhide('96','tp_bibtex')\">Close<\/a><\/p><\/div><div class=\"tp_links\" id=\"tp_links_96\" style=\"display:none;\"><div class=\"tp_links_entry\"><ul class=\"tp_pub_list\"><li><i class=\"fas fa-globe\"><\/i><a class=\"tp_pub_list\" href=\"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/7254\" title=\"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/7254\" target=\"_blank\">https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/7254<\/a><\/li><li><i class=\"ai ai-doi\"><\/i><a class=\"tp_pub_list\" href=\"https:\/\/dx.doi.org\/10.1142\/7254\" title=\"Follow DOI:10.1142\/7254\" target=\"_blank\">doi:10.1142\/7254<\/a><\/li><\/ul><\/div><p class=\"tp_close_menu\"><a class=\"tp_close\" onclick=\"teachpress_pub_showhide('96','tp_links')\">Close<\/a><\/p><\/div><\/div><\/div><\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Lectures plan<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Introduction\n<ul class=\"wp-block-list\">\n<li>What is an algorithm?<\/li>\n\n\n\n<li>What is a data structure?<\/li>\n\n\n\n<li>Inductive reasoning<\/li>\n\n\n\n<li>Inductive proof<\/li>\n\n\n\n<li>Complexity of an algorithm<\/li>\n\n\n\n<li>Sorting by insertion<\/li>\n\n\n\n<li>Analysis of sorting by insertion<\/li>\n\n\n\n<li>Asymptotic notations<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Sorting, Heap, Recursion\n<ul class=\"wp-block-list\">\n<li>Divide-and-conquer method.<\/li>\n\n\n\n<li>Sorting by merging &#8211; MergeSort.<\/li>\n\n\n\n<li>Complexity of merge sorting.<\/li>\n\n\n\n<li>Recursion, computing recursive complexity, solving recursion, the universal recursion theorem.<\/li>\n\n\n\n<li>Heap, heap property, restoring heap property, building a heap.<\/li>\n\n\n\n<li>Analysis of heap algorithms<\/li>\n\n\n\n<li>Heap Sorting, Priority Queues, Priority Sorting, Quicksort.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Priority queues, Quicksort, Linear time sorting.\n<ul class=\"wp-block-list\">\n<li>Priority queues<\/li>\n\n\n\n<li>Heap operations<\/li>\n\n\n\n<li>Implementation of priority queues<\/li>\n\n\n\n<li>Quicksort\n<ul class=\"wp-block-list\">\n<li>Algorithm<\/li>\n\n\n\n<li>Quicksort analysis<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Decision Tree Model alg. Sorting<\/li>\n\n\n\n<li>Sorting by counting, positional sorting, bucket sort.<\/li>\n\n\n\n<li>Dynamic Sorts, Stack, List<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Data structures, Stack, Queue, List, BST and RB Trees.\n<ul class=\"wp-block-list\">\n<li>Dynamic Sets<\/li>\n\n\n\n<li>Stack<\/li>\n\n\n\n<li>Queue<\/li>\n\n\n\n<li>List<\/li>\n\n\n\n<li>BST tree\n<ul class=\"wp-block-list\">\n<li>browse, search, delete operations<\/li>\n\n\n\n<li>complexity of BST tree operations<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Well-balanced trees\n<ul class=\"wp-block-list\">\n<li>Red-Black Tree (RB-Tree)\n<ul class=\"wp-block-list\">\n<li>inserting into RB-tree<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Skip lists, hash tables, positional statistics\n<ul class=\"wp-block-list\">\n<li>Skip lists<\/li>\n\n\n\n<li>hash tables\n<ul class=\"wp-block-list\">\n<li>direct addressing<\/li>\n\n\n\n<li>open addressing\n<ul class=\"wp-block-list\">\n<li>linear, square, double addressing<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>List implementation, collision resolution<\/li>\n\n\n\n<li>Hashing function<\/li>\n\n\n\n<li>positional statistics\n<ul class=\"wp-block-list\">\n<li>selection problem, selection in pessimistic linear time<\/li>\n\n\n\n<li>dynamic positional statistics<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Dynamic positional statistics, interval trees, graphs.\n<ul class=\"wp-block-list\">\n<li>dynamic positional statistics\n<ul class=\"wp-block-list\">\n<li>determination of an element of a given rank<\/li>\n\n\n\n<li>rotation in a tree of dynamic positional statistics<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Interval trees\n<ul class=\"wp-block-list\">\n<li>rotation in an interval tree<\/li>\n\n\n\n<li>searching for an interval in an interval tree<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Graphs\n<ul class=\"wp-block-list\">\n<li>graph representation, neighborhood matrix, neighborhood lists<\/li>\n\n\n\n<li>graph search, BFS algorithm<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Graphs, DFS, graph spanning tree, topological sorting.\n<ul class=\"wp-block-list\">\n<li>Graph algorithms\n<ul class=\"wp-block-list\">\n<li>Graph Searching\n<ul class=\"wp-block-list\">\n<li>BFS, DFS<\/li>\n\n\n\n<li>spanning tree creation<\/li>\n\n\n\n<li>edge classification\n<ul class=\"wp-block-list\">\n<li>forward edge, traversal edge, backward edge, spanning tree edge.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>directed acyclic graph\n<ul class=\"wp-block-list\">\n<li>topological sorting\n<ul class=\"wp-block-list\">\n<li>properties of topological sorting<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Graph algorithms, search for minimal paths.\n<ul class=\"wp-block-list\">\n<li>Minimum spanning tree<\/li>\n\n\n\n<li>Observation, optimal structure consists of optimal substructures.<\/li>\n\n\n\n<li>Prim algorithm for searching a minimal spanning tree * Prima algorithm for searching a minimal spanning tree<\/li>\n\n\n\n<li>Searching for minimal paths in any directed graph, Ford Bellman algorithm.<\/li>\n\n\n\n<li>A version of the Ford Bellman algorithm for directed acyclic graphs.<\/li>\n\n\n\n<li>Searching for shortest paths in a graph with nonnegative edge weights, Dijkstra&#8217;s algorithm.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Graph algorithms, amortised cost method.\n<ul class=\"wp-block-list\">\n<li>Dijkstra&#8217;s algorithm\n<ul class=\"wp-block-list\">\n<li>operation, complexity, correctness<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Spanning trees\n<ul class=\"wp-block-list\">\n<li>Kruskal algorithm<\/li>\n\n\n\n<li>Kruskal algorithm correctness<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>The problem of shortest paths between each pair of vertices in a graph.\n<ul class=\"wp-block-list\">\n<li>Warshal Floyd algorithm<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Amortised cost analysis\n<ul class=\"wp-block-list\">\n<li>dynamic arrays<\/li>\n\n\n\n<li>analysis by the summary cost method<\/li>\n\n\n\n<li>analysis by accounting method<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Flow networks, pattern finding algorithms\n<ul class=\"wp-block-list\">\n<li>Flow networks\n<ul class=\"wp-block-list\">\n<li>Ford-Fulkerson algorithm, residual network, augmented path, flow function.<\/li>\n\n\n\n<li>minimum crosssection, maximum flow.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Maximal associations in bipartite graphs.\n<ul class=\"wp-block-list\">\n<li>reduction to a flow network problem<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>pattern search in text\n<ul class=\"wp-block-list\">\n<li>\u201enaive\u201d algorithm, Rabin Karp algorithm,&nbsp;<\/li>\n\n\n\n<li>Finite state automata, introduction to KMP&nbsp;<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Text algorithms\n<ul class=\"wp-block-list\">\n<li>Pattern search\n<ul class=\"wp-block-list\">\n<li>finite automata<\/li>\n\n\n\n<li>searching for a pattern in a text using automata<\/li>\n\n\n\n<li>KMP algorithm (reduction of transition functions to an array)<\/li>\n\n\n\n<li>Boyer-Moore algorithm\n<ul class=\"wp-block-list\">\n<li>heuristics\n<ul class=\"wp-block-list\">\n<li>inconsistencies<\/li>\n\n\n\n<li>good suffix<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Text compression, Parallel algorithms\n<ul class=\"wp-block-list\">\n<li>text compression\n<ul class=\"wp-block-list\">\n<li>Information theory, Shannon&#8217;s entropy measure<\/li>\n\n\n\n<li>Huffman coding\n<ul class=\"wp-block-list\">\n<li>Huffman coding algorithm<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>LZW compression<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Parallel algorithms\n<ul class=\"wp-block-list\">\n<li>Flynn&#8217;s taxonomy of parallel systems<\/li>\n\n\n\n<li>parallel architectures<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>PRAM model\n<ul class=\"wp-block-list\">\n<li>EREW, CREW, ERCW, CRCW<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>examples of parallel algorithms\n<ul class=\"wp-block-list\">\n<li>Pascal&#8217;s triangle, minimum search, positional statistics, determining the rank of an element in a list.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Geometric algorithms\n<ul class=\"wp-block-list\">\n<li>basic concepts<\/li>\n\n\n\n<li>determining the position of points relative to each other<\/li>\n\n\n\n<li>the problem of intersection of two segments.<\/li>\n\n\n\n<li>construction techniques for geometric algorithms<\/li>\n\n\n\n<li>the problem of finding the convex envelope of a set of points<\/li>\n\n\n\n<li>Graham&#8217;s algorithm for finding the convex envelope of a set of points.<\/li>\n\n\n\n<li>Finding intersecting segments in a set of segments.<\/li>\n\n\n\n<li>algorithm for finding intersecting segments by the sweeping method<\/li>\n\n\n\n<li>problem of finding the least distant pair of points in a point set\n<ul class=\"wp-block-list\">\n<li>the divide and conquer algorithm<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Summary lecture<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Literature Lectures plan<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"page-templates\/full-width.php","meta":{"footnotes":""},"class_list":["post-250","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/home.agh.edu.pl\/~kkulak\/wp-json\/wp\/v2\/pages\/250","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/home.agh.edu.pl\/~kkulak\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/home.agh.edu.pl\/~kkulak\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/home.agh.edu.pl\/~kkulak\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/home.agh.edu.pl\/~kkulak\/wp-json\/wp\/v2\/comments?post=250"}],"version-history":[{"count":5,"href":"https:\/\/home.agh.edu.pl\/~kkulak\/wp-json\/wp\/v2\/pages\/250\/revisions"}],"predecessor-version":[{"id":322,"href":"https:\/\/home.agh.edu.pl\/~kkulak\/wp-json\/wp\/v2\/pages\/250\/revisions\/322"}],"wp:attachment":[{"href":"https:\/\/home.agh.edu.pl\/~kkulak\/wp-json\/wp\/v2\/media?parent=250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}