CSCI 3230 - Data Structures

Course Information

• Instructor: Dr. Yao Xu, Assistant Professor from Department of Computer Science
• Office: IT 2321, Statesboro Campus
• Email: [email protected]
• Lecture: Online asynchronous, Entirely at a distance
• Office Hours: Via Zoom by appointment (Please email me at least 24 hours in advance to schedule a meeting.)

Course materials such as syllabus, lecture recordings, slides, assignments, and important announcements will all be posted on Folio.

Prerequisites

• A minimum grade of "C" in CSCI 1302 (Programming Principles II) and MATH 2130 (Discrete Mathematics) or CSCI 2625 (Discrete Structures)

Assessments

Your performance in this course will be measured by the following.

Assessment Type	Number	Percentage of Final Grade
Conceptual Quizzes	4	28% (7% * 4)
Coding Quizzes	8	52% (6.5% * 8)
Final Exam	1	20%

Course Schedule (Updated Timely)

Abbreviations:

• Mx: Short for "Module x"
• Qx: Short for "Conceptual Quiz x"
• Codingx: Short for "Coding Quiz x"

Note: All coursework will be derived from the lecture recordings posted on Folio. The "Additional Materials" provided below are intended to enhance your understanding of the topics covered in the lectures.

Dates	Lecture Topics	Additional Materials
Week 1: -	Class 1: M0 - Course Introduction Explore the resources listed in the right column → Course Topics Make sure that you are familiar with the following Java concepts: Classes and Objects Interfaces Strings, Arrays Inheritance, Polymorphism Overloading, Overriding Type conversion, Class Type Casting Generics YouTube video: Object Oriented Programming YouTube video: Comparisons with Generics YouTube video: Generic Programming	Free online textbooks: An Introduction to the Analysis of Algorithms Algorithms, 4th Edition Tutorialspoint YouTube Channels: Neso Academy: Data Structures Data Structures by Dr. Rob Edwards HackerRank: Data Structure and Algorithms Visualizing data structures and algorithms: Visualgo Data Structure Visualizations Data Structures and Algorithms Visualizations Coding examples and hands-on practices: GeeksforGeeks LeetCode
	Class 2: M1 - Algorithm Analysis How to Analyze Algorithm's Running Time Asymptotic Notations	Pseudocode GeeksforGeeks: Asymptotic Notation and Analysis Types of Asymptotic Notations How to Analyse Loops for Complexity Analysis of Algorithms More resources on asymptotic analysis: Asymptotic Analysis Big-O-cheatsheet
	Class 3: M1 - Algorithm Analysis (cont'd) Asymptotic Analysis
	Class 4: M2 - Recursion Divide and Conquer Linear Recursion Binary Recursion Coding1 - Due on Saturday, 5/23	Coursera videos on a recursion example: Fibonacci Problem Overview Naive Algorithm Efficient Algorithm GeeksforGeeks: Introduction to Recursion How to analyse Complexity of Recurrence Relation Divide and Conquer Other resources: Puzzle Game: Tower of Hanoi
	Class 5: M2 - Recursion (cont'd) Solving Recurrences
	Q1 due on Sunday, 5/25
Week 2: -	5/26: Memorial Day - No Classes
	Class 1: M3 - Linear Data Structures Arrays ArrayList in Java	Coursera videos: Dynamic Arrays GeeksforGeeks: Array, ArrayList, Array vs ArrayList in Java Singly Linked List, Doubly Linked List Stack, Queue Visualizations: ArrayList LinkedList Array-based stack, List-based stack Array-based queue, List-based queue
	Class 2: M3 - Linear Data Structures (cont'd) Singly Linked Lists Doubly Linked Lists Coding2 - Due on Thursday, 5/28
	Class 3: M3 - Linear Data Structures (cont'd) Stacks Queues Coding3 - Due on Saturday, 5/30
	Class 4: M4 - Maps and Hash Tables Maps Hash Tables	GeeksforGeeks: Map Interface in Java Hashing Separate Chaining, Open Addressing, Double Hashing Visualizations: Open Hashing, Closed Hashing Hash Table: Linear Probing, Quadratic Probing, Double Hashing, Separate Chaining
	Q2 due on Sunday, 5/31
Week 3: -	Class 5: M5 - Trees Traverse a Tree Binary Trees	GeeksforGeeks: Binary Tree Tree Traversals (Inorder, Preorder and Postorder) Binary Tree Properties
	Class 1: M6 - Heaps and Priority Queues Heaps Coding4 - Due on Wednesday, 6/3	GeeksforGeeks: Heap Data Structure Introduction to Priority Queue Visualizations: Binary Heap Min Heap
	Class 2: M6 - Heaps and Priority Queues (cont'd) Heap Construction Priority Queues
	Class 3: M7 - Binary Search Trees (BST) Binary Search Trees Querying a BST Coding5 - Due on Saturday, 6/6	GeeksforGeeks: Binary Search Tree Find Minimum in BST, Find Maximum in BST Search and Insertion in BST Deletion in BST Visualizations: Binary Search Tree Binary Search Tree on Visualgo
	Class 4: M7 - BST (cont'd) Insertion and Deletion in BST
	Q3 due on Sunday, 6/7
Week 4: -	Class 1: M8 - Sorting Comparison Sorts Selection Sort Bubble Sort Insertion Sort Coding6 - Due on Wednesday, 6/10	GeeksforGeeks: Sorting Terminology Selection Sort, Bubble Sort, Insertion Sort Merge Sort Quick Sort HeapSort Tree Sort Lower bound for comparison sorts Visualizations: Comparison Sorting Algorithms: Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Quick Sort Visualgo: Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Quick Sort Heap Sort Heap Sort on Visualgo
	Class 2: M8 - Sorting (cont'd) Merge Sort Heapsort Tree Sort
	Class 3: M8 - Sorting (cont'd) Quicksort Lower Bound on Comparison Sorts Coding7 - Due on Saturday, 6/13
	Class 4: M8 - Sorting (cont'd) Linear Sorting Counting Sort Radix Sort Bucket Sort Bonus Coding - Due on Sunday, 6/14	GeeksforGeeks: Sorting without comparison of elements Counting Sort, Radix Sort, Bucket Sort Visualizations: Counting Sort, Radix Sort, Bucket Sort Visualgo: Counting Sort, Radix Sort
	Class 5: M9 - Graphs Graph Basics Graph Representations	GeeksforGeeks: Graph Introduction Graph and its representations Visualization: Graph representations
	Q4 due on Sunday, 6/14
Week 5: - 6/15	Class 1: M9 - Graphs (cont'd) Breadth First Search	GeeksforGeeks: Breadth First Search Visualizations: Breadth First Search BFS on Visualgo
	Class 2: M9 - Graphs (cont'd) Depth First Search Coding8 - Due on Wednesday, 6/17	GeeksforGeeks: Depth First Search Visualizations: Depth First Search DFS on Visualgo
	Class 3: M9 - Graphs (cont'd) Dijkstra's Algorithm for Shortest Paths (Optional)	GeeksforGeeks: Find Shortest Paths from Source to all Vertices using Dijkstra’s Algorithm Visualizations: Dijkstra Shortest Path Dijkstra’s Algorithm on Visualgo
	Final Exam on Thursday, 6/18