{"id":496,"date":"2025-07-05T21:52:21","date_gmt":"2025-07-06T01:52:21","guid":{"rendered":"https:\/\/www.notexponential.com\/notes\/?page_id=496"},"modified":"2025-07-05T21:52:21","modified_gmt":"2025-07-06T01:52:21","slug":"algorithms-cs-6212-syllabus","status":"publish","type":"page","link":"https:\/\/www.notexponential.com\/notes\/algorithms-cs-6212-syllabus\/","title":{"rendered":"Algorithms &#8211; CS 6212 &#8211; Syllabus"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Instructor and Contact<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Name:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Dr. Amrinder Arora<\/li>\n\n\n\n<li>Office hours:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Tuesday, 4:00-6:00 PM or By Appointment <\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Course Information<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Course: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Department of Computer Science, Artificial Intelligence<\/li>\n\n\n\n<li>Credits: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Bulletin Course Description<\/h2>\n\n\n\n<p>Design and analysis of algorithms: Turing machines; NP-Complete theory. Algorithmic techniques: divide-and-conquer, greedy, dynamic programming, graph traversal, backtracking, and branch-and-bound. Applications include sorting and searching, graph algorithms, and optimization.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Prerequisites<\/h2>\n\n\n\n<p>CSCI 1311, CSCI 1112.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Required Text(s)<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td>Type<\/td><td>Author<\/td><td>Title<\/td><td>Edition<\/td><td>Publisher<\/td><\/tr><tr><td><strong>Required<\/strong><\/td><td><strong>Amrinder Arora<\/strong><\/td><td><strong>Analysis and Design of Algorithms<\/strong> <strong>ISBN: 978-1793549952<\/strong><strong><\/strong><\/td><td><strong>Revised Third Edition<\/strong><\/td><td>Cognella, <a href=\"http:\/\/www.cognella.com\">www.cognella.com<\/a> <br>To order: <a href=\"mailto:orders@cognella.com\">orders@cognella.com<\/a><br>Also available on <a href=\"https:\/\/amzn.to\/44u1b0P\">amazon.com<\/a><\/td><\/tr><tr><td><strong>Recommended<\/strong><\/td><td colspan=\"4\"><a href=\"https:\/\/www.notexponential.com\/notes\">https:\/\/www.notexponential.com\/notes<\/a> &nbsp;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Learning Outcomes<\/h2>\n\n\n\n<p>As a result of completing this course, students will be able to:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Analyze given software programs (in form of pseudocode) to compute the time complexity<\/li>\n\n\n\n<li>Apply basic concepts in mathematics to evaluate given software programs<\/li>\n\n\n\n<li>Design and synthesize algorithms for given problems using standard algorithm design techniques and their combinations<\/li>\n\n\n\n<li>Understand applications of discrete math, algebra and number theory concepts to problems in computing.<\/li>\n\n\n\n<li>Apply knowledge of software engineering to design and implement software programs<\/li>\n<\/ol>\n\n\n\n<p><em>Note: here is the list of student outcomes:<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; a&nbsp;&nbsp;&nbsp;&nbsp; an ability to apply knowledge of mathematics, science and engineering<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; b&nbsp;&nbsp;&nbsp;&nbsp; an ability to design and conduct experiments, as well as to analyze and interpret data<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; c&nbsp;&nbsp;&nbsp;&nbsp; an ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; d&nbsp;&nbsp;&nbsp;&nbsp; an ability to function on multidisciplinary teams<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; e&nbsp;&nbsp;&nbsp;&nbsp; an ability to identify, formulate, and solve engineering problems<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; f&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; an understanding of professional and ethical responsibility<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; g&nbsp;&nbsp;&nbsp;&nbsp; an ability to communicate effectively (3g1 orally, 3g2 written)<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; h&nbsp;&nbsp;&nbsp;&nbsp; the broad education necessary to understand the impact of engineering solutions in a global, economic, environmental, and societal context<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a recognition of the need for, and an ability to engage in life-long learning<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; j&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a knowledge of contemporary issues<\/em><\/p>\n\n\n\n<p><em>&nbsp;&nbsp;&nbsp;&nbsp; k&nbsp;&nbsp;&nbsp;&nbsp; an ability to use the techniques, skills, and modern engineering tools necessary for engineering practice.<\/em><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Class Schedule [lecture by lecture, Tentative]<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td>Lecture<\/td><td>Topic(s) and readings<\/td><td>Assignment(s) Due<\/td><\/tr><tr><td>1<\/td><td>Introduction and Asymptotic Notations<\/td><td>&nbsp;<\/td><\/tr><tr><td>2<\/td><td>Summation and Series; Data Structures \u2013 Stack, List, Graph, Tree, Binary Search Tree, Union Find<\/td><td>&nbsp;<\/td><\/tr><tr><td>3<\/td><td>Divide and Conquer \u2013 General Template, Quick Search, Merge Sort<\/td><td>Project 1 (Asymptotic)<\/td><\/tr><tr><td>4<\/td><td>Divide and Conquer \u2013 Median Finding, Quick Select, Recurrence Relation Solving<\/td><td>&nbsp;<\/td><\/tr><tr><td>5<\/td><td>Greedy Method \u2013 Knapsack Problem, Minimum Spanning Tree, Union Find<\/td><td>&nbsp;<\/td><\/tr><tr><td>6<\/td><td>Dynamic Programming, Fibonacci sequence, Matrix Chain Multiplication, Game Programming, Shortest Path problems in Graph Theory<\/td><td>Project 2 (D&amp;C)<\/td><\/tr><tr><td>7<\/td><td>DP Review \u2013 comparison with greedy, comparison with D&amp;C, MVCS, LIS<\/td><td>&nbsp;<\/td><\/tr><tr><td>8<\/td><td>Midterm<\/td><td>&nbsp;<\/td><\/tr><tr><td>9<\/td><td>Graph Traversal, DFS, Biconnectivity<\/td><td>&nbsp;<\/td><\/tr><tr><td>10<\/td><td>BFS, Branch and Bound and its applications (Halloween Special!)<\/td><td>P3 (DP)<\/td><\/tr><tr><td>11<\/td><td>NP Completeness and Complexity Classes<\/td><td>&nbsp;<\/td><\/tr><tr><td>12<\/td><td>More Reductions + Theory of Lower Bounds<\/td><td>&nbsp;<\/td><\/tr><tr><td>13<\/td><td>Project Presentations<\/td><td>Project 4<\/td><\/tr><tr><td>14<\/td><td>Final exam<\/td><td>&nbsp;<\/td><\/tr><tr><td colspan=\"3\"><strong><em>Surprise quizzes can happen during any lecture.<\/em><\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h1 class=\"wp-block-heading\">Independent Learning Statement<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">Average minimum amount of out-of-class or independent learning expected per week:<\/h2>\n\n\n\n<p>The course includes 2.5 hours of direct instruction, and students are expected to spend a minimum of 5 hours of out-of-class independent learning, totaling a minimum of 7.5 hours per week.<\/p>\n\n\n\n<h1 class=\"wp-block-heading\">Assignments and Grades<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">Grading<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Midterm exam (20%)<\/li>\n\n\n\n<li>4 Projects (40%)<\/li>\n\n\n\n<li>Final exam (20%)<\/li>\n\n\n\n<li>Homeworks \/ Quizzes &#8211; 10%<\/li>\n\n\n\n<li>Attendance \/ Class Participation &#8211; 10%<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Projects \/ Assignments<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td>Assignment<\/td><td>Description<\/td><td>Total Points\/Course Weightage<\/td><\/tr><tr><td>Project 1<\/td><td>Analysis and validation of asymptotic running time of a program<\/td><td>10<\/td><\/tr><tr><td>Project 2<\/td><td>Implementation of a Divide and Conquer algorithm<\/td><td>10<\/td><\/tr><tr><td>Project 3<\/td><td>Group Implementation of a Greedy\/Dynamic Programming algorithm<\/td><td>10<\/td><\/tr><tr><td>Project 4<\/td><td>Group implementation project<\/td><td>10<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h1 class=\"wp-block-heading\">University Policies<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">University Policy on Religious Holidays<\/h2>\n\n\n\n<ol start=\"1\" class=\"wp-block-list\">\n<li>Students should notify faculty during the first week of the semester of their intention to be absent from class on their day(s) of religious observance.<\/li>\n\n\n\n<li>Faculty should extend to these students the courtesy of absence without penalty on such occasions, including permission to make up examinations.<\/li>\n\n\n\n<li>Faculty who intend to observe a religious holiday should arrange at the beginning of the semester to reschedule missed classes or to make other provisions for their course-related activities<\/li>\n<\/ol>\n\n\n\n<h2 class=\"wp-block-heading\">Support for Students Outside the Classroom<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">Disability Support Services (DSS)<\/h3>\n\n\n\n<p>Any student who may need an accommodation based on the potential impact of a disability should contact the Disability Support Services office at&nbsp;202-994-8250&nbsp;in the Rome Hall, Suite 102, to establish eligibility and to coordinate reasonable accommodations. For additional information please refer to:&nbsp;<a href=\"http:\/\/gwired.gwu.edu\/dss\/\" target=\"_blank\" rel=\"noreferrer noopener\">gwired.gwu.edu\/dss\/<\/a><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Mental Health Services 202-994-5300\u200b&nbsp;&nbsp;&nbsp;&nbsp;<\/h3>\n\n\n\n<p>The University&#8217;s\u200b \u200bMental Health Services offers 24\/7 assistance and referral to address students&#8217; personal, social, career, and study skills problems. Services for students include: crisis and emergency mental health consultations confidential assessment, counseling services (individual and small group), and referrals.&nbsp; <a href=\"http:\/\/counselingcenter.gwu.edu\/\" target=\"_blank\" rel=\"noreferrer noopener\">counselingcenter.gwu.edu\/<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Academic Integrity Code<\/h2>\n\n\n\n<p>Academic dishonesty is defined as cheating of any kind, including misrepresenting one&#8217;s own work, taking credit for the work of others without crediting them and without appropriate authorization, and the fabrication of information. For the remainder of the code, see: <a href=\"http:\/\/studentconduct.gwu.edu\/code-academic-integrity\">studentconduct.gwu.edu\/code-academic-integrity<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Instructor and Contact Course Information Bulletin Course Description Design and analysis of algorithms: Turing machines; NP-Complete theory. Algorithmic techniques: divide-and-conquer, greedy, dynamic programming, graph traversal, backtracking, and branch-and-bound. Applications include sorting and searching, graph algorithms, and optimization. Prerequisites CSCI 1311, CSCI 1112. Required Text(s) Type Author Title Edition Publisher Required Amrinder Arora Analysis and Design [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-496","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/496","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/comments?post=496"}],"version-history":[{"count":2,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/496\/revisions"}],"predecessor-version":[{"id":612,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/496\/revisions\/612"}],"wp:attachment":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/media?parent=496"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}