Programming Projects

Programming Projects require more problem-solving than Practice Programs and can usually be solved many different ways. Visit www.myprogramminglab.com to complete many of these Programming Projects online and get instant feedback.

  1. Write a program that allows the user to enter any number of student names and their scores. The program should then display the student names and scores according to the ascending order of scores. Use the template class vector and the generic sort function from the STL. Note that you will need to define a structure or class type for data consisting of one student name and score. You will also need to overload the < operator for this structure or class.

  2. A prime number is an integer greater than 1 and divisible only by itself and 1. An integer x is divisible by an integer y if there is another integer z such that x = y * z. The Greek mathematician Eratosthenes (pronounced: Er-ah-tos-thin-eeze) gave an algorithm, called the Sieve of Eratosthenes, for finding all prime numbers less than some integer N. The algorithm works like this: Begin with a list of integers 2 through N. The number 2 is the first prime. (It is instructive to consider why this is true.) The multiples of 2, that is, 4, 6, 8, etc., are not prime. We cross these off the list. Then the first number after 2 that was not crossed off is the next prime. This number is 3. The multiples of 3 are not primes. Cross the multiples of 3 off the list. Note that 6 is already gone, cross off 9, 12 is already gone, cross off 15, etc. The first number not crossed off is the next prime. The algorithm continues on in this fashion until we reach N. All the numbers not crossed off the list are primes.

    1. Write a program using this algorithm to find all primes less than a user-supplied number N. Use a vector container for the integers. Use an array of bool initially set to all true to keep track of crossed-off integers. Change the entry to false for integers that are crossed off the list.

    2. Test for N = 10, 30, 100, and 300.

      We can improve our solution in several ways:

    3. The program does not need to go all the way to N. It can stop at N/2. Try this and test your program. N/2 works and is better but is not the smallest number we could use. Argue that to get all the primes between 1 and N the minimum limit is the square root of N.

    4. Modify your code from part (a) to use the square root of N as an upper limit.

  3. Suppose you have a collection of student records. The records are structures of the following type:

    struct StudentInfo
{
    string name;
    int grade;
};

    The records are maintained in a vector<StudentInfo>. Write a program that prompts for and fetches data and builds a vector of student records, then sorts the vector by name, calculates the maximum and minimum grades and the class average, then prints this summarizing data along with a class roll with grades. (We aren’t interested in who had the maximum and minimum grade, though, just the maximum, minimum, and average statistics.) Test your program.

  4. Continuing Programming Project 3, write a function that separates the students in the vector of StudentInfo records into two vectors, one containing records of passing students and one containing records of failing students. (Use a grade of 60 or better for passing.)

    You are asked to do this in two ways, and to give some run-time estimates.

    1. Consider continuing to use a vector. You could generate a second vector of passing students and a third vector of failing students. This keeps duplicate records for at least some of the time, so don’t do it that way. You could create a vector of failing students and a test-for-failing function. Then you push_back failing student records, then erase (which is a member function) the failing student records from the original vector. Write the program this way.

    2. Consider the efficiency of this solution. You are potentially erasing O(N) members from the middle of a vector. You have to move a lot of members in this case. erase from the middle of a vector is an O(N) operation. Give a big-O estimate of the running time for this program.

    3. If you used a list<StudentInfo>, what are the run-times for the erase and insert functions? Consider how the time efficiency of erase for a list affects the run-time for the program. Rewrite this program using a list instead of a vector. Remember that a list provides neither indexing nor random access and its iterators are only bidirectional, not random access.

  5. Redo (or do for the first time) Programming Project 9 from Chapter 11, except use the STL set template class instead of your own set class. Use the generic set_intersection function to compute the intersection of Q and D.

    Here is an example of set_intersection to intersect set A with B and store the result in C, where all sets are sets of strings:

    #include <iterator>
#include <set>
#include <string>
…
set<string> C;
// Note space between >> in line below
insert_iterator<set<string> > cIterator(C, C.begin());
set_intersection(A.begin(), A.end(),
                 B.begin(),B.end(),
                 cIter);
// set C now contains the intersection of A and B

  6. In this project you are to create a database of books that are stored using a vector. Keep track of the author, title, and publication date of each book. Your program should have a main menu that allows the user to select from the following: (1) Add a book’s author, title, and date; (2) Print an alphabetical list of the books sorted by author; and (3) Quit.

    You must use a class to hold the data for each book. This class must hold three string fields: one to hold the author’s name, one for the publication date, and another to hold the book’s title. Store the entire database of books in a vector in which each vector element is a book class object.

    To sort the data, use the generic sort function from the <algorithm> library. Note that this requires you to define the < operator to compare two objects of type Book so that the author field from the two books are compared.

    A sample of the input/output behavior might look as follows. Your I/O need not look identical, this is just to give you an idea of the functionality.

    Select from the following choices:
1.          Add new book
2.          Print listing sorted by author
3.          Quit
1
Enter title:
More Than Human
Enter author:
Sturgeon, Theodore
Enter date:
1953
Select from the following choices:
1.          Add new book
2.          Print listing sorted by author
3.          Quit
1
Enter title:
Problem Solving with C++
Enter author:
Savitch, Walter
Enter date:
2015
Select from the following choices:
1.          Add new book
2.          Print listing sorted by author
3.          Quit
2
The books entered so far, sorted alphabetically by author are:
            Savitch, Walter.  Problem Solving with C++.  2015.
            Sturgeon, Theodore.  More Than Human.  1953.
Select from the following choices:
1.         Add new book
2.         Print listing sorted by author
3.         Quit
1
Enter title:
At Home in the Universe
Enter author:
Kauffman
Enter date:
1996
Select from the following choices:
1.         Add new book
2.         Print listing sorted by author
3.         Quit
2
The books entered so far, sorted alphabetically by artist are:
            Kauffman, At Home in the Universe, 1996
            Savitch, Walter.  Problem Solving with C++.  2015.
            Sturgeon, Theodore.  More Than Human.  1953.

  7. Redo or do for the first time Programming Project 8 from Chapter 14, except use the STL set class for all set operations and the STL linked list class to store and manipulate each individual permutation. When creating a set containing lists, make sure to place a space between the last two >’s if you are using a compiler earlier than C++11. For example, set<list<int>> defines a set where elements are linked lists containing elements of type int. The code set<list<int> > without a space will produce a compiler error. (This issue was eliminated with the release of C++11.)

  8. You have collected a file of movie ratings where each movie is rated from 1 (bad) to 5 (excellent). The first line of the file is a number that identifies how many ratings are in the file. Each rating then consists of two lines: the name of the movie followed by the numeric rating from 1 to 5. Here is a sample rating file with four unique movies and seven ratings:

    7
Harry Potter and the Order of the Phoenix
4
Harry Potter and the Order of the Phoenix
5
The Bourne Ultimatum
3
Harry Potter and the Order of the Phoenix
4
The Bourne Ultimatum
4
Wall-E
4
Glitter
1

    Write a program that reads a file in this format, calculates the average rating for each movie, and outputs the average along with the number of reviews. Here is the desired output for the sample data:

    Glitter: 1 review, average of 1 / 5
Harry Potter and the Order of the Phoenix: 3 reviews, average of 4.3 / 5
The Bourne Ultimatum: 2 reviews, average of 3.5 / 5
Wall–E: 1 review, average of 4 / 5

    Use a map or multiple maps to calculate the output. Your map(s) should index from a string representing each movie’s name to integers that store the number of reviews for the movie and the sum of the ratings for the movie.

  9. Consider a text file of names, with one name per line, that has been compiled from several different sources. A sample follows:

    Brooke Trout
Dinah Soars
Jed Dye
Brooke Trout
Jed Dye
Paige Turner

    There are duplicate names in the file. We would like to generate an invitation list but don’t want to send multiple invitations to the same person. Write a program that eliminates the duplicate names by using the set template class. Read each name from the file, add it to the set, and then output all names in the set to generate the invitation list without duplicates.

  10. Do Programming Project 16 from Chapter 8 except use a Racer class to store information about each race participant. The class should store the racer’s name, bib number, finishing position, and all of his or her split times as recorded by the RFID sensors. You can choose appropriate structures to store this information. Include appropriate functions to access or change the racer’s information, along with a constructor.

    Use a map to store the race data. The map should use the bib number as the key and the value should be the Racer object that corresponds to the bib number. With the map you won’t need to search for a bib number anymore, you can directly access the splits and final position based on the bib number.

    If you aren’t using C++11 or higher then don’t forget that you need a space between the >> characters when defining the map of vectors.

  11. Write a program that runs a counter in a separate thread. The counter should start at one and increment its value every second. Every five seconds the counter should output its value to the console. The following line of C++11 code will make the current thread wait for one second. You will need to include <chrono>:

    std::this_thread::sleep_for(std::chrono::seconds(1));

    While the counter thread is running, your main thread should allow you to input a number. If the number entered is less than or equal to the counter’s value, then the program should stop.

  12. Write a program that uses regular expressions to validate a date in the format MM/DD/YY. YY must always be two digits, but MM could possibly be a single digit from 1 to 9 (e.g., 1 for January rather than 01) or two digits from 01 to 12. The digits in MM should not exceed 12, for example, 13 is an invalid month. Similarly, DD could also be a single digit from 1 to 9 or two digits from 01 to 31. The digits in DD should not exceed 31, for example, 32 is an invalid day. Don’t worry about months with fewer than 31 days. For example, February 31 is an invalid date but for this problem you can consider it to be valid.