DATA STRUCTURES AND ALGORITHMS

11/24/24
DSA ASSIGNMENT#01

Objectives:
1. Linked list
2. Binary search
3. Linear search
4. Stack
5. Queue

Instructions:
• Submit a single ZIP file containing all source code files and a PDF report.
• Include well-documented and modularized code with meaningful comments.
• The PDF report must describe your approach, challenges, and outputs for each
task.
• Provide at least five complex examples with outputs for each task.
• Ensure the code is original; copied code will result in an automatic F grade.
• Test your code thoroughly and include test results in the report.
• Submit by the deadline; late submissions without prior approval will be penalized.
• Ensure your code runs in the specified environment and include a list of
dependencies if needed.
• Use proper coding practices (indentation, variable names, and modularity).
 DATA STRUCTURES AND ALGORITHMS
11/24/24
DSA ASSIGNMENT#01

Task 1: Multi-Tier Processing System

A warehouse management system requires a multi-tier processing system. The system

involves processing incoming shipments, storing them in the warehouse, and dispatching
them based on priority. The following data structures are required:

1. A stack to represent unloading shipments in the order they arrive.

2. A queue for dispatch requests (FIFO order).
3. A priority queue to ensure the highest-priority shipments are dispatched first.

Requirements:
- Use the stack to store shipment IDs as they are unloaded.
- Transfer shipment IDs to a queue when dispatch requests are made.
- Use a priority queue to manage dispatch based on shipment urgency.

Function Prototypes:
1. void unloadShipment(int shipmentID);
2. void addDispatchRequest(int shipmentID, int priority);
3. int processDispatch();
4. void displaySystemState();

Demonstrate the system with at least 10 shipments, including various priorities for
dispatch. Display the system state
after every operation.
 DATA STRUCTURES AND ALGORITHMS
11/24/24
DSA ASSIGNMENT#01

Task 2: Recursive Rule-Based Linked List Operations

Scenario:
A custom list stores customer data, including IDs and their order counts. You must
implement recursive operations on this list with the following rules:
1. If a customer's order count exceeds 10, move them to a VIP list.
2. If a customer's order count is less than 3, remove them from the list.
3. Provide a recursive function to calculate the total orders in the system.

Function Prototypes:
1. void moveToVIP(Node*& head, Node*& vipHead);
2. void removeLowOrders(Node*& head);
3. int calculateTotalOrders(Node* head);

Demonstrate the operations on a linked list with at least 15 customers. Show the state of
the main list and VIP list after processing.
 DATA STRUCTURES AND ALGORITHMS
11/24/24
DSA ASSIGNMENT#01

Task 3: Expression Conversion, Validation, and Evaluation

Scenario: A computational engine processes expressions in both prefix and postfix

notations with enhanced functionality. In addition to basic mathematical operators (+, -,
*, /), the system must also support modulus (%), exponentiation (^), and logical operators
(AND, OR). The system must validate, convert, and evaluate expressions, handling
complex nested operations and mixed types.

You must implement the following functionalities:

Requirements:

1. Validation:
o Ensure expressions are valid for the respective notation (prefix/postfix).
o Handle invalid operators, mismatched operands, and incomplete expressions.
o Reject expressions with improper logical-to-arithmetic operator combinations.
2. Conversion:
o Convert expressions between prefix and postfix notations.
o Preserve precedence and associativity of all operators, including logical ones.
3. Evaluation:
o Evaluate converted expressions.
o Include support for modular arithmetic, exponentiation, and logical operators:
▪ Logical AND (&) returns 1 if both operands are non-zero, else 0.
▪ Logical OR (|) returns 1 if at least one operand is non-zero, else 0.
o Return detailed error messages for invalid expressions.
4. Additional Functionalities:
o Implement a function to check whether an expression contains only arithmetic
operators, logical operators, or both.
o Implement a function to convert an infix expression directly to postfix or prefix.

Function Prototypes:

1. string prefixToPostfix(string prefix);

2. string postfixToPrefix(string postfix);
3. int evaluateExpression(string expression);
4. bool validateExpression(string expression, string notation);
5. string infixToPostfix(string infix);
6. string infixToPrefix(string infix);
7. string determineExpressionType(string expression);
(Returns "Arithmetic", "Logical", or "Mixed")
 DATA STRUCTURES AND ALGORITHMS
11/24/24
DSA ASSIGNMENT#01

Task 4: Advanced Search with Dynamic Analysis

A generic search engine requires a binary search implementation with dynamic time
complexity analysis.

Implement a
class template that:
1. Performs binary search on both sorted arrays and sorted linked lists.
2. Dynamically analyzes the execution time for different input sizes.

Function Prototypes:
1. template <typename T> class BinarySearch
2. bool searchArray(T array[], int size, T key);
3. bool searchLinkedList(Node<T>* head, T key);
4. void analyzeExecutionTime(string structureType, int inputSize, T key);

Provide results for arrays and linked lists of sizes 100, 1,000, and 10,000. Compare and
analyze the performance of binary search in these structures, providing detailed execution
times.