COMP 1011 Programming Fundamentals
Final Assignment
This assignment has four questions and accounts for 35% of your final grade. For every question, write the breakdown of the problem or pseudocode (no more than one page!) first and then write code. The reasons are two-fold. It helps you figure the solution, and this would earn you some points if your program is incorrect. Unless specified, you can only use “stdio.h” for each question. Besides, you also need to show the screenshot of the test cases.
You are required to submit the assignment via filling the answer sheet. Any plagiarism will lead to failure of this assignment. Since the workload of the final assignment is intended for 2-4 hours, any late submissions will also lead to failure of this assignment.
Question 1 (20 points)
Given an integer array arr with size n. Calculate the product of the array if the integer is non-zero. For example, arr = {1, 2, 3, 5, 0}, the function should return 30. You are required to implement 4 different versions of functions to achieve this. Note, for, while, or do-while looping statements cannot be used for more than one time in this question. The product will not exceed the limit of the maximum of int.
Test cases:
arr = {1,2,3,5,0}, n =5
arr = {1,2,3,4,5,6}, n =6
arr = {1,4,9,0,0,7,2,0}, n =8 (the array is derived from the digits of your netid)
1) int calculate_product1(int [] arr, int n); 2) int calculate_product2(int [] arr, int n); 3) int calculate_product3(int [] arr, int n); 4) int calculate_product4(int [] arr, intn);
Question 2 (30 points)
Christmas is approaching. Alice wants to draw a Christmas tree. Could you help her to draw and print it using a computer? The requirements are as follows.
The tree consists of branch and trunk (see the figure below). The height of trunk is half of that of branch. branch_size belongs to [1, 100].
The tree is formed by sequential capital letters (from A to Z, after Z start from A again).
The order of letter in branch is from left to right line by line, while the order in trunk is from up to down as shown in the figure.
Branch
Trunk
1) Write a function char* print_tree(int branch_size) to print out the tree. The parameter argument is the height of branch. And the returned string is formed by the characters sequentially (no space, no newline). For example, in example of the figure, the following string should be returned.
“ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRS
TUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKL
MNOPQRSTUVWWXXYYZZAA”
2) Instead of using alphabet table, write another function char * print_tree_userdefine(int branch, char * pattern, int n), where pattern is the string to be repeated with a length of n. For example, below is the printed patterns of print_tree_userdefine(10, “CHRISTMAS”, 9). Also, this function will return a string consists of all the characters.
“CHRISTMASCHRISTMASCHRISTMASCHRISTMASCHRISTMASC HRISTMASCHRISTMASCHRISTMASCHRISTMASCHRISTMASCH RISTMASCHHRRIISSTT”
3) In the print_tree function, given branch_size, the tree is determined. Write a function int search_tree(int branch_size, char * str, int n) to determine whether the tree contains a given string (str with length of n) by looking at corresponding characters sequentially. If yes, return 1, otherwise return 0. For example, the figure above shows the tree of branch_size=10. Given “CHRIS”, 1 should be returned.
Question 3 (30 points)
We have learned many types of ADT. The ADT stack could be implemented using array and linked list. A stack S should contain the following operations:
push(S, x) — Push element x onto the stack S.
pop(S) — Remove the element on top of the stack.
is_empty(S) — check the stack is empty or not
print(S) — show the content of the stack, from bottom to top.
1) Implement the stack for storing char variables using linked list. Besides the application in the problem, give two more applications that are commonly solved using stacks.
2) Given a string containing alphabets and brackets including “{}”, “[]”, “()”. Using a stack to check whether the given string has isolated brackets. If yes, return 1. Otherwise, return 0. For the following cases, “if(a==1)}”, “main() {int a; printf);}”, “” the function should return 1.
3) Could you use at most two stacks to implement a Queue ADT including en_queue, de_queue, and is_empty operations?
Question 4 (20 points)
A linked list is a very important and fundamental structure. It usually contains a data field for storing the data and link field for linking to the next node. Now, you are required to write a function to deep copy a given linked list. Deep copy means the nodes are dereferenced rather than references to objects being copies. The copied linked list is thus independent of the original linked list. You may refer to here for more information of deep copy.
The node of the linked list to be copied consists of the following fields.
val: an integer data
next_item: a pointer pointing to the next node.
previous_item: a pointer pointing to the previous node.
random_item: a pointer pointing to a random node, could be null, previous nodes, or nodes afterwards.
1) Give the design of struct Node according to the description of the problem.
2) Compared to normal linked list, what are the pros and cons of having two link fields
(next_item and previous_item)?
3) Write a function struct Node * deep_copy (struct Node * head). The input is a 2D array
showing the number of nodes. For each subarray, it contains the data and the index of random_item. For example, the figure below is illustration of the first input test case.
Test cases:
Input: head = [[10,2],[20,2],[30,null]]
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]