Programming Questions and Answers March 08, 2021

1. Draw a transition diagram to recognize the following operators Lexemes Token Name Attribute Value artop MU artop EX relop GT relop GE relop EQ relop NE

Consider histogrambased density estimation for some PDF p(x) defined on the interval 0, 1. Suppose that we are given a training set D of n samples drawn from p(x), D X1, X2, ..., xn. Further suppose we use the following m equallength bins for computing the histogram B0, 1m), B21m, 2m), Bm(m1)m, 1. With this, we may count the number of samples

2 Let p(x) U(0, a) be uniform from 0 to a, and let a Parzen window be defined as (x) ex for 0 and 0 for x 0. (a) Show that the mean of such a Parzenwindow estimate is given by Pn(x) 0 (1ehn) (eahn 1)ehn x 0 0 x a ar. (b) Plot Pn(x) versus x for a 1 and h 1, 14, and 116. (c) How small does h have to be to have less than one percent bias

Find the coefficient of each of the following. a) x5y8 in (xy)13. b) x7 in (1x)11

a) What is a basic block b) Convert the following C code to assembly code. Then find out (1) basic blocks, (2) data dependence, (3) antidependence, (4) output dependence, and (5) control dependence. for (i 0 i 10 i) xi 2 yi Note Use so and s1 for base address registers of x and y array, respectively, and use ao for i. For the rest of registers,

What are the preorder, inorder, and postorder sequences for the following tree 46 31

12. What is wrong with the following program 1 public class Temperature ( 2 3 4 5 6 7 8 9 10 11 12 13 public static void main (String args) double tempf 98.6 double tempc 0.0 ftoc (tempf, tempc) System.out.println (Body temp in C is tempc) converts Fahrenheit temperatures to Celsius public static void ftoc (double tempf, double tempc)

1. Find a minimumcost path from s to t in the multistage graph of Figure 5.4. Do this first using the forward approach and then using the backward approach. S 1 5 2 2 3 3 3 8 6 5 4 5 6 1 4 2 6 Figure 5.4 Multistage graph for Exercise 1 2 7 8 7 3 9 t

Calculate the codewords for the following bit strings using CRC8. Show your work (a) k 12 bits, the dataword is 0100 0011 0101, n 20 bits, and the 9bit CRC divisor is 1 0000 0111 (b) k 24 bits, the dataword is 0011 0011 0011 0111 0011 0010, n 32 bits, and the 9bit CRC divisor is 1 0000 0111

We have a combinatorial logic function that can be decomposed into three steps each with the indicated delay with a resulting clock speed of 4.55 GHz. 55ps 60ps 80ps You can use an expression if you like. Reg 25ps Assume we further pipeline this logic by adding just one additional register between the first two or last two stages of combinatorial

Consider a complete binary tree, i.e., nodes have either 0 or 2 children which can be accessed via pointers node.left and node.right and each node is also associated with a numeric key node.k. Note that the children pointers for leaves will be NULL. Employ a Divide and Conquer approach to sum the keys of all nodes in the tree given a pointer to

What is the time complexity of the following code segment def run(s list) for x in s for i in range(0,1000) print(xi)

What is printed after the following code snippet terminates void solve(struct Node head) The LinkedList is defined as headdata value of the node headnext address of next element from the node The List is 1232 5 int sum 0 while(head next NULL) sum headdata headheadnext printf(d , sum)

What is the output of the code,int main() int a1 int p, q pa qP printf(d , a) p2 printf(d , a) q3 printf(d , a) return 0

4. What are the values of these sum (2 Marks) 1), 1(21 j) 2) 1(2j3)

What is the output of the following code snippet for 12345 void solve(struct Node head) while(head NULL) printf(d , head data) head head next

What is time complexity of fun() int fun (int n) int count 0 i 0 i 2) for (int j 0 j

Given the table1 below A tibble 6 x 4 country year cases population 1 Afghanistan 1999 745 19987071 2 Afghanistan 2000 2666 20595360 3 Brazil 1999 37737 172006362 4 Brazil 2000 80488 174504898 5 China 6 China 1999 212258 1272915272 2000 213766 1280428583 Explain the result after running RScript below table1 count (year, wt cases)

a) i) The convolution operator is defined as hn x n hixni Eq(1). 00 Simplify yn hn xn to a closedform expression given that, i0 72 n xn (1) un and hn () un. N n0 Do not use the ztransform method use the summation formula for the simplification an 1a N1 1a ,n 0,a 1 (4 marks) ii) From the closedform expression obtained above, evaluate yn for

Let cos sin A . 9 0,2. sin cos Find expressions for cond, (A) and cond. (A) as functions of 9 and verify them using the corresponding MATLAB functions for various values of 0.

In general, how many key of a for 2by2 Hill cipher exist Show your work. Please follow these steps as guide to find the answer If the determinant of the matrix, adbc is 13 or is even the matrix is not allowed. Therefore a. Find the number of matrices whose determinant is even because one or both rows are even, i.e. all element of that row are

4. Create a AVL tree for the following numbers 15,30,25,35,10,12,70 50,90

What is the time complexity of the function f(n) log i in i1

What category of logic circuit is shown here CAZA CA 02 01 00 HalfAdder HaltAdder STOIT SUM CARRY SUM CARE FullAdder SUM CARRY FORAnder UM CARRY FullAdder SUM CARRY HalfAdder display 7777 SUM CARRY

Draw the Linked list resulting from the execution of the below program. class Application public static void main(String args) Linked List list1 new LinkedList() NodeData (33)) NodeData (77)) list1.addTail (new NodeData (11)) list1.delete (33) list1.addHead(new list1.addHead(new list1.insert(new NodeData (55), 2) list1.print() end main()

Consider Finite State Machines and depicted in Figure 5. input a,b pure output yo, y pure To ay 21 by ay (a) System X2 ay input a, b pure output y pure (a) 5 marks Is E simulated by E Prove your answer. (b) 5 marks Is E simulated by E Prove your answer. ay ay 21 ay Figure 5 Systems E and E for Question 6. by (b) System 23 by 22 ay

3 7. Starting at vertex r, perform a depth first search. a P a 3 8. Starting at vertex p. perform a breadth first search. h I h b b

In twodimensional graphics, a clip region may be defined so that pixels are only drawn within the boundaries of a window or frame. Clip regions can also be used to selectively control pixel rendering for aesthetic or artistic purposes. a) ANALYSE the types of clipping algorithm and clipping algorithm that can be used to processing the speed and

The structure Person is declared as follows struct Person string personSS string personName int personAge double balance 1. Write a definition statement that defines a Person structure variable initialized with the following data (10 points) SS590904090, Name Juan Perez. Age30, balance20,000 2. Define an array of 20 of Person structure variables

Write a program to print out all Armstrong numbers between 1 and 500. If sum of cubes of each digit of the number is equal to the number itself, then the number is called an Armstrong number. For example, 153 ( 111) (5 5 5) (333) Sample run Please enter the number 153 The number is 153 is an Armstrong number

2. Given the graph, G(V,E a. Draw the Minimum Spanning Tree using Prims Algortihm (source A) b. Draw the Minimum Spanning Tree using Kruskals Algortihm. c. Solve for the SingleSourceShortestPath (SourceA, TargetG) using Dijkstras Algorithm and related DP table.,A D 7 9 6 B 15 F 8 7 8 11 E 5 C 9 G

Given a knapsack of capacity (M) 8, put some combination of the following objects in it to maximize the overall value of the knapsack. Item Weight Value 1 2 3 4 st 5 6 4 2 3 1 6 4 6 4 5 3 9 7 Acti b. What is the estimated worstcase time complexity of finding the optimal combination of objects Go to for the generalized knapsack problem

2. Using Kruskals Algorithm a. find the MST of this graph. S 3 P 9 5 2 P 6 b. what is the estimated worstcase time complexity of finding this tree 6 6 a 3 5 4

4. Using Dijkstras Algorithm a. find the Single Source Shortest Path (SSSP) from node A to node node M 8 H 5 F node 12 18 B 9 E 7 G 47 13 K 26 edge and weight b. List the nodes of the shortest path c. What is the estimated worst case time complexity to find the shortest path 34 M

Use Kruskals algorithm and provide a minimumweight spanning tree for the following graph. Provide 1 5 5 3 3 3 4 3 details of how your MST is built stepbystep. 4 2 2 5 5 5 4 points

Use Sympy to 1. Solve the following system of equations (50 pts) x y z x y 4 2 x y 2 2. Solve the following ordinary differential equation (50 pts) f(x) 2 f(x) f(x) sin(x)

.

What will be displayed when the button is clicked Sub btnDisplayClick( ). Dim x, y As String X SI yNO Swap (x, y) msgBox (x y) End Sub Sub Swap (ByVal x As String, ByVal y As String) Dim temp As String temp x x y y temp End Sub

What will be displayed when the button is clicked Sub btnDisplayClick( ) Dim num As Integer 10 Compute (num) txtBox.Text CStr (num) End Sub Sub Compute(ByVal var As Integer) var var 3 End Sub

What will be displayed when the button is clicked Sub btnDisplayClick( ) Dim a, b, c As String. a y b E C S PrintWords (a, b, c) End Sub Sub PrintWords (ByVal x As String, ByVal y As String, ByVal z As String) Strig myVar myVar z y x msgbox (myvar) End Sub

Write a C programs to 1. Create a class called Student with four (4) private member variables, name (string), quiz, midterm, final (all double type) (1 point) 2. Include all necessary member functions for this class (at least 1 constructor, 1 get function, and 1 grading function see 6) (3 points) 3. Declare three (3) objects of Student type

Write a C program that accepts an integer number and prints the following 1) Sum of even factors of the number if the number more than 99 2) Sum of digits of the number if the first bit in binary representation is 1. 3) The next prime if the number is not prime.

Write a C Program to print the first letter and last name of (Mohamed Thnabi) using stars. Note 1) Using nested dowhile Loop 2) The number of lines is given by user. 3) Using one Outer loop to print your letters. 4) Print the letters beside each other. For example Student Name Mohamed Kareem Output

e) What will be the output from the following code for recursive(5) Please show how void int recursive(int a) If (a0 a1) return 1 int b recursive(a1) recursive (a2) return b

(c) (i) The algorithm Mystery (A0..n1,K) is given in Appendix G. Derive a recurrence relation for the number of times the basic operation is performed. 2 marks (ii) Using the Masters theorem or otherwise, determine the efficiency class of algorithm Mystery. 2 marks,Appendix G Mystery(A0..n1, K) Input An array A0..n1 sorted in ascending order and

Find the value of J after executing the following program. I1 J0 15 J J212 IF (LEQ 3) GO TO 16 I11 GO TO 15 16 CONTINUE

The value of j after executing the following code is i0 while i

What are the values of i and j after executing this code j 0 i1 Whilej 5,Fori1,i

Find the loop invariant of the code where n 1). Algorithm 1 sum (int n) p0 i0 while in do pp2i i end while return p (a) (4 points) What does the loop do Write down a formula with the variable n. Prove the correctness of the loop invariant. (b) (4 points) Basis step (when n 1) (c) Inductive step i. (3 points) What is your inductive hypothesis ii.

Select the output of this small code snippet. int a 3 if (a 1) cout Greater than 1. cout Less that 1. Less than 1. Greater than 1. Greater than 1.Less than 1. This code will not compile.

Analyze the worstcase time complexity of the following algorithm in detail Input is an array of some size, say n, containing numbers that fit into a word of the machine. You may assume n is a power of 4. What is the size of the input and why Algorithm Weird (Array A). If A is of size less than 5, then call Mergesort (A) otherwise Divide A into

Consider the following definition of the recursive function mystery. int mystery(int num) if (num

What is the output of Mystery(10) Mystery(n) for (in,i 0, i) enqueue (ii) on the queue while (the queue is not empty) dequeue an integer off the queue write the integer on the screen

Write a C function (along with helper functions) that prints out all the prime numbers in a given array of integers. Your code should follow the exact function declaration given below void printPrimes(int array, int arrsize) Input int array Array of integers that will be passed to this function as a reference int arr size Size of the input array

1. Device an algorithm for a binary search implementing a Decrease by factor algorithm. Compute for its running time. When will be the time it is in best case, average and worst case. 2. Show how shaker sort will be implemented when sorting data in ascending order 98436 10 2 23 156 3. Compute how the course will be taken using Topological sort.

An approximate formula for 1 (sin(2x)2r) is sin(2.r) 2x 1 2 2 15 4 315 Write a program that, for given a, computes 1sin(2x)2r using the approximate formula provided above, and then computes the exact value using the math function sin(). The program should read from the keyboard and should report the exact value, the approximation, and the percent

Given the following code for a form Discipline Code Title

Given the method implementation, do the following int CalculateDeviation (int x, int y) a int total0 b if (x30) C total (x40y50).95 d for (int i0 i

Write a program which reads a date in the format DayMonYear (e.g., 10december2011) and then prints the result to the screen. Your program inputoutput should look like Enter a date in the format DayMonYear 08Jan2020 You Entered 08Jan2020 C program language

Let G be the graph below. A B H I C (b) What is the chromatic number of G Explain. (c) What is the chromatic index of G Explain. J K G D FL E (a) Determine whether it is bipartite. If the graph is bipartite, determine whether it has a perfect matching. Justify your answer. (d) Does G have a Hamiltonian Path Justify. (e) Does G have an Euler tour

Let G and H be the graphs below. For each graph, determine whether it is bipartite. If the graph is bipartite, determine whether it has a perfect matching. Justify your answer. Graph G a h Graph H b

What is the output that you see on the screen if the following piece of code ran Only type what is printed onto the screen due to this code running. int x for (x5 x

Show the expected screen output in the space indicated. int main (void) int num 1 while (num

What is printed to the screen when the following piece of code is executed 1 include 2 include 3 4 int main() 5 6 7 8 9 10 float amount amount 15 2 4.0 3 printf(f, amount)

Find a Minimum Spanning Tree for the following graph. a 4 6 4 b 7 h 8 9 6 50 g f

Write the weakest possible precondition that prevents any inbuilt exceptions from being thrown in the following Java function. Pre int foo(int A, int B) int r 0 for (int i 0 i A.length1 i) rAi1 Bi return r

Write a C program that does the following 1) Use a C function named readArray (int array) to read 15 integer numbers into an array 2) Use a C function named maxOfArray (int array) to find the maximum number of the above array and display it 3) Use a C function named minOfArray (int array) to find the minimum number of the above array and display

Determine the running time of the following findMaxDoubleArray method using longer method that we have discussed in the class. int findMaxDoubleArray(int a) int n sizeof(a0) sizeof(int) int maxa00 for(int i0 i

How many times will the for loop in the following code run and what will the output be Work this out by hand and just use MATLAB to check your answer. x 2 sum 1 for k 15 end sum 11xsum disp(sum ) disp (sum)

Calculate the result of blending the following colors, assuming that source blending factor is equal to source colors alpha value and sum of source and destination blending factors is one (write down the calculation steps). (a) (5 points) destination glColor4f(0.1, 0.2, 0.8, 0.5), source glColor4f(0.7, 0.3, 0.1, 0.3) (b) (10 points) There are

In the code below we have the variables x, y and z. In which segments will we find the data structures that they are bound to global, stack or heap. int x 3 int sompek(int i) int y 10, 11, 12, 13 return yi int main() int z sompek (x) printf(sompek d , z) return 0 xglobal, y heap, z stack X global, y stack, z stack x heap, y heap, z

Write a C program. Use a dowhile loop that takes in positive integer numbers between 1 and 100. Break out of the loop when enters 1. Output the count of numbers greater than or equal to 50. Enter the number 6 Enter the number 61 Enter the number 4 Enter the number 5 Enter the number 50 Enter the number 89 Enter the number 1 you entered 3 nos 50.

Generate a MATLAB code that plots the following truncated Fourier series for a square wave of period To and peaktopeak amplitude 2V N 2A XN (t) einwot jnn nN This can be rewritten in the combined XN (t) Or in the trigonometric form as trigonometric form as 4A n1 n odd NIT cos (nwot 7). N 4A xv(t) ta sin(nwot), nn n1 n odd The program should

a) A processor executes native instructions by using six basic operations of fetch, decode, execute, addressdecode, memory access and writeback. Each of these operations take one clock period. Show how pipelining the hardware units for the abovementioned basic operations can lead to a speedup over an equivalent non pipelined processor if three

Given a cyclic graph, we want to traverse entire graph in such a way that from starting node till supporting node named, each node should be visited twice through different neighbors with any cost, after reaching that node from now further every node should be visited once only with minimum cost. Your task is to design a program that traverse and

Assume we have a continuoustime analog signal with duration of 10 minutes, and we want to transform it into a digital signal via sampling and quantization. The sampling frequency is 100 MHz. (i) How many sampled values are obtained for every second of the analog signal (2 marks) (ii) When each sampled value is quantized with 32 levels, what is the

1. Calculate the indegree and outdegree of each node. Execute BFS and DFS on this graph. Write down the output. Suppose, A is the starting node. A B D E F

Using the following topology Answer 29524 Switcho fa01 PCPT PCO fa03 Sales 10.0.0.1 fa02 D PCPT PC1 Account 10.0.0.2 Trunk Port fa03 295024 Switch1 fa01 PCPT PC2 Sales 10.0.0.3 A) Create a similar topology using Cisco Packet Tracer. B) Configure the IP addresses on the PCs. C) Create two VLANs (Sales and Account) D) Configure VLAN trunking. fa02

1. a) b) c) d) What are the difference between arithmetic and logical operation What types of operation are possible in SAP1 Computer Write down the instruction set and the corresponding opcode of SAP1 Computer. How many operations are possible in SAP1 computer Explain your answer. Create a SAP1 assembly language program and then generate the

1. The following questions will be based on the Employee Table as below EmpName (b) (c) Write SQL commands to (a) Create table EMPLOYEE. (d) EmpNo 100 (e) Ali Hassan 101 Mohd Anwar Ali 102 Aminah Hassan 103 Rahayu Rahim 104 Jamaluddin Johari 105 Sarimah Ibrahim 106 Mohd Ali Hashim Date Birth 121971 121972 841973 961975 2171977 1121970 1961970

2. You are assigned to design a Hospital Management System for Klang Valley Medical Centre. The following are requirements of the system There are three types of employees in this hospital which are the physician (medical doctor), nurse and administrator. Unlike administrative staff, a physician and a nurse staff have special attributes. A

1. a) Find the complexity of the following algorithm. What will be the output for mn6 FinalGame(int m, int n) for (i0 i

5. Convert the following NPDA to an equivalent contextfree grammar. 90 8. 8 8,8 E. E 91 92 0,8 X 1,8 X 93 0, E X 1, X E 1,8 X 0, X 8

Write a Java program to find the longest prefix that is also a suffix of a given string. The prefix and suffix must not overlap. Sample program runs Enter a text pattern ABABABABAB Longest nonoverlapping suffix that is also a prefix is ABAB its length is 4 Enter a text pattern AAAA Longest nonoverlapping suffix that is also a prefix is AA its

1. Consider the mechanical system shown in figure below. If xi(t) is the input, obtain the transfer function Y(s)X(s) of the system. All initial conditions are zero. (30 pts) ww Figure1. Mechanical System

Find the transfer function X,(s)X(s) of the mechanical system shown in Figure 450. The displacements x, and x, are measured from their respective equilibrium positions. Obtain the displacement xo(t) when the input x (1) is a step displacement of magnitude X, occurring at t 0. Assume that x,(0) 0. Figure 450 Mechanical system. k b www CH ww k Xo

After which line of code, the rslt will receive the data from database O A. try (ResultSet rslt pstmt.executeQuery()) O B. if (rslt.next()) O C. pstmt.setInt(1, id) O D. try (PreparedStatement pstmt conn.prepareStatement(SELECT id FROM Favorites WHERE id , ResultSet.TYPEFORWARDONLY, ResultSet. CONCURUPDATABLE)),try (Connection conn

Find the solution x(t) of the differential equation x 4x 0, x(0) 5, Problem B223 Obtain the solution x(t) of the differential equation x x 1, x(0) 0, Problem B224 Determine the solution x(t) of the differential equation 2x 2x x 1, x(0) 0, Problem B225 Obtain the solution x(t) of the differential equation x x sin 3t, x(0) 0, (0) 0 (0)

Write a program that accepts an integer array as input from the user and prints out only elements that do not repeat themselves. Your program should have a function, named finduniqueelements for finding the elements that are unique to that array and print them on the screen. Also, write a separate input function for reading in the array elements

The Preorder Traversal of the following Binary Search Tree is 1 3 6 4 8 (10) (14) 7 (13) O 8, 1, 3, 6, 7, 4, 10, 13, 14 O 1, 4, 7, 6, 3, 13, 14, 10, 8 O 8, 3, 1, 6, 4, 7, 10, 14, 13 O 1, 4, 3, 6, 7, 10, 14, 13, 8 O 8, 3, 1, 6, 7, 4, 10, 13, 14

You are asked to compare the sorting algorithms below both empirically and theoretically. Use 1000 randomly generated arrays for each problem size (small (size 100), medium (size 1000), and large (size 10000)). Empirical results should be obtained as the average of the 1000 independent runs for each algorithm and problem size individually.

What is the time complexity of the below algorithm: def myFunction ( n ) : if n < 2 : out = 1 else: out = myFunction ( n - 1 ) + myFunction ( n - 2 ) return out Group of answer choices O ( 2 ^ n ) O ( log ( n ) ) O ( n log ( n ) ) O ( n ^ 2 )

In the array representation of the following Binary tree, the index of node (F) is F B 10 O 6 O 12 O 7 O 5 D G H E

What is the Boolean function for the following truth table x y Z F 0000 001 1 010 0 1 0 1 1 1 1 0 1 00 0 0 1 1 1 0 0 1 1 0 O A. F zy zy OB. Fyz O C. Fyz O D. F xy O E. F xy xz

Consider the unweighted directed graph G (V, E) below. h How many strong connected components does the graph have A. 1 B. 2 C. 3 D. 4 E. Strong connected component algorithms can only be applied on DAG graphs.

Use fixedpoint iteration to locate the root of f(x) cos x x Use an initial guess of co 0.5 and iterate until a 0.01. Display graphically the approximate solutions and relative errors in each iteration steps. (b) 10 points Use the NewtonRaphson method to determine a root of f(x) 9x 1.6x2 using To 0.5. Perform the computation until Eq is less

There are some syntax errors on the following code fragment. Rewrite the correct code. public Student string name boolean gender char grade. A public static void main(String args ) Student ali new Student () name Ali bin Abu gender true System.out.println (grade) (5 marks)

Frame A and B are initially coincident. Frame B is translated 10 units along x axis, 5 units along y and 1 unit along z axis. Find T Q A point in B is p find the coordinates in A

Consider the network shown in the figure below (H) 14 6 F 1 1 4 2 9 3 (B1 2 4 (A) (E) a) Show the operation of Dijkstras (Link State) algorithm for computing the least cost path from A to all destinations and based on this result define the least cost from F to A b) Consider only the part of the network made up by the nodes H, G, and B and ignore

Consider the following preemptive variant of the Load Balancing problem There are m identical machines, and n jobs with processing times t, t2,, tn respectively. Each machine can process at most one job at a time. Each job can run on more than one machines but must run on at most one machine at any time. Let T max maxisjntj, E

Assume at the sampling instant for the second bit of the 0101 pattern, we get (x4) mV, 0.7mv, (x) mV, and (x4) mV from the four symbols and (x3) mV from the noise. 1. What is the ISI component 2. What is the sampler output of this bit 3. Can we receiver this bit correctly if the threshold is 0.25mv 4. What will be the output if we have a ZFE in