{"id":1986,"date":"2018-01-16T05:56:03","date_gmt":"2018-01-16T10:56:03","guid":{"rendered":"https:\/\/www.jsums.edu\/nmeghanathan\/?page_id=1986"},"modified":"2018-04-14T21:10:06","modified_gmt":"2018-04-15T02:10:06","slug":"csc323-sp2018","status":"publish","type":"page","link":"https:\/\/www.jsums.edu\/nmeghanathan\/csc323-sp2018\/","title":{"rendered":"CSC 323 Algorithm Design and Analysis, Spring 2018"},"content":{"rendered":"

Exam 3 (Take Home; Due on April 24th at 1 PM; submit in my office, ENB 275)<\/a><\/span><\/p>\n

Reading List for Quiz 7 (in class Quiz, Closed Notes, on April 17th)<\/a><\/span><\/p>\n

Projects 6 – 8 <\/b> posted. Check in Canvas.
\nSee Canvas.<\/p>\n

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

Syllabus<\/a>
\n
Lecture Slides<\/a>
\n
\nQuestion Bank<\/a>
\n
\nProject Descriptions<\/a>
\n
\nQuizzes and Exams<\/a>
\n
\nCode Tutorial<\/a>
\n
\nDr. Meg’s Desktop Selected Lecture Videos<\/a>
\n
\nQuiz, Exam and Project Schedules<\/a><\/p>\n

<\/p>\n

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

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

CSC323 Syllabus, Spring 2018<\/a><\/span><\/p>\n

<\/p>\n

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

Module 1: Algorithm Efficiency Analysis<\/a> (Updated – version #4<\/b>. Right click and Reload your page to get the latest version)<\/span><\/p>\n

<\/p>\n

Module 2: Divide and Conquer<\/a>
(Updated – version #1<\/b>. Right click and Reload your page to get the latest version)<\/span><\/p>\n

<\/p>\n

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

<\/p>\n

Module 4: Dynamic Programming<\/a>(Updated – version #2<\/b>. Right click and Reload your page to get the latest version)<\/span><\/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

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

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

<\/p>\n

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

<\/p>\n

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

<\/p>\n

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

<\/p>\n

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

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

Project 1: Brute Force Algorithm for Element Uniqueness Problem (Due by: Feb. 8th 1 PM)<\/a><\/span>
Check Canvas for Startup Code<\/p>\n

Project 2: Implementation and Performance Comparison of the Bubble Sort and Insertion Sort Algorithms (Due by: Feb. 15th, 1 PM)<\/a><\/span><\/p>\n

Project 3: 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 by: March 1st, 1 PM)<\/a><\/span>
Check Canvas for Sample Code on Hashtables and a Startup Code for the Project<\/p>\n

Project 4: Recursive Algorithm to Find the Minimum Integer in an Array and its Space-Time Tradeoff Performance Comparison Analysis with an Iterative Algorithm (Due by: March 8th, 1 PM)<\/a><\/span><\/p>\n

Project 5: Dynamic Programming Algorithm for Optimum Coin Collection in a Two-Dimensional Grid (Due by: March 29th, 1 PM, Submission in Canvas)<\/a><\/span><\/p>\n

Project 6: Dynamic Programming-based Solution for the Longest Common Subsequence Problem (Due by: April 5th, 1 PM, Submission in Canvas)<\/a><\/span><\/p>\n

Project 7: Use the Results of Depth First Search to Assign Directions to an Undirected Graph and Obtain a Directed Acyclic Graph (DAG) (Due by: April 12th, 1 PM, Submission in Canvas)<\/a><\/span><\/p>\n

Project 8: Use the Results of Breadth First Search to Extract the Shortest Paths from a Particular Vertex to the Rest of the Vertices in an Undirected Graph (Due by: April 19th, 1 PM, Submission in Canvas)<\/a><\/span><\/p>\n

 <\/p>\n

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

Quiz 5 (Programming Quiz: Take Home): Implementation of the Greedy Algorithm to Determine an Optimal Allocation of Files in a Tape to Minimize the Average Cost to Access the Files<\/u>, Due on March 27th @ 1 PM (Submission through Canvas)<\/a><\/span><\/p>\n

Exam 2 (Take Home): Due on March 20th @ 1 PM, in class<\/a><\/span><\/p>\n

Exam 1 (Take Home): Due on Feb. 20th @ 1 PM, in class<\/a><\/span><\/p>\n

Quiz 3 (Take Home): Due on Feb. 27th @ 1 PM, in class<\/a><\/span><\/p>\n

Quiz 4 (Take Home): Due on March 6th @ 1 PM, Submit in Canvas<\/a><\/span><\/p>\n

Quiz 5 (Take Home): Due on March 27th @ 1 PM, Submit in Canvas<\/a><\/span><\/p>\n

Quiz 6 (Take Home): Due on April 3rd @ 1 PM (Hard copy in class)<\/a><\/span><\/p>\n

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

 <\/p>\n

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

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

 <\/p>\n

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

Module 1: Analyzing the Efficiency of Algorithms<\/span><\/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

<\/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

Module 2: Classical Algorithm Design Techniuqes<\/span><\/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

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

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

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

Module 4: Dynamic Programming<\/span><\/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

<\/a>Module 5: Graph Theory Algorithms<\/span><\/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!!<\/span><\/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

<\/a>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

<\/a>Module 6: P, NP and NP-Complete Problems<\/span><\/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>Quiz, Exam and Project Schedules\"\"<\/a><\/h3>\n

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

Exam 3 (Take Home; Due on April 24th at 1 PM; submit in my office, ENB 275) Reading List for Quiz 7 (in class Quiz, Closed Notes, on April 17th) Projects 6 – 8 posted. Check in Canvas. See Canvas. —————————————————– Syllabus Lecture Slides Question Bank Project Descriptions Quizzes and Exams Code Tutorial Dr. Meg’s […]<\/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\/1986"}],"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=1986"}],"version-history":[{"count":67,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/1986\/revisions"}],"predecessor-version":[{"id":2301,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/1986\/revisions\/2301"}],"wp:attachment":[{"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/media?parent=1986"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}