CSCI 3110 -- Data Structures

CSCI 3110: Data Structures

Spring 2024

Instructor: Dr. Cen Li
Email: Cen.Li@mtsu.edu
Office hours: Tue, Wed, Thur, 10:30 am -- 12:00 pm
Others by appointment

Teaching Assistant: Mr. Caleb Griffy
Email: cgg3a@mtmail.mtsu.edu
Office hours: Monday 4:00-6:00pm

Tentative Class schedule (subject to change)

Week	Date	Lecture Topics	Code Examples	Project Assignments
Week 1	Jan 16th(Tue) and Jan 18th(Thur)	No class
Week 2	Jan 22nd (Tue)	Course Syllabus Review: Array, structure type, Array of structure, file I/O, Linear Search, Sorting, formatted output Introduction to Data Structures	Example illustrating: Array of Structure, linear search in array, and sorting of an array of structs: type.h main.cpp movies.dat theaters.dat showings.dat	Download and install Visual Studio Code: VS Code Learn to Build, Run and Debug C++ program in VS Code Download the Program from the class to build, run and debug in VSCode before Thursday's class. You may access VS Code from Jupyterhub MTSU Jupiterhub (Log in with your MTSU pipeline ID)
Week 2	Jan 24th (Thur)	Debugging in VS Code Discuss Project 1 Introduction to Data Structures		Project 1 (Evaluation Rubric) Due: midnight Thursday Feb 1st, Deadline: midnight Monday Feb 5th Start files and data file type.h, main.cpp, grades.dat Read: Requirements for Programs l-value and r-value explained
Week 3	Jan 30th (Tue)	Function review Enumeration type Review C++ Class a more detailed review Code walkthrough: CheckingAcct example. CheckingAcct.h CheckingAcct.cpp main.cpp	Example 1: basic concepts Sphere.h Sphere.cpp main.cpp mainArray.cpp (array of objects) Example 2: C++ class with array as its data: slist.h slist.cpp main.cpp Example 3: C++ class with array and array element is of struct type List.h List.cpp main.cpp Example 4: List Class (sorted, array based implementation): slist.h slist.cpp main.cpp	Homework 1 (D2L Quiz) (Due: midnight Friday Feb 2nd) Other readings: static data and static member function in c++ class conversion constructors The explicit specifier
Week 3	Feb 1st (Thur)	Review C++ Class a more detailed review	Example : overloaded operators FeetInches.h FeetInches.cpp main.cpp	Read: Use "explicit" on a constructor to prevent auto conversion
Week 4	Feb 6th	Overloaded Operators Review Class friendship Project consists of multiple classes Cho Han Example Discuss Project 2	Example : overloaded operators -- Date Class Date.h Date.cpp main.cpp Example : Copy constructor and overloaded = operator with dynamically allocated memory: StudentTestScores.h, main.cpp ChoHan Example - Program with 3 classes Die.h Die.cpp Dealer.h Dealer.cpp Player.h Player.cpp main.cpp makefile	Project 2 Evaluation Rubric starting files and data files: main.cpp student.h roster.h grades.dat Makefile oneStudent.dat(for testing and debugging only) In addition, you need to create student.cpp and roster.cpp files Homework 2 (D2L Quiz) (Due: midnight Friday Feb 9th)
Week 4	Feb 8th	Pointer review	Example: List Class (unsorted, linked list implmentation): list.h list.cpp main.cpp Example: List Class (sorted, linked list implmentation): slist.h slist.cpp main.cpp
Week 5	Feb 13th	Linked List review Templated function, Templated Class Templated linked list class	Example: Templated Linked List Class LinkedList.h main.cpp FeetInches.h FeetInches.cpp	Read: Cplusplus.com vector Cplusplus.com list Cplusplus.com deque Homework 3 (D2L Quiz) (Due: midnight Friday Feb 16th) Read: Overload << operator for template class
Week 5	Feb 15th	Standard Template Library (STL) STL vector STL Set and Map	Example 1: vector basics vectorQuestion.cpp vectorDr.cpp words.dat Example 2: STL vector vector.cpp Example 3: STL list listQuestion.cpp Example 4: STL deque deque.cpp
Week 6	Feb 20th	STL Stack Discuss Project 3	STL stack Checking balanced braces IsBalanced.cpp Postfix expression evaluation postfix.cpp	Homework 4 (D2L Quiz) Project 3 Evaluation rubric Provided code and data files: main.cpp flightMap.h flightMap.cpp type.h type.cpp cities.dat flights.dat Example code to demonstrate how to use STL list with struct type data type.h ExampleMain.cpp
Week 6	Feb 22nd	Review for Test 1
Week 7	Feb 27th	Test 1 (Test 1 Preparation Guide)
Week 7	Feb 29th	Stack and Queue (continued) STL Queue cpp reference.com std::stack cpp reference.com std::queue	STL queue Checking for parlindrome parlindrome.cpp
Week 8	March 5th and 7th	Spring Break, no class
Week 9	March 12th	Inheritance 1	Inheritance: Class calling sequence sequence.cpp Inheritance: execution order executionOrder.cpp Inheritance: Mammal and Dog mammal.h mammal.cpp dog.h dog.cpp main.cpp	Project 4 main.cpp type.h type.cpp flightMap.h flightMap.cpp cities.dat flights.dat requests.dat Project evaluation rubric Read: The C++ Virtual Table
Week 9	March 14th	Inheritance 2	inheritance: Employee base class and 2 derived classes Employee.h Employee.cpp HourlyEmployee.h HourlyEmployee.cpp SalariedEmployee.h SalariedEmployee.cpp main.cpp Inheritance: Shape class and two derived classes Shape.h Shape.cpp Circle.h Circle.cpp Rectangle.h Rectangle.cpp main.cpp	Homework 5 (D2L Quiz)(Due: midnight, Wednesday March 20th)
Week 10	March 19th	Algorithm Analysis(1)
Week 10	March 21st	Algorithm Analysis(2)		Homework 6 (D2L Quiz)(Due: midnight, Wednesday March 27th)
Week 11	March 26th	Recursion revisited	Tower of Hanoi: solveTower.cpp Eight Queen's Problem: Queens.h, Queens.cpp, main.cpp
Week 11	March 28th	Sorting Algorithms Animated sorting algorithms	Watch Proof: Recursive identity for Binomial Coefficients Selection Sort Bubble Sort insertion Sort Merge Sort Quick Sort shell Sort radix Sort Student suggested sorting video	Homework 7 (D2L Quiz)(Due: midnight, Wednesday April 3rd) Project 5, Evaluation parameters.h, main.cpp, eagle.dat, Bonus Project (Optional) (Grading: (1) The maximum points added to the project total is 60 bonus points, (20 points for solving each maze) (2) Upload into the Dropbox a screenshort of the solved mazes from program output in addition to all the files used in this project) Here is a help file for the project: Project Help File Here are all the provided files: type.h CreatureClass.h CreatureClass.cpp MazeClass.h MazeClass.cpp main.cpp myMaze1.dat myMaze2.dat myMaze3.dat
Week 12	April 2nd	Sorting algorithms (continued)
Week 12	April 4th	Heap, Priority Queue, Heap Sort	Heap Class Heap.h Heap.cpp	Homework 8 (D2L Quiz)
Week 13	April 9th	Heap, Priority Queue, Heap Sort	Binary Search Tree bst.h bst.cpp Template BST with exception handling BST.h BST.cpp main.cpp TreeException.cpp
Week 13	April 11th	Test 2 (Test review sheet)
Week 14	April 16th	Tree, Binary Tree, Binary Search Tree		Homework 9 Project 6 (evaluation rubric) data1, example result for data1 data2 Provided code: wordEntry.h (Updated with more details), wordEntry.cpp BST.h (Updated line 10), BST.cpp, main.cpp
Week 14	April 18th	Tree, Binary Tree, Binary Search Tree(continued) AVL tree	AVL-node.cpp AVL.cpp
Week 15	April 23rd	Hashing Why a prime number is often selected as the hash table size?		Homework 10
Week 16	Final Exam	Thursday, May 2nd, 1:00 - 3:00 pm

Useful Information

OneNote to class notes
C++ Online Reference
C++ Reference
Other C++ concepts:
- C++ string functions
- random number generation