{"id":3355,"date":"2020-08-18T05:13:54","date_gmt":"2020-08-18T10:13:54","guid":{"rendered":"https:\/\/www.jsums.edu\/nmeghanathan\/?page_id=3355"},"modified":"2020-09-23T21:20:28","modified_gmt":"2020-09-24T02:20:28","slug":"csc323-fall2020","status":"publish","type":"page","link":"https:\/\/www.jsums.edu\/nmeghanathan\/csc323-fall2020\/","title":{"rendered":"CSC 323 Algorithm Design and Analysis, Fall 2020"},"content":{"rendered":"

Assignments 1, 2 and Exam 1<\/span> <\/strong>posted.<\/p>\n

 <\/p>\n

\n

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

CSC323 Syllabus, Fall 2020<\/a><\/strong><\/p>\n

 <\/p>\n

<\/a>Teaching Assistants (TAs)<\/strong><\/p>\n

Landrie Tchakoua
<\/span><\/strong>Zoom (Meeting ID: 816 538 7125)<\/span>
Tuesday 10 AM to 12 PM<\/span>
Wednesday 12 PM to 4 PM<\/span>
Thursday 10 AM to 12 PM; 4 PM to 6 PM<\/span>


Oluwaseun Akintade<\/strong>
Google Meet Link:\u00a0<\/span>https:\/\/meet.google.com\/jqv-druy-njz\u00a0(Links to an external site.)<\/span><\/a>
Monday 12 PM to 6 PM<\/span>
Wednesday 11 AM to 3 PM<\/span>
Friday 1 PM to 5 PM<\/span><\/p>\n

 <\/p>\n

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

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

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

Module 3: Binary Search<\/a><\/p>\n

Module 4: Greedy Strategy<\/a><\/p>\n

Module 5: Dynamic Programming<\/a><\/p>\n

Sample C++ Code and Explanation on dynamically creating and using a two-dimensional array<\/a><\/p>\n

Module 6: Graph Algorithms<\/a><\/p>\n

Module 7: P, NP, NP-Complete Problems<\/a><\/p>\n

 <\/p>\n

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

Algorithm Efficiency Analysis<\/a><\/p>\n

Classical Design Techniques<\/a> (includes Divide and Conquer, Binary Search)<\/p>\n

Greedy Strategy<\/a><\/p>\n

Dynamic Programming<\/a><\/p>\n

Graph Theory Algorithms<\/a><\/p>\n

<\/a>Assignments<\/strong><\/h3>\n

Assignment 1: Brute Force Algorithm for the Element Uniqueness Problem, Due: Sept. 8th, 11.59 PM<\/a><\/b><\/p>\n

Assignment 2: 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, Due: Sept. 15th, 2020, by 11.59 PM<\/a><\/strong><\/p>\n

Check Canvas for Code<\/p>\n

 <\/p>\n

 <\/p>\n

<\/a>Exams<\/strong><\/h3>\n

Exam 1 (covers Modules 1 and 2); Due by Sept. 24th, 11.59 PM<\/a><\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

<\/a>Dr. Meg’s Desktop Selected Lecture Videos (YouTube Links)<\/strong><\/h3>\n

Analyzing the Efficiency of Algorithms<\/u><\/h4>\n

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

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

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

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

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

Classical Algorithm Design Techniuqes<\/u><\/h4>\n

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

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

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

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

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

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

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

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

Greedy Technique<\/u><\/h4>\n

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

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

Dynamic Programming<\/u><\/h4>\n

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

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

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

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

Graph Theory Algorithms<\/u><\/h4>\n

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

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

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

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

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

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

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

Kruskal’s Algorithm: Proof of Correctness<\/a><\/p>\n

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

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

Property 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><\/p>\n

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

Floyd’s All Pairs Shortest Paths Algorithm<\/b><\/p>\n

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

P, NP and NP-Complete Problems<\/u><\/h4>\n

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

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

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

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

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

 <\/p>\n

 <\/p>\n

 <\/p>\n

<\/a>Assignment and Exam Schedules<\/h3>\n

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

Assignments 1, 2 and Exam 1 posted.   Syllabus CSC323 Syllabus, Fall 2020   Teaching Assistants (TAs) Landrie TchakouaZoom (Meeting ID: 816 538 7125)Tuesday 10 AM to 12 PMWednesday 12 PM to 4 PMThursday 10 AM to 12 PM; 4 PM to 6 PMOluwaseun AkintadeGoogle Meet Link:\u00a0https:\/\/meet.google.com\/jqv-druy-njz\u00a0(Links to an external site.)Monday 12 PM to 6 […]<\/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\/3355"}],"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=3355"}],"version-history":[{"count":16,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/3355\/revisions"}],"predecessor-version":[{"id":3434,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/3355\/revisions\/3434"}],"wp:attachment":[{"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/media?parent=3355"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}