CSC 228 Data Structures and Algorithms, Fall 2018

Exam 3 (IN-CLASS; on Nov. 29th @ 2.30 PM): OPEN NOTES. Reading List

Exam 2 (Take Home: Due on Nov. 8th) posted.

Projects 9-10 posted

Quiz 7 (Take Home) posted (Due on Nov. 15th, 11.59 PM)

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

Syllabus

Teaching Assistant

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

 

Syllabus

CSC228 Syllabus, Fall 2018

 

Teaching Assistant

Fall2018-TA-information

 

Lecture Slides

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

Module 2 – List ADT (Last updated: Sept. 4th)

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 Sep. 11th, 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 Sep. 18th, 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 Sep. 25th, 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

 

Project 4 (Due on Oct. 8th, 11.59 PM): Design and Implementation of an Algorithm to Find the Next Greater Element of the Elements in an Array in Θ(n) Time

See Canvas for the code and a help video

 

Project 5 (Due on Oct. 9th, 11.59 PM): Stack-based Implementation of Queue

See Canvas for the code

 

Project 6 (Due on Oct. 16th, 11.59 PM): Hash table Tradeoff Analysis: Average Insertion Time vs. Load Imbalance Index

See Canvas for the code

 

Project 7 (Due on Oct. 23rd, 11.59 PM): Binary Tree: Checking for Complete Binary Tree and Binary Search Tree

See Canvas for the code

 

Project 8 (Due on Oct. 30th, 11.59 PM): Project 8: Binary Search Tree: Lowest Common Ancestor Node

See Canvas for the code

 

Project 9 (Due on Nov. 6th, 11.59 PM): Project 9: 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 10 (Due on Nov. 13th, 11.59 PM): Project 10: Degree Distribution of the Vertices in a Graph

Startup Code (PDF)

See Canvas for the code

 

Quizzes and Exams

Quiz 2 (Due on Sep. 27th, 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

 

Exam-1 (Due on Oct. 4th, 11.59 PM)

See Canvas for the code

 

Quiz 3 (Due on Oct. 11th, 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

 

Quiz 4 (Due on Oct. 18th, 11.59 PM): Height-Balanced Binary Trees

See Canvas for the code

 

Quiz 5 (Due on Oct. 25th, 11.59 PM): Binary Search Tree: Average Number of Comparisons for a Successful Search

See Canvas for the code

 

Exam-2 (Due on Nov. 8th, 2.30 PM hardcopy to be submitted in-class)

 

Quiz 7 (Due on Nov. 15th, 11.59 PM): Quiz 7: Breadth First Search on a Graph: Test for Bipartivity

Startup Code (PDF)

See Canvas for the code

 

 

 

Quiz, Exam and Project Schedules