{"id":75,"date":"2015-04-30T23:59:58","date_gmt":"2015-05-01T04:59:58","guid":{"rendered":"https:\/\/www.jsums.edu\/nmeghanathan\/?page_id=75"},"modified":"2015-05-01T02:19:26","modified_gmt":"2015-05-01T07:19:26","slug":"csc-323-algorithm-design-and-analysis-spring-2015","status":"publish","type":"page","link":"https:\/\/www.jsums.edu\/nmeghanathan\/csc-323-algorithm-design-and-analysis-spring-2015\/","title":{"rendered":"CSC 323 Algorithm Design and Analysis, Spring 2015"},"content":{"rendered":"

\n\tInstructor: Dr. Natarajan Meghanathan
\n<\/h4>\n

\n\t—————————————————–
\n\tSyllabus<\/a>
\n\tLecture Slides<\/a>
\n\tProject Descriptions<\/a>
\n\tDr. Meg's Desktop Selected Lecture Videos<\/a>
\n\tQuiz, Exam and Project Schedules<\/a>
\n\t—————————————————–\n<\/p>\n

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

\n\tCSC 323 Syllabus, Spring 2015<\/a>\n<\/p>\n

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

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

\n\tModule 2: Classical Design Techniques<\/a>\n<\/p>\n

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

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

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

\n\tModule 6: NP Complete Problems and Approximation Heuristics<\/a>\n<\/p>\n

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

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

\n\tProject 1: Element Uniqueness Problem<\/a>, Due: Feb. 12\n<\/p>\n

\n\tProject 2: Comparing the Performance of a Recursive vs. a Non-Recursive Algorithm to Determine the Index of the Element with the Largest Value in an Array<\/a>, Due: Feb. 19\n<\/p>\n

\n\tProject 3: Computing the Number of Paths of a Certain Length in a Graph using Matrix Multiplication<\/a>, Due: March 5\n<\/p>\n

\n\tProject 4: Determining the Common Elements across All Arrays using Hash Tables and Java Collection Classes<\/a>\n<\/p>\n

\n\tVideo Explanation: Vector Example<\/a>        Video Explanation: TreeMap Example<\/a>\n<\/p>\n

\n\tProject 5: Coin Collection Problem using Dynamic Programming<\/a>\n<\/p>\n

\n\tProject 6: Theorem Proving Project: Bloom Filters, Breadth First Search and Asymptotic Complexity<\/a>\n<\/p>\n

\n\tProject 7: Theorem Proving Project: Topological Sort (DAG), Dijkstra Algorithm and Bellman-Ford Algorithm<\/a>\n<\/p>\n

\n\t \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: Coin-Collecting Problem for a Robot 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\tQuiz, Exam and Project Schedules<\/a>
\n<\/h3>\n

\n\t\"CSC<\/a>\n<\/p>\n

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

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

Instructor: Dr. Natarajan Meghanathan —————————————————– Syllabus Lecture Slides Project Descriptions Dr. Meg's Desktop Selected Lecture Videos Quiz, Exam and Project Schedules —————————————————– Syllabus CSC 323 Syllabus, Spring 2015 Lecture Slides Module 1: Algorithm Efficiency Analysis Module 2: Classical Design Techniques Module 3: Greedy Strategy Module 4: Dynamic Programming Module 5: Graph Theory Algorithms Module 6: […]<\/p>\n","protected":false},"author":168,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"open","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\/75"}],"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=75"}],"version-history":[{"count":25,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/75\/revisions"}],"predecessor-version":[{"id":118,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/75\/revisions\/118"}],"wp:attachment":[{"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/media?parent=75"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}