CS
CS163 Spring 2021 Program #1
Individual Programming Assignment #1
CS 163 Data Structures
As a Data structures course, the primary goal with the programming assignments
is to focus on how to design classes that are well structured and efficient and focus
on the required data structures.
Scope: When beginning this project, the first thing to keep in mind is that we only
have 2 weeks to complete each assignment. Therefore, it is critical that you focus
on a limited scope, with an emphasis on the class(es), data structures, and testing
the code that has been developed. You will be primarily graded on your use of classes,
member functions, arguments, data structures, pointers, the efficiency of your code, and
thorough testing.
• Your program should compile and run
• But, the application is not being developed (imagine another group of
programmers are working on the application development)
• Instead your main (called the client program) should be aimed at
thoroughly testing your class member functions
• This should be done by building a menu interface!
• DO NOT hard code in the test cases - all tests should be interactive with
the user.
After the program description, please find a checklist that helps set the pace for implementing the code.
Background Information – Building Abstract Data Types
Topic #1 introduces the notion of an Abstract Data Type (ADT). Our programs this
term will be creating these, using the class construct. Since our classes will be
representing a data type, it wouldn’t make sense for them to interact with the user
by prompting, reading in information or displaying error messages. A data type
can’t assume that there is a human user ready to answer prompts! We also want
to hide the details about the data structure behind a public interface; this means
we need to learn about wrapper functions this term.
Program using a consistent style of indentation, header comments for each function, inline comments for each major block of code. Select self-documenting variable names. Style is worth 20% of the assignment’s grade.
CS163 Spring 2021 Program #1
Follow the Rules of Data Abstraction:
1. Member functions must;
a. Receive the information that they need through arguments
b. Use the return type to represent success/failure of the operation
c. Pass class (or struct) objects as references (or constant references)
whenever possible
2. Member functions must not:
a. Prompt
b. Read from the user
c. Output error messages
3. Public Member functions must avoid:
a. Have “nodes” or “pointers” to the data structure as arguments
• They may call private functions, passing in head or other
necessary pointers as arguments
b. Returning a struct or class object
Program Assignment #1 Specification:
It is hard to imagine that we have spent a year with Covid-19 and essentially for
some of us in lock-down. Much of the last year, I have been home more than ever
before. As my friends and family look for ways to stay connected when we are
apart, we have come up with games that we can play online or at least while we
are remote. Trivia games work relatively well if each of us divides up our deck of
questions. On Zoom, one person can ask a question and another person on Zoom
can respond. It would be best if we could get these questions electronically.
Programming Assignment #1: This first program of the term is an exercise in
building, traversing, and destroying linear linked lists. With program #1, you will
build a data structure to keep lists of trivia questions, and answers. You will want
to keep track of those that have been used and those that are available. To make it
fun, we will organize the questions that are available by category – so the person
being asked a question can let the program know which type of question they
would like (e.g., a question about Movie trivia versus History, etc.). There can be
as many type of questions as the application desires –we should not hard code the
types into our abstraction!
The data structure that you will be creating is a linear linked list of categories,
where each has a head pointer to a list of questions and their corresponding
answers.
CS163 Spring 2021 Program #1
Using Classes
We will be building a class (e.g., CS_Trivia) to manage the data structures
mentioned. You must have the following functions; the information that these
functions need to work with should be passed as an argument. For example, to
add a new trivia question and answer, the information about the item should be
passed to the function from “the client program”.
Task 1. Construct an object (constructor)
Task 2. Release all dynamic memory (destructor)
Task 3. Add a Trivia Question
• pass in the category, the question, and the answer
Task 4. Display Questions of a particular category
Task 5. Display all Questions (for debugging purposes)
Task 6. Remove a Category of Questions
• Pass in the category and remove all questions in that list
Task 7. Select a Trivia Question
• Pass in the category and randomly select a question
• Display the question
Task 8. Check Answer
• For the most recently played Trivia question, compare the
answer supplied as an argument with that trivia question
• Return true if there is a match, false otherwise
• This should not be case sensitive
Things you should know...as part of your program:
1) You may use a combination of structures and classes.
2) If a member function has the name “display”, “output” or “print” as part if
it, then it may output directly to the user
3) Do not use statically allocated arrays in your classes or structures. All
memory must be dynamically allocated and kept to a minimum!
4) All data members in a class must be private
5) Never prompt and read from the user when inside a class member function
6) Never output error messages from a class member function
7) Global variables are not allowed in CS163
8) Do not use the String class! (use arrays of characters instead!); however,
you may use the cstring library of strlen, strcpy, strcmp
9) Use modular design, separating the .h files from the .cpp files. Never
implement functions in your .h file! And, never "#include" .cpp files!
CS163 Spring 2021 Program #1
CS163 - Checklist for First Week of Cycle
Cycle Monday Tuesday Thursday Friday
First week Discussion
(Planning
Design)
Draft .h file Discussion
Response
Revised .h
Draft .cpp
Tasks #1-3
Second week Discussion
(Planning
Testing)
Progress
Submission
Tasks 4-6
Discussion
Response
Finished
Assignment &
Writeup
______1 Monday - Begin by Collaborating with your Virtual Group
• Using the Canvas Discussions
• You may share your design ideas:
- How will the rules of Data Abstraction be followed?
- What will you need to do to support the Data structures?
- Explore sample prototypes that meet the rules of Data
Abstraction and share those among your group (although don’t
share so much that no one else has anything left to do!)
- Make sure to ask a question to help others respond to you!
______2 Tuesday - Submit a Draft .h file
• Due by 7pm
• Submit to Assignments on Canvas
• It should contain prototypes for all of the public functions outlined in this assignment with arguments and returned types
• It should contain all of the structures needed - If you plan to use additional classes, these should also
be represented
• You may change your .h as you program
______3 By Thursday – Constructive Response to your Virtual Group
______4 Friday - Submit a Revised .h file and a Draft .cpp file
• Due by 7pm
• Submit to Assignments on Canvas
• Implement and demonstrate Tasks #1, 2, 3.
• Provide “stubs” for the rest of the functions
• Have header comments (1 paragraph minimum) for each file
CS163 Spring 2021 Program #1
CS163 - Checklist for Second Week of Cycle
Cycle Monday Tuesday Thursday Friday
First week Discussion
(Planning
Design)
Draft .h file Discussion
Response
Revised .h
Draft .cpp
Tasks #1-3
Second week Discussion
(Planning
Testing)
Progress
Submission
Tasks 4-6
Discussion
Response
Finished
Assignment &
Writeup
______1 Monday – Discuss Testing with your Virtual Group
• Using the Canvas Discussions
• Prior to your design submission, respond to the discussion topic regarding the design of program #1
• You may share your design ideas:
- List the test cases that need to take place for one member
functions
- Describe how the client program will fully be able to test
all possible combinations of conditions
- Consider how the client program can be used by others to
test ADT as updates are made to the abstraction
- Make sure to ask a question to help others respond to you!
______2 Tuesday - Submit a Progress Submission
• Due by 7pm
• Submit to Assignments on Canvas
• It must compile and run to gain credit
• Implement and Demonstrate Tasks #4, 5, 6
______3 By Thursday – Constructive response to your Virtual Group
• Are there changes you would make to the approach for the next programming assignment?
______4 Friday - Submit a Completed Assignment with Efficiency Writeup
• Due by 7pm
• Submit to Assignments on Canvas
• Tar or Zip all of the .h and .cpp files together
• Upload the Efficiency Writeup separately