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