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

Exam 3 will be conducted in two parts: Both parts are in-class, OPEN notes. Part I will be tested on Wednesday, April 24th (1 PM to 1.50 PM) and Part II will be tested on Friday, April 26th (1 PM to 1.50 PM). Reading List for both parts

Projects 4-8 assigned.

Exam 2 and Quiz 5 assigned (both are Take Home Programming-based; Upload using Canvas)

Quiz 6 & Quiz 7 (Take Home; assigned together; Submit hardcopy of both the quizzes together in class on April 12th, 1 PM)

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

Syllabus

Lecture Slides

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

Syllabus

CSC228 Syllabus, Spring 2019

Teaching Assistant

TA Schedule

Lecture Slides

Module 1:Asymptotic Time Complexity and Intro to Abstract Data Types, C++ Code Review

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

Code 6: Run Time Complexity Analysis

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

Project 1 (Due on Feb. 20th, 11.59 PM): Algorithm Design and Time Complexity Analysis for Operations on the Dynamic Array Implementation of the List ADT

See Canvas for the code

Project 2 (Due on Feb. 27th, 11.59 PM): Implementation of the Merge List Function (for Merger of Unique Elements) for Singly Linked List and the Time Complexity Analysis

See Canvas for the code

Project 3 (Due on March 6th, 11.59 PM): Determination of Maximum Depth of Nested Parentheses in an Expression and Evaluation of an Expression in Pre-fix Format

See Canvas for the code

Project 4 (Due on March 20th, 11.59 PM): Hash table Tradeoff Analysis: Average Insertion Time vs. Load Imbalance Index

See Canvas for the code

Project 5 (Due on March 27th, 11.59 PM): Binary Tree: Design and Implementation of an Iterative Algorithm (using the Stack ADT) to do a Preorder Traversal of the Vertices

See Canvas for the code

Project 6 (Due on April 3rd, 11.59 PM): Binary Search Tree: Average Number of Comparisons for a Successful Search

See Canvas for the code

Project 7 (Due on April 10th, 11.59 PM): Binary Search Tree: Lowest Common Ancestor Node

See Canvas for the code

Project 8 (Due on April 17th, 11.59 PM): Checking whether a Binary Tree is a Max Heap

See Canvas for the code

Quizzes and Exams

Quiz 2 (Due on Feb. 15th, 11.59 PM): Dynamic Array Implementation of the List ADT: Doubling the List Size vs. Incrementing the List Size by One: Memory and Run Time Analysis

See Canvas for the code

Quiz 3 (Due on Feb. 22nd, 11.59 PM): Implementation of the Stack ADT using Singly Linked List and the Time Complexity Analysis of the Push and Pop Operations

See Canvas for the code

EXAM 1 (Due on March 4th, 11.59 PM): CSC228-Sp2019-Exam-1

See Canvas for the code

Quiz 4 (Due on March 8th, 11.59 PM): Stack-based Implementation of Queue

See Canvas for the code

Quiz 5 (Due on March 22nd, 11.59 PM): Intersection of Two Linked Lists using a Hashtable

See Canvas for the code

EXAM 2 (Due on March 29th, 11.59 PM): CSC228-Sp2019-Exam-2

See Canvas for the code

Quiz 6 and Quiz 7 (Due on April 12th, 1 PM; submit the quizzes together as a single submission): CSC228-Sp2019-Quiz-6-7-TakeHome