[2022] CS 331: Data Structures and Algorithms - Course Project - Checkpoint Simulation System
Data Structure Course Projects Course Objectives
The purpose of "Data Structure Course Projects" is to achieve the combination of theory and practical application, to enable students to learn the methods of data organization according to the characteristics of data objects, strengthen and deepen understanding the topics in “CS 331: Data Structures and Algorithms”, including the logical characteristics and physical representation of data structures, the selection and application of data structures, and the design and implementation of algorithms. This course also cultivates students' practical ability and learning ability to solve complex problems.
Course Requirements
" Data Structure Course Projects " is a compulsory practical course, which requires each student to complete it in the computer room within the specified time.
Each student needs to be checked by the teacher. After the course design, each student is required to submit the report (including the paper and electronic version) and the codes.
Grading
The final grade of the course design is comprehensively assessed by the usual practice attendance, demonstration of program functions and answering teacher questions, and course projects report.
Note the following situations:
1. If you are not checked by the teacher, i.e., if you do not demonstrate the program functions and answer teacher questions, you will fail this course.
2. If you do not submit the report, you will fail this course.
3. If you plagiarize other people's report, both the plagiarist and the plagiarized will
fail this course.
Academic Integrity
You are welcome to discuss questions with classmates, but all final work must be your own. You cannot copy other people's code or use the code on the network as your own code, and you cannot give your code/report directly to others. If you want to open source the code, please upload the blog or Github after submitting the course project report
Projects
1. Discrete Event Simulation: Customs Checkpoint Simulation System
【Problem Description】
Consider a customs checkpoint responsible for checking transit vehicles and develop a concrete simulation system. For this system, the following basic considerations are assumed:
(1) The duty of the customs is to check the passing vehicles, here only one direction of traffic inspection is simulated.
(2) Assuming that vehicles arrive at a certain rate, there is a certain randomness, and a vehicle arrives every a to b minutes.
(3) The customs has k inspection channels, and it takes c to d minutes to inspect a vehicle.
(4) Arriving vehicles wait in line on a dedicated line. Once an inspection channel is free, the first vehicle in the queue will enter the channel for inspection. If a vehicle arrives with an empty lane and there is no waiting vehicle, it immediately enters the lane and starts checking.
(5) The desired data include the average waiting time of vehicles and the average time passing through checkpoints.
【Basic Requirements】
The system needs to simulate the inspection process at a customs checkpoint and output a series of events, as well as the average queuing time and average transit time for vehicles.
【Extended Requirements】
Please modify the customs checkpoint simulation system to use a management strategy of one waiting queue per inspection channel. Do some simulations of this new strategy and compare the simulation results with the strategy of sharing the waiting queue.
2. Calculate the truth value of propositional calculus formulas
【Problem Description】
The propositional calculus formula refers to a formula composed of logical variables (its value is TRUE or FALSE) and logical operators ∧ (AND), ∨ (OR) and Ø (NOT) according to certain rules (operations such as implication can be used ∧ , ∨ andtorepresent).Thesequenceofformulaoperationsis Ø,∧,∨,andparentheses () can change the priority. Given a propositional calculus formula and the value of each variable, it is required to design a program to calculate the truth value of the formula.
【Basic Requirements】
(1) Use a binary tree to calculate the truth value of the formula.
Firstly, use the stack to change the infix form of the formula into the suffix form. Secondly, according to the suffix form, construct the corresponding binary tree from the leaf node. Finally, traverse the binary tree in post-order, and find the value of each subtree. That is, each time a node is reached, the value of its subtree has been
calculated. When the root node is reached, the truth value of the formula is obtained. (2) Design a variety of propositional calculus formulas in different forms, and check
the validity of each propositional calculus formula.
(3) The identifier of the logical argument is not limited to a single letter, but can be an
alphanumeric string of any length. Logical arguments can appear multiple times in
a formula.
(4) Print the construction process of the binary tree, print suffix form of the formula and
the post-order traversal sequence of the binary tree.
(5) Enter the value of each variable, calculate and display the truth value of the formula,
print the evaluation process of the binary tree.
(6) Display the truth table of the formula.
【Extended Requirements】
Please replace logical operators with arithmetic operators and use binary tree to calculate the arithmetic expression.
