A car company promotes a particular model of its electric cars every month.

Part A – Coding

Write a class to keep track of the monthly promoted models and their prices with a stack data structure. The class needs to support:

1)   Pushing the latest promoted model onto the stack.

2)   Popping the latest promoted model off the stack.

3)   Peeking the latest promoted model at the top of the stack (without popping).

4)   Getting the lowest priced model and highest priced model among the past promoted models.

Files to get you started:

•    promotedCarModelStack.h: The header file containing the PromotedModel and PromotedCarModelStack class definitions. You must NOT change the class names and the function signatures, otherwise, Gradescope autograding will fail. You may add member variables or helper functions to the PromotedCarModelStack class as you see necessary.

•    promotedCarModelStack.cpp: The implementation file where you will write your code for implementing the stack functions.

o You must NOT rename the promotedCarModelStack.h and promotedCarModelStack.cpp; otherwise, Gradescope autograding will fail.

•    driver.cpp: A file you can run to test your code. It includes test examples for basic tests; however, you may want to write more tests to test your code according to the prompt.

•    Makefile: A makefile to allow you to automate the compilation of your code. Check out the “Frequently Asked Questions” link in the C/C++ programming in Linux / Unix reference page on Canvas for simple Makefile reference.

o Use the “make” command to compile. Use “make clean” to delete compiled object code or executable. Cleaning before each make is important as you can end up running old code    even after doing a new make command.

o Use ./carstack to execute.

Assumptions:

1.   Prices of the promoted models in different months will be different.

Algorithm Requirements:

1)   Breaking either one of the requirements in 3), 4), or 5) below would cap your assignment 2 grade to

50% of the total assignment 2 grade, meaning the most you could get from assignment 2 would be

50 points.

2)   The pop, peek, getHighestPricedPromotedModel, getLowestPricedPromotedModel should throw a logic_error exception with an error message “Promoted car model stack is empty” if the PromotedCarModelStack is empty.

3)   You must NOT use the C++ standard template library std::stack class, you must implement your own Stack.

a.   Whether you use dynamic array-based list (vector) or linked list for implementing the stack (see hint below), you can use at most two vectors or two linked lists or [one vector and   one linked list] in your Stack class for tracking the monthly promoted models, and the highest and lowest price models over the time.

4)   All methods should run in constant O(1) time complexity.

5)   All methods should run with constant auxiliary O(1) space. Auxiliary space does NOT include the space for the method arguments and class member variables.

Hint:

1)   For push, pop, peek operations, think which C++ STL collection type (other than the stack class) would give constant time and space for accessing or updating the beginning or the end of the data    collection. You could use an implementation of the list ADT such as a dynamic array (amortized O(1) time for appending and removing at the end of the array) or a linked list type for implementing your Stack and its operations.

2)   You need to be able to retrieve the highest and lowest priced models from the stack in constant time at any time, which data structure would give constant-time lookup time?

3)   Note the highest and lowest priced models in the stack could change with each push or pop, you basically would need to track the highest and lowest priced model at every point of the stack.

Programming and testing:

•    Please refer to C/C++ programming in Linux / Unix page.

•    You may use C++ 11 standard for this assignment, see the given Makefile.

•    We strongly recommend you set up your local development environment under a Linux environment (e.g., Ubuntu 18.04 or 20.04, or CentOS 8), develop and test your code there first, then port your code to Edoras (e.g., filezilla or winscp) to compile and test to verify. The gradescope autograder      will use a similar environment as Edoras to compile and autograde your code.

Grading:

Passing 100% auto-grading may NOT give you a perfect score for this Part A. The satisfaction of the         algorithm requirements (see above), your code structure, coding style, and commenting will also be part of the rubrics (see Syllabus Course Design - assignments). Your code shall follow industry best practices:

•    Be sure to comment your code appropriately. Code with no or minimal comments are automatically lowered one grade category.

•   NO hard code – Magic numbers, etc.

•    Have proper code structure between .h and .c / .cpp files, do not #include .cpp files.

•    Design and implement clean interfaces between modules.

Part B – Complexity Analysis

Show your algorithm has the time and auxiliary space complexities as required. For each function / method  implemented, you would need to analyze the implementation logic for the worst-case scenario to separate the constant and non-constant operations with respect to the stack size for tracking monthly promoted models and their prices, then show and explain the time complexity and space complexity in the O notations. Follow zyBook 12.7.1 and 12.7.3 for time complexity analysis, follow zyBook 11.6.6 for space complexity analysis.