CSC 228 Data Structures and Algorithms, Fall 2017 - Natarajan Meghanathan, Professor of Computer Science, Jackson State University

Exam 3 (on Dec. 6th: 1 PM to 2.50 PM): Module 9 (Slides 1-47): Open Notes

—————————————————-

Syllabus
Lecture Slides
Lecture Code (C++)
Lecture Code (Java)
Project Descriptions
Quizzes and Exams
Quiz, Exam and Project Schedules

Information about Teaching Assistants

—————————————————–

Syllabus

CSC228 Syllabus, Fall2017

Lecture Slides

Module 1:Asymptotic Time Complexity and Intro to Abstract Data Types

Module 2 – List ADT

Module 3 – Stack ADT

Module 4 – Queue ADT

Module 5 – Dictionary ADT: Hash tables

Module 6 – Binary Trees

Module 7 – Binary Search Trees

Module 8 – Heap

Module 9 – Graphs

Lecture Code (C++)

Module 2: List ADT

Code 1: Static List Implementation using Arrays

Code 2: Dynamic List Implementation using Arrays

Code 3: Singly Linked List

Code 4: Recursion and Random Number Generation

Code 5: Reversing a Singly Linked List

Module 3: Stack ADT

Code 1: Dynamic Array based Stack

Code 2: Doubly Linked List based Stack

Code 3: Example to Illustrate String Processing in C++

Code 4: Using Stack to Check for Parenthesis Balance

Code 5: Example to Illustrate String Tokenizing in C++

Code 6: Evaluation of an Expression in PostFix Format using Stack

Module 4: Queue ADT

Code 1: Dynamic Array based Queue

Code 2: Doubly Linked List based Queue

Module 5: Dictionary ADT: Hashtable

Code 1: Singly Linked List-based Implementation of Hashtable

Code 2: Use of Hashtable to Determine whether two Integer Sequences are Permutations of each other

Code 3: Use of Hashtable to Print the Unique Elements in an Array

Code 4: Use of Hashtable to Determine the Union (with unique elements) of Two Linked Lists (that may have duplicates)

Module 6: Binary Trees

Code 1: To Read Text from a File

Code 2: Implementation of Binary Trees

Code 3: Use of Breadth First Search to Determine the Depth of the Nodes in a Binary Tree

Code 4: Preorder Traversal of a Binary Tree

Module 7: Binary Search Trees

Code 1: Construction of a Binary Search Tree (Input: Sorted Array of Integers)

Code 2: Selection Sort

Code 3: Construction of a Binary Search Tree (Input: Randomly Generated Array of Integers)

Code 4: Searching for a Key in a Binary Search Tree

Lecture Code (Java)

Module 2: List ADT

Code 1: Static List Implementation using Arrays

Code 2: Dynamic List Implementation using Arrays

Code 3: Singly Linked List

Code 4: Recursion and Random Number Generation

Code 5: Reversing a Singly Linked List

Module 3: Stack ADT

Code 1: Dynamic Array based Stack

Code 2: Doubly Linked List based Stack

Code 3: Example to Illustrate String Processing in Java

Code 4: Using Stack to Check for Parenthesis Balance

Code 5: Example to Illustrate String Tokenizing in Java

Code 6: Evaluation of an Expression in PostFix Format using Stack

Module 4: Queue ADT

Code 1: Dynamic Array based Queue

Code 2: Doubly Linked List based Queue

Module 5: Dictionary ADT: Hashtable

Code 1: Singly Linked List-based Implementation of Hashtable

Code 2: Use of Hashtable to Determine whether two Integer Sequences are Permutations of each other

Code 3: Use of Hashtable to Print the Unique Elements in an Array

Code 4: Use of Hashtable to Determine the Union (with unique elements) of Two Linked Lists (that may have duplicates)

Module 6: Binary Trees

Code 1: To Read Text from a File

Code 2: Implementation of Binary Trees

Code 3: Use of Breadth First Search to Determine the Depth of the Nodes in a Binary Tree

Code 4: Preorder Traversal of a Binary Tree

Module 7: Binary Search Trees

Code 1: Construction of a Binary Search Tree (Input: Sorted Array of Integers)

Code 2: Selection Sort

Code 3: Construction of a Binary Search Tree (Input: Randomly Generated Array of Integers)

Code 4: Searching for a Key in a Binary Search Tree

Project Descriptions

Bonus Project 1 (Due: Aug 30, 1 PM)

Project 1: List ADT – Dynamic Arrays (Due: Sept. 13, 1 PM)

Project 2: Implementation of Recursive Print and Merge List Functions for
Singly Linked List (Due: Sept. 27, 1 PM)
Check Canvas for the startup code

Project 3: Finding the Next Greater Element of an Element in an Array in Θ(n) Time (Due: Oct. 4, 1 PM)
Project Idea
Check Canvas for the startup code

Project 4: Stack-based Implementation of Queue (Due: Oct. 11, 1 PM)
Check Canvas for the startup code

Project 5: Using Hashtables to Print the Duplicate Elements in an Array exactly once (Due: Oct. 18, 1 PM)
Check Canvas for the startup code

Project 6: Checking whether a binary tree is height-balanced or not. (Due: Oct. 27, 1 PM)
Check Canvas for the startup code

Project 7: Binary Trees: Checking for Complete Binary Tree and Binary Search Tree (Due: Nov. 3, 1 PM)
Check Canvas for the startup code

Project 8: Binary Search Tree: Average Number of Comparisons for a Successful Search (Due: Nov. 10, 1 PM)
Check Canvas for the startup code

Project 9: Binary Search Tree: Lowest Common Ancestor Node for Two Keys (Due: Nov. 17, 1 PM)
Check Canvas for the startup code

Project 10: Binary Tree: Checking for a Max Heap (Due: Nov. 29, 1 PM)
Check Canvas for the startup code

Quizzes and Exams

Quiz 2 (Take Home); Due on Sept. 18 by 1 PM (Check Canvas for the Code and other instructions)

Exam 1 (Take Home); Due on Oct. 2 by 1 PM (Check Canvas for the Code and other instructions)

Exam 2 (Take Home); Due on Nov. 13 1 PM (Check Canvas for other instructions)

Quiz 3 (Take Home); Due on Oct. 9 by 1 PM (Check Canvas for the Code and other instructions)

Quiz 4 Solutions

Quiz 5 Solutions

Quiz 6 Solutions

Quiz 7 (Take Home); Due on Nov. 6 by 1 PM (Check Canvas for the Code and other instructions)