{"id":7583,"date":"2023-06-12T11:50:44","date_gmt":"2023-06-12T08:50:44","guid":{"rendered":"https:\/\/www.uol.ac.cy\/?post_type=courses&#038;p=7583"},"modified":"2024-10-08T17:27:17","modified_gmt":"2024-10-08T14:27:17","slug":"cs341-complexity-theory","status":"publish","type":"courses","link":"https:\/\/www.uol.ac.cy\/en\/courses\/cs341-complexity-theory\/","title":{"rendered":"CS341 &#8211; Complexity Theory"},"content":{"rendered":"","protected":false},"featured_media":0,"template":"","meta":{"_acf_changed":false,"_seopress_robots_primary_cat":"","_seopress_titles_title":"","_seopress_titles_desc":"","_seopress_robots_index":"","_uag_custom_page_level_css":"","site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"set","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}}},"class_list":["post-7583","courses","type-courses","status-publish","hentry"],"acf":[],"spectra_custom_meta":{"_last_editor_used_jetpack":["classic-editor"],"_edit_lock":["1728397656:17"],"_edit_last":["17"],"c_course_main_title":["Bachelor of Science in Computing and Business Technologies"],"_c_course_main_title":["field_6447c49f617d3"],"c_course_unit_title":["Complexity Theory"],"_c_course_unit_title":["field_6447c246335b9"],"course_unit_code":["CS341"],"_course_unit_code":["field_63f6047058b75"],"type_of_unit":["Core"],"_type_of_unit":["field_63f6047758b76"],"level_of_course_unit":["First cycle"],"_level_of_course_unit":["field_63f6047c58b77"],"year_of_study":["Third year"],"_year_of_study":["field_63f6048558b78"],"semester":["Core"],"_semester":["field_63f6049158b79"],"number_of_ects_credits":["7.5"],"_number_of_ects_credits":["field_63f6049b58b7a"],"class_contact_hours":["36"],"_class_contact_hours":["field_63f604a358b7b"],"course_unit_objectives":["The objective of this course is to introduce students to the theory of computational complexity. The students will learn how to analyse the complexity of algorithms, and important concepts in this area, like the P=NP problem and the master theorem."],"_course_unit_objectives":["field_63f606bd0ec15"],"c_learning_outcomes":["The students completing the course should be able to:"],"_c_learning_outcomes":["field_63f607e69bd76"],"c_learning_outcomes_description":["<ul>\r\n \t<li>Understand basic notions in computational complexity theory: turing machines and the halting problem.<\/li>\r\n \t<li>Understand the different complexity classes, like NP and P.<\/li>\r\n \t<li>Understand how to analyse the complexity of algorithms.<\/li>\r\n \t<li>Understand how to analyse divide and conquer algorithms and learn how to use the master theorem.<\/li>\r\n \t<li>Introduction to graph theory and algorithms.<\/li>\r\n<\/ul>"],"_c_learning_outcomes_description":["field_63f607f99bd77"],"c_mode_of_delivery":["Mode of Delivery"],"_c_mode_of_delivery":["field_6447c76184617"],"c_prerequisites":["None"],"_c_prerequisites":["field_6447c76c84618"],"c_course_content":["<ol>\r\n \t<li>Introduction to complexity theory and the analysis of algorithms<\/li>\r\n \t<li>Introduction to complexity classes. The P=NP problem.<\/li>\r\n \t<li>The master theorem and divide and conquer algorithms<\/li>\r\n \t<li>Introduction to linear programming and dynamic programming<\/li>\r\n \t<li>Introduction to graphs (Graph diagrams definitions, directed\/undirected graphs, complements and subgraphs)<\/li>\r\n \t<li>Graph based algorithms (minimum spanning tree, single-source shortest paths, min cut max flow, Djikstra\u2019s algorithm)<\/li>\r\n<\/ol>"],"_c_course_content":["field_63f608209bd78"],"c_truefalse":["0"],"_c_truefalse":["field_6447c80f84619"],"c_readings_0_c_readings_1st_row":["<strong>Textbooks:<\/strong>\r\n\r\n1. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009\r\n\r\n<strong>Optional textbook:<\/strong>\r\n\r\n2. Richard Wilson (2010). Introduction to Graph Theory\r\n\r\n3. Miklos Bona (2011) A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory: An Introduction to Enumeration and Graph Theory (Third Edition)"],"_c_readings_0_c_readings_1st_row":["field_6447d03051789"],"c_readings_0_c_readings_2st_row":[""],"_c_readings_0_c_readings_2st_row":["field_6447d0425178a"],"c_readings":["1"],"_c_readings":["field_6447d00351788"],"_seopress_redirections_type":["301"],"_seopress_redirections_logged_status":["both"],"site-sidebar-layout":["default"],"site-content-layout":["default"],"theme-transparent-header-meta":["default"],"_seopress_analysis_target_kw":[""],"_eael_post_view_count":["1937"],"_trp_automatically_translated_slug_el":["cs341-theoria-polyplokotitas"],"classic-editor-remember":["classic-editor"],"_wp_page_template":["default"],"English_Course":["a:1:{i:0;s:7:\"English\";}"],"_English_Course":["field_664a7ab2b54a8"],"greek_course":[""],"_greek_course":["field_664afc80bfc9b"],"yesno":["1"],"_yesno":["field_6648f406b6def"],"core_en_and_gr":["Core Course"],"_core_en_and_gr":["field_664c54e2559a3"],"Teacher\u2019s_name":["#"],"_Teacher\u2019s_name":["field_6647979a4a918"],"Course_Unit_Objectives_new":["#"],"_Course_Unit_Objectives_new":["field_664c5c2365623"],"Learning_Outcomes_select":["Learning Outcomes"],"_Learning_Outcomes_select":["field_63f607e69bd76"],"Select_mode_of_delivery_language":["Face to Face"],"_Select_mode_of_delivery_language":["field_66546dc27e3f7"],"select_from_Prerequisites_language":["Prerequisites"],"_select_from_Prerequisites_language":["field_6447c76c84618"],"Prerequisites":[""],"_Prerequisites":["field_664a8078df416"],"Course_Content":["Course Content"],"_Course_Content":["field_664892bc7a322"],"add_course_content":[""],"_add_course_content":["field_664a842c9b2b8"],"Features":["Course Features"],"_Features":["field_664a88b548af2"],"add_course_feautres":["<strong>Planned learning activities and teaching methods<\/strong>\r\nLectures; in-class discussion and debates; in-class exercises; problem sets; team work; video case studies, team presentations, interactive online learning via Moodle (quizzes, assignments, forums)\r\n\r\n<strong>Assessment methods and criteria<\/strong>\r\n10% Class Participation\r\n90% Final Examination\r\n\r\n<strong>Language of Instruction<\/strong>\r\nEnglish"],"_add_course_feautres":["field_664a89441aacf"],"read_choice_lang":["Readings"],"_read_choice_lang":["field_664a8c0bc9898"],"feature_image_program":[""],"_feature_image_program":["field_668bbb4805cdb"],"return_to_the_program":["<a href=\"https:\/\/www.uol.ac.cy\/en\/program\/bsc-in-economics\/\">Return to the program<\/a>"],"_return_to_the_program":["field_668ff14d984ef"],"ast-site-content-layout":["default"],"site-content-style":["default"],"site-sidebar-style":["default"],"astra-migrate-meta-layouts":["set"],"_uag_css_file_name":["uag-css-7583.css"],"_elementor_page_assets":["a:0:{}"],"_uag_page_assets":["a:9:{s:3:\"css\";s:263:\".uag-blocks-common-selector{z-index:var(--z-index-desktop) !important}@media (max-width: 976px){.uag-blocks-common-selector{z-index:var(--z-index-tablet) !important}}@media (max-width: 767px){.uag-blocks-common-selector{z-index:var(--z-index-mobile) !important}}\n\";s:2:\"js\";s:0:\"\";s:18:\"current_block_list\";a:1:{i:0;s:11:\"core\/search\";}s:8:\"uag_flag\";b:0;s:11:\"uag_version\";s:10:\"1775340643\";s:6:\"gfonts\";a:0:{}s:10:\"gfonts_url\";s:0:\"\";s:12:\"gfonts_files\";a:0:{}s:14:\"uag_faq_layout\";b:0;}"]},"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false,"trp-custom-language-flag":false},"uagb_author_info":{"display_name":"p.efstathiou@uol.ac.cy","author_link":"https:\/\/www.uol.ac.cy\/en\/author\/"},"uagb_comment_info":0,"uagb_excerpt":null,"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/www.uol.ac.cy\/en\/wp-json\/wp\/v2\/courses\/7583","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.uol.ac.cy\/en\/wp-json\/wp\/v2\/courses"}],"about":[{"href":"https:\/\/www.uol.ac.cy\/en\/wp-json\/wp\/v2\/types\/courses"}],"version-history":[{"count":0,"href":"https:\/\/www.uol.ac.cy\/en\/wp-json\/wp\/v2\/courses\/7583\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.uol.ac.cy\/en\/wp-json\/wp\/v2\/media?parent=7583"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}