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.
If it is a programming problem, your answers must contain the following three parts.
• Breakdown of the problem or pseudocode
• Code
• Test results
Question 1 (20 points)
Since the four functions have the same purpose, one pseudocode is enough, but every function must be tested individually.
• int calculate_product1(int [] arr, int n);
• int calculate_product2(int [] arr, int n);
• int calculate_product3(int [] arr, int n);
• int calculate_product4(int [] arr, int n);
Question 2 (30 points)
• 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.
• 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.
• 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)
• 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.
• 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.
• 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)
• Give the design of struct Node according to the description of the problem.
• Compared to normal linked list, what are the pros and cons of having two link fields (next_item and previous_item)?
• 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]]