{"id":4,"date":"2025-06-04T19:51:30","date_gmt":"2025-06-04T19:51:30","guid":{"rendered":"https:\/\/courses.cs.colostate.edu\/cs003\/?page_id=4"},"modified":"2026-01-20T10:50:28","modified_gmt":"2026-01-20T17:50:28","slug":"cs-001","status":"publish","type":"page","link":"https:\/\/courses.cs.colostate.edu\/cs420\/","title":{"rendered":"CS 420"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\"><strong>Introduction to Analysis of Algorithms<\/strong><\/h2>\n\n\n\n<p>For fundamental algorithms we study the analysis of important properties such as correctness, optimality, and running time. Basic discrete probability is covered in order to analyze randomized algorithms. Knowledge of proof techniques including mathematical induction is assumed.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Prerequisites<\/h3>\n\n\n\n<p>CS 320 with a minimum grade of C<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Topics<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Graph coloring: greedy and randomized greedy algorithms<\/li>\n\n\n\n<li>Linear programming and semidefinite programming<\/li>\n\n\n\n<li>NP-completeness<\/li>\n\n\n\n<li>Entropy and the optimality of Huffman coding<\/li>\n\n\n\n<li>Randomized algorithms for sorting and order statistics<\/li>\n\n\n\n<li>Approximation algorithms for cut problems: the Goemans\u2013Williamson algorithm and Karger&#8217;s algorithm<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Optional textbook<\/h3>\n\n\n\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Introduction_to_Algorithms\" data-type=\"link\" data-id=\"https:\/\/en.wikipedia.org\/wiki\/Introduction_to_Algorithms\">Introduction to Algorithms<\/a> by Cormen, Leiserson, Rivest, Stein. 3rd edition or later recommended.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">2026 Spring Semester Details<\/h3>\n\n\n\n<div class=\"wp-block-group is-nowrap is-layout-flex wp-container-core-group-is-layout-ad2f72ca wp-block-group-is-layout-flex\">\n<div class=\"wp-block-columns wp-container-content-9cfa9a5a is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<h4 class=\"wp-block-heading\">Instructor(s)<\/h4>\n\n\n<style>.kb-table-container4_9ba4ca-32{overflow-x:auto;}.kb-table-container .kb-table4_9ba4ca-32 th{padding-top:var(--global-kb-spacing-xxs, 0.5rem);padding-right:var(--global-kb-spacing-xxs, 0.5rem);padding-bottom:var(--global-kb-spacing-xxs, 0.5rem);padding-left:var(--global-kb-spacing-xxs, 0.5rem);text-align:right;}.kb-table-container .kb-table4_9ba4ca-32 caption{text-align:center;}.kb-table-container .kb-table4_9ba4ca-32 td{padding-top:var(--global-kb-spacing-xxs, 0.5rem);padding-right:var(--global-kb-spacing-xxs, 0.5rem);padding-bottom:var(--global-kb-spacing-xxs, 0.5rem);padding-left:var(--global-kb-spacing-xxs, 0.5rem);text-align:left;}.kb-table-container .kb-table4_9ba4ca-32 tr{border-top:1px solid #888;border-right:1px solid #888;border-bottom:1px solid #888;border-left:1px solid #888;}@media all and (max-width: 1024px){.kb-table-container .kb-table4_9ba4ca-32 tr{border-top:1px solid #888;border-right:1px solid #888;border-bottom:1px solid #888;border-left:1px solid #888;}}@media all and (max-width: 767px){.kb-table-container .kb-table4_9ba4ca-32 tr{border-top:1px solid #888;border-right:1px solid #888;border-bottom:1px solid #888;border-left:1px solid #888;}}<\/style><div class=\"kb-table-container kb-table-container4_9ba4ca-32 wp-block-kadence-table\"><table class=\"kb-table kb-table4_9ba4ca-32\">\n<tr class=\"kb-table-row kb-table-row4_170755-54\">\n<td class=\"kb-table-data kb-table-data4_b4a01f-dc\">\n\n<p><strong>Instructor<\/strong><\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_1ab8d2-bb\">\n\n<p>Ewan Davies&nbsp;<\/p>\n\n<\/td>\n<\/tr>\n\n<tr class=\"kb-table-row kb-table-row4_35a45a-77\">\n<td class=\"kb-table-data kb-table-data4_0fe0f0-db\">\n\n<p><strong>Office<\/strong><\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_418880-51\">\n\n<p>CSB 448<\/p>\n\n<\/td>\n<\/tr>\n\n<tr class=\"kb-table-row kb-table-row4_a62e2b-c1\">\n<td class=\"kb-table-data kb-table-data4_bc694d-de\">\n\n<p><strong>Email<\/strong><\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_c0ba5e-78\">\n\n<p><a href=\"mailto:cs420@cs.colostate.edu\">cs420@cs.colostate.edu<\/a><\/p>\n\n<\/td>\n<\/tr>\n\n<tr class=\"kb-table-row kb-table-row4_3ad8c5-02\">\n<td class=\"kb-table-data kb-table-data4_3ff462-5a\">\n\n<p><strong>Office Hours<\/strong><\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_b37505-e5\">\n\n<p>Thursday 11am, CSB 448<\/p>\n\n<\/td>\n<\/tr>\n<\/table><\/div><\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<h4 class=\"wp-block-heading\">Class Schedule<\/h4>\n\n\n<style>.kb-table-container4_1be4b8-bf{overflow-x:auto;}.kb-table-container .kb-table4_1be4b8-bf th{padding-top:var(--global-kb-spacing-xxs, 0.5rem);padding-right:var(--global-kb-spacing-xxs, 0.5rem);padding-bottom:var(--global-kb-spacing-xxs, 0.5rem);padding-left:var(--global-kb-spacing-xxs, 0.5rem);text-align:center;}.kb-table-container .kb-table4_1be4b8-bf caption{text-align:center;}.kb-table-container .kb-table4_1be4b8-bf td{padding-top:var(--global-kb-spacing-xxs, 0.5rem);padding-right:var(--global-kb-spacing-xxs, 0.5rem);padding-bottom:var(--global-kb-spacing-xxs, 0.5rem);padding-left:var(--global-kb-spacing-xxs, 0.5rem);text-align:left;}.kb-table-container .kb-table4_1be4b8-bf tr{border-top:1px solid #888;border-right:1px solid #888;border-bottom:1px solid #888;border-left:1px solid #888;}@media all and (max-width: 1024px){.kb-table-container .kb-table4_1be4b8-bf tr{border-top:1px solid #888;border-right:1px solid #888;border-bottom:1px solid #888;border-left:1px solid #888;}}@media all and (max-width: 767px){.kb-table-container .kb-table4_1be4b8-bf tr{border-top:1px solid #888;border-right:1px solid #888;border-bottom:1px solid #888;border-left:1px solid #888;}}<\/style><div class=\"kb-table-container kb-table-container4_1be4b8-bf wp-block-kadence-table\"><table class=\"kb-table kb-table4_1be4b8-bf\">\n<tr class=\"kb-table-row kb-table-row4_76cbba-eb\">\n<th class=\"kb-table-data kb-table-data4_fb9170-a7\">\n\n<p>Section<\/p>\n\n<\/th>\n\n<th class=\"kb-table-data kb-table-data4_7b09a2-a3\">\n\n<p>Schedule<\/p>\n\n<\/th>\n\n<th class=\"kb-table-data kb-table-data4_d89863-cf\">\n\n<p>Location<\/p>\n\n<\/th>\n\n<th class=\"kb-table-data kb-table-data4_c4f2e9-0d\">\n\n<p>Instructor<\/p>\n\n<\/th>\n<\/tr>\n\n<tr class=\"kb-table-row kb-table-row4_6ae12b-bf\">\n<td class=\"kb-table-data kb-table-data4_c1bdbe-df\">\n\n<p>001<\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_3dbf82-79\">\n\n<p>MWF 9:00am &#8211; 9:50am<\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_130cee-fd\">\n\n<p>Walnut 111<\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_983ccf-64\">\n\n<p>Ewan Davies<\/p>\n\n<\/td>\n<\/tr>\n\n<tr class=\"kb-table-row kb-table-row4_ae92b0-fd\">\n<td class=\"kb-table-data kb-table-data4_94fc11-da\">\n\n<p>R01<\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_ca401b-2a\">\n\n<p>W 3:00pm-3:50pm<\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_3b1e40-2f\">\n\n<p>CSB 425<\/p>\n\n<\/td>\n\n<td class=\"kb-table-data kb-table-data4_521d86-ef\">\n\n<p>Ewan Davies<\/p>\n\n<\/td>\n<\/tr>\n<\/table><\/div><\/div>\n<\/div>\n<\/div>\n\n\n\n<div class=\"wp-block-group is-nowrap is-layout-flex wp-container-core-group-is-layout-ad2f72ca wp-block-group-is-layout-flex\">\n<div class=\"wp-block-columns wp-container-content-9cfa9a5a is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<h3 class=\"wp-block-heading\" id=\"TAs\">TA Information<\/h3>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<p>Ali Bigdeli<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Introduction to Analysis of Algorithms For fundamental algorithms we study the analysis of important properties such as correctness, optimality, and running time. Basic discrete probability is covered in order to analyze randomized algorithms. Knowledge of proof techniques including mathematical induction is assumed. Prerequisites CS 320 with a minimum grade of C Topics Optional textbook Introduction [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"template-no-page-title.php","meta":{"_kad_blocks_custom_css":"","_kad_blocks_head_custom_js":"","_kad_blocks_body_custom_js":"","_kad_blocks_footer_custom_js":"","footnotes":""},"class_list":["post-4","page","type-page","status-publish","hentry","post-preview"],"taxonomy_info":[],"featured_image_src_large":false,"author_info":{"display_name":"admin","author_link":"https:\/\/courses.cs.colostate.edu\/cs420\/author\/admin_41g0qmxe\/"},"comment_info":0,"_links":{"self":[{"href":"https:\/\/courses.cs.colostate.edu\/cs420\/wp-json\/wp\/v2\/pages\/4","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courses.cs.colostate.edu\/cs420\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/courses.cs.colostate.edu\/cs420\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/courses.cs.colostate.edu\/cs420\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/courses.cs.colostate.edu\/cs420\/wp-json\/wp\/v2\/comments?post=4"}],"version-history":[{"count":19,"href":"https:\/\/courses.cs.colostate.edu\/cs420\/wp-json\/wp\/v2\/pages\/4\/revisions"}],"predecessor-version":[{"id":85,"href":"https:\/\/courses.cs.colostate.edu\/cs420\/wp-json\/wp\/v2\/pages\/4\/revisions\/85"}],"wp:attachment":[{"href":"https:\/\/courses.cs.colostate.edu\/cs420\/wp-json\/wp\/v2\/media?parent=4"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}