Consider rendering a triangular mesh using OpenGL. A uniform…

Question Answered step-by-step Consider rendering a triangular mesh using OpenGL. A uniform… Consider rendering a triangular mesh using OpenGL. A uniform material is used for the entire mesh and the reflection model of the material consists of ambient, diffuse and specular components. There are two point light sources in the scene. Given these assumptions, answer the following questions: (a) Gourand and Phong shading are two different methods of interpolating colours between vertices. Explain how each method interpolates colours. [5 marks] (b) Discuss the trade-offs in terms of quality and computational costs for Phong and Gourand shading. Assume that the number of rendered pixels is much larger than the number of vertices. What kind of artefacts can one of the methods produce and what is the reason for those artefacts? 7 marks] (c) For each of Gourand and Phong shading, explain how you would implement each shading method using vertex and fragment shaders in OpenGL. Complete the diagram shown below by listing all inputs, outputs and uniforms for each shader. Then, explain what is computed in each shader in the case of both shading methods. There is no need to write equations or code, but you may include them if it helps your explanationA 2-3 tree is analogous to a 2-3-4 tree but has only 2-nodes and 3-nodes. (a) Show in detail the steps to build a 2-3 tree from the sequence . Highlight any procedural differences to building a 2-3-4 tree. [7 marks] (b) A red-black tree can be based on a 2-3 tree. An example red violation for such a structure is sketched below, with red nodes represented using unfilled circles. Sketch examples of the remaining red-violation cases, providing example values within the nodes. For each case, sketch its resolution, assuming each case occurs as a sub-tree of a larger tree. [5 marks] (c) Consider restricting the 2-3 variant of a red-black tree so that red nodes may only lie on the left of a parent. (i) Discuss the effect this has on the search and insert performance. How does it impact the implementation? [5 marks] (ii) How does it affect the worst-case costs of finding the minimum and maximum values iFoundations of Computer Science (a) Write brief notes on ML datatypes and pattern-matching in function declarations. [6 marks] (b) A binary tree is either a leaf (containing no information) or is a branch containing a label and two subtrees (called the left and right subtrees). Write ML code for a function that takes a label and two lists of trees, returning all trees that consist of a branch with the given label, with the left subtree taken from the first list of trees and the right subtree taken from the second list of trees. [6 marks] (c) Write ML code for a function that, given a list of distinct values, returns a list of all possible binary trees whose labels, enumerated in inorder, match that list2 CST.2013.1.3 2 Foundations of Computer Science The function perms returns all n! permutations of a given n-element list. fun cons x y = x::y; fun perms [] = [[]] | perms xs = let fun perms1 ([],ys) = [] | perms1 (x::xs,ys) = map (cons x) (perms (rev ys @ xs)) @ perms1 (xs,x::ys) in perms1 (xs,[]) end; (a) Explain the ideas behind this code, including the function perms1 and the expression map (cons x). What value is returned by perms [1,2,3]? [7 marks] (b) A student modifies perms to use an ML type of lazy lists, where appendq and mapq are lazy list analogues of @ and map. fun lperms [] = Cons ([], fn() => Nil) | lperms xs = let fun perms1 ([],ys) = Nil | perms1 (x::xs,ys) = appendq (mapq (cons x) (lperms (rev ys @ xs)), perms1 (xs,x::ys)) in perms1 (xs,[]) end; Unfortunately, lperms computes all n! permutations as soon as it is called. Describe how lazy lists are implemented in ML and explain why laziness is not achieved here. [5 marks] (c) Modify the function lperms, without changing its type, so that it computes permutations upon demand rather than all at once. [8 marks] All ML code must be explained clearly and should be free of needless complexity. 3 (TURN OVER) CST.2013.1.4 SECTION B 3 Discrete Mathematics I (a) Consider the following assertions about the sets A, B and C. Write them down in the language of predicate logic. Use only the constructions of predicate logic (?, ?, ¬, ?, ?, ?) and the element-of symbol (?). Do not use derived notions (?, ?, =, etc.). Example: “A is a subset of B” can be formalized as ?x. x ? A =? x ? B. (i) The sets A and B are equal. (ii) Every element of A is in the set B or the set C. (iii) If A is disjoint from B then B and C overlap. [6 marks] (b) State the principle of induction over lists. Use the language of predicate logic. [2 marks] (c) Consider the following functions over lists of integers, written in ML syntax. fun app([],ys) = ys | app(x::xs,ys) = x::app(xs,ys); fun rev([]) = [] | rev(x::xs) = app(rev(xs),x::[]); fun revapp([],ys) = ys | revapp(x::xs,ys) = revapp(xs,x::ys); Prove that ?xs. revapp(xs,[]) = rev(xs) Your proof should be clear but it does not need to be a structured proof. You may use the abbreviation xs @ ys for app(xs,ys). You may assume the following facts. ?xs. xs @ [] = xs ?xs, ys, zs. xs @ (ys @ zs) = (xs @ ys) @ zs Hint: first use induction to show that ?xs. ?ys. revapp(xs,ys) = app(rev(xs),ys). [12 marks] 4 CST.2013.1.5 4 Discrete Mathematics I (a) Write down the introduction and elimination rules for the universal quantifier (?), the existential quantifier (?) and negation (¬) in structured proof. [6 marks] (b) Write down the introduction rule for implication (=?) in structured proof. [1 mark] (c) Write down a structured proof of the following sentence. (?x. ¬P(x)) =? ¬?x. P(x) [5 marks] (d) Write down a structured proof of the following sentence. Clearly state any proof rules that you use in addition to those included in part (a) and part (b). (¬?x. ¬P(x)) =? ?x. P(x) [8 marks] 5 (TURN OVER) CST.2013.1.6 SECTION C 5 Algorithms I One of several ways to perform string matching efficiently is with a finite state automaton (FSA). (a) Give a brief but clear explanation of the FSA string matching algorithm, its complexity and any associated data structures. [Note: pseudocode of up to 10 lines is allowed, but not required.] [4 marks] (b) Build the FSA that will find matches of the pattern P = pepep in an arbitrary string T over the alphabet {e, o, p}, explaining what you do and why. [6 marks] (c) The correctness proof of the FSA string matching algorithm involves the function ?P (x), which is parametric in the pattern P and takes as input a string x. Define ?P (x), explaining what it returns. [1 mark] (d) Let A, B, C, D be character strings; let |A| be the length of string A; let + denote integer addition or string concatenation depending on its operands. Let D be the longest suffix of A that is a prefix of B. For each of the following claims: either prove the claim correct, or give a counterexample that proves it is incorrect. You may draw an explanatory picture if it helps clarity. (i) ?B(A) = D [3 marks] (ii) ?B(A + C) = |D| + |C| [3 marks] (iii) |C| = 1 ? ?B(A + C) = ?B(A) + 1 [3 marks] 6 CST.2013.1.7 6 Algorithms I A palindrome is a string that, if reversed, remains the same, for example “madamimadam”. A subsequence of a string x is one obtained by dropping zero or more characters from x and taking the remaining ones in order: for example “tan” is a subsequence of “pentagon”. In this question you must find the longest palindrome subsequence (LPS) of a given string. [Note that the LPS may not be unique.] (a) Explain why it is possible to apply dynamic programming to the LPS problem. Develop and explain a recursive equation for the length of the LPS. [6 marks] (b) Develop and describe in detail, with pictures where appropriate, a bottom-up dynamic programming algorithm to solve the LPS problem. Include an explanation of how to recover the LPS from the bottom-up table you build. If you use pseudocode (not required), keep each pseudocode chunk under 10 lines and comment it clearly. Incomprehensible code will be scored as wrong. [9 marks] (c) Derive the asymptotic worst-case running time of your algorithm. [2 marks] (d) What else would you have to do to recover all the LPSs of a given string? [3 marks] 7 (TURN OVER) CST.2013.1.8 SECTION D 7 Floating-Point Computation The following two functions are algorithms for exponentiation where x is a singleprecision floating-point value and n is an integer, fun power1(x, n) = if n=0 then 1.0 else x * power1(x, n-1) fun power2(x, n) = if n=0 then 1.0 else if even n then power2(x * x, n div 2) else x * power2(x, n-1) (a) What is, roughly, the largest value of n that can be used without overflow when x is 10.0? [1 mark] (b) Suppose x is close to 1.0. (i) What is the worst possible relative error to expect in the answer from power1 when n = 100? [3 marks] (ii) Can we say anything useful about the absolute error in part (b)(i)? [1 mark] (iii) What is the expected value of the relative error in results from power1? [1 mark] (c) Sometimes the expected magnitude of error can be estimated as the result of a random walk. (i) Under what conditions is this appropriate? [2 marks] (ii) What is the random walk estimate for the relative error in part (b)(i)? [3 marks] (d) If x is again close to 1.0, what is the worst possible relative error to expect from power2 when n = 100? [6 marks] (e) For what range or class of x values will power2 with n = 100 give a result with no error? [3 marks] 8 CST.2013.1.9 8 Object-Oriented Programming with Java Sparse matrices are matrices whose elements are predominantly zero. This question develops a Java representation for them called SparseMatrix. The code below seeks to use an ArrayList of LinkedLists . ANSWER ALL QUESTIONS, Computer Science Engineering & Technology C++ Programming FIN 9999 Share QuestionEmailCopy link Comments (0)