Description
Problem 1
You are tasked with creating a memory-efficient implementation for storing and processing a sparse matrix using a
linked list. The matrix has a large number of rows and columns, but only a small percentage of the entries are nonzero.
Complete the provided program listmatrix.c, which includes a definition of a matrix as a linked list and the
documentation. The program also includes a function to print the matrix and a main function with sample test ( Make
sure you add your own tests to ensure your solution’s correctness).
You are to complete the following functions:
1) void insert_entry(struct SparseMatrix* result, int row, int col, int value);
The Function adds a new entry to the SpareMtrix at the front. Assume all arguments are valid.
2) struct SparseMatrix multiply_matrices(const struct SparseMatrix* matrix1,
const struct SparseMatrix* matrix2);
The Function takes two SparseMatrix and returns the result of multiplying those two matrices.
3) void free_sparse_matrix(struct SparseMatrix* matrix);
The function frees the memory allocated on the heap pointed at by the head of the matrix.
You are to submit listmatrix.c file containing all implemented functions (you must delete the test cases
portion/main function). However, you must keep the required included libraries and structure definitions.
Note: The order of multiplication or the output (order of printed lines) doesn’t matter as long as it represents the
results correctly.
Here is a sample test and the expected output:
1. #include <stdio.h>
2. #include <stdlib.h>
3. // A structure for representing a single entry in the matrix. THis part is stored in the heap
4. struct MatrixEntry {
5. int row; // the row number of a specific entry
6. int col; // the col number of a specific entry
7. int value;
8. struct MatrixEntry* next; // Pointer to the next entry in the linked list
9. };
10. // A structure for representing the sparse matrix. This part is stored in the stack
11. struct SparseMatrix {
12. int num_rows; // the dimension of the matrix is
13. int num_cols; // num_rows X num_cols
14. struct MatrixEntry* head; // Pointer to the first entry of the linked list
15. };
16.
17. // Define a function to insert a new entry into the front of the result matrix
18. void insert_entry(struct SparseMatrix* result, int row, int col, int value) { }
19.
20. // Define a function that multiplies two sparse matrices with valid sizes
21. struct SparseMatrix multiply_matrices(const struct SparseMatrix* matrix1, const struct SparseMatrix* matrix2) {
}
22.
23. // Define a function to free memory allocated for a sparse matrix
24. void free_sparse_matrix(struct SparseMatrix* matrix) { }
25.
26. // Function to print a sparse matrix
27. // Do not change this Function
28. void print_sparse_matrix(const struct SparseMatrix* matrix) {
29. for (struct MatrixEntry* entry = matrix->head; entry != NULL; entry = entry->next) {
30. printf(“(%d, %d): %d\n”, entry->row, entry->col, entry->value);
31. }
Page 3 of 9
32. }
33.
34. // for testing. Do not submit the main Function
35. int main(void) {
36. // Create and initialize sparse matrices (matrix1 and matrix2)
37. struct SparseMatrix matrix1;
38. matrix1.num_rows = 3;
39. matrix1.num_cols = 4;
40. matrix1.head = NULL;
41. // Initialize matrix1 with some entries
42. insert_entry(&matrix1, 0, 0, 1);
43. insert_entry(&matrix1, 1, 1, 2);
44. insert_entry(&matrix1, 2, 2, 3);
45. insert_entry(&matrix1, 0, 3, 5);
46. printf(“Matrix1 3×4:\n”);
47. print_sparse_matrix(&matrix1);
48.
49. struct SparseMatrix matrix2;
50. matrix2.num_rows = 4;
51. matrix2.num_cols = 3;
52. matrix2.head = NULL;
53.
54. // Initialize matrix2 with some entries
55. insert_entry(&matrix2, 0, 0, 4);
56. insert_entry(&matrix2, 1, 1, 5);
57. insert_entry(&matrix2, 2, 2, 6);
58. insert_entry(&matrix2, 3, 2, 3);
59. printf(“Matrix2 4×3:\n”);
60. print_sparse_matrix(&matrix2);
61. // Multiply matrices
62. struct SparseMatrix result = multiply_matrices(&matrix1, &matrix2);
63.
64. // Print the result matrix
65. printf(“Result matrix1 x matrix2:\n”);
66. print_sparse_matrix(&result);
67.
68. // Free memory allocated for matrices and result
69. free_sparse_matrix(&matrix1);
70. free_sparse_matrix(&matrix2);
71. free_sparse_matrix(&result);
72.
73. return 0;
74. }
75.
The expected output (the order of the output of the matrix itself does not matter):
Matrix1 3×4:
(0, 3): 5
(2, 2): 3
(1, 1): 2
(0, 0): 1
Matrix2 4×3:
(3, 2): 3
(2, 2): 6
(1, 1): 5
(0, 0): 4
Result matrix1 x matrix2:
(0, 0): 4
(1, 1): 10
(2, 2): 18
(0, 2): 15
Page 4 of 9
Problem 2
Duck-Duck-Goose is a game in which a group of people sit in a circle while one person walks around the circle at a time.
• Let’s call the person walking around the circle P As P passes people sitting down, they will tap on the sitting
person’s head and say either ”duck” or ”goose”.
• If P says ”duck”, nothing will happen, and they will continue walking.
• If P says goose, the sitting person will get up and chase P around the circle.
• If P is touched before running around the circle once, they must stay as P.
• Otherwise, the previously sitting person becomes P.
• In this alternative of the game, the loser will instead be eliminated from playing, and the winner will become P.
For this question, you will simulate a game of duck-duck-goose.
The struct to represent a person is as follows:
typedef struct Person {
int id;
int speed;
struct Person* next;
}Person;
Create a program that takes in as input lines…
person1 speed1
person2 speed2
.
.
.
personn speedn
where personn is a unique integer ID to represent the nth person and speedn is a positive integer to represent the
speed of the nth person. Construct a link list of people in the order they are given that forms a ring such that the last
person points to the first person in the list.
P will start off as the first person to read in from standard input. After reading in all participants, the program should do
the following:
I) P will call n people “duck” and the n + 1th person goose where n is the id of P. As P goes from person
to person, print either
c duck d
or
c goose! d
Where c is the id of P and where d is the id of the sitting person P passes.
Page 5 of 9
II) When P calls goose, the winner is the person with the highest speed value.
If the speeds are the same, the winner is the “goosed” person. That person will become the new P, and the loser will
leave the circle. Continue playing duck-duck-goose, moving on to the person after the winner until one person is left.
III) At the end, print
winner! d
where d is the id of the winner.
Example Input1
1 2
2 4
3 3
4 1
?
Example Output1
1 duck 2
1 goose! 3
3 duck 4
3 duck 2
3 duck 4
3 goose! 2
2 duck 4
2 duck 4
2 goose! 4
winner! 2
Page
6 of
9
Example Input
2
1 2
2 3
3 4
4 5
5 6
6 7 ?
Example Output
2
1 duck 2
1 goose! 3
3 duck 4
3 duck 5
3 duck 6
3 goose! 2
3 duck 4
3 duck 5
3 duck 6
3 goose! 4
4 duck 5
4 duck 6
4 duck 5
4 duck 6
4 goose! 5
5 duck 6
5 duck 6
5 duck 6
5 duck 6
5 duck 6
5 goose! 6
winner! 6
Page
7 of
9
Example Intput
3
3 6
1 5
2 7
4 4
6 1
5 3 ?
Example Output
3
3 duck 1
3 duck 2
3 duck 4
3 goose! 6
3 duck 1
3 duck 2
3 duck 4
3 goose! 5
3 duck 1
3 duck 2
3 duck 4
3 goose! 1
3 duck 2
3 duck 4
3 duck 2
3 goose! 4
3 duck 2
3 duck 2
3 duck 2
3 goose! 2
winner! 2
Page 8 of 9
Example Intput4
1 5
2 7
3 5
4 1
?
Example Output4
1 duck 2
1 goose! 3
3 duck 4
3 duck 2
3 duck 4
3 goose! 2
2 duck 4
2 duck 4
2 goose! 4
winner! 2
Create a C program duckgoose.c that completes the following functions :
Person updatePerson(int id, int speed);
void addPerson(Person** start, Person* new);
Person* play(Person* start)// frees any person who leaves the game.
You are to submit this file containing all implemented functions (that is, you must delete the test cases portion/main
function). However, you must keep the required included libraries and structure definitions.
The provided main function to play the game:
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <stdbool.h>
4.
5. typedef struct Person{
6. int id;
7. int speed;
8. struct Person* next;
9. }Person;
10.
Page 9 of 9
11. Person updatePerson(int id, int speed) {
12. }
13.
14. void addPerson(Person** start, Person* new) {
15. }
16. // Returns the winner
17. Person* play(Person* start) {
18. }
19.
20. int main(){
21. int amount;
22. int p, s;
23. // List of people
24. Person* lop = NULL;
25. // Read in participants
26. while (scanf(“%d %d”, &p, &s) == 2){
27. Person* np = (Person*)malloc(sizeof(Person));
28. *np = updatePerson(p, s);
29. addPerson(&lop, np);
30. }
31. Person* winner = play(lop);
32. free(winner);
33. }
34.