{"id":2825,"date":"2019-08-18T16:55:36","date_gmt":"2019-08-18T21:55:36","guid":{"rendered":"https:\/\/www.jsums.edu\/nmeghanathan\/?page_id=2825"},"modified":"2019-11-14T01:23:10","modified_gmt":"2019-11-14T06:23:10","slug":"csc323-fall2019","status":"publish","type":"page","link":"https:\/\/www.jsums.edu\/nmeghanathan\/csc323-fall2019\/","title":{"rendered":"CSC 323 Algorithm Design and Analysis, Fall 2019"},"content":{"rendered":"

\n\tQuiz 7<\/strong> due in my office ENB 275<\/em> by Dec. 3rd, 1 PM<\/strong> (slide under the door)<\/span>\n<\/p>\n

\n\tEXAM 3<\/strong> posted in Canvas<\/em> (to be taken in Canvas as a quiz; to be completed by Dec. 3rd, 1 PM<\/strong>)<\/span>\n<\/p>\n

\n\t \n<\/p>\n

\n\t—————————————————–<\/span>\n<\/p>\n

\n\t \n<\/p>\n

\n\tSyllabus<\/a>\n<\/p>\n

\n\tTeaching Assistant<\/a>\n<\/p>\n

\n\tLecture Slides<\/a>\n<\/p>\n

\n\tQuestion Bank<\/a>\n<\/p>\n

\n\tProject Descriptions<\/a>\n<\/p>\n

\n\tQuizzes and Exams<\/a>\n<\/p>\n

\n\tCode Tutorial<\/a>\n<\/p>\n

\n\tDr. Meg's Desktop Selected Lecture Videos<\/a>\n<\/p>\n

\n\tQuiz, Exam and Project Schedules<\/a>\n<\/p>\n

\n\t—————————————————–<\/span>\n<\/p>\n

\n\t<\/a>Syllabus
\n<\/h3>\n

\n\tCSC323 Syllabus, Fall 2019<\/a><\/strong>\n<\/p>\n

\n\t<\/a>Teaching Assistant
\n<\/h3>\n

\n\tMahzabin Akhter <akhterm86@gmail.com><\/span>\n<\/p>\n

\n\tRoom: ENB 163<\/span>\n<\/p>\n

\n\tTuesday: 9 am – 11 am, 1 pm – 2 pm, 4 pm – 5pm<\/span>
\n\tThursday: 9 am – 11 am, 1 pm – 2 pm, 4 pm – 5pm<\/span>
\n\tFriday: 9 am – 1 pm<\/span>\n<\/p>\n

\n\t \n<\/p>\n

\n\t<\/a>Lecture Slides
\n<\/h3>\n

\n\tModule 1: Algorithm Efficiency Analysis<\/a> <\/span>\n<\/p>\n

\n\tModule 2: Divide and Conquer<\/a><\/span>\n<\/p>\n

\n\tModule 3: Greedy Strategy<\/a><\/span>\n<\/p>\n

\n\tModule 4: Dynamic Programming<\/a><\/span>\n<\/p>\n

\n\tModule 5: Graph Algorithms<\/a><\/span>\n<\/p>\n

\n\tModule 6: P, NP, NP-Complete Problems<\/a><\/span>\n<\/p>\n

\n\t \n<\/p>\n

\n\t<\/a>Question Bank
\n<\/h3>\n

\n\tQB Module 1: Algorithm Efficiency Analysis<\/a><\/span>\n<\/p>\n

\n\tQB Module 2 – Classical Design Techniques<\/a><\/span>\n<\/p>\n

\n\tQB Module 3 – Greedy Strategy<\/a><\/span>\n<\/p>\n

\n\tQB Module 4 – Dynamic Programming<\/a><\/span>\n<\/p>\n

\n\tQB Module 5 – Graph Theory Algorithms<\/a><\/span>\n<\/p>\n

\n\t<\/a>Project Descriptions
\n<\/h3>\n

\n\tProject 1 (Due: Sept. 17th, 11.59 PM): Brute Force Algorithm for the Element Uniqueness Problem<\/a><\/strong>\n<\/p>\n

\n\t \n<\/p>\n

\n\tProject 2 (Due: Oct. 1st, 11.59 PM): <\/strong><\/span><\/b> Algorithm to Determine the Longest Subsequence of Consecutive Integers in an Array using Hash tables, its Optimization and the Analysis of the Space-Time Tradeoff<\/a><\/strong>\n<\/p>\n

\n\tSee Canvas for the code\n<\/p>\n

\n\t \n<\/p>\n

\n\tProject 3 (Due: Oct. 8th, 11.59 PM): <\/strong><\/span><\/b>Recursive Algorithm to Find the Minimum Integer in an Array and its Space-Time Tradeoff Performance Comparison Analysis with an Iterative Algorithm<\/a><\/strong>\n<\/p>\n

\n\t \n<\/p>\n

\n\tProject 4 (Due: Oct. 15th, 11.59 PM): <\/strong><\/span><\/b>Design and Implementation of Algorithms to Generate a Unimodal Array of Unique Elements and Implementation of the Binary Search Algorithm to Determine the Maximum Element in a Unimodal Array<\/a><\/strong>\n<\/p>\n

\n\t \n<\/p>\n

\n\tProject 5 (Due: Oct. 22nd, 11.59 PM): <\/strong><\/span><\/b>Dynamic Programming Algorithm for Optimum Coin Collection in a Two-Dimensional Grid<\/a><\/strong>\n<\/p>\n

\n\t \n<\/p>\n

\n\tProject 6 (Due: Oct. 29th, 11.59 PM): <\/strong><\/span><\/b>Dynamic Programming-based Solution for the Longest Common Subsequence Problem<\/a><\/strong>\n<\/p>\n

\n\t \n<\/p>\n

\n\tProject 7 (Due: Nov. 5th, 11.59 PM): <\/strong><\/span><\/b>Dynamic Programming: Coin Change Problem<\/a><\/span><\/strong>\n<\/p>\n

\n\tSee Canvas for the code<\/span>\n<\/p>\n

\n\t \n<\/p>\n

\n\tProject 8 (Due: Nov. 12th, 11.59 PM): <\/strong><\/span><\/b>Number of Walks of a certain Length between any Two Vertices<\/a><\/strong>\n<\/p>\n

\n\tSee Canvas for the code<\/span>\n<\/p>\n

\n\t \n<\/p>\n

\n\t<\/a>Quizzes and Exams
\n<\/h3>\n

\n\tQuiz 2 (Due: Oct. 3rd, 11.59 PM): <\/strong><\/span><\/b> Evaluation of the Bubble Sort Algorithm with and without the Optimization Approach<\/a><\/strong>\n<\/p>\n

\n\tSee Canvas for the code\n<\/p>\n

\n\t \n<\/p>\n

\n\tQuiz 3 (Due: Oct. 10th, 11.59 PM): <\/strong><\/span><\/b> Using the Merge Sort and Insertion Sort Algorithms to Determine the Number of Inversions and the Inverted Pairs of an Array<\/a><\/strong>\n<\/p>\n

\n\tSee Canvas for the code\n<\/p>\n

\n\t \n<\/p>\n

\n\tQuiz 4 (Due: Oct. 17th, 11.59 PM): <\/strong><\/span><\/b>Binary Search vs. Brute Force Search Algorithms for Finding a Local Minimum in a Two-Dimensional Array<\/a><\/strong>\n<\/p>\n

\n\t \n<\/p>\n

\n\tQuiz 5 (Due: Oct. 24th, 11.59 PM): <\/strong><\/span><\/b>Greedy Algorithm for Selecting the Longest Sequence of Non-Overlapping Activities based on their Finish times<\/a><\/strong>\n<\/p>\n

\n\tSee Canvas for code\n<\/p>\n

\n\t \n<\/p>\n

\n\tExam 2 (Take Home; Due on Oct. 31st, 2.30 PM)<\/a><\/strong>\n<\/p>\n

\n\t \n<\/p>\n

\n\tQuiz 6 (Due: Nov. 7th, 2.30 PM): <\/strong><\/span><\/b>Matrix Chain Multiplication<\/a><\/strong><\/span>\n<\/p>\n

\n\tQuiz 7 (Due: Dec. 3rd, 1 PM): <\/strong><\/span><\/b>Prim's Minimum Spanning Tree Algorithm<\/a><\/strong><\/span>\n<\/p>\n

\n\t \n<\/p>\n

\n\t<\/a>Code Tutorial
\n<\/h3>\n

\n\t \n<\/p>\n

\n\t \n<\/p>\n

\n\t \n<\/p>\n

\n\t \n<\/p>\n

\n\t \n<\/p>\n

\n\t<\/a>Dr. Meg's Desktop Selected Lecture Videos (YouTube Links)<\/span>
\n<\/h3>\n

\n\tModule 1: Analyzing the Efficiency of Algorithms<\/span><\/u>
\n<\/h4>\n

\n\tTime-Complexity analysis of a recursive algorithm to compute the factorial of an integer<\/a>\n<\/p>\n

\n\tExample for solving recurrence relations<\/a>\n<\/p>\n

\n\tTime-complexity analysis of an iterative algorithm to determine whether an array has unique elements<\/a>\n<\/p>\n

\n\tTime-Complexity analysis of a recursive algorithm to determine the number of bits needed to represent a positive integer<\/a>\n<\/p>\n

\n\tDecrease and Conquer – Insertion Sort Algorithm and Examples<\/a>\n<\/p>\n

\n\tModule 2: Classical Algorithm Design Techniuqes<\/span><\/u>
\n<\/h4>\n

\n\tBrute Force Algorithms QB – String Matching Problems<\/a>\n<\/p>\n

\n\tDivide and Conquer – Theorem-Proof: In order Traversal of a Binary Search Tree<\/a>\n<\/p>\n

\n\tDivide and Conquer – Master Theorem<\/a>\n<\/p>\n

\n\tBinary Search Algorithm and Examples<\/a>\n<\/p>\n

\n\tComparison of Bottom-up and Top-down Approaches for Heap Construction<\/a>\n<\/p>\n

\n\tTransform and Conquer – Proof for Euclid's GCD Formula<\/a>\n<\/p>\n

\n\tTransform and Conquer – Heap Sort<\/a>\n<\/p>\n

\n\tSpace-Time Tradeoffs for the Sorting Algorithms (Merge, Insertion and Heap Sorts)<\/a>\n<\/p>\n

\n\t<\/a>Module 3: Greedy Technique<\/span><\/u>
\n<\/h4>\n

\n\tGreedy Technique – Fractional Knapsack Problem<\/a>\n<\/p>\n

\n\tGreedy Technique – Huffman Codes (Variable Length Prefix-free Encoding)<\/a>\n<\/p>\n

\n\tModule 4: Dynamic Programming<\/span><\/u>
\n<\/h4>\n

\n\tDynamic Programming: Coin-row Problem Discussion and Example<\/a>\n<\/p>\n

\n\tDynamic Programming: Binomial Coefficient<\/a>\n<\/p>\n

\n\tDynamic Programming Solution for the Coin Collecting Problem in a Two-Dimensional Grid<\/a>\n<\/p>\n

\n\tDynamic Programming: Integer Knapsack Problem (0-1 Knapsack Problem)<\/a>\n<\/p>\n

\n\t<\/a>Module 5: Graph Theory Algorithms<\/span><\/u>
\n<\/h4>\n

\n\tDepth First Search on Directed Graph<\/a>\n<\/p>\n

\n\tDepth First Search and Articulation Points<\/a>\n<\/p>\n

\n\tBreadth First Search and 2-Colorability of Graphs<\/a>\n<\/p>\n

\n\tTopological Sort on DAGs and Proof for Neccessary and Sufficient Condition<\/a>\n<\/p>\n

\n\tDijkstra's Algorithm for Shortest Path Trees and Proof for Correctness<\/a>\n<\/p>\n

\n\tBellman-Ford Algorithm for Shortest Path Trees and Examples<\/a> New!!<\/span>\n<\/p>\n

\n\tKruskal's Algorithm: Examples to find Minimum Spanning Trees<\/a>\n<\/p>\n

\n\tKruskal's Algorithm: Proof of Correctness<\/a>\n<\/p>\n

\n\tProperties (1 and 2) of Minimum Spanning Tree: IJ-Cut and Minimum Weight Edge<\/a>\n<\/p>\n

\n\tProperties (3 and 4) of Minimum Spanning Tree: A graph with unique edge weights has only one minimum spanning tree<\/a>\n<\/p>\n

\n\tProperty 5 of Minimum Spanning Tree: Given a graph with unique edge weights, the largest weight edge in any cycle cannot be part of any minimum spanning tree<\/a>\n<\/p>\n

\n\tPrim's Algorithm for Minimum Spanning Trees and Proof for Correctness<\/a>\n<\/p>\n

\n\t<\/a>Floyd's All Pairs Shortest Paths Algorithm<\/b>\n<\/p>\n

\n\tPart 1<\/a> Part 2<\/a> Part 3<\/a> Part 4<\/a> Part 5<\/a> Part 6<\/a> Part 7<\/a>\n<\/p>\n

\n\t<\/a>Module 6: P, NP and NP-Complete Problems<\/span><\/u>
\n<\/h4>\n

\n\tPolynomial Reduction: Hamiltonian Circuit to Traveling Salesman Problem<\/a>\n<\/p>\n

\n\tMinimal Number of Uncovered Neighbors Heuristic: Example to determine an Independent Set, Vertex Cover and Clique<\/a>\n<\/p>\n

\n\tPolynomial Reductions: Independent Set, Clique and Vertex Cover<\/a>\n<\/p>\n

\n\tMulti-fragment Heuristic for the Traveling Salesman Problem<\/a>\n<\/p>\n

\n\tTwice around the tree Heuristic for the Traveling Salesman Problem and the Proof for approximation ratio<\/a>\n<\/p>\n

\n\t \n<\/p>\n

\n\t \n<\/p>\n

\n\t \n<\/p>\n

\n\t<\/a>Quiz, Exam and Project Schedules
\n<\/h3>\n

\n\t\"\"<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Quiz 7 due in my office ENB 275 by Dec. 3rd, 1 PM (slide under the door) EXAM 3 posted in Canvas (to be taken in Canvas as a quiz; to be completed by Dec. 3rd, 1 PM)   —————————————————–   Syllabus Teaching Assistant Lecture Slides Question Bank Project Descriptions Quizzes and Exams Code Tutorial […]<\/p>\n","protected":false},"author":168,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/2825"}],"collection":[{"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/users\/168"}],"replies":[{"embeddable":true,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/comments?post=2825"}],"version-history":[{"count":49,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/2825\/revisions"}],"predecessor-version":[{"id":3030,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/2825\/revisions\/3030"}],"wp:attachment":[{"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/media?parent=2825"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}