1. In one or two sentences, describe what a greedy algorithm is. Your definition should be informal, something you could share with a non computer scientist. 2. There are many different problems all described as “scheduling” problems. In the following questions, pay attention to the details of the problem setup, as they will change each time! (a) Let each job have a start time, an end time, and a value. We want to schedule as much value of non-conflicting jobs as possible. Use a counterexample to show that Earliest Finish First (the greedy algorithm we used for jobs with all equal value) does NOT work in this case. (b) Kleinberg, Jon. Algorithm Design (p. 191, q. 7) Now let each job consist of two durations. A job i must be preprocessed for pi time on a supercomputer, and then finished for fi time on a standard PC. There are enough PCs available to run all jobs at the same time, but there is only one supercomputer (which can only run a single job at a time). The completion time of a schedule is defined as the earliest time when all jobs are done running on both the supercomputer and the PCs. Give a polynomial time algorithm that finds a schedule with the earliest completion time possible. CS 577 Assignment 3: Greedy Algorithms (c) Prove the correctness and efficiency of your algorithm from part (c). Page 2 of 6 CS 577 Assignment 3: Greedy Algorithms 3. Kleinberg, Jon. Algorithm Design (p. 190, q. 5) (a) Consider a long straight road with houses scattered along it. We want to place cell phone towers along the road so that every house is within four miles of at least one tower. Give an efficient algorithm that achieves this goal using the minimum possible number of towers. (b) Prove the correctness of your algorithm. Page 3 of 6 CS 577 Assignment 3: Greedy Algorithms 4. Kleinberg, Jon. Algorithm Design (p. 197, q. 18) Your friends are planning to drive north from Madison to the town of Superior, Wisconsin over winter break. They have drawn a directed graph with nodes representing potential stops and edges representing the roads between them. They have also found a weather forecasting site that can accurately predict how long it will take to traverse one of the edges on their graph, given the starting time t. This is important because some of the roads on their graph are affected strongly by the seasons and by extreme weather. It’s guaranteed that it never takes negative time to traverse an edge, and that you can never arrive earlier by starting later. (a) Design an algorithm your friends can use to plot the quickest route. You may assume that they start at time t = 0, and that the predictions made by the weather forecasting site are accurate. Page 4 of 6 CS 577 Assignment 3: Greedy Algorithms (b) Demonstrate how your algorithm works using a small example with 6 nodes. Your demonstration should include any data structures you maintain during the execution of your algorithm and any queries you make to the weather forecasting site. For example, if your algorithm maintains a “current path” that grows from (M)adison to (S)uperior, you might show something like the following table: Path Total time M 0 M,A 2 M,A,E 5 M,A,E,F 6 M,A,E 5 M,A,E,H 10 M,A,E,H,S 13 Page 5 of 6 CS 577 Assignment 3: Greedy Algorithms Coding Question 5. Implement the optimal algorithm for interval scheduling (for a definition of the problem, see the Greedy slides on Canvas) in either C, C++, C#, Java, or Python. Be efficient and implement it in O(n log n) time, where n is the number of jobs. The input will start with an positive integer, giving the number of instances that follow. For each instance, there will be a positive integer, giving the number of jobs. For each job, there will be a pair of positive integers i and j, where i < j, and i is the start time, and j is the end time. A sample input is the following: 2 1 1 4 3 1 2 3 4 2 6 The sample input has two instances. The first instance has one job to schedule with a start time of 1 and an end time of 4. The second instance has 3 jobs. For each instance, your program should output the number of intervals scheduled on a separate line. Each output line should be terminated by a newline. The correct output to the sample input would be: 1 2
1. Kleinberg, Jon. Algorithm Design (p. 67, q. 3, 4). Take the following list of functions and arrange them in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your list, then it should be the case that f(n) is O(g(n)). (a) f1(n) = n 2.5 f2(n) = √ 2n f3(n) = n + 10 f4(n) = 10n f5(n) = 100n f6(n) = n 2 log n (b) g1(n) = 2log n g2(n) = 2n g3(n) = n(log n) g4(n) = n 4/3 g5(n) = n log n g6(n) = 2(2n) g7(n) = 2(n 2 ) CS 577 Assignment 2 – Asymptotic Analysis & Graphs 2. Kleinberg, Jon. Algorithm Design (p. 68, q. 5). Assume you have a positive, non-decreasing function f and a positive, increasing function g such that g(n) ≥ 2 and f(n) is O(g(n)). For each of the following statements, decide whether you think it is true or false and give a proof or counterexample. (a) log2 f(n) is O(log2 g(n)) (b) 2 f(n) is O(2g(n) ) (c) f(n) 2 is O(g(n) 2 ) Page 2 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs 3. Kleinberg, Jon. Algorithm Design (p. 68, q. 6). You’re given an array A consisting of n integers. You’d like to output a two-dimensional n-by-n array B in which B[i, j] (for i < j) contains the sum of array entries A[i] through A[j] — that is, the sum A[i] + A[i + 1] + … + A[j]. (Whenever i ≥ j, it doesn’t matter what is output for B[i, j].) Here’s a simple algorithm to solve this problem. f o r i = 1 to n f o r j = i + 1 to n add up a r ra y e n t r i e s A[ i ] through A[ j ] s t o r e the r e s u l t i n B[ i , j ] e n d fo r e n d fo r (a) For some function f that you should choose, give a bound of the form O(f(n)) on the running time of this algorithm on an input of size n (i.e., a bound on the number of operations performed by the algorithm). (b) For this same function f, show that the running time of the algorithm on an input of size n is also Ω(f(n)). (This shows an asympto tically tight bound of Θ(f(n)) on the running time.) (c) Although the algorithm provided is the most natural way to solve the problem, it contains some highly unnecessary sources of inefficiency. Give a different algorithm to solve this problem, with an asymptotically better running time. In other words, you should design an algorithm with running time O(g(n)), where limn→∞ g(n) f(n) = 0. Page 3 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs Graphs 4. Given the following graph, list a possible order of traversal of nodes by breadth-first search and by depth-first search. Consider node 1 to be the starting node. 5 4 3 2 1 9 8 7 6 5. Kleinberg, Jon. Algorithm Design (p. 108, q. 5). A binary tree is a rooted tree in which each node has at most two children. Show by induction that in any binary tree the number of nodes with two children is exactly one less than the number of leaves. Page 4 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs 6. Kleinberg, Jon. Algorithm Design (p. 108, q. 7). Some friends of yours work on wireless networks, and they’re currently studying the properties of a network of n mobile devices. As the devices move around, they define a graph at any point in time as follows: There is a node representing each of the n devices, and there is an edge between device i and device j if the physical locations of i and j are no more than 500 meters apart. (If so, we say that i and j are “in range” of each other.) They’d like it to be the case that the network of devices is connected at all times, and so they’ve constrained the motion of the devices to satisfy the following property: at all times, each device i is within 500 meters of at least n 2 of the other devices. (We’ll assume n is an even number.) What they’d like to know is: Does this property by itself guarantee that the network will remain connected? Here’s a concrete way to formulate the question as a claim about graphs. Claim: Let G be a graph on n nodes, where n is an even number. If every node of G has degree at least n 2 , then G is connected. Decide whether you think the claim is true or false, and give a proof of either the claim or its negation. Page 5 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs Coding Question 7. Implement depth-first search in either C, C++, C#, Java, or Python. Given an undirected graph with n nodes and m edges, your code should run in O(n + m) time. Remember to submit a makefile along with your code, just as with week 1’s coding question. Input: the first line contains an integer t, indicating the number of instances that follows. For each instance, the first line contains an integer n, indicating the number of nodes in the graph. Each of the following n lines contains several space-separated strings, where the first string s represents the name of a node, and the following strings represent the names of nodes that are adjacent to node s. You can assume that the nodes are listed line-by-line in lexicographic order (0-9, then A-Z, then a-z), and the adjacent nodes of a node are listed in lexicographic order. For example, consider two consecutive lines of an instance: 0, F B, C, a Note that 0 < B and C < a. Input constraints: • 1 ≤ t ≤ 1000 • 1 ≤ n ≤ 100 • Strings only contain alphanumeric characters • Strings are guaranteed to be the names of the nodes in the graph. Output: for each instance, print the names of nodes visited in depth-first traversal of the graph, with ties between nodes visiting the first node in input order. Start your traversal with the first node in input order. The names of nodes should be space-separated, and each line should be terminated by a newline. Sample: Input: 2 3 A B B A C 9 1 2 9 2 1 6 5 3 4 6 6 2 4 5 2 3 2 7 7 3 8 9 9 1 8 Output: A B C 1 2 6 4 5 3 7 9 8 The sample input has two instances. The first instance corresponds to the graph below on the left. The second instance corresponds to the graph below on the right. Page 6 of 7 CS 577 Assignment 2 – Asymptotic Analysis & Graphs A B C 5 4 3 2 1 9 8 7 6
1. Using a truth table, show the equivalence of the following statements. (a) P ∨ (¬P ∧ Q) ≡ P ∨ Q Solution: (b) ¬P ∨ ¬Q ≡ ¬(P ∧ Q) Solution: CS 577 Assignment 1 – Discrete Review (c) ¬P ∨ P ≡ true Solution: (d) P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R) Solution: Page 2 of 15 CS 577 Assignment 1 – Discrete ReviewSets 2. Based on the definitions of the sets A and B, calculate the following: |A|, |B|, A ∪ B, A ∩ B, A B, B A. (a) A = {1, 2, 6, 10} and B = {2, 4, 9, 10} Solution: (b) A = {x | x ∈ N} and B = {x ∈ N | x is even} Solution: Relations and Functions 3. For each of the following relations, indicate if it is reflexive, antireflexive, symmetric, antisymmetric, or transitive. (a) {(x, y) : x ≤ y} Solution: (b) {(x, y) : x > y} Solution: Page 3 of 15 CS 577 Assignment 1 – Discrete Review (c) {(x, y) : x < y} Solution: (d) {(x, y) : x = y} Solution: 4. For each of the following functions (assume that they are all f : Z → Z), indicate if it is surjective (onto), injective (one-to-one), or bijective. (a) f(x) = x Solution: (b) f(x) = 2x − 3 Solution: (c) f(x) = x 2 Solution: 5. Show that h(x) = g(f(x)) is a bijection if g(x) and f(x) are bijections. Solution: Page 4 of 15 CS 577 Assignment 1 – Discrete Review Induction 6. Prove the following by induction. (a) Pn i=1 i = n(n + 1)/2 Solution: (b) Pn i=1 i 2 = n(n + 1)(2n + 1)/6 Solution: (c) Pn i=1 i 3 = n 2 (n + 1)2/4 Solution: Page 5 of 15 CS 577 Assignment 1 – Discrete Review Graphs and Trees 7. Give the adjacency matrix, adjacency list, edge list, and incidence matrix for the following graph. 1 2 5 3 4 Solution: 8. How many edges are there is a complete graph of size n? Prove by induction. Solution: Page 6 of 15 CS 577 Assignment 1 – Discrete Review 9. Draw all possible (unlabelled) trees with 4 nodes. Solution: 10. Show by induction that, for all trees, |E| = |V | − 1. Solution: Page 7 of 15 CS 577 Assignment 1 – Discrete Review Counting 11. How many 3 digit pin codes are there? Solution: 12. What is the expression for the sum of the ith line (indexing starts at 1) of the following: 1 2 3 4 5 6 7 8 9 10 . . . Solution: 13. A standard deck of 52 cards has 4 suits, and each suit has card number 1 (ace) to 10, a jack, a queen, and a king. A standard poker hand has 5 cards. For the following, how many ways can the described hand be drawn from a standard deck. (a) A royal flush: all 5 cards have the same suit and are 10, jack, queen, king, ace. Solution: (b) A straight flush: all 5 cards have the same suit and are in sequence, but not a royal flush. Solution: (c) A flush: all 5 cards have the same suit, but not a royal or straight flush. Solution: (d) Only one pair (2 of the 5 cards have the same number/rank, while the remaining 3 cards all have different numbers/ranks): Solution: Page 8 of 15 CS 577 Assignment 1 – Discrete Review Proofs 14. Show that 2x is even for all x ∈ N. (a) By direct proof. Solution: (b) By contradiction. Solution: 15. For all x, y ∈ R, show that |x + y| ≤ |x| + |y|. (Hint: use proof by cases.) Solution: Page 9 of 15 CS 577 Assignment 1 – Discrete Review Program Correctness (and Invariants) 16. For the following algorithms, describe the loop invariant(s) and prove that they are sound and complete. (a) Algorithm 1: findMin Input: a: A non-empty array of integers (indexed starting at 1) Output: The smallest element in the array begin min ← ∞ for i ← 1 to len(a) do if a[i] < min then min ← a[i] end end return min end Solution: Page 10 of 15 CS 577 Assignment 1 – Discrete Review (b) Algorithm 2: InsertionSort Input: a: A non-empty array of integers (indexed starting at 1) Output: a sorted from largest to smallest begin for i ← 2 to len(a) do val ← a[i] for j ← 1 to i − 1 do if val > a[j] then shift a[j..i − 1] to a[j + 1..i] a[j] ← val break end end end return a end Solution: Page 11 of 15 CS 577 Assignment 1 – Discrete Review Recurrences 17. Solve the following recurrences. (a) c0 = 1; cn = cn−1 + 4 Solution: (b) d0 = 4; dn = 3 · dn−1 Solution: Page 12 of 15 CS 577 Assignment 1 – Discrete Review (c) T(1) = 1; T(n) = 2T(n/2) + n (An upper bound is sufficient.) Solution: (d) f(1) = 1; f(n) = Pn−1 1 (i · f(i)) (Hint: compute f(n + 1) − f(n) for n > 1) Solution: Page 13 of 15 CS 577 Assignment 1 – Discrete Review Coding Question Most assignments will have a coding question. You can code in C, C++, C#, Java, Python, or Rust. You will submit a Makefile and a source code file. Makefile: In the Makefile, there needs to be a build command and a run command. Below is a sample Makefile for a C++ program. You will find this Makefile in assignment details. Download the sample Makefile and edit it for your chosen programming language and code. # Build commands to copy : # Replace g++ -o HelloWorld HelloWord . cpp below with the appropriate command . # Java : # javac source_file . java # Python : # echo ” Nothing to compile .” #C#: # mcs -out: exec_name source_file .cs #C: # gcc -o exec_name source_file .c #C ++: # g++ -o exec_name source_file . cpp # Rust : # rustc source_file .rs build : g ++ -o HelloWorld HelloWord . cpp # Run commands to copy : # Replace ./ HelloWorld below with the appropriate command . # Java : # java source_file # Python 3: # python3 source_file .py #C#: # mono exec_name #C/C ++: # ./ exec_name # Rust : # ./ source_file run : ./ HelloWorld HelloWorld Program Details The input will start with a positive integer, giving the number of instances that follow. For each instance, there will be a string. For each string s, the program should output Hello, s! on its own line. A sample input is the following: 3 World Marc Owen Page 14 of 15 CS 577 Assignment 1 – Discrete Review The output for the sample input should be the following: Hello, World! Hello, Marc! Hello, Owen!
Algorithms and Data Structures (M) SAMPLE EXAM This exam is multiple-choice and contains 25 questions ((i)-(xxv)). You should select one answer (a, b, c, d) for each question. Each correct answer is worth 2 marks. Incorrect answers will result in a penalty of two thirds of a mark to discourage guessing. A negative mark overall for this question will be rounded up to zero. (i) Which of the following would we use to declare a class named A with a single generic type? (a) public class A { ... } (b) public class A { ... } (c) public class A(E) { ... } (d) public class A(E, F) { ... } (ii) Which of the following methods is not in the Collection interface? (a) clear() (b) isEmpty() (c) size() (d) getSize() (iii) You can use a for-each loop to traverse all elements in a container object that implements which of the following interfaces? (a) Iterator (b) Collection (c) Iterable (d) ArrayList (iv) If list is a LinkedList that contains 1 million int values and A and B are the following fragments of code: A: for (int i = 0; i < list.size(); i++) sum += list.get(i); B: for (int i: list) sum += i; Which of the following statements is true? (a) Code fragment A runs faster than code fragment B (b) Code fragment B runs faster than code fragment A (c) Code fragment A runs as fast as code fragment B (d) It is impossible to tell which of A or B is faster without knowledge of the size of the input integers (v) What will be displayed by the following code? List list = new ArrayList(); list.add("A"); list.add("B"); list.add("C"); list.add("D"); for (int i = 0; i < list.size(); i++) System.out.print(list.remove(i)); (a) ABCD (b) AB (c) AC (d) BCD (vi) What is the output from the following code? import java.util.*; public class Test { public static void main(String[] args) { Set set = new HashSet(); set.add(new A()); set.add(new A()); set.add(new A()); set.add(new A()); System.out.println(set); } } class A { int r = 1; public String toString() { return r + ""; } public int hashCode() { return r; } } (a) [1] (b) [1, 1] (c) [1, 1, 1] (d) [1, 1, 1, 1] (vii) For a sorted list of 1024 elements, a binary search takes at most x comparisons (where a comparison is a check whether an element is greater than, equal to, or less than another element). What is x? (a) 11 (b) 100 (c) 512 (d) 6 (viii) The following recursive algorithm is to calculate the nth Fibonacci number, Fib(n). 1 if n ≤ 2 return 1 2. else return Fib(n-1) + Fib(n-2) The time complexity for Fib(n) is: (a) O(nlogn) (b) O(n2) (c) O(logn) (d) O(2n) (ix) Consider the following code: public class Test { public static void main(String[] args) { Map map = new HashMap(); map.put("123", "John Smith"); map.put("111", "Ella Smith"); map.put("123", "Steve Price"); map.put("222", "Steve Price"); } } Which one of the following statements is true? (a) After all the four entries are added to the map, "123" is a key that corresponds to the value "John Smith" (b) After all the four entries are added to the map, "123" is a key that corresponds to the value "Steve Price" (c) After all the four entries are added to the map, "Steve Price" is a key that corresponds to the value "222" (d) A runtime error occurs because two entries with the same key "123" are added to the map. (x) What is the worst-case time complexity for quick-sort? (a) O(log n) (b) O(n log n) (c) O(n) (d) O(n2) (xi) What is the best-case time complexity for quick-sort? (a) O(log n) (b) O(n log n) (c) O(n) (d) O(n2) (xii) Which of the following Binary Search Trees would result from inserting the values 1, 10, 16, 7, 5 and 2 into an empty Binary Search tree in the given order (i.e. without balancing)? (xiii) Which of the following AVL Trees would result from inserting the values 1, 10, 16, 7, 5 and 2 into an empty AVL tree in the given order (i.e. with balancing)? (xiv) What is the preorder traversal ofthe binary search tree below? (a) 1, 2, 4, 3, 2, 6, 6, 9, 8, 10 (b) 2, 4, 3, 1, 6, 5, 8, 10, 9, 7 (c) 7, 5, 1, 3, 2, 4, 6, 9, 8, 10 (d) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (xv) What is the postorder traversal ofthe binary search tree in (xiii)? (a) 1, 2, 4, 3, 2, 6, 6, 9, 8, 10 (b) 2, 4, 3, 1, 6, 5, 8, 10, 9, 7 (c) 7, 5, 1, 3, 2, 4, 6, 9, 8, 10 (d) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (xvi) What is the inorder traversal ofthe binary search tree in (xiii)? (a) 1, 2, 4, 3, 2, 6, 6, 9, 8, 10 (b) 2, 4, 3, 1, 6, 5, 8, 10, 9, 7 (c) 7, 5, 1, 3, 2, 4, 6, 9, 8, 10 (d) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (xvii) Consider the following algorithm for reading a file of (unsorted) values into a sorted array. There are n values in the file. 1.Set m to 0. 2.While not at end of file f, repeat: 2.1. Read value val from f 2.2. Insert val into the correct position in the sorted array a [0…m–1] 2.3. Increment m 3.Terminate. The complexity of this algorithm is: (a) O(n) (b) O(n2) (c) O(log n) (d) O(n log n) (xviii) Consider the following statements: (S1) When you create an array using new int[10], an array object is created with ten integers of value 0. (S2) When you create an array using new int[10], an array object is created with no values in the array (S3) When you create an ArrayList using new ArrayList (), an ArrayList object is created with no elements in the ArrayList object. (S4) When you create an ArrayList x using new ArrayList (10), x.size() is 10 Which of the following is correct? (a) only S2, S3 and S4 are true (b) only S2 and S4 are true (c) only S1 and S4 are true (d) only S1 and S3 are true (ixx) What is list after the following code is executed? ArrayList list = new ArrayList(); list.add(1); list.add(2); list.add (3); list.add(4); list.remove(2); System.out.println(list); (a) [1,2,3,4] (b) [1,3,4] (c) [1,1,1,1] (d) [1,2,4] (xx) What is the output from the following code? LinkedHashSet set1 = new LinkedHashSet(); set1.add("bubblegum"); set1.add("starburst"); LinkedHashSet set2 = (LinkedHashSet)(set1.clone()); set1.add("smarties"); set2.add("dolly mixture"); set1.remove("bubblegum"); System.out.println(set2); (a) [bubblegum, starburst, smarties, dolly mixture] (b) [starburst, smarties, dolly mixture] (c) [bubblegum, starburst, dolly mixture] (d) [starburst, smarties, dolly mixture] (xxi) What are the best-case and worst-case complexities of the MergeSort algorithm respectively? (a) n log n, n log n (b) n log n, n2 (c) n2, n log n (d) n2, n2 (xxii) Consider the following code: public class Test { public static void main(String[] args) { Map map = new HashMap(); map.put(100, "Darth Vader"); map.put(75, "Kylo Ren"); map.put(150, "Yoda"); map.put(200, "Han Solo"); map.put(150, "R2-D2"); map.put(150, "Boba Fett"); } } Which one of the following statements is true? (a) A runtime error occurs because more than one entry with the same key 150 are added to the map (b) After all the six entries are added to the map, 150 is a key that corresponds to the value "Boba Fett" (c) After all the six entries are added to the map, "Boba Fett" is a key that corresponds to the value 150 (d) After all the six entries are added to the map, 150 is a key that corresponds to the value "Yoda R2-D2 Boba Fett" (xxiii) Suppose that we use a closed bucket hash table H of size 520 to store a set of 1000 words. The load factor of H is approximately: (a) 1/1520 (b) 1520 (c) 2 (d) 0.5 (xxiv) Suppose lists L1 and L2 are represented using singly linked lists whose headers contain only references to the first node of the list in each case. If L1 and L2 have n and n9 elements respectively, the time complexity of concatenating the two lists is: (a) O(1) (b) O(nn9) (c) O(n+n9) (d) O(n) (xxv) Suppose lists L1 and L2 are as for part (xxiii) but this time their using headers contain references to the first and last nodes of the list in each case. The time complexity of concatenating the two lists is now: (a) O(1) (b) O(nn9) (c) O(n+n9) (d) O(n)
EEE8088 Reconfigurable Hardware Design (coursework) Module Outline Aims of the module ● Knowledge, skills and design experience on reconfigurable hardware platforms (FPGA chips) in the context of the respective Degree Programmes. ● Understanding of needs of the modern electronics and comms industry as outlined in IRDS (current edition). ● Consistency in preparation of the students to the Individual Project Group work ● Groups of about 5 students ● Define the functions within the group ● The minutes of 3 progress meetings to be kept for inspection on Teams (to meet the objective of group work training). Very brief. ● Do not copy the reports from each other ● Overview and Discussion sections Assessment ● Report: 100% ● Progress (Part A): oral formative feedback ● Each student submits a separate report ● Please observe the deadline – Penalties for late submission Report ● Individual, one report per student! ● 4000 words, tables, diagrams, code, equations and screen shots are not included in the word count. ● Full listing of code --> Appendix, not included into the word count ● The main text includes only the essential fragments of code/diagrams. Everything else --> Appendix. Sections in the report ● Title page with your details, st. number, etc. ● Aims and Objectives. The two aims (educational and technical). ● Introduction, including discussion of IRDS on reconfigurable platforms, and brief ontology – selected references with a brief comment what is used from them. ● Design specification and the platform. ● Implementation ● Experiments and Discussion ● Conclusion (comment on all your objectives) ● List of References and Appendices
CADE10002 – Lab 4 Signals and Dynamics ay24421 Abstract According to the CADE10002 Lab Guidelines and Dynamics Lab Circuit Step-by-Step Building Guide from the University of Bristol, the experimental purpose, experimental equipment, experimental methods and calculation formulas were determined. The aim of this experiment is to estimate Young's modulus of a metal ruler by using its natural vibration frequency. The experiment involved constructing a microphone circuit with a Raspberry Pi Pico to capture sound signals, processing these signals with Python to determine frequency, and applying a theoretical model to calculate material properties. Key findings indicate that the ruler's Young's modulus approximates that of steel, around 257.305 GPa, though limitations such as errors, noise and measurement precision introduce uncertainty. The experiment successfully demonstrates a low-cost method for material property estimation, applicable in resource-limited scenarios like disaster relief. 1. Introduction The determination of material properties, such as Young's modulus, is critical in engineering applications, particularly in scenarios where traditional testing facilities are unavailable, such as disaster relief efforts requiring emergency repairs. This investigation explores a cost-effective method to estimate the Young's modulus of a metal ruler by measuring its natural frequency as a cantilever oscillator. The approach leverages basic electronics and programming skills to capture and analyze time-varying sound signals produced by the vibrating ruler. Drawing from concepts introduced in Session 17, including vibrational dynamics and signal processing, the experiment aims to calculate the Young's modulus using the fundamental frequency and assess its suitability as a substitute material, for instance, in an ambulance suspension repair. The specific objectives are to construct a functional microphone circuit, acquire and process sound signals accurately, and derive a reliable estimate of the material's Young's modulus. 2. Methods As shown in figure 1, the microphone circuit was assembled on the breadboard. Key components included a condenser microphone (CMC-9745-44P), an LM741 op-amp, resistors, capacitors, and a Raspberry Pi Pico for data acquisition. The circuit amplified the microphone's output, with a high-pass filter (C1) removing DC offset and an op-amp providing gain, while Schottky diodes (1N5817) protected the Pico's ADC pin. Figure 1: the microphone circuit The ruler was clamped to a table edge using a hardback book, creating a cantilever with overhang lengths of 80 mm, 100 mm, and 120 mm, as shown in figure 2. The microphone was positioned 5 cm from the ruler’s free end. DataAcquisition.py was executed in Thonny to record sound signals at 1 kHz when the ruler was 'twanged' three times per length. Figure 2: Experimental setup for 100 mm overhang Signal data was exported as .csv files and analyzed in Jupyterlab. The python code extracted the larger amplitude portion of the ruler vibration signal to eliminate the effect of background noise to accurately analyze the frequency. Implementation steps: 1. Use Jupyterlab to calculate the mean by reading the initial noise file (0.csv) Estimate the amplitude of the static portion of the signal as the noise level 2. The processed data and the initial mean value were subtracted from the parameters of the steel rule vibration respectively to obtain the data with the transverse axis of 0 3. Set 30% of the maximum amplitude to the threshold, retaining only signal segments whose amplitude exceeds the threshold. 4. Find the start and end points in the signal with significant amplitude and crop the signal to extract valid data. 5. Plot images and estimate frequencies using Jupyterlab. Then the basic frequency of the ruler was estimated by counting the number of times the signal crosses the "zero point". Finally, equation 1, equation 2 and deformation equation 3 were used to calculate Young's modulus of steel rule. [1] where f is the fundamental frequency in Hz, E is the Young’s Modulus, I is the second moment of area, q is the mass per unit length, L the free overhang length of the cantilever. [2] where I is the second moment of area, b is the width and h is the thickness. [3] where E is the Young’s Modulus, f is the fundamental frequency in Hz, I is the second moment of area, q is the mass per unit length, L the free overhang length of the cantilever. 3. Results Measurements of the ruler yields a width (b) of 0.0254 m and thickness (h) of 0.0007 m. According to equation 2, the second moment of area I = 7.26 × 10-13 m4 . According to Davis’s paper entitled Metals Handbook Desk Edition. ASM, the density of steel is 7850 kg/m^3. And due to equation 4, the mass per unit length q = 0.1396kg/m [4] where q is the mass per unit length,P is the density, b is the width and h is the thickness According to Jupyterlab's calculations, the initial mean is 35437.4305 (0mm overhang). When the overhang length of the steel rule is 80mm, the original vibration signal curve is shown in Figure 3. Figure 3: 80mm original vibration signal The adjusted vibration signal curve of the 80mm suspension is shown in Figure 4. Figure 4: 80mm adjusted vibration signal The cropped effective vibration signal curve of 80mm overhang is shown in Figure 5. Figure 5: 80mm cropped effective vibration signal By clipping and calculating the zero-intersection using python code, the final frequency is estimated to be 104.52 Hz. Finally, using formula 3, Young's modulus is 274.31 GPa. When the overhang length of the steel rule is 100mm, the original vibration signal curve is shown in Figure 6. Figure 6: 100mm original vibration signal The adjusted vibration signal curve of the 100mm suspension is shown in Figure 7. Figure 7: 100mm adjusted vibration signal The cropped effective vibration signal curve of 100mm overhang is shown in Figure 8. Figure 8: 100mm cropped effective vibration signal By clipping and calculating the zero-intersection using python code, the final frequency is estimated to be 33.51Hz. Finally, using formula 3, Young's modulus is 68.82 GPa. When the overhang length of the steel rule is 120mm, the original vibration signal curve is shown in Figure 9. Figure 9: 120mm original vibration signal The adjusted vibration signal curve of the 100mm suspension is shown in Figure 10. Figure 10: Figure 7: 120mm adjusted vibration signal The cropped effective vibration signal curve of 100mm overhang is shown in Figure 11. Figure 11: 120mm cropped effective vibration signal By clipping and calculating the zero-intersection using python code, the final frequency is estimated to be 43.48Hz. Finally, using formula 3, Young's modulus is 240.30 GPa. 4. Discussion In the second experiment, when the steel rod is overhung at 100 mm, the estimated frequency and Young's modulus are much lower than normal. The possible cause is that the force applied by the hand is not consistent with the other times, which may be caused by too little force. For a longer overhang length (100mm), the vibration of the steel ruler may also be doped with some other vibrations, which are frequencies of other modes, so that the calculated Young's modulus is low. It is also possible that the clamping conditions are unstable, and the clamping point between the steel rule and the book may slip or loosen slightly, affecting the accurate measurement of the frequency. It is also possible that when the signal is clipped, there is a large noise interference in the signal, or the improper selection of the clipping threshold, resulting in inaccurate zero crossing detection, making the frequency estimation wrong. Therefore, this set of experimental data will be invalid. Taking the data of 80mm and 120mm overhang, the average Young's modulus is 257.305GPa and the standard deviation is 17.005GPa. This average of 257.31 GPa is close to the typical Young's modulus of steel (190-210 GPa), but slightly higher, possibly due to measurement errors or differences in the material properties of the steel ruler. Measurement errors may include the difficulty in accurately controlling the magnitude and direction of the force when applying it manually; The steel rule and the hardcover book clamping place are not completely fixed, there will be slight loosening; The method of estimating the frequency through the zero crossing may not be very accurate, the signal will mutate as if by interference, and the error is still significant after slight removal of the mutation in the horizontal axis of the signal. For material properties, the steel ruler may not be pure steel, or there may be manufacturing inhomogeneity, resulting in the actual Young's modulus not exactly consistent with the theoretical value. However, improvements can include the use of standard weights instead of manual force to ensure the same force and direction for each excitation vibration; The use of professional clamps instead of hardcover books to ensure that the steel ruler is completely fixed at the clamp, reducing the change of boundary conditions; The sampling accuracy can also be improved to improve the resolution and accuracy of the frequency measurement. Thus, more accurate measurement of Young's modulus of steel rule material characteristics can be achieved. 5. Conclusion The experiment successfully uses the low-cost microphone circuit and Python signal processing technology to estimate the Young's modulus of the steel ruler by measuring its natural vibration frequency. After excluding the abnormal 100mm overhang data, the average Young's modulus based on the 80mm and 120mm overhang results is 257.31 GPa, close to the typical value of steel (190-210 GPa). Despite some errors, this method demonstrates the feasibility of material property estimation in resource-limited environments such as disaster relief. In the future, the measurement accuracy can be further improved through standardized force application, professional fixation, higher sampling rate and more accurate signal processing technology, and the scheme can also be used to estimate Young's modulus of other materials. References University of Bristol, CADE10002 Lab Guidelines, 2024. University of Bristol, Dynamics Lab Circuit Step-by-Step Building Guide, 2024. Davis, J.R. Metals Handbook Desk Edition. ASM, 1998.
Individual Assignment • Each student is required to submit an individual assignment. • Imagine the future evolution of an organism (an existing species) and describe its adaptative features for a particular habitat that it lives in. • Make a sketch of this organism. • Annotate 3 adaptive features on the sketch, write a 100-150 words description for each adaptive feature. • Include reference if applicable. Evolutionary adaptations (@ 100-150 words): 1. Eyespots The eyespots at the rump of plains zebras is an anti-predator adaptation. Plains zebras are preyed by ambush predators such as lions, the eye- like pattern at the rump helps to deter predators and increase their survival rate (Radford et al., 2020). Plains zebras (and other zebra species) are born with black and white stripes, and the pattern of the stripes varies among individuals. Individuals with stripe pattern that slightly resembles a circular pattern have slight fitness advantage over individuals that do not; and pattern that resembles eyes are more advantageous than pattern that just resembles a cycle. Therefore, the eye-like stripe pattern is favoured by natural selection because those zebras have higher survival rate, hence are more likely to pass on their gene to the next generation. 2. Black and white neck mane They evolve a thick layer of mane with black and white bands around the neck. The mane provide production to the throat when a predator attack, therefore is favoured by natural selection. The conspicuous black and white pattern on the mane is the evolutionary outcome of sexual selection. Males with more conspicuous black and white stripes on the neck mane stand out more to the predators, therefore have a higher risk of predation. Females use the black and white pattern as an indicator of the males’ fitness (the ability to escape from predators) and prefer to mate with males that have more conspicuous stripe pattern. 3. Widened snout The snout of plains zebras is flat and widened. This gives them an advantage when grazing by allowing them bite off more grass. Individuals that have a wider snout are able to graze more efficiently than individuals that have a narrower snout, therefore, get an advantage in the intra- specific competition for food. When grazing, plains zebras grab a mouthful of grass, then put their head up to stay vigilant of predators while chewing (Sze et al., 2021). A wider snout allows them to grab more grass every time they put their head down and spend more time looking out for predators, reducing the risk of predation. References: Radford, C., McNutt, J.W., Rogers, T., Maslen, B., & Jordan, N. (2020) Artificial eyespots on cattle reduce predation by large carnivores. Communications Biology, 3:430. Yiu, S.W., Keith, M., Karczmarski, L., & Parrini, F. (2021) Predation risk effects on intense and routine vigilance of Burchell's zebra and blue wildebeest. Animal Behaviour, 173:159-168.
Unit: EFIM10023 Mathematics for Economics Assessment’s contribution to unit: 10% Release Date: 23/06/2025 Submission Date: 21/07/2025 at 11:00 am Feedback Released: 21/08/2025 Students are strongly advised to submit their work ahead of the deadline. Should you have a problem with submission to Blackboard you should email ec[email protected] for guidance immediately. • Your video should not exceed 10 minutes. Exceeding this limit will incur a penalty. Details relating to penalties are at the end of this document. • Assignments handed in after the deadline, without a pre-arranged extension, will be subject to late penalties. Details relating to penalties are at the end of this document. • Your assignment should be combined into a single document and submitted as a video with a Word document containing the student numbers. • Your answer will be assessed using the University Marking Criteria. This is a piece of COURSEWORK that contributes to your Unit mark and you can: • Use resources to support you in completing your answer. • Draw upon a range of accepted resources including, your own notes, lecture slides/recordings, course material, textbooks, journal articles, online resources. ALL work should be written in your own words. • Ask for help from your personal tutors or academic lecturers if you do not understand an aspect of the coursework. • Broad discussion with your tutors, fellow students, friends and family on the assessment topic and your ideas/approach may help you to further your knowledge and understanding. • Use your network of family and friends to gain support and encouragement during the assessment period. Please remember this is a formal assessment and you should behave in a manner consistent with our values. This means you cannot: • Allow others to directly contribute to your answer by revising or adding to the academic content. This is collusion and is against University Regulations. • Share your assessment with others or ask others to share their work with you. • Copy and paste any material (text, images, coding, calculations) from other sources, including teaching material and shared revision notes directly into your answer without appropriate acknowledgement. This is plagiarism and is against University Regulations. • Pay another person or company to complete the assessment for you. This is contract cheating and is against University Regulations. In this assignment, you are expected to solve the following open question and present the solution as a video. The video will be judged on its “raw content”, i.e., how it addresses the initial question, but also on the “pedagogical aspect”, i.e., how easy it is for a student to understand the solution. One economist wants to understand the consumption of housing in the United Kingdom. She assumes that households have the following utility: where ch denotes the consumption of housing and cn denotes the consumption of the rest (non-housing, hence n). We have also 0 < α < 1. She would like to estimate ρ in the data; she is less interested in α. 1. Calculate the (log) marginal rate of substitution between housing and non-housing. as a function of the (log) relative consumption. 2. Intuitively, the marginal rate of substitution between housing and non-housing should relate to the relative price between housing and non-housing ph/pn. How, and why? 3. Assume that the economist observes the (different) relative expenditures (phch)/(pncn) and relative prices ph/pn faced by individuals surveyed all across the United Kingdom. How could she use the data to estimate the parameter ρ (using the previous questions)?
Algorithms and Data Structures (M) Exam Code Question 1 Parts (i) - (v) refer to the Java interface for an abstract data type NewStack, the implementing class, LinkedNewStack, and a testing class containing a main method, TestNewStack shown in Boxes 1, 2 and 3. (i) The code defining the Node class within the LinkedNewStack class is referred to as a (a) defining class (b) subclass (c) inner class (d) linked class (ii) Even though the toString method of the interface is not implemented within the LinkedNewStack class, there is no corresponding Java compile-time error reporting an unimplemented method. Why? (a) The toString method isnot called in the main method in the TestNewStack class, so it doesn’t matter (b) The toString method is a public method in the Object class, so it will just not be overridden (c) There would not be an error message if any of the NewStack methods were not implemented in LinkedNewStack (d) There will be an error reported at runtime rather than at compile time (iii) Suppose that we had a correct (according to the descriptive comment in the interface) implementation of the toString() method in the LinkedNewStack class, which of the following strings correctly shows the contents ofthe stack after the main method has executed? (a) 4, 2, 0 (b) 8, 6, 4 (c) 6, 4, 2, 0 (d) 0, 2, 4 (iv) If these two lines of code were added to the bottom of the main method, what would happen? int stackSize = stack1.size (); System.out.println("The stack has size " + stackSize); (a) The following would be output: "The stack has size 3" (b) The following would be output: "The stack has size 4" (c) The following would be output: "The stack has size " (d) There would be an error, as the method size() is undefined for the type NewStack (v) Suppose that I have an alternative implementing class, ArrayNewStack, that implements all the methods of NewStack, but uses an array to store the elements of the stack. To what should I change the instantiation of stack1 in TestNewStack to use a NewStack of that type? (Note that the line breaks in (c) and (d) are not relevant, the code would not fit on one line in these cases). (a) ArrayNewStack stack1 = new NewStack() (b) NewStack stack1 = new ArrayNewStack() (c) ArrayNewStack stack1 = new NewLinkedStack() (d)NewStack stack1 = new NewStack (); (vi) Which of the following correctly describes an Abstract Data Type (ADT)? (a) a type characterised by its possible values, operations and data representation (b) a type characterised by its data representation and operations only (c) a type characterised by its possible values and operations only (d) a type characterised by its possible values and data representation only (vii) Consider the following statements: (S1) When you create an array using new int[10], an array object is created with ten integers of value 0. (S2) When you create an array using new int[10], an array object is created with no values in the array (S3) When you create an ArrayList using new ArrayList(), an ArrayList object is created with no elements in the ArrayList object. (S4) When you create an ArrayList x using new ArrayList(10), x.size() is 10 Which of the following is correct? (a) only S2, S3 and S4 are true (b) only S2 and S4 are true (c) only S1 and S3 are true (d) only S1, S3 and S4 are true (viii) What is printed when the following code is executed? ArrayList list = new ArrayList(); list.add(3); list.add(2); list.add(1); list.add(0); list.remove(3); System.out.println(list); (a) [2,1,0] (b) [3,2,1] (c) [2,1,0] (d) [3,2,1,0] (ix) Consider the following algorithm: Let L be an empty list For i = 1, … , n, repeat: For j = 1,… , n, repeat: For k=1,… , 3, repeat: For m=1,… , 11, repeat: Multiply i,j,k and m and add to L What is the complexity of this algorithm? You may assume that adding to the list is a constant time operation. (a) O(n2) (b) O(n3) (c) O(n4) (d) O(1) (x) Consider the following algorithm to sort an array of integers b Let len be the length of b For i = len-1, … , 1, repeat: For j = i-1, … , 0, repeat: if b[j] is more than b[i] swap b[i] and b[j] What is the complexity of this algorithm? (a) O(n2) (b) O(n3) (c) O(n4) (d) O(1) Question 2 Parts (i) - (iv) refer to the following trees, labelled (A) to (D): (i) Which tree is the result of adding the elements 0,1,2,3,4,5,6 in the given order to an empty binary search tree (i.e. without balancing)? (a) A (b) B (c) C (d) D (ii) Which tree is the result of adding the elements 0,1,2,3,4,5,6 in the given order to an empty AVL (i.e. with balancing)? (a) A (b) B (c) C (d) D (iii) Balancing the tree in question (ii) required the use of which of the following rotations? Note that SR(x) and SL(x) denote a single right/left rotation about the node containing the value x, and DLR(x) and DRL(x) denote a double left- right/double right-left rotation about the node containing the value x. (a) SR(0) and SR(2), SR(1), SR(4) (b) SL(0), SL(2), SL(1), SL(4) (c) SL(0), SL(2), DLR(1) (d) SR(0), SL(2), DLR(4) (iv) Which of the sequences below denotes a postorder traversal oftree (C)? (a) 0, 1, 2, 3, 4, 5, 6 (b) 3, 1, 0, 2, 4, 5, 6 (c) 0, 2, 1, 6, 5, 4, 3 (d) 6, 5, 4, 3, 2, 1, 0 (v) Which of the sequences below denotes a preorder traversal oftree (C)? (a) 0, 1, 2, 3, 4, 5, 6 (b) 3, 1, 0, 2, 4, 5, 6 (c) 0, 2, 1, 6, 5, 4, 3 (d) 6, 5, 4, 3, 2, 1, 0 Parts (vi) - (viii) refer to the partition algorithm, shown in Box 4. (vi) If array a is {2,3,7,10,8,4,1,5,12,0} and the partition algorithm shown in Box 4 is applied to a, with left=0 and right=9, and m is (the integer part of ) (right-left)/2, what is the final state of a? (a) {2,3,4,1,0,5,7,8,12,10} (b) {0,1,2,3,4,5,7,8,10,12} (c) {2,3,7,4,1,5,0,8,12,10} (d) {8,10,12,4,0,1,2,3,5,7} (vii) For an array of length n, what is the maximum number of times that step 3.2.1 is executed? (a) n (b) n-1 (c) log n (d) 1 (viii) If the partition algorithm is used in the partitioning step of the quicksort algorithm, to sort an array of length n, what is the worst-case complexity of quicksort? (a) O(n log n) (b) O(n2) (c) O(n2 log n) (d) O(1) (ix) The recursive Quicksort algorithm is to be used to sort an array of length 15. How many times is Quicksort called (including the original call, and the call to all subarrays, including the arrays of size 1 and 0)? You may assume that the partitioning algorithm used at each stage successfully divides the subarray (excluding the pivot) into parts whose sizes differ by at most 1. (a) 8 (b) 15 (c) 15 x 15 (d) 15 x 3 (i.e. 15 x (log 15)) (x) What are the best-case and worst-case complexities of the MergeSort algorithm respectively? (a) O(n log n), O(n log n) (b) O(n log n), O(n2) (c) O(n), O(n log n) (d) O(n2), O(n2) Question 3 (i) A programmer uses a closed-bucket hash table to store the set of book titles available in a small children’s library. Each book is uniquely identified by a code called an ibcode which consists of the first two letters of the author’s surname (in lower case), the first two letters of the book title (in lower case), and four digits denoting the year of publication. E.g., the ibcode for the book titled “Crossfire” by Malorie Blackman, published in 2019 is blcr2019. The programmer uses a hashtable of size 89, and the hash function determined using the algorithm given in Box 5. What is the hashcode for the book above (with ibcode blcr2019)? (a) 31 (b) 34 (c) 9 (d) 44 (ii) For the hashtable example described in (i), what is the hashcode for the book titled “Gruffalo” by Julia Donaldson, published in 1999? (a) 116 (b) 16 (c) 27 (d) 12 (iii) For the hash table described in part 3(i), assuming that all feasible ibcodes are possible, what is the maximum value that the load factor can be? (a) 89/(262 x 102) (b) 89/(264 x 104) (c) (262 x 102)/89 (d) (264 x 104)/89 Parts (iv) – (v) refer to maps map1 and map2, the data for which is shown in Box 6. (iv) Suppose that map1 and map2 are maps used to store details of the names of players of an online game and their usernames. In each map the keys denote the player names, and the values the usernames. Suppose that some Java code involves the instantiation of both maps as empty treemaps with initial size 20 and their population with the data shown in Box 6, followed by the following code fragment:. map1.putAll(map2); map1.remove("Jessica"); System.out.println("Map 1 is now: " + map1); What is output when the code is run? (a) {Zihan=twoShoes, Ann=m_Inc, Navid=prospo} (b) {Ann=m_Inc, Jessica=notMyBag, Navid=prospo, Zihan=twoShoes} (c) {Ann=m_Inc, Navid=prospo, Zihan=twoShoes} (d) {Ann=m_Inc, Navid=tigerLily, Zihan=twoShoes} (v) What would the output be guaranteed to be ifa hashmap of size 20 were used to implement each of map1 and map2, and the code fragment of part 3(iv) executed? (a) {Navid=prospo, Zihan=twoShoes, Ann=m_Inc} (b) {Ann=m_Inc, Jessica=notMyBag, Navid=prospo, Zihan=twoShoes} (c) {Ann=m_Inc, Navid=prospo, Zihan=twoShoes} (d) None of the above. It is impossible to predict the order in which elements are stored in a hashmap . (vi) Suppose that we have a map with n entries whose keys are integers between 0 and m-1 and whose values are strings (where n ≤ m). We could store the map in the following ways: (a) as a key-indexed array of size m, (b) as a binary search tree, (c) as an ordered singly linked list. Which of these representations would allow the fastest implementation of the put operation? You may assume that the binary search tree is well balanced. (a) The key-indexed array (b) The singly linked list (c) The binary search tree (d) They will be the same - they all have O(n) complexity as we potentially must search the whole map to insert a new entry. (vii) Which of the representations in part (vi) would allow the fastest implementation of the remove operation (which removes the element with a given key - if it exists)? (a) The key-indexed array (b) The singly linked list (c) The binary search tree (d) They will be the same – they all have O(n) complexity as we potentially must search the whole map to remove a new entry. Parts (viii – x) refer to the list of linked list instructions in Box 7. (viii) Let SLL denote a singly linked list of nodes, each of which contain an element and a link to the next node in the list and suppose that SLL’s header consists ofa link to its first node,first. Assuming that the list is not empty, which sequence of instructions from Box 7 should be carried out to insert a new node containing element e into SLL after an existing node pred? (a) G, J, D (b) G, D, J (c) G, D, E (d) D, J, B (ix) If instead we want to add a new node containing element e into an empty singly linked list, what sequence of instructions must we carry out? (a) E, G (b) G, E (c) G, L (d) G, B (x) Let DLL denote a doubly linked list of nodes, each of which contain an element and links to the next and previous nodes in the list and suppose that DLL’s header consists of links to its first and last nodes,first and last. Assuming that the list is not empty, which sequence of instructions from Box 7 should be carried out to insert a new node containing element e into DLL after last? (a) A, H, F, K (b) A, K, H, F (c) A, C, H, F (d) A, D, F, H
Problem Scenario Protein kinases have been an important target for drug discovery, with 71 FDA-approved small-molecule kinase inhibitors as of May 2021, accounting for approximately 30% of approved small-molecule therapeutics in the past two decades. There are over 500 protein kinases in humans, collectively known as the kinome, with only a minority of these kinases explored as primary drug targets in clinical studies. In the past 20 years, the increased access to high-resolution kinase structures and the availability of high-throughput, whole-kinome “profiling” techniques have enabled a deeper knowledge of the basic structure and function of human kinases. This has led to a further understanding of various signaling pathways and their roles in normal physiology, carcinogenesis, and cancer progression. These advances have accelerated the discovery of novel kinase targets, particularly in those treatment-resistant cancer types, and have aided the development of next-generation kinase inhibitors. Table 1. Protein kinase targets and known inhibitors Protein Known Inhibitor JAK1 P23458 Golidocitinib A, B, C, D, Z AKT1 P31749 Capivasertib E, F, G, H, I CDK6 Q00534 Palbociclib J, K, L, M, N ABL P00519 Dasatinib O, P, Q, R, S BTK Q06187 Remibrutinib T, U, V, W, X, Y Many kinases already have approved drugs to treat different diseases. This project aims to find new effective bioactive chemicals for protein kinase targets using in silico approaches to develop an effective treatment for cancers characterized by kinase abnormalities. Please choose one protein kinase from Table 1 as your research target. Marketed anti-cancer standard drugs shall be used for comparative evaluation. Specifically, you will perform. virtual screening through LBDD method (e.g. MOE pharmacophore module) and SBDD method (e.g. Autodock VINA). From the analysis of screening results of these two methods, you will get a shortlist with at least 10 candidate molecules for your target, and assess their bioavailability and toxicity profiles using ADMETlab 3.0 web server. Finally, you will use the molecular dynamics method to analyze the interaction between protein structure and one of the best candidate molecules in your list, with the known drug as the reference. Task 1.Task 2.Task 3.Task 1 as the binding site to do the virtual screening with AutoDock VINA. Process the preparation process for the candidate molecules from Task 4.T 3 to analysis their bioavailability and toxicity profiles on ADMETlab 3.0 web server. Report your key findings and explain. Select the best one candidate molecule comprehensively from docking results from T 5. Take the best one candidate molecule from ASK as a reference system to conduct MD simulation parallelly. Task
ECO2101 Microeconomics CA1 Individual Project July 2025 Semester (Blended) CA1 Individual Project Assessment This CA1 constitutes 30% of the overall ECO2101 Microeconomics course assessment. Rationale of Individual Project This individual project allows you to pursue authentic learning and to apply theories taught in class to real world situations. This encourages independence and self-confidence as well as developing one’s thinking and analytical skills when working through real world situations. Choosing Product Market for Analysis This project involves choosing product(s) for your project analysis, using microeconomics concepts discussed in Lectures 1 to 5. The product or service market can be either general or specific, local or international. Some examples of product or service market: • Smartphones (general) • Apple iphone (specific brand in the smartphone market) • Starbuck Coffee in China (local, specific to a country) • Coffee (international) Choosing Articles as References for Analysis Search through newspapers sources (other sources are strictly not permitted), either in print or online for THREE (3) articles based on the product market you have chosen. Articles should contain real world situations and should be in English. Articles that contain analysis or researched by others should not be used. The articles must be related to the concepts discussed in Lectures 1 to 5. Articles must be dated from 1st March 2025 onwards. The articles are to be based on the following topics. Article 1 – Lecture Topic 1 on Production Possibilities Frontier Article 2 – Lecture Topic 3 on Market Equilibrium Article 3 – Lecture Topic 4 on Elasticity OR Lecture Topic 5 on Utility Select THREE (3) articles on the SAME PRODUCT (for example, all 3 articles on coffee) or DIFFERENT PRODUCTS (for example, 1st article on coffee, 2nd article on apparel and 3rd article on smartphone). Analysing your Product Market n For each article, identify the event(s) or phenomena. Summarise these events in your own words. n Analyse these events using the appropriate microeconomic concepts. Reproducing or paraphrasing the article does NOT constitute an analysis. n Economic diagram(s), where applicable must be drawn to support your analysis. Diagrams must be fully labelled and should not be hand-drawn. n The following analysis must be included. Article 1 - Lecture Topic 1: PPF and Opportunity Cost Shift in PPF (to include diagram to show the shift in PPF) Explain the shape of the PPF (whether bowed shape or straight line PPF) Analyse the opportunity cost when more of one product is produced Article 2 - Lecture Topic 3: Market Equilibrium and Efficiency Change in demand or supply or both (this is term as event) (to include diagram to show the changes in the event and the equilibrium quantity and price) Analyse whether market is efficient before and after change in event Analyse whether consumer surplus, producer surplus and total surplus increase or decrease after change in event (to include diagram to show the changes in consumer surplus and producer surplus) Analyse whether total surplus is maximised before and after change in event Article 3 - Lecture Topic 4: Elasticity Analyse the type of elasticity Explain the type of elasticity using the factors that affect the type of elasticity Analyse the changes in total revenue (to include diagram to show the changes in total revenue) OR - Lecture Topic 5: Utility Analyse the changes in the budget line (to include diagram to show the changes in the budget line) Analyse the changes in the consumer equilibrium using equalisation of MU per dollar (to include the MU per dollar diagram to show the changes in consumer equilibrium) n The following are some suggestions for the analysis: Using PPF concept to analyse a reduction in the production of crops due to natural disasters like earthquakes or flood (topic 1) Using market equilibrium analysis to analyse the changes in the price of semiconductor chips due to the high demand and reduced supply of semiconductor chips (topic 3) Using price elasticity of demand to analyse the elasticity of oil as price of oil rises due essential needs and no close substitutability (topic 4) Using utility and demand to analyse on household consumption choices (topic 5) Writing your Report n Use Times New Roman Font Size 12pt. Number your pages. Use single line spacing. Do a full justification (that is both left and right justified) of your report. n The report should be between 1,000 to 1,500 words. Each Analysis should have at least 180 words. n Use the template in Appendix 1 for your report format. • Limit each analysis to one page. • Begin each analysis on a new page. For example, analysis 2.1 on a new page, analysis 2.2 on a new page, and so on. • Ensure consistency throughout the report. For example, consistent formatting (such as same font type and font size, same line spacing) throughout the whole report; diagrams are all drawn using the same software such as Powerpoint or WPS. Report Grading n This is a short report. The key to a good report is to be clear and concise. Report will be graded on the various report components, namely proper Cover Page, Introduction, Article Summary, Analysis, Diagrams, Conclusion, References as well as Report Consistency. • Marking Scheme Items Marking Scheme Introduction 8 marks Article Summary 18 marks Analysis 39 marks Economic Diagram 18 marks Conclusion 8 marks References 3 marks Report Consistency 6 marks Total 100 marks • Penalty will be imposed for o 20% for late submission of report (within one (1) day after the submission dateline) o Up to 20% for use of non-newspaper sources o Up to 20% for not adhering to dates of articles o Up to 20% for any non-compliance of the other CA1 instruction o Plagiarism, which includes copying from student’s own report submitted previously to SIMGE or other educational institutions, other student reports, any other sources and copying of economics diagrams from google or other sources. Any use of artificial intelligence (AI) software, chatbot, chatbot AI or any system powered by AI, software or otherwise is considered as plagiarism. Submission of Report n Submit the Word format of your report online via Canvas by 25 July 2025 11:59am. Reports submitted through other ways (e.g. through email or hardcopy to the lecturer or the school) will not be accepted.
EEE8088 Reconfigurable Hardware Design Audio Processing on DE1 Aims and Objectives Aim: an approach to the solution Objectives: ● Specification and Architecture ● Reading the manual: codec specs and protocols ● I2C Interface, discussion of the template ● DSP Interface, discussion of the template ● Simulation with ModelSim ● If labs accessible: Debugging with SignalTap, signal generator and oscilloscope Design Specifications ● Source-destination: analogue audio codec ● Input/Output: analogue audio converted into 16- bit, 44.1kHz digital stream. ● Read the CODEC manual and choose the configuration modes (several valid options available) ● Processing: FIR filter on FPGA, 8 taps ● Language: VHDL WM8731 Datasheet rev. 4.8 is used for reference Terasic DE1-SoC development board, Cyclone V FPGA Design Architecture Start with the CODEC! CODEC Configuration ● Analogue I/O – Line ● Gain 1 unit, or 0dB ● Audio CD sampling format; Left channel ● Read “Normal Mode Sample Rates” and see Table 1, mode 01000 (or 11000) ● No CODEC filters, no bypass, no any fancy things... CODEC Clock/Reset ● Clock is denoted as MCLK or AUD_XCK, see p.41, “Normal Mode Sample Rates” ● Power-on reset circuit is built-in ● Software reset by writing to register 0000000, see Table 30, p. 50, “Register Map Description” CODEC Interfaces ● Control Interface: 2-wire MPU, a.k.a. I2C – Used for the initial configuration – Any speed up to 500kHz (choose 100kHz) ● Digital Audio Interface: 3-wire DSP, a.k.a. I2S – Input and output digital audio streams – Master mode (configured on init via I2C) – DSP mode (configured on init via I2C) – Speed 64x44.1 kHz I2C Bus Format ● Bus clock of “almost” arbitrary frequency ● 3 bytes of information – 24 bits total ● Start transition ● Stop transition ● 3 Ack bits – high impedance state Control Information ● 24 bits (see previous slide), MSB first – 7 bits device address, fixed 0011010 – 1 bit R/W bit – 0 for writing – 7 bits register address, see Table 30 – 9 bits of register data, see Table 30 ● The Digital Audio Interface will not work without the configuration supplied via Control Interface!
COMP9414 Artificial Intelligence Assignment 2: Reinforcement Learning Term 2, 2025 Due: Week 9, Friday, 1 August 2025, 5:00 PM AEST Worth: 25 marks (25% of final grade) Submission: Electronic submission via Moodle 1 Problem Overview In this assignment, you will implement and compare two reinforcement learning al- gorithms: Q-learning and SARSA, within a static grid world environment. The grid world consists of an 11 × 11 grid in which the agent must navigate from a random starting position to a designated goal while avoiding fixed obstacles arranged in two distinct patterns. You will first develop the Q-learning and SARSA algorithms, implementing action selec- tion policies that allow the agent to choose actions using an epsilon-greedy approach to balance exploration and exploitation. To ensure fair comparison between the algorithms, you must use identical hyperparameters across all experiments. After training the baseline agents, you will simulate interactive reinforcement learn- ing (IntRL) by introducing a teacher-student framework. In this setup, a pre-trained agent (the teacher) provides advice to a new agent (the student) during its training. Each algorithm will teach its own type: Q-learning teachers will guide Q-learning students, and SARSA teachers will guide SARSA students. The teacher’s advice will be configurable in terms of its availability (probability of of- fering advice) and accuracy (probability that the advice is correct). You will evaluate the impact of teacher feedback on the student’s learning performance by running experiments with varying levels of availability and accuracy. By maintaining consistent hyperparameters across all four tasks, you can meaningfully compare how each algorithm performs with and without teacher guidance. The goal is to understand how teacher interaction influences the learning efficiency of each algorithm and to determine which algorithm benefits more from teacher guidance under identical conditions. 2 Environment The environment is provided in the env .py file. This section provides a brief overview of the grid world environment you will be working with. For detailed information about the environment including setup instructions, key func- tions, agent movement and actions, movement constraints, and the reward structure, please refer to the Environment User Guide provided separately as a PDF file. En- sure you familiarise yourself with the environment before proceeding with the assignment. 2.1 Environment Specifications The environment has the following specifications: – Grid Size: 11 × 11 – Obstacles: 10 cells arranged in two patterns: ◦ L-shaped pattern: (2,2), (2,3), (2,4), (3,2), (4,2) ◦ Cross pattern: (5,4), (5,5), (5,6), (4,5), (6,5) – Goal Position: (10, 10) – Rewards: ◦ Reaching the goal: +25 ◦ Hitting an obstacle: -10 ◦ Each step: -1 Figure 1: The 11 × 11 grid world environment with visual elements. The agent must navigate from its starting position to the goal whilst avoiding the L-shaped and cross- shaped obstacle patterns. Environment Elements: Agent Grey robot that navigates the grid world Goal Red flag at position (10,10) Rewards +25 points Obstacles Construction barriers Penalty of -10 points Status Bar Information: - Episode number - Teacher availability (%) - Teacher accuracy (%) 3 Hyperparameter Guidelines For this assignment, you should use the following baseline parameters: – Learning rate (α): 0.1 to 0.5 – Discount factor (γ): 0.9 to 0.99 – Epsilon: – For exploration strategies with decay: Initial 0.8 to 1.0, Final 0.01 to 0.1 – Decay strategy: Can use linear decay, exponential decay, or other decay strategies – For fixed epsilon (no decay): 0.1 to 0.3 – Number of episodes: 300 to 1000 – Maximum steps per episode: 50 to 100 You may experiment within these ranges, but must: – Use identical parameters across all four tasks (Tasks 1–4) to ensure fair comparison between Q-learning and SARSA, both with and without teacher guidance – Document your final chosen values and provide brief justification – For Tasks 3 and 4 (teacher experiments), you may use fewer episodes to reduce computational time while maintaining meaningful results. 4 Task 1: Implement Q-learning In this task, you will implement the Q-learning algorithm and train an agent in the provided environment. Implementation Requirements Your Q-learning implementation should: – Train the agent for the specified number of episodes using the hyperparameters from Section 3 – Use epsilon-greedy action selection for exploration – Update Q-values according to the Q-learning update rule Metrics to Track During training, track these metrics for each episode: – Total Rewards per Episode: The cumulative reward accumulated during the episode – Steps per Episode: The number of steps taken to complete the episode – Successful Episodes: Whether the agent reached the goal Required Outputs After training is complete, you must produce the following: – Generate a plot that displays the episode rewards over time. The plot should include: ◦ Raw episode rewards (with transparency to show variance) ◦ A moving average line (e.g., 50-episode window) for smoothing ◦ A horizontal line at y=0 to indicate the transition between positive and neg- ative rewards ◦ Appropriate labels, title, and legend Figure 2 shows a sample of what your Q-learning performance plot should look like (generated with simulated data). – Calculate and report the Success Rate, Average Reward per Episode, and Average Learning Speed, using the following formulas: – Success Rate: where N is the total number of episodes. – Average Reward per Episode: where Ri is the total reward in the i-th episode. – Average Learning Speed: where Si is the number of steps taken in the i-th episode. – Keep track of the following outputs: ◦ The three calculated metrics: average reward, success rate, and average learn- ing speed ◦ The trained Q-table, as it will be used as the teacher in Task 3 Figure 2: Sample Q-learning performance plot showing episode rewards and 50-episode moving average. This is generated with simulated data for demonstration purposes only. 5 Task 2: Implement SARSA Important: You must use the same hyperparameters (learning rate, discount factor, epsilon, episodes, and maximum steps) that you chose in Task 1 to ensure fair comparison between Q-learning and SARSA. In this task, you will implement the SARSA algorithm and train an agent in the provided environment. Implementation Requirements Your SARSA implementation should: – Train the agent for the specified number of episodes using the same hyperparameters as Task 1 – Update Q-values according to the SARSA update rule Metrics to Track During training, track these metrics for each episode: – Total Rewards per Episode: The cumulative reward accumulated during the episode – Steps per Episode: The number of steps taken to complete the episode – Successful Episodes: Whether the agent reached the goal Required Outputs After training is complete, you must produce the following: – Generate a plot that displays the episode rewards over time. The plot should include: ◦ Raw episode rewards (with transparency to show variance) ◦ A moving average line (e.g., 50-episode window) for smoothing ◦ A horizontal line at y=0 to indicate the transition between positive and neg- ative rewards ◦ Appropriate labels, title, and legend Figure 3 shows a sample of what your SARSA performance plot should look like (generated with simulated data). – Calculate and report the Success Rate, Average Reward per Episode, and Average Learning Speed using the same formulas as in Task 1 (Equations 1, 2, and 3). – Keep track of the following outputs: ◦ The three calculated metrics: average reward, success rate, and average learn- ing speed ◦ The trained Q-table, as it will be used as the teacher in Task 4 Figure 3: Sample SARSA performance plot showing episode rewards and 50-episode mov- ing average. This is generated with simulated data for demonstration purposes only. 6 Baseline Comparison After completing Tasks 1 and 2, you should compare the baseline performance of Q- learning and SARSA. This comparison will help you understand the fundamental differ- ences between the two algorithms before introducing teacher guidance. Creating the Comparison Generate comparison visualisations that include: – Learning Progress Comparison ◦ Episode rewards for both Q-learning and SARSA (with transparency) ◦ 50-episode moving averages for both algorithms ◦ The y=0 reference line ◦ Average reward values for each algorithm – Success Rate Comparison ◦ Rolling success rates (50-episode window) for both algorithms ◦ Overall success rates for each algorithm ◦ Success rate ranging from 0 to 100% Figure 4 shows a sample baseline comparison plot (generated with simulated data). Figure 4: Sample baseline comparison showing Q-learning vs SARSA performance. Left: Episode rewards with moving averages. Right: Success rate over time. This is generated with simulated data for demonstration purposes only. 7 Teacher Feedback Mechanism A teacher feedback system is a valuable addition to the training process of agents using Q-learning or SARSA. In this system, a pre-trained agent (the teacher) assists a new agent by offering advice during training. The advice provided by the teacher is based on two key probabilities: – The availability factor determines whether advice is offered by the teacher at any step. – The accuracy factor dictates whether the advice given is correct or incorrect. 7.1 How It Works At each step, the system first determines whether the teacher provides advice (based on availability). If advice is given, it then determines whether the advice is correct (based on accuracy). These two checks ensure that advice is provided probabilistically and may not always be accurate. The agent responds to the teacher’s advice as follows: • If the generated advice is correct (given the accuracy parameter), the agent follows the teacher’s recommended action (the action with highest Q-value in the teacher’s Q-table). • If the generated advice is incorrect, the agent takes a random action, excluding the trainer’s best action. • If no advice is given, the agent continues its independent learning using its explor- ation strategy (epsilon-greedy). Figure 5 illustrates the complete decision process for the teacher feedback mechanism. Figure 5: Flowchart showing the teacher feedback mechanism. The student agent’s action selection depends on two probability checks: availability (whether the teacher provides advice) and accuracy (whether the advice is correct). 8 Task 3: Teacher Advice Using Q-learning Agent Important: You must use the same hyperparameters (learning rate, discount factor, epsilon, episodes, and maximum steps) that you chose in Task 1 to ensure fair comparison across all tasks. In this task, you will implement the teacher-student framework where a pre-trained Q- learning agent (from Task 1) acts as a teacher to guide a new Q-learning student agent. Implementation Requirements Your implementation should: – Load the trained Q-table from Task 1 to use as the teacher – Train a new Q-learning student agent with teacher guidance – Implement the teacher feedback mechanism as described in Section 7 – Test all combinations of teacher availability and accuracy parameters Parameter Combinations You must evaluate the following parameter combinations using nested loops: – Availability: [0.1, 0.3, 0.5, 0.7, 1.0] – Accuracy: [0.1, 0.3, 0.5, 0.7, 1.0] This results in 25 different teacher configurations to test. Metrics to Track For each teacher configuration, track these metrics during training: – Total Rewards per Episode: The cumulative reward accumulated during each episode – Steps per Episode: The number of steps taken to complete each episode – Successful Episodes: Whether the agent reached the goal Required Outputs After training with all parameter combinations, you must: – Calculate performance metrics for each configuration: ◦ Success Rate using Equation 1 ◦ Average Reward per Episode using Equation 2 ◦ Average Learning Speed using Equation 3 – Store all results in a structured format with the following data: ◦ Availability ◦ Accuracy ◦ Avg Reward ◦ Success Rate (%) ◦ Avg Learning Speed – Generate a heatmap visualisation showing average rewards for all teacher configur- ations: ◦ X-axis: Availability values ◦ Y-axis: Accuracy values ◦ Colour intensity: Average reward achieved ◦ Include appropriate colour bar and labels Figure 6 shows a sample of what your teacher performance heatmap should look like (generated with simulated data). Figure 6: Sample heatmap showing Q-learning performance with different teacher con- figurations. Note that accuracy increases from bottom to top. This is generated with simulated data for demonstration purposes only. 9 Task 4: Teacher Advice Using SARSA Agent Important: You must use the same hyperparameters (learning rate, discount factor, epsilon, episodes, and maximum steps) that you chose in Task 1 to ensure fair comparison across all tasks. In this task, you will implement the teacher-student framework where a pre-trained SARSA agent (from Task 2) acts as a teacher to guide a new SARSA student agent. Implementation Requirements Your implementation should: – Load the trained Q-table from Task 2 to use as the teacher – Train a new SARSA student agent with teacher guidance – Implement the teacher feedback mechanism as described in Section 7 – Test all combinations of teacher availability and accuracy parameters – Use the same implementation structure as Task 3 for consistency Parameter Combinations You must evaluate the following parameter combinations using nested loops: – Availability: [0.1, 0.3, 0.5, 0.7, 1.0] – Accuracy: [0.1, 0.3, 0.5, 0.7, 1.0] This results in 25 different teacher configurations to test. Metrics to Track For each teacher configuration, track these metrics during training: – Total Rewards per Episode: The cumulative reward accumulated during each episode – Steps per Episode: The number of steps taken to complete each episode – Successful Episodes: Whether the agent reached the goal Required Outputs After training with all parameter combinations, you must: – Calculate performance metrics for each configuration: ◦ Success Rate using Equation 1 ◦ Average Reward per Episode using Equation 2 ◦ Average Learning Speed using Equation 3 – Store all results in a structured format with the following data: ◦ Availability ◦ Accuracy ◦ Avg Reward ◦ Success Rate (%) ◦ Avg Learning Speed – Generate a heatmap visualisation showing average rewards for all teacher configur- ations: ◦ X-axis: Availability values ◦ Y-axis: Accuracy values ◦ Colour intensity: Average reward achieved ◦ Include appropriate colour bar and labels This will allow direct comparison with the Q-learning teacher results from Task 3 to determine which algorithm provides better teaching capabilities. 10 Testing and Discussing Your Code After completing all four tasks, you should analyse and compare your results to understand the impact of teacher guidance on reinforcement learning performance. 10.1 Required Analysis You must perform the following analysis to demonstrate your understanding: 1. Teacher Impact on Learning Curves For selected teacher availability levels (e.g., 0.1, 0.5, 1.0), create plots showing how differ- ent teacher accuracies affect learning progress compared to the baseline. Each plot should show: ◦ Episode rewards (50-episode moving average) on the y-axis ◦ Episodes on the x-axis ◦ Multiple lines for different accuracy levels ◦ Baseline performance for reference Figure 7 shows a sample comparison for Q-learning with 50% teacher availability. Figure 7: Sample comparison of teacher accuracy impact on Q-learning performance with 50% availability. Generated with simulated data. 2. Teacher Effectiveness Summary Create a comprehensive analysis comparing how teacher guidance affects both algorithms: ◦ Generate learning curves showing Q-learning and SARSA performance with selected combinations of teacher availability and accuracy values ◦ Include baseline performance (no teacher) as a reference line ◦ Show multiple combinations of teacher availability (e.g., 0.1, 0.5, 1.0) and accuracy (e.g., 0.3, 0.7, 1.0) to demonstrate the range of teacher impact ◦ Use moving averages to smooth the learning curves for clarity Figure 8 shows a sample teacher effectiveness summary analysis. Figure 8: Sample teacher effectiveness summary showing the impact of different teacher configurations on both Q-learning and SARSA algorithms. This analysis helps identify optimal teacher parameters and compare algorithm responsiveness to guidance.
Algorithms and Data Structurs M COMPSCI5004 April-May diet 2021 (Multiple Choice) This exam is multiple-choice and contains 25 questions ((i)-(xxv)). You should select exactly one answer (a, b, c, d) for each question (if multiple answers are given the question will be marked as wrong). Each correct answer is worth 2 marks. This paper will be implemented as a Moodle quiz. This examination paper is worth a total of 50 marks (i) Suppose that I have a Java class ArrayStack that implements a Java interface Stack, whose operations include the usual push, pop and isEmpty operations. Consider the following Java class: // import statements omitted public class StackExample { public static void main(String[] args) { Stack myStack = new ArrayStack(10); String[] nameArray = { "Albert", "Eddie", "Anna", "David", "Fiona", "Greta" }; String[] newArray = new String[7]; for (String s : nameArray) myStack.push(s); int i = 0; while (!myStack.isEmpty()) { newArray[i] = myStack.pop(); i++; } } } What are the final contents of array newArray? (a) [“Albert”, “Eddie”, “Anna”, “David”, “Fiona”, “Greta”] (b) [“Albert”, “Anna”, “David”, “Eddie”, “Fiona”, “Greta”] (c) [“Greta”, “Fiona”, “David”, “Anna”, “Eddie”, “Albert”] (d) [“Greta”, “Fiona”, “Eddie”, “David”, “Anna”, “Albert”] (ii) Consider the recursive factorial algorithm below, for positive integer n: Factorial(n): yields the factorial of n If n=1 yield 1 Else, yield n*Factorial (n-1) What is the time complexity of this algorithm? (a) O(n) (b) O(2n) (c) O(n2) (d) O(log n) (iii) Consider the following Java class: public class ListExample { public static void pListSet(List l, Set s){ for (Integer i:l) System.out.print (i + " "); System.out.print("; "); for (Integer j:s) System.out.print(j + " "); } public static void main(String[] args) { List myList = new ArrayList(7); Set mySet = new TreeSet(); int temp = 0; for (int i=0;i g swap a[r] with a[g] increment g and r Else if a[r] is “yellow” : if r > y swap a[r] with a[y]. if r > g, swap a[r] with a[g]. Increment y, g, and r. 3. Terminate. If the algorithm is applied to the array a below: a = ["green", "yellow", "red", "green", "red"] What is the final state of a? (a) ["green", "yellow", "red", "green", "red"] (b) ["yellow", "green", "green", "red", "red"] (c) ["green", "green", "yellow", "red", "red"] (d) ["red", "red", "yellow", "green", "green"] (xii) What is the time complexity of the algorithm of part (xi), given that swapping two elements of the array is a constant time operation? (a) O(n2) (b) O(n) (c) O(log n) (d) O(1) (xiii) Consider the following sorted array: If linear search is used to locate the string “pear”, what are the strings contained in the first 3 array positions visited? If required, you may assume that, for an array with smallest and largest indices left and right respectively, the index approximately at the middle of the array is calculated as the integer part of (left+right)/2. (a) “melon”, “raspberry”, “pear” (b) “satsuma”, “raspberry”, “pear” (c) “melon”, “pear” (no further positions need to be visited) (d) “apple”, “banana”, “grape” (xiv) If binary search is instead used to search the array from part (xiii) to locate the string “pear”, what are the strings contained in the first 3 array positions visited? If required, you may assume that, for an array with smallest and largest indices left and right respectively, the index approximately at the middle of the array is calculated as the integer part of left+right/2. (a) “melon”, “raspberry”, “pear” (b) “satsuma”, “raspberry”, “pear” (c) “melon”, “pear” (no further positions need to be visited) (d) “apple”, “banana”, “grape” (xv) Which of the following correctly describe an Abstract Data Type (ADT)? (a) a type characterised by its values, operations and data representation (b) a type characterised by its data representation and operations only (c) a type characterised by its values and data representation only (d) a type characterised by its values and operations only (xvi) The QuickSort algorithm for sorting an array involves a sub-algorithm known as Partition which acts on an array a [left…right]. The algorithm is shown below: pivot left r +1,…,right r :2.1.1.Copy r p p r pivotintoa[+1].2.1.2.Increment .3. Terminate yielding ppublic static boolean equals(Setset1,Setset2){if(set1.size()!=set2.size()) return false;Iterator i1=set1.iterator();Iterator i2=set2.iterator();while(i1.hasNext() &&i2.hasNext())if(!i1.next().equals(i2.next())) return false;returntrue; If A is the average time complexity of the algorithm implemented by this method when applied to sets s1 and s2 of equal size n, instantiated as follows: Set s1 = new TreeSet(); Set s2 = new TreeSet(); and B the time complexity of the algorithm implemented by this method when applied to s1 and s2 of equal size n, instantiated as follows: Set s1 = new HashSet(); Set s2 = new HashSet(); Which of the following is true? (a) A = O(log n) and B = O(n) (b) A = O(n) and B=O(n) (c) A = O(log n) and O(n2) (d) A = O((log n)2 ) and B=O(n2 ) (xxii) Suppose that a new node N is inserted into an AVL tree using standard Binary Search Tree insertion prior to balancing and that k1 is the deepest node in the tree to become unbalanced by the insertion. Let k2 be the right child of k1 and k3 the left child of k2, where k2 and k3 are the next nodes on the path from k1 to N. Consider the following actions: A: single right rotation about k1 B: single left rotation about k1 C: single right rotation about k2 D: single left rotation about k2 Which sequence of actions when performed in the given order will balance the tree? (a) C, A (b) B (c) C, B (d) D, A (xxiii) Consider a hypothetical university in which each student-number is a string of 4 decimal digits. The student records are to be stored in a closed-bucket hash-table of size 7, in which the keys are student-numbers. Assume the hash function is: hash(k) = remainder on division by 7 of the last digit of k So for example, hash(0001) = 1 and hash(3457) = 0. Starting with an empty hash- table, the following student-numbers are added to the hash table: 8001, 7008, 0002, and 1443. What is the number of comparisons required when the resulting hash-table is searched for the student-number 4158? You can assume that comparisons only take place within a bucket. (a) 2 (b) 1 (c) 0 (d) 4 (xxiv) Let map1 and map2 be Maps used to store details of library books. In each Map the keys denote the book code, and the values the book title. Suppose that some Java code involves the instantiation of both maps as empty HashMaps with initial size 20 and their population with the data above, followed by the following code fragment:. map1.putAll(map2); System.out.println(map1); What is output when the code is run? (a) {5=The Little Prince, 9=Pollyanna, 10=The Gruffalo, 16=The Borrowers} (b) {2=[Desert Island, Jane Eyre], 5=The Little Prince, 7=[Snow White, The BFG], 9=Pollyanna,10=The Gruffalo, 16=The Borrowers} (c) {2=Jane Eyre, 5=The Little Prince, 7=The BFG, 9=Pollyanna,10=The Gruffalo, 16=The Borrowers} (d) {2=Desert Island, 5=The Little Prince, 7=Snow White, 9=Pollyanna,10=The Gruffalo, 16=The Borrowers} (xxv) If the Java code fragment in question (vi) is replaced by: map1.remove(16,map1.get(16)); System.out.println(map1); what is output when the full code is run? (a) There is an error, as the method get(int) is undefined for the type Map (b) An exception is thrown as map1 has no entry with key 16 (c) {} (the empty map) (d) {2=Desert Island, 7=Snow White, 9=Pollyanna, 10=The Gruffalo}
ECO2101 Microeconomics (Blended) July 2025 Semester CA1 Individual Project 25 July 2025 1 Introduction (One paragraph to explain or discuss why you have selected the product(s) for your report.) (One paragraph to summarise the events and analysis of all the three articles.) 2 Analysis 2.1 Analysis 1 – Climate change impact on wheat production (Topic 1: PPF and Opportunity Cost) Source: Quote the source of the article or if the article is obtained from the web, quote the web address Summary (One to two short paragraphs summarising the key event(s) in the article) Analysis (Two to three short paragraphs on analysing the key event(s) using microeconomic concepts) (Economic diagram(s) to support the analysis) 2.2 Analysis 2 – Changes in demand and supply of wheat (Topic 3: Market Equilibrium) Source: Quote the source of the article or if the article is obtained from the web, quote the web address Summary (One to two short paragraphs summarising the key event(s) in the article) Analysis (Two to three short paragraphs on analysing the key event(s) using microeconomic concepts) (Economic diagram(s) to support the analysis) 2.3 Analysis 3 – Inelastic demand for wheat (Topic 4: Elasticity) OR Analysis 3 – Increased consumption of wheat due to higher utility (Topic 5: Utility and Demand) Source: Quote the source of the article or if the article is obtained from the web, quote the web address Summary (One to two short paragraphs summarising the key event(s) in the article) Analysis (Two to three short paragraphs on analysing the key event(s) using microeconomic concepts) (Economic diagram(s) to support the analysis 3 Conclusion One paragraph on the overall view of the key analysis. (The objective is to present an overall view or coherent view of the key analysis. It is NOT to be written in a ‘listing’ style. where all the key analysis is listed one by one for each topic). References (Use either APA or Harvard Referencing Method) List the sources of all the articles.
COMP9414 Arti cial Intelligence GridWorldEnv Environment User Guide Term 2, 2025 Version: 1.0 Last Updated: July 2025 Purpose: This guide provides comprehensive documentation for the GridWorldEnv class used in Assignment 2 1 Overview The GridWorldEnv class implements a grid world environment for reinforcement learn- ing experiments. This guide covers installation, usage, and troubleshooting for the envi- ronment provided in env .py. 2 Environment Speci cations The environment implements an 11 × 11 grid world with the following characteristics: { Grid Size: 11 × 11 cells { State Space: Discrete 2D coordinates (x;y) where x;y ∈ {0;1;:::;10} { Action Space: 4 discrete actions { Goal Position: (10; 10) - bottom-right corner { Starting Position: Random (avoiding obstacles and goal) { Episode Termination: Only when goal is reached 2.1 Coordinate System The environment uses a standard 2D coordinate system: o Origin (0; 0) is at the top-left corner o X-axis increases downward (rows) o Y-axis increases rightward (columns) 2.2 Obstacles The environment contains 10 xed obstacles arranged in two patterns: L-shaped pattern (top-left area): o Positions: (2; 2), (2; 3), (2; 4), (3; 2), (4; 2) Cross pattern (centre): o Positions: (5; 4), (5; 5), (5; 6), (4; 5), (6; 5) 2.3 Action Space Action Value E ect Up 0 Decrease x by 1 Down 1 Increase x by 1 Left 2 Decrease y by 1 Right 3 Increase y by 1 2.4 Reward Structure Event Reward Reach Goal Hit Obstacle Normal Step +25 -10 -1
Algorithms and Data Structures (M) MOCK EXAM Question 1 Parts (i) – (ii) refer to the algorithm shown in Box 1. The algorithm takes an array a and searches it for a substring that matches a shorter array b. This uses an auxiliary algorithm that compares two subarrays of equal length. a n [0…-1 m :1.For =0,…, -,repeat:1.1. ai…+-1] [0…-1], .2.Terminate with answer .Auxiliary algorithm:Totestwhetherai…+-1] [0…-1]:1.Forj m If[+] ≠ [], .2.Terminate with answer .publicclassListExample{publicstaticvoidpListSet(>l,SetInteger out ");System..print(";");for(Integer j:s)System..print(j+"");}publicstaticvoidmainString ){ListIntegermyListnewArrayListInteger > = >();inttemp=0;for(inti=0;iif(i%2==0) temp=8-2*i;elsetemp =10-2*i;myList.add(i,temp);mySet.add(temp);}printListSet(,);}}1. Setgtoleft,setrtoleft,andsety toleft.2. Whiler ≤right,repea Box 3 Algorithm to reorder elements in an array (i) If the algorithm is applied to the array a below: a = ["green", "yellow", "red", "green", "red"] What is the final state of a? (a) ["green", "yellow", "red", "green", "red"] (b) ["yellow", "green", "green", "red", "red"] (c) ["green", "green", "yellow", "red", "red"] (d) ["red", "red", "yellow", "green", "green"] (ii) What is the time complexity of the algorithm of part (i), given that swapping two elements of the array is a constant time operation? (a) O(n2) (b) O(n) (c) O(log n) (d) O(1) (iii) Consider the following sorted array: If linear search is used to locate the string “pear”, what are the strings contained in the first 3 array positions visited? If required, you may assume that, for an array with smallest and largest indices left and right respectively, the index approximately at the middle of the array is calculated as the integer part of (left+right)/2. (a) “melon”, “raspberry”, “pear” (b) “satsuma”, “raspberry”, “pear” (c) “melon”, “pear” (no further positions need to be visited) (d) “apple”, “banana”, “grape” (iv) If binary search is instead used to search the array from part (xiii), what are the strings contained in the first 3 array positions visited? If required, you may assume that, for an array with smallest and largest indices left and right respectively, the index approximately at the middle of the array is calculated as the integer part of (left+right)/2. (a) “melon”, “raspberry”, “pear” (b) “satsuma”, “raspberry”, “pear” (c) “melon”, “pear” (no further positions need to be visited) (d) “apple”, “banana”, “grape” (v) Java’s generic Iterator interface, Iterator supports which of the following sets of methods? (a) hasNext(),next(),remove() (b) getFirst(),next(),addLast() (c) hasNext(),getFirst(),remove() (d) getFirst(),next(),remove() (vi) This question involves the deletion of a node from a non-empty doubly linked list L with first node first. Any Node N consists of an element (N.elem) and references to the next node in the list (N.next) and the previous node in the list, (N.pred). Assuming that del is the node to be deleted, which pair of steps from the following list, when performed in the given order, will delete the node from the list? (a) A, C (b) B,D (c) A,D (d) C,B (vii) Suppose that two binary search trees BST1 and BST2 store sets S1 and S2 respectively, where S1 and S2 have size n. What are the average and worst time complexities respectively for determining if the sets are equal (i.e., they contain the same elements)? You may assume that the average height of a BST containing n elements is O(log n). (a) O(n log n) and O(n2) (b) O(n log n) and O(n log n) (c) O(n2) and O(n2) (d) O(n2) and O(n log n) (viii) Suppose that a new node N is inserted into an AVL tree using standard Binary Search Tree insertion prior to balancing and that k1 is the deepest node in the tree to become unbalanced by the insertion. Let k2 be the right child ofk1 and k3 the left child ofk2, where k2 and k3 are the next nodes on the path from k1 to N. Consider the following actions: A: single right rotation about k1 B: single left rotation about k1 C: single right rotation about k2 D: single left rotation about k2 Which sequence of actions when performed in the given order will balance the tree? (a) C, A (b) B (c) C, B (d) D, A (ix) Suppose that in part (viii), k3 were the right child ofk2. Which of the actions A-D, when performed in the given order will balance the tree? A: single right rotation about k1 B: single left rotation about k1 C: single right rotation about k2 D: single left rotation about k2 (a) C, A (b) B (c) C, B (d) D, A (x) Which of the following statements is not true? (a) the Queue ADT is a special case of the List ADT (b) the Stack ADT is a special case of the List ADT (c) the Stack ADT is a special case of the Queue ADT (d) A Java ArrayList is one of several implementations ofthe List ADT Question 3 (i) Suppose that we use a closed bucket hash table H of size 32 to store a set of 4567 words. The load factor of H is: (a) 32/4567 (b) 4567 - 32 (c) 32 - 4567 (d) 4567/32 (ii) If a hash table is used to represent a Set of integers, which of the following statements about the hash function is true? (a) The hash function should always leave some buckets empty (b) The hash function should ensure that data is spread evenly and thinly throughout the table (c) The hash function should always ensure that a prime number of buckets are used (d) The hash function should always be applied to the first few digits of the inputs (iii) Consider a hypothetical university in which each student-number is a string of 4 decimal digits. The student records are to be stored in a closed-bucket hash-table of size 7, in which the keys are student-numbers. Assume the hash function is: hash(k) = remainder on division by 7 of the last digit of k So for example, hash(0001) = 1 and hash(3457) = 0. Starting with an empty hash- table, the following student-numbers are added to the hash table: 8001, 7008, 0002, and 1443. What is the number of comparisons required when the resulting hash-table is searched for the student-number 4158? (a) 2 (b) 1 (c) 0 (d) 4 Parts (iv)-(vi) refer to the maps map1 and map2 shown in Box 4. Box 4 Maps map1 and map2 Box 4 shows two maps used to store details of library books. In each map the keys denote the book code, and the values the book title. (iv) Suppose that some Java code involves the instantiation of both maps as empty HashMaps with initial size 20 and their population with the data above, followed by the following code fragment:. map1.putAll(map2); System.out.println(map1); What is output when the code is run? (a) {5=The Little Prince, 9=Pollyanna, 10=The Gruffalo, 16=The Borrowers} (b) {2=[Desert Island, Jane Eyre], 5=The Little Prince, 7=[Snow White, The BFG], 9=Pollyanna,10=The Gruffalo, 16=The Borrowers} (c) {2=Jane Eyre, 5=The Little Prince, 7=The BFG, 9=Pollyanna,10=The Gruffalo, 16=The Borrowers} (d) {2=Desert Island, 5=The Little Prince, 7=Snow White, 9=Pollyanna,10=The Gruffalo, 16=The Borrowers} (v) If the Java code fragment in question (iv) is replaced by: map1.remove(16,map1.get(16)); System.out.println(map1); what is output when the full code is run? (a) There is a syntax error, as the method get(int) is undefined for the type Map (b) An exception is thrown as map1 has no entry with key 16 (c) {} (the empty map) (d) {2=Desert Island, 7=Snow White, 9=Pollyanna, 10=The Gruffalo} (vi) If the code fragment were instead replaced with: for(String title:map1.values()) System.out.print(title+", "); what is output when the full code is run? (a) there is an error - we cannot iterate over map1.values (b) there is an error - there is no Map method values() (c) Desert Island, Snow White, Pollyanna, The Gruffalo, (d) Snow White, Pollyanna, The Gruffalo, Desert Island, (vii) Which of the following would we use to declare a class named A with a single generic type? (a) public class A { ... } (b) public class A { ... } (c) public class A(E) { ... } (d) public class A(E, F) { ... } (viii) Which of the following methods is not in the Collection interface? (a) clear() (b) isEmpty() (c) size() (d) getSize() (ix) If list is a LinkedList that contains 1 million int values and A and B are the following fragments of code: A: for (int i = 0; i < list.size(); i++) sum += list.get(i); B: for (int i: list) sum += i; Which of the following statements is true? (a) Code fragment A runs faster than code fragment B (b) Code fragment B runs faster than code fragment A (c) Code fragment A runs as fast as code fragment B (d) It is impossible to tell which of A or B is faster without knowledge of the size of the input integers (x) What is the output from the following code? import java.util.*; public class Test { public static void main(String[] args) { Set set = new HashSet(); set.add(new A()); set.add(new A()); set.add(new A()); set.add(new A()); System.out.println(set); } } class A { int r = 1; public String toString() { return r + ""; } public int hashCode() { return r; } } (a) [1] (b) [1, 1] (c) [1, 1, 1] (d) [1, 1, 1, 1]
Project 5 AssignmentScore is 30 points (10 poinst each question).Question 1Exploring and Analyzing Data Using R FunctionsObjectiveThis assignment will assess your ability to:• Import and explore a dataset in R• Apply basic R functions for data manipulation and analysis• Generate summary statistics and visualizations• Write clean, well-commented R codeInstructions1. Dataset SelectionUse the built-in dataset mtcars in R for this assignment.2. Tasks(A) Data Explorationo Display the first 6 rows of the dataset using an appropriate R function.o Use str(), summary(), and dim() functions to explore the dataset.o Identify the variable with the highest mean value using R code.(B) Data Manipulationo Create a new variable efficiency as mpg/hp. Add this as a new column.o Filter the dataset to include only cars with mpg > 20.o Sort the dataset in descending order based on efficiency.(C) Data Analysiso Calculate the mean, median, and standard deviation of mpg, hp, and wt.o Use the aggregate() function to compute the average horsepower (hp) grouped by the number of cylinders (cyl).o Create a bar plot to compare the average mpg by cylinder count.(D) Code Presentation (20 marks)o Your R script should include meaningful comments.o Use clear, readable formatting.o Include a brief summary (3–5 sentences) of your findings in a comment block at the top.Question 2R Programming Assignment: User-Defined FunctionsAssignment: Analyzing Student GradesScenario: You've been given a dataset of student scores for three different assignments (Assignment 1, Assignment 2, and Final Exam). You need to create R functions to perform some basic analysis on these scores.Instructions:1. Create a function calculate_average_score:o This function should take a numeric vector of scores as input.o It should return the average (mean) of these scores.o Handle the case where the input vector might contain NA values by removing them before calculation.2. Create a function assign_grade_category:o This function should take a single numeric score (representing an average score) as input.o It should return a character string representing the grade category based on the following criteria:▪ 90-100: "Excellent"▪ 80-89: "Good"▪ 70-79: "Satisfactory"▪ 60-69: "Pass"▪ Below 60: "Fail"o Assume the input score will be between 0 and 100.3. Demonstrate your functions:o Create a sample data frame named student_scores with the following data:Student Assignment1 Assignment2 FinalExamAlice 85 92 88Bob 70 NA 75Carol 95 88 90David 55 60 50o Export to Sheetso Using your calculate_average_score function, add a new column to student_scores called OverallAverage which contains the average of 'Assignment1', 'Assignment2', and 'FinalExam' for each student.o Using your assign_grade_category function, add another new column to student_scores called GradeCategory based on the OverallAverage score.o Print the final student_scores data frame.Question 3R Assignment: Calculating the Area of a CircleObjective: Create a user-defined function in R that calculates the area of a circle given its radius.Instructions:1. Define a function named calculate_circle_area that takes one argument: radius.2. Inside the function, use the formula for the area of a circle: Area=pi*radius2.3. The function should return the calculated area.4. Test your function by calculating the area of a circle with a radius of 5 and another with a radius of 10.5. Print the results clearly.Submission Guidelines• Submit an .R script file named lastname_firstname_assignment.R.• Make sure your code runs without errors.• Use only base R and built-in datasets/functions (no external libraries).
