{"id":1013,"date":"2016-08-23T01:13:05","date_gmt":"2016-08-23T06:13:05","guid":{"rendered":"https:\/\/www.jsums.edu\/nmeghanathan\/?page_id=1013"},"modified":"2016-12-01T22:41:08","modified_gmt":"2016-12-02T03:41:08","slug":"csc323-fall2016","status":"publish","type":"page","link":"https:\/\/www.jsums.edu\/nmeghanathan\/csc323-fall2016\/","title":{"rendered":"CSC 323 Algorithm Design and Analysis, Fall 2016"},"content":{"rendered":"

\n\tExam 3 (Take Home Part) posted. Click here<\/span><\/a>.<\/span><\/a><\/strong> Due on: Dec. 6 @ 9 AM  in Room ENB 212. <\/strong><\/span>\n<\/p>\n

\n\tExam 3 (In-class Part) Reading List posted. Click here.<\/span><\/a><\/strong>\n<\/p>\n

\n\tExam 3 (In-class Part) will be on Dec. 6 @ 9 AM in Room ENB 212.<\/strong><\/span>\n<\/p>\n

\n\tQuiz 8 (Take Home) posted. Due on: Dec. 1 @ 11.30 AM.<\/span> <\/strong><\/span>  NO late submissions!\n<\/p>\n

\n\tTERM PROJECT PRESENTATION SCHEDULE<\/span><\/a><\/strong><\/span>\n<\/p>\n

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

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

\n\tSyllabus<\/a>
\n\tLecture Slides<\/a>
\n\tQuestion Bank<\/a>
\n\tProject Descriptions<\/a>
\n\tTerm Project<\/a>
\n\tQuizzes and Exams<\/a>
\n\tCode Tutorial<\/a>
\n\tDr. Meg's Desktop Selected Lecture Videos<\/a>
\n\tQuiz, Exam and Project Schedules<\/a>\n<\/p>\n

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

\n\tSyllabus<\/a>
\n<\/h3>\n

\n\tCSC 323 Syllabus, Fall 2016<\/a><\/span>\n<\/p>\n

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

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

\n\tModule 2 – Classical Design Techniques<\/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: NP-Complete Problems and Heuristics<\/span><\/a>\n<\/p>\n

\n\tQuestion Bank<\/a>
\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\tProject Descriptions<\/a>
\n<\/h3>\n

\n\tProject 1: Element Uniqueness Problem, Due: Sept. 29<\/a><\/span>\n<\/p>\n

\n\tProject 2: Iterative vs. Recursive Algorithms to Compute the Factorial of an Integer<\/a><\/span>, Due: Oct. 13\n<\/p>\n

\n\tProject 3: Binary Search vs. Brute Force Search Algorithms for Finding a Local Minimum in a Two-Dimensional Array, Due: Oct. 27<\/a><\/span>\n<\/p>\n

\n\tProject 4: Optimum Coin Collection in a Two-Dimensional Grid, Due: Nov. 17<\/a><\/span>\n<\/p>\n

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

\n\tTerm Project<\/a>
\n<\/h3>\n

\n\tTerm Project Descriptions and Team Assignments<\/a><\/span><\/strong>\n<\/p>\n

\n\tTeam 1: <\/strong>Algesa Haywood Jr., Brian Williams, Michael D. Moore\n<\/p>\n

\n\tTeam 2: <\/strong>Kabinad Melaku, <\/span>Kirubel Benalfew, YosefGetachew<\/span>\n<\/p>\n

\n\tTeam 3: <\/strong>Karmeen Powell-Childress & Deonta Kilpatrick<\/span>\n<\/p>\n

\n\tTeam 4: <\/strong>Quavanti Hart, Nicholas Whitfield, Alishia Harmon<\/span>\n<\/p>\n

\n\tTeam 5: <\/strong> Darius Leroy, Ladarius Felix, Shawndon Portis<\/span>\n<\/p>\n

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

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

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

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

\n\tQuiz 1 Solutions<\/a><\/span>\n<\/p>\n

\n\tQuiz 3 (Take Home): Due on Oct. 4 at 11.30 AM<\/a><\/span>\n<\/p>\n

\n\tQuiz 4 and Bonus Quiz 1 (Take Home): Due on Oct. 11 at 11.30 AM<\/a><\/span>\n<\/p>\n

\n\tQuiz 6 (Take Home; Due: Oct. 25 @ 11.30 AM)<\/a><\/span>\n<\/p>\n

\n\tExam 2 (Take Home; Due: Nov. 1 @ 11.30 AM)<\/a><\/span>\n<\/p>\n

\n\tQuiz 7 (Take Home: Due on Nov. 10 @ 11.30 AM)<\/a><\/span>\n<\/p>\n

\n\tQuiz 8 (Take Home) posted. Due on: Dec. 1 @ 11.30 AM<\/a><\/span>\n<\/p>\n

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

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

\n\tBasics of Vector Class<\/a><\/span>\n<\/p>\n

\n\tPopulating a 1-dim and 2-dim Array with Elements in Random Order chosen from a Vector that has the Elements in Sequential Order<\/a><\/span>\n<\/p>\n

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

\n\tDr. Meg's Desktop Selected Lecture Videos (YouTube Links)<\/a><\/font>
\n<\/h3>\n

\n\tModule 1 (Chapter 2): Analyzing the Efficiency of Algorithms<\/font><\/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\tModule 2 (Chapters 3-6): Classical Algorithm Design Techniuqes<\/font><\/u>
\n<\/h4>\n

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

\n\tDecrease and Conquer – Insertion Sort Algorithm and Examples<\/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\tModule 3 (Chapter 9): Greedy Technique<\/font><\/a><\/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 (Chapter 8): Dynamic Programming<\/font><\/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\tModule 5: Graph Theory Algorithms<\/font><\/a><\/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!!<\/font>\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\tFloyd's All Pairs Shortest Paths Algorithm<\/b><\/a>
\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\tModule 6: P, NP and NP-Complete Problems<\/font><\/a><\/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\tQuiz, Exam and Project Schedules<\/a>
\n<\/h3>\n

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

\n\t\"csc323-fall2016-schedule-upd-nov-10\"<\/a>\n<\/p>\n

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

\n\t