CSC 228 Data Structures and Algorithms, Fall 2019

EXAM 3 will be on Tuesday, December 3rd, from 9 AM to 10.50 AM at ENB 162 (regular classroom). It will be in-class, OPEN notes. Reading List for EXAM 3

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

Syllabus

Lecture Slides

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

 

Syllabus

CSC228 Syllabus, Fall 2019

 

Teaching Assistant

Mahzabin Akhter <akhterm86@gmail.com>

Room: ENB 163

Tuesday: 9 am – 11 am, 1 pm – 2 pm, 4 pm – 5pm
Thursday: 9 am – 11 am, 1 pm – 2 pm, 4 pm – 5pm
Friday: 9 am – 1 pm

 

Lecture Slides

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

Module 2 – List ADT (updated)

Module 3 – Stack ADT

Module 4 – Queue ADT

Module 5 – Dictionary ADT: Hash tables

Module 6 – Binary Trees

Module 7 – Binary Search Trees (Last updated: Oct. 24th)

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: Sept. 19th, 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

 

Project 2 (Due: Sept. 26th, 11.59 PM): Project 2: 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: Oct. 10th, 11.59 PM): Project 3: Implementation of the Stack ADT using a Singly Linked List and Comparing its Performance with a Doubly Linked List-based Implementation

See Canvas for the code

 

Project 4 (Due: Oct. 17th, 11.59 PM): Project 4: Implementation of the Queue ADT using a Stack Object and Performance Comparison of the EnqueueCostly and the DequeueCostly Approaches

See Canvas for the code

 

Project 5 (Due: Oct. 24th, 11.59 PM): Project 5: Using a Hashtable to Determine the Common Elements in all the Lists

See Canvas for the code

 

Project 6 (Due: Nov. 7th, 11.59 PM): Project 6: Determining the Average Number of Comparisons for a Successful Search and an Unsuccessful Search in a Binary Search Tree based on its Structure Only

See Canvas for the code

 

Project 7 (Due: Nov. 14th, 11.59 PM): Project 7: Binary Search Tree: Lowest Common Ancestor Node

See Canvas for the code

 

Project 8 (Due: Nov. 21st, 11.59 PM): Project 8: Checking whether a Binary Tree is a Min Heap

See Canvas for the code

 

Quizzes and Exams

Quiz 1 (Due: Sept. 24th, 11.59 PM): Design and Implementation of an Algorithm to Determine whether a Linked List has Unique Elements

See Canvas for the code

 

Exam 1 (Due: Oct. 1st, 11.59 PM)

See Canvas for the code

 

Quiz 2 (Due: Oct. 15th, 11.59 PM): Quiz 2: Determination of Maximum Depth of Nested Parentheses in an Expression

See Canvas for the code

 

Quiz 3 (Due: Oct. 22nd, 11.59 PM): Quiz 3: Insertion and Deletion of Data at an Arbitrary Index in a Queue

See Canvas for the code

 

Exam 2 (Due: Oct. 29th, 11.59 PM)

Exam 2 (Take Home)

See Canvas for the code

 

Quiz 4 (Due: Nov. 5th, 11.59 PM): Quiz 4: Setting the Data for the Nodes in a Binary Tree to Satisfy the Property of a Binary Search Tree without Changing the Structure of the Binary Tree

See Canvas for the code

 

Quiz 5 and Quiz 6 (Due on Nov. 19th, @ 11.30 AM; submit the quizzes together as a single submission): CSC228-Fall2019-Quiz-5-6-TakeHome

 

Quiz, Exam and Project Schedules