{"id":2027,"date":"2018-01-22T06:11:26","date_gmt":"2018-01-22T11:11:26","guid":{"rendered":"https:\/\/www.jsums.edu\/nmeghanathan\/?page_id=2027"},"modified":"2018-04-17T18:15:09","modified_gmt":"2018-04-17T23:15:09","slug":"csc228-01-sp2018","status":"publish","type":"page","link":"https:\/\/www.jsums.edu\/nmeghanathan\/csc228-01-sp2018\/","title":{"rendered":"CSC 228 Data Structures and Algorithms (1 PM class), Spring 2018"},"content":{"rendered":"

Exam 3 – Take Home Part (Due on April 25th, Wednesday, at 1 PM, submit a hardcopy in-class)<\/a><\/p>\n

Exam 3 – Reading List for In-class Part<\/a><\/p>\n

Exam 3 (In-class Part) will be on April 25th, Wednesday, from 1 PM to 2.50 PM; OPEN notes <\/b><\/p>\n

Projects 7-10 <\/b> posted. Check in Canvas<\/p>\n

Quiz 7-8 posted. All Take Home. Check in Canvas.<\/p>\n

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

Syllabus<\/a>
\nLecture Slides<\/a>
\nLecture Code (C++)<\/a>
\nProject Descriptions<\/a>
\nQuizzes and Exams<\/a>
\nQuiz, Exam and Project Schedules<\/a><\/p>\n

\n <\/p>\n

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

CSC228 Syllabus (1 PM class), Spring 2018<\/a><\/span><\/p>\n

<\/p>\n

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

\nModule 1:Asymptotic Time Complexity and Intro to Abstract Data Types<\/a><\/p>\n

Module 2 – List ADT<\/a><\/p>\n

Module 3 – Stack ADT<\/a><\/p>\n

Module 4 – Queue ADT<\/a><\/p>\n

Module 5 – Dictionary ADT: Hash tables <\/a><\/p>\n

Module 6 – Binary Trees<\/a><\/p>\n

Module 7 – Binary Search Trees<\/a><\/p>\n

Module 8 – Heap<\/a><\/p>\n

Module 9 – Graphs<\/a><\/p>\n

<\/a>Lecture Code (C++)<\/h3>\n

\nModule 2: List ADT<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>Static List Implementation using Arrays<\/a><\/span><\/p>\n

Code 2:<\/strong> Dynamic List Implementation using Arrays<\/a><\/span><\/p>\n

Code 3: <\/strong>Singly Linked List<\/a><\/span><\/p>\n

Code 4: <\/strong>Recursion and Random Number Generation<\/a><\/span><\/p>\n

Code 5: <\/strong>Reversing a Singly Linked List<\/a><\/span><\/p>\n

Code 6: <\/strong>Run Time Complexity Analysis<\/a><\/span><\/p>\n

Module 3: Stack ADT<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>Dynamic Array based Stack<\/a><\/span><\/p>\n

Code 2:<\/strong> Doubly Linked List based Stack<\/a><\/span><\/p>\n

Code 3: <\/strong>Example to Illustrate String Processing in C++<\/a><\/span><\/p>\n

Code 4: <\/strong>Using Stack to Check for Parenthesis Balance<\/a><\/span><\/p>\n

Code 5: <\/strong>Example to Illustrate String Tokenizing in C++<\/a><\/span><\/p>\n

Code 6: <\/strong>Evaluation of an Expression in PostFix Format using Stack<\/a><\/span><\/p>\n

Module 4: Queue ADT<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>Dynamic Array based Queue<\/a><\/span><\/p>\n

Code 2:<\/strong> Doubly Linked List based Queue<\/a><\/span><\/p>\n

Module 5: Dictionary ADT: Hashtable<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>Singly Linked List-based Implementation of Hashtable<\/a><\/span><\/p>\n

Code 2: <\/strong>Use of Hashtable to Determine whether two Integer Sequences are Permutations of each other<\/a><\/span><\/p>\n

Code 3: <\/strong>Use of Hashtable to Print the Unique Elements in an Array<\/a><\/span><\/p>\n

Code 4: <\/strong>Use of Hashtable to Determine the Union (with unique elements) of Two Linked Lists (that may have duplicates)<\/a><\/span><\/p>\n

Module 6: Binary Trees<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>To Read Text from a File<\/a><\/span><\/p>\n

Code 2: <\/strong>Implementation of Binary Trees<\/a><\/span><\/p>\n

Code 3: <\/strong>Use of Breadth First Search to Determine the Depth of the Nodes in a Binary Tree<\/a><\/span><\/p>\n

Code 4: <\/strong>Preorder Traversal of a Binary Tree<\/a><\/span><\/p>\n

<\/p>\n

Module 7: Binary Search Trees<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>Construction of a Binary Search Tree (Input: Sorted Array of Integers)<\/a><\/span><\/p>\n

Code 2: <\/strong>Selection Sort<\/a><\/span><\/p>\n

Code 3: <\/strong>Construction of a Binary Search Tree (Input: Randomly Generated Array of Integers)<\/a><\/span><\/p>\n

Code 4: <\/strong>Searching for a Key in a Binary Search Tree<\/a><\/span><\/p>\n

<\/a>Lecture Code (Java)<\/h3>\n

Module 2: List ADT<\/strong><\/span><\/p>\n

Code 1: <\/strong>Static List Implementation using Arrays<\/a><\/span><\/p>\n

Code 2: <\/strong>Dynamic List Implementation using Arrays<\/a><\/span>
\n
\nCode 3: <\/strong>Singly Linked List<\/a><\/span><\/p>\n

Code 4: <\/strong>Recursion and Random Number Generation<\/a><\/span><\/p>\n

Code 5: <\/strong>Reversing a Singly Linked List<\/a><\/span><\/p>\n

<\/p>\n

Module 3: Stack ADT<\/strong><\/span><\/p>\n

Code 1: <\/strong>Dynamic Array based Stack<\/a><\/span><\/p>\n

Code 2:<\/strong> Doubly Linked List based Stack<\/a><\/span><\/p>\n

Code 3: <\/strong>Example to Illustrate String Processing in Java<\/a><\/span><\/p>\n

Code 4: <\/strong>Using Stack to Check for Parenthesis Balance<\/a><\/span><\/p>\n

Code 5: <\/strong>Example to Illustrate String Tokenizing in Java<\/a><\/span><\/p>\n

Code 6: <\/strong>Evaluation of an Expression in PostFix Format using Stack<\/a><\/span><\/p>\n

<\/p>\n

Module 4: Queue ADT<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>Dynamic Array based Queue<\/a><\/span><\/p>\n

Code 2:<\/strong> Doubly Linked List based Queue<\/a><\/span><\/p>\n

<\/p>\n

Module 5: Dictionary ADT: Hashtable<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>Singly Linked List-based Implementation of Hashtable<\/a><\/span><\/p>\n

Code 2: <\/strong>Use of Hashtable to Determine whether two Integer Sequences are Permutations of each other<\/a><\/span><\/p>\n

Code 3: <\/strong>Use of Hashtable to Print the Unique Elements in an Array<\/a><\/span><\/p>\n

Code 4: <\/strong>Use of Hashtable to Determine the Union (with unique elements) of Two Linked Lists (that may have duplicates)<\/a><\/span><\/p>\n

Module 6: Binary Trees<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>To Read Text from a File<\/a><\/span><\/p>\n

Code 2: <\/strong>Implementation of Binary Trees<\/a><\/span><\/p>\n

Code 3: <\/strong>Use of Breadth First Search to Determine the Depth of the Nodes in a Binary Tree<\/a><\/span><\/p>\n

Code 4: <\/strong>Preorder Traversal of a Binary Tree<\/a><\/span><\/p>\n

<\/p>\n

Module 7: Binary Search Trees<\/strong><\/span><\/span><\/p>\n

Code 1: <\/strong>Construction of a Binary Search Tree (Input: Sorted Array of Integers)<\/a><\/span><\/p>\n

Code 2: <\/strong>Selection Sort<\/a><\/span><\/p>\n

Code 3: <\/strong>Construction of a Binary Search Tree (Input: Randomly Generated Array of Integers)<\/a><\/span><\/p>\n

Code 4: <\/strong>Searching for a Key in a Binary Search Tree<\/a><\/span><\/p>\n

<\/p>\n

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

Project 1 (Due on Feb. 7th, 1 PM): <\/strong>Algorithm Design and Time Complexity Analysis for Operations on the Dynamic Array Implementation of the List ADT<\/a><\/span>
\n   
\ncpp code:<\/strong>In a Word Document<\/a>
The code is also available in Canvas<\/span><\/p>\n

<\/p>\n

Project 2 (Due on Feb. 14th, 1 PM): <\/strong>Implementation of the Merge List Function (for Merger of Unique Elements) for Singly Linked List and the Time Complexity Analysis<\/a><\/span>
\n   
\ncpp code:<\/strong>In a Word Document<\/a>
Also, check Canvas for the code<\/span><\/p>\n

<\/p>\n

Project 3 (Due on Feb. 21st, 1 PM): <\/strong>Implementation of the Stack ADT using Singly Linked List and the Time Complexity Analysis of the Push and Pop Operations<\/a>
Check in Canvas for the code<\/span><\/p>\n

Project 4 (Due on Feb. 28th, 1 PM): <\/strong>Design and Implementation of an Algorithm to Find the Next Greater Element of the Elements in an Array in \u0398(n) Time<\/a>
Check in Canvas for the code<\/span><\/p>\n

Project 5 (Due on March 7th, 11.59 PM): <\/strong>Stack-based Implementation of Queue<\/a>
Check in Canvas for the code<\/span><\/p>\n

Project 6 (Due on March 21st, 11.59 PM): <\/strong>Binary Tree: Checking for Complete Binary Tree and Binary Search Tree<\/a>
Check in Canvas for the code<\/span><\/p>\n

Project 7 (Due on March 28th, 11.59 PM): <\/strong>Binary Tree: Design and Implementation of an Iterative Algorithm (using the Stack ADT) to do a Preorder Traversal of the Vertices<\/a>
Check in Canvas for the code and text files<\/span><\/p>\n

Project 8 (Due on April 4th, 11.59 PM): <\/strong>Binary Search Tree: Average Number of Comparisons for a Successful Search<\/a>
Check in Canvas for the code and text files<\/span><\/p>\n

Project 9 (Due on April 11th, 11.59 PM): <\/strong>Checking whether a Binary Tree is a Max Heap<\/a>
Check in Canvas for the code and text files<\/span><\/p>\n

Project 10 (Due on April 18th, 11.59 PM): <\/strong>Degree Distribution of the Vertices in a Graph<\/a>
Check in Canvas for the code and text files<\/span><\/p>\n

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

Exam 3 – Take Home Part (Due on April 25th, Wednesday, at 1 PM, submit a hardcopy in-class)<\/a><\/p>\n

Quiz 2: Take Home (Due on Feb. 9th, 1 PM): <\/strong>Dynamic Array Implementation of the List ADT: Doubling the List Size vs. Incrementing the List Size by One: Memory and Run Time Analysis<\/a><\/span>
\n   
\ncpp code:<\/strong>In a Word Document<\/a><\/span><\/p>\n

The code is also available in Canvas<\/p>\n

<\/p>\n

Quiz 3: Take Home (Due on Feb. 16th, 11.59 PM): <\/strong>Linked List vs. Dynamic Array Implementation of the List ADT: Impact of Insertion Index, Data Size and List Size: Memory and Run Time Analysis<\/a><\/span>
\n   
\ncpp code:<\/strong>In a Word Document<\/a><\/span><\/p>\n

The code is also available in Canvas<\/p>\n

<\/p>\n

Exam 1: Take Home (Due on Feb. 23rd, 11.59 PM): <\/strong>Covers Modules 2 and 3<\/a>     Check Canvas for Code<\/span><\/p>\n

Quiz 4: Take Home (Due on March 2nd, 11.59 PM): <\/strong>Determination of Maximum Depth of Nested Parentheses in an Expression and Evaluation of an Expression in Pre-fix Format<\/a>     Check Canvas for Code<\/span><\/p>\n

Quiz 5: Take Home (Due on March 9th, 11.59 PM): <\/strong>Hash table Tradeoff Analysis: Average Insertion Time vs. Load Imbalance Index<\/a>     Check Canvas for Code<\/span><\/p>\n

Quiz 6: Take Home (Due on March 23rd, 11.59 PM): <\/strong>Height-Balanced Binary Trees<\/a>     Check Canvas for Code<\/span><\/p>\n

Quiz 7: Take Home (Due on April 13th, 11.59 PM): <\/strong>Binary Search Tree: Lowest Common Ancestor Node<\/a>     Check Canvas for Code<\/span><\/p>\n

Quiz 8: Take Home (Due on April 20th, 11.59 PM): <\/strong>Breadth First Search on a Graph: Test for Bipartivity<\/a>     Check Canvas for Code<\/span><\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

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

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

Exam 3 – Take Home Part (Due on April 25th, Wednesday, at 1 PM, submit a hardcopy in-class) Exam 3 – Reading List for In-class Part Exam 3 (In-class Part) will be on April 25th, Wednesday, from 1 PM to 2.50 PM; OPEN notes Projects 7-10 posted. Check in Canvas Quiz 7-8 posted. All Take […]<\/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\/2027"}],"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=2027"}],"version-history":[{"count":63,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/2027\/revisions"}],"predecessor-version":[{"id":2308,"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/pages\/2027\/revisions\/2308"}],"wp:attachment":[{"href":"https:\/\/www.jsums.edu\/nmeghanathan\/wp-json\/wp\/v2\/media?parent=2027"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}