You are given the following description of the entities that need to be stored in the database. Your task is to design a database schema (set of tables) to store these entities.Your schema must be minimally redundant in storing data. In other words, you should build a set of tables that minimize the repetition of data, by using foreign keys – credit will be in accordance with this. • Artist: An individual or a group/band, uniquely identified by their name. An artist might release albums, as well as songs that are not in albums (singles).• Song: A song has a title and is performed by an artist, either as a part of an album, or as a single that’s not part of an album. Every song in an album has the release date of the album, but a single song has its own release date. A song title is unique to an artist (the same artist records a songexactly once), but the title may be shared by multiple artists (i.e. covers). A song belongs to one or more genres. For example, a song could be in a single genre, such as R & B, or could be in multiple genres such as Pop and Rock. Genres are pre-defined, and every song must be in at least one genre. Also, songs in an album need not all be in the same genre.• Album: An album is a collection of songs released by an artist, on a certain date. For example, the album Achtung Baby was made by the artist (band) U2, released on November 19, 1991. An album name is not unique, but the combination of album name and artist name is unique.• User: A user is uniquely identified by their username. A user can optionally have one or more playlists, and optionally have ratings for songs, albums, or playlists. In other words, it’s possible that a user has no playlists, and hasn’t given any ratings.• Playlist: A user can make any number of playlists of songs. Note: A playlist may not include an entire album, only individual songs. Each song is either from some album, or a single that’s not in any album.Every playlist has a title, and a date+time when it was created. A playlist may be modified any number of times after creation by adding or removing songs, but the title and date+time will not change.The title of a playlist is not unique since different users might create playlists with the same title. However, a user’s playlists will have unique titles.• Rating: A user could rate an album, a song (even if it’s in an album), or a playlist. A rating is limited to 1,2,3,4, or 5 (numeric), and is made on a specific date.Note: The items listed above do NOT necessarily correspond 1-1 with tables, although some of them might. They simply detail all the data you will need to store whatever table structure you adopt. This also means you can create as many tables as you need to reduce redundancy.Your database structure should have the most appropriate data type and size for each column in each table. For size of data, think of a realistic online music service and imagine how many songs/artists/albums/ playlists/users/ratings it might have to support. The idea is to use the least amount of storage space for each column that will be able to store the entire range of foreseeable values.Make sure you define and specify all primary keys, foreign keys, unique valued columns or unique valued combination of columns, and null/non-null properties for columns. In the document you will submit, type in the create table statement for each of the tables you create in the database. If you don’t have the full create statement for a table, you will not get credit for it.Note: When you test your design in MySQL, you might use alter table statements after the initial create. However, for the submission, you are required to rewrite the whole sequence as a single create table statement per table.Every query must be written in a single SQL statement, meaning that if you were to write it in a MySQL client session on a terminal, there would be a single terminating semicolon. So, for example, you can have nested or multiple SQLs for a query, provided you can write it all up with a single terminating semicolon in a MySQL client session. No Python code!For any of the queries: • If the result might require breaking ties, then unless otherwise specified in the query, let the MySQL engine deal with it (you need not do anything explicit) • If the result has fewer than the required number of entities, report all of them. • For all queries that ask for ‘top n’ or ‘most’, the result must appear from highest ranked to lowest ranked.Type the SQL queries in the document you will submit, and make sure to write the query number against each query. (If you want to play it extra safe, copy the query statement from this list, then write your answer SQL query.)Write queries for the following. 1. Which 3 genres are most represented in terms of number of songs in that genre? The result must have two columns, named genre and number_of_songs. 2. Find names of artists who have songs that are in albums as well as outside of albums (singles). The result must have one column, named artist_name3. What were the top 10 most highly rated albums (highest average user rating) in the period 1990-1999? Break ties using alphabetical order of album names. (Period refers to the rating date, NOT the date of release). The result must have two columns, named album_name and average_user_rating.4. Which were the top 3 most rated genres (this is the number of ratings of songs in genres, not the actual rating scores) in the years 1991-1995? (Years refers to the rating date, NOT the date of release). The result must have two columns, named genre_name and number_of_song_ratings.5. Which users have a playlist that has an average song rating of 4.0 or more? (This is the average of the average song rating for each song in the playlist.) A user may appear multiple times in the result if more than one of their playlists make the cut. The result must 3 columns named username, playlist_title, average_song_rating6. Who are the top 5 most engaged users in terms of number of ratings that they have given to songs or albums? (In other words, they have given the most number of ratings to songs or albums combined.)The result must have 2 columns, named username and number_of_ratings.7. Find the top 10 most prolific artists (most number of songs) in the years 1990-2010? Count each song in an album individually. The result must have 2 columns, named artist_name and number_of_songs.8. Find the top 10 songs that are in most number of playlists. Break ties in alphabetical order of song titles. The result must have a 2 columns, named song_title and number_of_playlists.9. Find the top 20 most rated singles (songs that are not part of an album). Most rated meaning number of ratings, not actual rating scores. The result must have 3 columns, named song_title, artist_name, number_of_ratings.10. Find all artists who discontinued making music after 1993. The result should be a single column named artist_title
Given a CSV data file as represented by the sample file EuCitiesTemperatures.csv (213 records), load it into a Pandas DataFrame and perform the following tasks on it.Preprocessing/Analysis (28 pts) 1. [9 pts] Fill in the missing latitude and longitude values by calculating the average for that country. Round the average to 2 decimal places.2. [9 pts] Find out the subset of cities that lie between latitudes 40 to 60 (both inclusive) and longitudes 15 to 30 (both inclusive). Find out which countries have the maximum number of cities in this geographical band. (More than one country could have the maximum number of values.)3. [10 pts] Fill in the missing temperature values by the average temperature value of the similar region type. A region type would be a combinaton of whether it is in EU (yes/no) and whether it has a coastline (yes/no).For example, if we have a missing temperature value for Bergen, Norway, which is not in the EU but lies on the coast, we will fill it with the average temperature of cities with EU=’no’ and coastline=’yes’)Visualization (27 pts) For all plots, make sure to label the axes, and set appropriate tick labels. 1. [6 pts] Plot a bar chart for the number of cities belonging to each of the regions described in Preprocessing/Analysis #3 above.2. [7 pts] Plot a scatter plot of latitude (y-axis) v/s longitude (x-axis) values to get a map-like visual of the cities under consideration. All the cities in the same country should have the same color.3. [6 pts] The population column contains values unique to each country. So two cities of the same country will show the same population value. Plot a histogram of the number of countries belonging to each population group: split the population values into 5 bins (groups).4. [8 pts] Plot subplots (2, 2), with proper titles, one each for the region types described in Preprocessing/Analysis #3 above. Each subplot should be a scatter plot of Latitude (y-axis) vs. City (x-axis), where the color of the plot points should be based on the temperature values: ‘red’ for temperatures above 10, ‘blue’ for temperatures below 6 and ‘orange for temperatures between 6 and 10 (both inclusive). For each subplot, set xticks to an array of numbers from 0 to n-1 (both inclusive), where n is the total number of cities in each region type. This represents each city as a number between 0 and n-1.Given a CSV data file as represented by the sample file GermanCredit.csv (1000 records), load it into a Pandas DataFrame, and perform the following tasks on it.Preprocessing (31 pts) 1. [8 pts] Drop the 3 columns that contribute the least to the dataset. These would be the columns with the highest number of non-zero ‘none’ values. Break ties by going left to right in columns. (Your code should be generalizable to drop n columns, but for the rest of the analysis, you can call your code for n=3.)2. [4 pts] Certain values in some of the columns contain unnecessary apostrophes (‘). Remove the apostrophes.3. [5 pts] The checking_status column has values in 4 categories: ‘no checking’, ‘
Given a CSV data file as represented by the sample file pokemonTrain.csv, perform the following operations on it. 1. [7 pts] Find out what percentage of “fire” type pokemons are at or above the “level” 40. (This is percentage over fire pokemons only, not all pokemons)Your program should print the value as follows (replace … with value): Percentage of fire type Pokemons at or above level 40 = … The value should be rounded off (not ceiling) using the round() function. So, for instance, if the value is 12.3 (less than or equal to 12.5) you would print 12, but if it was 12.615 (more than 12.5), you would print 13, as in: Percentage of fire type Pokemons at or above level 40 = 13 Do NOT add % after the value (such as 13%), only print the numberPrint the value to a file named “pokemon1.txt” If you do not print to a file, or your output file name is not exactly as required, you will get 0 points.2. [10 pts] Fill in the missing “type” column values (given by NaN) by mapping them from the corresponding “weakness” values.You will see that typically a given pokemon weakness has a fixed “type”, but there are some exceptions. So, fill in the “type” column with the most common “type” corresponding to the pokemon’s “weakness” value.For example, most of the pokemons having the weakness “electric” are “water” type pokemons but there are other types too that have “electric” as their weakness (exceptions in that “type”). But since “water” is the most common type for weakness “electric”, it should be filled in. In case of a tie, use the type that appears first in alphabetical order.3. [13 pts] Fill in the missing (NaN) values in the Attack (“atk”), Defense (“def”) and Hit Points (“hp”) columns as follows: a. Set the pokemon level threshold to 40. b. For a Pokemon having level above the threshold (i.e. > 40), fill in the missing value for atk/def/hp with the average values of atk/def/hp of Pokemons with level > 40.So, for instance, you would substitute the missing “atk” value for Magmar (level 44), with the average “atk” value for Pokemons with level > 40. Round the average to one decimal place.c. For a Pokemon having level equal to or below the threshold (i.e.
You are required to design a prototype movie recommendation program in Python as detailed in the assignment description.You will work individually. We will NOT be using Autolab in this class for submitting assignments. This means your program will only be graded once, after the submission deadline has passed. Make sure you abide by the DCS Acadmic Integrity Policy for Programming Assignments.What to submit Write all the required functions described below in the given template file named hw1.py Fill in the function code for all the functions in this template. Note: Every function has a pass statement because Python does not allow empty functions. The pass statement does nothing, it’s simply a filler. You can delete it when you write in your code.You may implement other helper functions as needed. Make sure to test your programs on files other than the samples we have provided, to cover the various paths of logic in your code. Make sure you write ALL your test calls in the main() function. Do NOT write ANY code outside of any of the functions.When you are done writing and testing, submit ONLY the filled-in hw1.py file to Canvas. Do NOT submit a Jupyter notebook, it will not be accepted for grading. You are allowed up to 5 submissions, only the last submission will be graded.How to test your code You can test your program by calling your functions in the hw1.py file from the main() function. All test code must be in the main() function ONLY. If you write ANY code outside of any of the functions, you will lose credit.In Terminal, execute your program like this: > python hw1.pyThis was explained in class: see jan22_notes.ipynb/jan22_notes.html between cells #23 and #24 – Writing and executing standalone (outside Jupyter notebook) Python programs.Make sure the test files are in the same folder as the program. You may develop and test your code in a Jupyter notebook, but for submission you will need to move your code over to hw1.py and execute it as above to make sure it works correctly. The process of moving code from a Jupyter notebook to a Python file has been explained in class.You can run your tests on the given ratings and movies files, but testing on only these files may not be sufficient. You should make your own test files as well, to make sure that you cover the various paths of logic in your functions. You are not required to submit any of your test files.You may assume that all parameter values to your functions will be legitimate, so you are not required to check whether the parameter values are valid. In any function that requires the returned values to be sorted or ranked, ties may be broken arbitrarily between equal values.You may retain the main() function when submitting, but we will IGNORE it.For this assignment only, grading will be done by an AUTOGRADER program that will call the functions in your hw1.py, and check the returned value against the expected correct value. It will NOT call your main() function.The AUTOGRADER does not look at printed output, so anything you print in your program will be ignored. There will not be any manual inspection of code, credit is based solely on whether your functions return correct results.Partial Credit There is no partial credit for code structure, etc. Credit is given only when correct values are returned from your functions. However, each function will be tested on several cases. So for instance, if a function runs correctly on 2 out of 3 test cases, you will get full points for the 2 cases and zero for the third. (In this sense, there is partial credit for each function.)Data Input • Ratings file: A text file that contains movie ratings. Each line has the name (with year) of a movie, its rating (range 0-5 inclusive), and the id of the user who rated the movie. A movie can have multiple ratings from different users. A user can rate a particular movie only once. A user can however rate multiple movies. Here’s a sample ratings file.• Movies file: A text file that contains the genres of movies. Each line has a genre, a movie id, and the name (with year) of the movie. To keep it simple, each movie belongs to a single genre. Here’s a sample movies file.Note: A movie name includes the year, since it’s possible different movies have the same title, but were made in different years. However, no two movies will have the same name in the same year. You may assume that input files will be correctly formatted, and data types will be as expected. So you don’t need to write code to catch any formatting or data typing errors. For all computation of rating, do not round up (or otherwise modify) the rating unless otherwise specified.Implementation1. [10 pts] Write a function read_ratings_data(f) that takes in a ratings file name, and returns a dictionary. (Note: the parameter is a file name string such as “myratings.txt”, NOT a file pointer.) The dictionary should have movie as key, and the list of all ratings for it as value. For example: movie_ratings_dict = { “The Lion King (2019)” : [6.0, 7.5, 5.1], “Titanic (1997)”: [7] }2. [10 pts] Write a function read_movie_genre(f) that takes in a movies file name and returns a dictionary. The dictionary should have a one-to-one mapping from movie to genre. For example { “Toy Story (1995)” : “Adventure”, “Golden Eye (1995)” : “Action” } Watch out for leading and trailing whitespaces in movie name and genre name, and remove them before storing in the dictionary.1. [8 pts] Genre dictionary Write a function create_genre_dict that takes as a parameter a movie-to-genre dictionary, of the kind created in Task 1.2. The function should return another dictionary in which a genre is mapped to all the movies in that genre. For example: { genre1: [ m1, m2, m3], genre2: [m6, m7] }2. [8 pts] Average Rating Write a function calculate_average_rating that takes as a parameter a ratings dictionary, of the kind created in Task 1.1. It should return a dictionary where the movie is mapped to its average rating computed from the ratings list. For example: {“Spider-Man (2002)”: [3,2,4,5]} ==> {“Spider-Man (2002)”: 3.5}1. [10 pts] Popularity based In services such as Netflix and Spotify, you often see recommendations with the heading “Popular movies” or “Trending top 10”.Write a function get_popular_movies that takes as parameters a dictionary of movie-to-average rating ( as created in Task 2.2), and an integer n (default should be 10). The function should return a dictionary ( movie:average rating, same structure as input dictionary) of top n movies based on the average ratings. If there are fewer than n movies, it should return all movies in ranked order of average ratings from highest to lowest.2. [8 pts] Threshold Rating Write a function filter_movies that takes as parameters a dictionary of movie-to-average rating (same as for the popularity based function above), and a threshold rating with default value of 3.The function should filter movies based on the threshold rating, and return a dictionary with same structure as the input. For example, if the threshold rating is 3.5, the returned dictionary should have only those movies from the input whose average rating is equal to or greater than 3.5.3. [12 pts] Popularity + Genre based In most recommendation systems, genre of the movie/song/book plays an important role. Often,features like popularity, genre, artist are combined to present recommendations to a user. Write a function get_popular_in_genre that, given a genre, a genre-to-movies dictionary (as created in Task 2.1), a dictionary of movie:average rating (as created in Task 2.2), and an integer n (default 5), returns the top n most popular movies in that genre based on the average ratings. The return value should be a dictionary of movie-to-average rating of movies that make the cut. If there are fewer than n movies, it should return all movies in ranked order of average ratings from highest to lowest.Genres will be from those in the movie:genre dictionary created in Task 1.2. The genre name will exactly match one of the genres in the dictionary, so you do not need to do any upper or lower case conversion.One important analysis for content platforms is to determine ratings by genre. Write a function get_genre_rating that takes the same parameters as get_popular_in_genre above, except for n, and returns the average rating of the movies in the given genre.Write a function genre_popularity that takes as parameters a genre-to-movies dictionary (as created in Task 2.1), a movie-to-average rating dictionary (as created in Task 2.2), and n (default 5), and returns the top-n rated genres as a dictionary of genre:average rating. If there are fewer than n genres, it should return all genres in ranked order of average ratings from highest to lowest. Hint: Use the above get_genre_rating function as a helper.1. [10 pts] Read the ratings file to return a user-to-movies dictionary that maps user ID to a list of the movies they rated, along with the rating they gave. Write a function named read_user_ratings for this, with the ratings file as the parameter.For example: { u1: [ (m1, r1), (m2, r2) ], u2: [ (m3, r3), (m8, r8) ] } where ui is user ID, mi is movie, ri is corresponding rating. You can handle user ID as int or string type, but make sure you consistently use it as the same type everywhere in your code.2. [12 pts] Write a function get_user_genre that takes as parameters a user id, the user-to-movies dictionary (as created in Task 4.1 above), and the movie-to-genre dictionary (as created in Task 1.2), and returns the top genre that the user likes based on the user’s ratings. Here, the top genre for the user will be determined by taking the average rating of the movies genre-wise that the user has rated. If multiple genres have the same highest ratings for the user, return any one of genres (arbitrarily) as the top genre.3. [12 pts] Recommend 3 most popular (highest average rating) movies from the user’s top genre that the user has not yet rated. Write a function recommend_movies for this, that takes as parameters a user id, the user-to-movies dictionary (as created in Task 4.1 above), the movie-togenre dictionary (as created in Task 1.2), and the movie-to-average rating dictionary (as created in Task 2.2).The function should return a dictionary of movie-to-average rating. If fewer than 3 movies make the cut, then return all the movies that make the cut in ranked order of average ratings from highest to lowest.
The purpose of this assignment is to design, code, and test a C program performs operations with complex numbers.The following are the requirements of the program: • The program shall add two complex numbers. • The program shall subtract two complex numbers • The program shall find the magnitude and phase of a complex number given in rectangular form, a + j b.• The program shall find the rectangular form given magnitude and phase of a complex number. • The program shall find the multiplication of two complex numbers. • The program shall find the division of two complex numbers.• Given two impedances the program shall calculate the impedance of the parallel combination.Assignment Submission Requirements The following are the submission requirements for the assignment: • The files will be submitted to Canvas • The flowchart or pseudo code • The C code with compile instructions in the banner • The test code with compile instructions in the banner • A screen shot of a few test cases demonstrating the working solution.
The purpose of this assignment is to design, code, and test a C program that serves as a FIR filter for discrete data. The math for an FIR filter is: 1 0 ( ) ( ) ( ) M k y n h k x n k for all n − = = − The following are the requirements of the filter: • The filter shall accept 7 floating point filter coefficients. • The filter shall accept 512 floating point input data samples • The filter shall produce 512 output data samples which are the filtered values. • The calculation of the first 6 outputs result in negative input data index and shall by handled by utilizing the first sample• The filter coefficients can be found with the Matlab command >h=fir1(6,0.1). • The input data can be generated with Matlab command >x=0.1*randn(1,512). • The desired output data can be generated with Matlab command >y=filter(h,1,x). • The filter shall be testing for constant input data with no shift in output data expected• The filter shall be tested with single value of 1 at location 256 in the input data and the filter coefficients are expected as output data values • The filter shall be tested with noisy input data with noise reduced output data expectedAssignment Submission Requirements The following are the submission requirements for the assignment: • The files will be submitted to Canvas • The C code with compile instructions in the banner • The test code with compile instructions in the banner • A screen shot of your filter coefficients test of your code showing the correct filter coefficients produced.
The purpose of this assignment is to design, code, and test a C program that serves as a high level state machine for a machine controller.The following are the requirements of the machine controller: • The controller shall have 4 states, stopped, startup, running, coastdown • The controller shall have one input, run, which determines the next state. • In the stopped state a run of 1 shall move to startup state. • In the startup state for more than 15 seconds a run of 1 shall move to running state.• In the running state a run of 0 shall move to the coastdown state. • In the coastdown state for 30 seconds the controller shall move to the stopped state. • The controller shall have one output, speed_command, which determines the speed of the machine.• In the stopped state the speed_command shall be 0%. • In the startup state the speed_command shall be 50%. • In the running state the speed_command shall be 100%. • In the coastdown state the speed_command shall be 25%. • After the machine has started it must go through the coastdown state and stopped state.Assignment Submission Requirements The following are the submission requirements for the assignment: • The files will be submitted to Canvas • The flowchart or pseudo code • The C code with compile instructions in the banner • The test code with compile instructions in the banner • A screen shot of one test run of your code.
In this homework assignment, you will write a simple trivia quiz game. Your program first allows players to create their trivia questions and answers. Multiple questions should be organized and managed using a linked data structured; no array is allowed in this homework assignment.Then, your program asks a question to the player, input the player’s answer, and check if the player’s answer matches the actual answer. If so, award the player the award points for that question. If the player enters the wrong answer your program should display the correct answer. When all questions have been asked, the total award points that the player has won should be displayed. Please perform the following steps to finish this assignment.• Step 1: Create a TriviaNode structure that contains (1) information about a single trivia question and (2) a pointer pointing to other TriviaNode. This structure must contain a string for the question, a string for the answer to the question, an integer representing points the question is worth, and a pointer of the TriviaNode type. Please keep in mind that a harder question should be worth more points.• Step 2: Create a linked list of Trivia using the TriviaNode structure defined in step 1. • Step 3: Design and implement a function that initialize the Trivia linked list by hard-coding the following three trivia questions (including answers and award points). The o Trivia 1:▪ Question: How long was the shortest war on record? (Hint: how many minutes) ▪ Answer: 38 ▪ Award points: 100 o Trivia 2: ▪ Question: What was Bank of America’s original name? (Hint: Bank of Italy or Bank of Germany) ▪ Answer: Bank of Italy ▪ Award points: 50 o Trivia 3: ▪ Question: What is the best-selling video game of all time? (Hint: Call of Duty or Wii Sports)?▪ Answer: Wii Sports ▪ Award points: 20 • Step 4: Design and implement a function to create and add a new TriviaNode into the linked list. You must use operator new to dynamic allocate memory to a new TriviaNode. Please remember to check that a new TriviaNode is successfully created.• Step 5: Design and implement a function that asks a question to the player, input the player’s answer, and check if the player’s answer matches the actual answer. If so, award the player the dollar amount for that question. If the player enters the wrong answer your program should display the correct answer.o Input: a linked list of TriviaNode, the number of trivia to be asked in the list o Output: void or int – 0 indicates success and 1 indicates failure. • Step 6: Write a test driver to perform unit testing for the function implemented in step 5. Assume there are three trivia in your created list, you must cover at least the following cases: (see Fig. 1 on page 3 for the sample user interface.)o Case 1: ask 0 question o Case 2: ask 1 question (i.e., the first one) from the list ▪ Correct answer ▪ Wrong answer o Case 3: ask 3 questions (i.e., all the questions) from the list. ▪ Correct answer ▪ Wrong answero Case 4: ask 5 questions that exceed the number of available trivia in the linked list (i.e., the index of the trivia is larger than the size of the linked list). • Step 7: Write the main function that performs the following: (see Fig. 2 on page 4 for the sample user interface)o Create hard-code trivia quizzes (i.e., questions/answers/awards) (Note: just call the function implemented in step 3). o Create more than 1 trivia quiz from a keyboard (Note: just call the function implemented in step 4).o Write a for loop; in each iteration do the following: ▪ asks a question to the player ▪ takes the player’s answer ▪ compares the input answer with the actual answer • if the player’s answer matches the actual answer, then award the player the corresponding award points for that question, • else (i.e., the player enters the wrong answer) your program should display the correct answer. o When all questions have been asked, display the total award points the player has won. • Step 8: Create two versions using conditional compilation.o Version 1: simply run the test driver implemented in step 6. o Version 2: a regular version run the main function implemented in step 7.Note: this version should not include the test driver. You must provide the following user interface for the debug version. In this version, your program must run the test driver you build in step 6.***This is a debugging version *** Unit Test Case 1: Ask no question. The program should give a warning message. Warning – the number of trivia to be asked must equal to or be larger than 1. Case 1 Passed Unit Test Case 2.1: Ask 1 question in the linked list. The tester enters an incorrect answer.Question: How long was the shortest war on record? Answer: 85 Your answer is wrong. The correct answer is 38 Your total points 0 Case 2.1 passed Unit Test Case 2.2: Ask 1 question in the linked list. The tester enters a correct answer. Question: How long was the shortest war on record? Answer: 38 Your answer is correct! You receive 100 points. Your total points: 100 Case 2.2 passed Unit Test Case 3: Ask all the questions of the last trivia in the linked list. Question: How long was the shortest war on record? Answer: 38 Your answer is correct! You receive 100 points. Your total points: 100 Question: What was Bank of America’s original name? (Hint: Bank of Italy or Bank of Germany)? Answer: Bank of Germany Your answer is wrong. The correct answer is Bank of Italy. Your total points 100 show question here Add your answer here . . . Case 3 passed Unit Test Case 4: Ask 5 questions in the linked list. Warning – There is only 3 trivia in the list. Case 4 passed *** End of the Debugging Version *** Fig. 1: Sample user interface for the debug versionYou must provide the following user interface for the production version. The user input is depicted as Bold, but you do not need to display user input in bold. Please replace “Li” with your name. In this version, your program must run the test driver you build in step 6. *** Welcome to Li’s trivia quiz game *** Enter a question: enter your first question here. Enter an answer: enter your first answer here. Enter award points: enter your first award points here. Continue? (Yes/No): Yes Enter a question: enter your second question here. Enter an answer: enter your second answer here. Enter award points: enter your second award points here. Continue? (Yes/No): NoQuestion: How long was the shortest war on record? (Hint: how many minutes) Answer: 38 Your answer is correct. You receive 100 points. Your total points: 100 Question: What was Bank of America’s original name? (Hint: Bank of Italy or Bank of Germany)? Answer: Bank of Germany Your answer is wrong. The correct answer is: Bank of Italy Your Total points: 100 Question: What is the best-selling video game of all time? (Hint: Call of Duty or Wii Sports)? Answer: Wii Sports Your answer is correct. You receive 20 points. Your total points: 120 … Display more questions/answers and information here… … *** Thank you for playing the trivia quiz game. Goodbye! *** Fig. 2: Sample user interface for the production version How to Create Two Versions? You can use the preprocessor directive #ifdef to create and maintain two versions (i.e., a debugging version and a product version) in your program. If you have the following code: 1. #define UNIT_TESTING 2. #ifdef UNIT_TESTING 3. add your unit testing code here 4. #else 5. add your code for the product version here 6. #endif in your program, the code that is compiled depends on whether a preprocessor macro by that name is defined or not. For example, if the UNIT_TESTING has been defined, i.e., line is enabled, then line 3 ‘’ add your unit testing code here” is compiled and line 5 ‘’add your code for the product version here” is ignored. If the macro is not defined, i.e., 6 line 1 is disabled, then line 5 ” add your code for the product version here” is compiled and line 3 “add your unit testing code here” is ignored. These macros look a lot like if statements, but macros behave completely differently. More specifically, an if statement decides which statements of your program must be executed at run time, while a #ifdef controls which lines of code in your program are actually compiled. Unit Testing: Unit testing is a way of determining if an individual function or class works as expected. You need to isolate a single function or class and test only that function or class. For each function in this homework, you need to check normal cases and boundary cases. Examples for tested values: – String – empty string, medium length, very long – Array – empty array, first element, last element – Integer – zero, mid-value, high-value You must implement a unit test driver for each function implemented in your program. You may need to use assert() to develop your unit test drivers if tested results are predictable. Integration Testing: Integration testing (a.k.a., Integration and Testing) is the phase in software testing in which individual software modules are combined and tested as a group. You may use the sample user interface illustrated in Fig. 2 on page 4 to perform an integration testing for your program. Requirements: 1.(2.5 points) Use comments to provide a heading at the top of your code containing your name, Auburn UserID, filename, and how to compile your code. Also describe any help or sources that you used (as per the syllabus). 2.(2.5 points) Your source code file should be named as “project4_lastname_userID.cpp”, e.g., project4_Harn_pzh0039.cpp. 3.(12.5 points) Your program must use structures and a linked list. (see steps 1-2) 4.(5 points) Your program must use string rather than char array. (see steps 1-2) 5.(5 points) A function that creates 3 hard-coding trivia quizzes. (see step 3) 6.(10 points) A function that creates new quiz from a keyboard. (see step 4) 7.(15 points) A function that asks a question and checks a player’s answer. (see step 5) 8.(15 points) Write a test driver using assert() for function implemented in step 5. 9.(10 points) Correctly implement the main function. (step 7) 10. (10 points) Create two versions using conditional compilation. 11. (5 points) You must reduce number of global variables and data. 12. (5 points) Usability of your program (e.g., user interface). 13. (2.5 points) Readability of your source code.Note: You will lose at least 40 points if there are compilation errors or warning messages when the TA compiles your source code. You will lose points if you: do not use the specific program file name, or do not have a comment, or don’t have a commend block on program you hand in. Programming Environment: Write a short program in C++. Compile and run it using AU server (no matter what kind of editor you use, please make sure your code could run on AU server. The only test bed we accept is the AU server).Deliverables: Submit your source code file named as “project4_lastname_userID.cpp” through the Canvas system. Late Submission Penalty: – Late submissions will not be accepted and will result in a ZERO without valid excuses, in which case you should talk to Dr. Zhou to explain your situation. – GTA/Instructor will not accept any late submission caused by internet latency. Rebuttal period: You will be given a period of 2 business days to read and respond to the comments and grades of your homework or project assignment. The TA may use this opportunity to address any concern and question you have. The TA also may ask for additional information from you regarding your homework or project.
Write a program that merges the numbers in two files and writes all the numbers into a third file. Your program takes input from two different files and writes its output to a third file. Each input file contains a list of numbers of type int in sorted order from the smallest to the largest. After the program is run, the output file will contain all the numbers in the two input files in one longer list in sorted order from smallest to largest.You must provide the following user interface. The user input is depicted as Bold, but you do not need to display user input in bold. Please replace “Li” with your name. Your program loads two input files and merges the numbers in the two files.*** Welcome to Li’s sorting program *** Enter the first input file name: input1.txt The list of 6 numbers in file input1.txt is: 4 13 14 17 23 89 Enter the second input file name: input2.txt The list of 5 numbers in file input2.txt is: 3 7 9 14 15 2 The sorted list of 11 numbers is: 3 4 7 9 13 14 14 15 17 23 89 Enter the output file name: output.txt *** Please check the new file – output.txt *** *** Goodbye.*** Your program must follow the above user interface. Design Issues: Please do NOT intend to implement this project using a single main() function. You need at least three functions to implement this project. The suggested functions are: 1. array_size filename; cout
In the land of Puzzlevania, Aaron, Bob, and Charlie had an argument over which one of them was the greatest puzzle-solver of all time. To end the argument once and for all, they agreed on a duel to the death (this makes sense?). Aaron was a poor shooter and only hit this target with a probability of 1/3.Bob was a bit better and hit his target with a probability of 1/2. Charlie was an expert marksman and never missed. A hit means a kill and the person hit drops out of the duel. To compensate for the inequities in their marksmanship skills, the three decided that they would fire in turns, starting with Aaron, followed by Bob, and then by Charlie. The cycle would repeat until there was one man standing.That man would be remembered for all time as the Greatest Puzzle-Solver of All Time. Strategy 1: An obvious and reasonable strategy is for each man to shoot at the most accurate shooter still alive, on the grounds that this shooter is the deadliest and has the best chance of hitting back. Write a program to simulate the duel using this strategy. Your program should use random numbers and the probabilities given in the problem to determine whether a shooter hits his target.You will likely want to create multiple functions to complete the problem. My solution had only one function to simulate the duels and it passed in the odds and the three guys as pass-by-reference parameters. Once you can simulate a duel, add a loop to your program that simulates 10,000 duels. Count the number of times that each contestant wins and print the probability of winning for each contestant (e.g., for Aaron your might output “Aaron won 3612/10000 duels or 36.12%).Strategy 2: An alternative strategy for Aaron is to intentionally miss on his first shot, while the rest of duel is as same as that in Strategy 1. Write a function to simulate Strategy 2. Your program will determine which strategy is better for Aaron. 2 Note: You must provide the following user interface. Probabilities might be slightly different for different runs due to the random number, but strategy 2 should be always better than strategy 1.You do not need to display text in red. Please replace “Li” with your name. *** Welcome to Li’s Duel Simulator *** Unit Testing 1: Function – at_least_two_alive() Case 1: Aaron alive, Bob alive, Charlie alive Case passed … Case 2: Aaron dead, Bob alive, Charlie alive Case passed … Case 3: Aaron alive, Bob dead, Charlie alive Case passed … Case 4: Aaron alive, Bob alive, Charlie dead Case passed … Case 5: Aaron dead, Bob dead, Charlie alive Case passed … Case 6: Aaron dead, Bob alive, Charlie dead Case passed … Case 7: Aaron alive, Bob dead, Charlie dead Case passed … Case 8: Aaron dead, Bob dead, Charlie dead Case passed … Press any key to continue…Unit Testing 2: Function Aaron_shoots1(Bob_alive, Charlie_alive) Case 1: Bob alive, Charlie alive Aaron is shooting at Charlie Case 2: Bob dead, Charlie alive Aaron is shooting at Charlie Case 3: Bob alive, Charlie dead Aaron is shooting at Bob Press any key to continue… Unit Testing 3: Function Bob_shoots(Aaron_alive, Charlie_alive) Case 1: Aaron alive, Charlie alive Bob is shooting at Charlie Case 2: Aaron dead, Charlie alive Bob is shooting at Charlie Case 3: Aaron alive, Charlie dead Bob is shooting at Aaron Press any key to continue…Unit Testing 4: Function Charlie_shoots(Aaron_alive, Bob_alive) Case 1: Aaron alive, Bob alive Charlie is shooting at Bob Case 2: Aaron dead, Bob alive Charlie is shooting at Bob Case 3: Aaron alive, Bob dead Charlie is shooting at Aaron 3 Press any key to continue… Unit Testing 5: Function Aaron_shoots2(Bob_alive, Charlie_alive) Case 1: Bob alive, Charlie alive Aaron intentionally misses his first shot Both Bob and Charlie are alive. Case 2: Bob dead, Charlie alive Aaron is shooting at Charlie Case 3: Bob alive, Charlie dead Aaron is shooting at Bob Press any key to continue… Ready to test strategy 1 (run 10000 times): Press any key to continue… Aaron won 3593/10000 duels or 35.9% Bob won 4169/10000 duels or 41.69% Charlie won 2238/10000 duels or 22.38% Ready to test strategy 2 (run 10000 times): Press any key to continue… Aaron won 4131/10000 duels or 41.31% Bob won 2594/10000 duels or 25.94% Charlie won 3275/10000 duels or 32.75% Strategy 2 is better than strategy1. Requirements: 1. You must follow the above user interface to implement your program. 2. You must implement the following functions: 1) bool at_least_two_alive(bool A_alive, bool B_alive, C_alive) /* Input: A_alive indicates whether Aaron is alive */ /* B_alive indicates whether Bob is alive */ /* C_alive indicates whether Charlie is alive */ /* Return: true if at least two are alive */ /* otherwise return false */ 2) void Aaron_shoots1(bool& B_alive, bool& C_alive) /* Strategy 1: Use call by reference * Input: B_alive indicates whether Bob alive or dead * C_alive indicates whether Charlie is alive or dead * Return: Change B_alive into false if Bob is killed. * Change C_alive into false if Charlie is killed. */ 4 3) void Bob_shoots(bool& A_alive, bool& C_alive) /* Call by reference * Input: A_alive indicates if Aaron is alive or dead * C_alive indicates whether Charlie is alive or dead * Return: Change A_alive into false if Aaron is killed. * Change C_alive into false if Charlie is killed. */ 4) void Charlie_shoots(bool& A_alive, bool& B_alive) /* Call by reference * Input: A_alive indicates if Aaron is alive or dead * B_alive indicates whether Bob is alive or dead * Return: Change A_alive into false if Aaron is killed. * Change B_alive into false if Bob is killed. */ 5) void Aaron_shoots2(bool& B_alive, bool& C_alive) /* Strategy 2: Use call by reference * Input: B_alive indicates whether Bob alive or dead * C_alive indicates whether Charlie is alive or dead * Return: Change B_alive into false if Bob is killed. * Change C_alive into false if Charlie is killed. */ 2. You must implement five unit-test drivers (five functions) to test the above five functions (see the example output on pages 2 and 3). 3. You must use assert in your test driver. 4. You must define at least three constants in your implementation. For example, the total number of runs (i.e., 10,000) can be defined as a constant. Hints: 1. How to implement “Press any Enter to continue…” cout
This is the second half of Lab04 and is worth 50 points. In this lab assignment (Lab04-2), your job is to implement the randomized version of Quick-sort. That is, you must choose a random pivot from the elements in A[p…r] when partitioning the subarray. For more details, see page 179 of the textbook.The following webpage describes a simple way to obtain a random integer: http://www.cplusplus.com/reference/cstdlib/rand/ Input structure The input starts with an integer number which indicates the number of elements (integers) to be sorted, n. Then, the elements follow, one per line.Output structure Output the elements in non-decreasing order. Each element must be followed by ;. Examples of input and output: Input 6 5 3 2 1 6 4Output 1;2;3;4;5;6; Note that the output is only one line and has no white characters. See the lab guidelines for submission/grading, etc., which can be found in Files/Labs.
In this lab assignment (lab 04-1), your job is to implement heap-sort. This is the first half of lab 04 and is worth 50 points.Input structure The input starts with an integer number which indicates the number of elements (integers) to be sorted, n. Then, the elements follow, one per line.Output the elements in non-decreasing order. Each element must be followed by ;.Examples of input and output: Input 6 5 3 2 1 6 4 Output 1;2;3;4;5;6;Note that the output has only one line and has no white characters. See the lab guidelines for submission/grading, etc., which can be found in Files/Labs.
Suppose that we have to store a sequence of symbols (a file) efficiently, namely we want to minimize the amount of memory needed. For the sake of simplicity we assume that the symbols are restricted to the first 6 letters of the alphabet. For example, let us assume that the frequency of different symbols that you have to store are the following:symbol frequency A 1000 B 150 C 200 D 800 E 300 F 50 Total 2500As we have to store 6 different symbols, the obvious way is to encode each of them in 3 bits, as with 3 bits it is possible to encode 23 different symbols. With this encoding, we need 2500 × 3 = 7500 bits to store the above symbols. A different way to address the problem is the following. Instead of assigning to each symbol a code with the same length (i.e., number of bits), we assign shorter codes to symbols that are more frequent, and longer codes to symbols that are less frequent. One possible encoding according to this sequence is the following symbol encoding A 0 B 10101 C 1011 D 11 E 100 F 10100According to this encoding the number of required bits is: 1000 × 1 + 150 × 5 + 200 × 4 + 800 × 2 + 300 × 3 + 50 × 5 = 5300. This idea is at the basis of the programs used to compress files. First they analyze the input, then they choose the codes, and then they recode the input according to the determined codes.While this idea brings benefits in terms of the space requirements, using variable length codes presents some problems. Once we have coded a file according to a variable length code, we must also be able to decode it in the original format (i.e., once we have compressed the file, we want to able to decompress it). The encoding works only if the codes assigned to different characters are such that no code is a prefix of any other code. If this property does not hold, there is a problem of ambiguity when trying to decompress the sequence.You can prove that in the depicted example no code is a prefix of any other code. For example: no code starts with 0 except from the code of A. So while decompressing the file, if we find a symbol whose code starts with 0, we know it’s A. If we find a character whose code starts with 11, we know it’s D. It can’t be any other symbol, as no code starts with 11 other than D’s code.And so on. How do we assign codes? This is done through a greedy algorithm. We assign the shortest code to the most frequent character, the second longest one to the second most frequent character, and so on. The figure below illustrates the first few stages of the algorithm.Given N characters with their respective frequencies, the algorithm initially builds N trees, each one consisting just of a single node (step 1, in the figure). Then, iteratively, it joins together the trees whose roots have the lowest frequencies (steps 2, 3, etc. in the figure). The tree with the lowest root frequency becomes the left child and the tree with the second-lowest root frequency becomes the right child. Left children are associated with the bit 0, right children with the bit 1. Internal nodes (i.e., root nodes created) can be thought of as dummy nodes storing a fictitious character (which does not appear in our sequence). This procedure is iterated until there is just one tree. At this point, in order to know the code associated with one symbol you simply need to concatenate the 0s and 1s you encounter while moving from the root down to the symbol.Note that the greedy strategy is applied in the reverse way. Symbols with low frequencies end up down in the tree (i.e., they are associated with long codes), while nodes with high frequencies are near the root (i.e., they are assigned short codes).Questions and input structure The input consists of 6 integers, one per each line. Each integer represents the frequency of characters, A, B, C, D, E, and F, in this order. The test cases have been built so that while building trees it never happens that the same frequency appears twice. Then, the decision about which tree goes to the left and which one goes to the right is always straightforward, and the final tree should be unique.Examples of input and output Input 15 11 5 1 2 4 Output A:0 B:10 C:110 D:11100 E:11101 F:1111 See the lab guidelines for submission/grading, etc., which can be found in Files/Labs.
A strongly connected component (SCC) of a directed graph G = (V, E) is defined as a maximal set of vertices C ⊆ V such that for every pair of vertices u and v in C, the two vertices are reachable from each other. In this lab assignment, you are asked to decompose a given directed graph G = (V, E) into a collection of SCCs.Input The input will have the following format. The first integer refers to the number of vertices, |V |. The second integer is the number of edges, |E|. Vertices are indexed by 0, 1, …, |V | − 1. Then, two numbers u v appearing in each line means an edge (u, v). See the example given below.Output Output the SCC ID of every vertex. A SCC’s ID is defined as the smallest index of any vertex in the SCC. In other words, you have to output, for each vertex v, the ID of the unique SCC the vertex v belongs to. You must output the ID for each vertex, considering vertices in the order of 0, 1, …, |V | − 1.Examples of input and output Input 8 13 0 1 1 2 1 4 1 5 2 3 2 6 3 2 3 7 4 0 4 5 5 6 6 5 6 7 Output for problem 2 0 0 2 2 0 5 5 7What this answer implies is that the graph is decomposed into four SCCs, {0, 1, 4}, {2, 3}, {5, 6}, {7}. Note that all vertices in the same SCC have the same label, which is equal to the smallest index of all vertices in the same component. For example, vertices 0,1 and 4 are all labeled with 0.See the lab guidelines for submission/grading, etc., which can be found in Files/Labs.
In this assignment you are asked to implement a dynamic programming algorithm for the matrix chain multiplication problem (chapter 15.2), where the goal is to find the most computationally efficient matrix order when multiplying an arbitrary number of matrices in a row. You can assume that the entire input will be given as integers that can be stored using the standard C++ int type and that matrix sizes will be at least 1.Input The input has the following format. The first number, n ≥ 1, in the test case will tell you how many matrices are in the sequence. The first number will be then followed by n + 1 numbers indicating the size of the dimensions of the matrices. Recall that the given information is enough to fully specify the dimensions of the matrices to be multiplied.Output First, you need to output the minimum number of scalar multiplications needed to multiply the given matrices. Then, print the matrix multiplication sequence, via parentheses, that minimizes the total number of number multiplications. Each matrix should be named A#, where # is the matrix number starting at 0 (zero) and ending at n − 1. See the examples below.Examples of input and output 2 2 3 5 30 (A0A1) 3 10 100 5 50 7500 ((A0A1)A2) 3 10 30 5 60 4500 ((A0A1)A2) 6 30 35 15 5 10 20 25 15125 ((A0(A1A2))((A3A4)A5)) See the lab guidelines for submission/grading, etc., which can be found in Files/Labs.
In this assignment you are asked to implement a dynamic programming algorithm for the Rod Cutting Problem (chapter 15.1). In the Rod Cutting problem, you are given an integer n ≥ 1, along with a sequence of positive prices, p1, p2, …, pn, where pi is the market price of a rod of length i.The goal is to figure out a best way of cutting the given rod of length n to generate the maximum revenue. You can assume that the given prices p1, p2, …, pn are all integers.Input The input has the following format. The input starts with n. Then, p1, p2, …, pn follow, one per each line.Output In the first line, output the maximum revenue (rn), followed by an enter key. In the second line, sequentially output the length of each piece in your optimal cutting, followed by a space key. The second line must end by -1 and an enter key.Examples of input and output Input 7 1 5 8 9 10 17 17 Output 18 1 6 -1The following is the output with white characters shown. 18(enter) 1(space)6(space)-1(enter) Alternatively, the second line can be replaced with “6 1 -1”, “2 2 3 -1”, “2 3 2 -1”, or “3 2 2 -1”. That is, any sequence of piece lengths giving the maximum revenue will be considered to be correct.See the lab guidelines for submission/grading, etc., which can be found in Files/Labs.
In this assignment you will implement RadixSort. See the textbook for the pseudocode. Input structure You are going to apply RadixSort to sort vectors. The input starts with an integer number which indicates the number of vectors to be sorted. Then vectors follow, one vector per line. Each vector consists of 10 numbers where each number has a value in {0, 1, 2, 3}. Entries of a vector are separated by a space.Output structure Output the sorted sequence of vectors, one per line. Vector i must appear before vector j in your output if and only if for some d ∈ {1, 2, …, 10}, vector i is smaller than or equal to vector j on the dth entry, and the two vectors are equal for any of the first d−1 entries.Examples of input and output Input 5 3 3 3 3 3 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 1 3 0 0 2 1 0 0 0 0 1 3 0 0 2 2 0 0 0 0 2 3 2 1 2 2 2 2 2 2 Output 1;3;0;0;2;1;0;0;0;0; 1;3;0;0;2;2;0;0;0;0; 2;3;2;1;2;2;2;2;2;2; 2;3;2;2;2;2;2;2;2;2; 3;3;3;3;3;2;2;2;2;2;More precisely, this output example has 6 lines since a “cout
In this assignment you are requested to implement a hash table that handles collisions by chaining. You have to use linked lists, either from the Standard Template Library (STL) (recommended) or by implementing your own. For usage of STL, refer – for instance – to http://www.cppreference.com/wiki.You need to implement the insert, search and delete operations. The keys are integers (C++ int type) and you can assume that all keys are non-negative. The first number in the input will be the size m of the chained hash table. You will use the simple hash function h(k) = k mod m.Then lines will follow starting with ‘i’, ‘s’, ‘d’,‘o’, or ‘e’. The details are as follows: • Use the hash function h(k) = k mod m. • i(key): Insert (key) into the table. For example, “i2” implies “Insert key 2 into the table.”For collisions, insert the colliding key at the beginning of the linked list. You just need to insert the key and don’t have to output anything in this case.• d(key): delete (key) from the table. For example, d2 implies “Delete key 2 from the table.” If there are multiple elements of the same key value, delete the element of the key value that appears the earliest in the list. If the delete was successful, you have to output (key):DELETED; If not (since there was no element with the key value), output (key):DELETE_FAILED;• s(key): search (key) in the table. If there is an element with the key value, then you have to output (key):FOUND_ATi,j; where i is the hash table index and j is the linked list index. If there are multiple elements with the same key value, choose the first one appearing in the linked list. If you couldn’t find the key, then output (key):NOT_FOUND;• o: output the table. Output the entire hash table. Each line should begin with the slot/hash table index followed by key values in the linked list. For example, if m = 3 and we inserted 3, 6, and 1 into an empty table in this order, then you should output 0:6->3->; 1:1->; 2:;• e: finish your program. Example of input and output The following example shows an execution of the program in interactive mode. See the input files and output files under the testfiles folder for examples where input and output are separated. 2 i4 i2 i6 i3 o 0:6->2->4->; 1:3->; s2 2:FOUND_AT0,1; s4 4:FOUND_AT0,2; d5 5:DELETE_FAILED; d2 2:DELETED; o 0:6->4->; 1:3->; e See the lab guidelines for submission/grading, etc., which can be found in Files/Labs.
