/* Suggested solutions to exam TDA548 2017-10-26 */ // --------- 1 -------------- (4p) See lecture notes // --------- 2 -------------- (2p) int result = add(div(sub(7, 6), 5), 4); // Type error, will not compile Reason: Result from div (double) can't be implicitly casted to int (add param's are int) NOTE: sub returns int but implicit cast to double (for div param) is ok. // --------- 3 ------------------- (4p) double sqrt(double n) { double xi = n; for (int i = 0; i < 5; i++) { double xiPlus1 = 0.5 * (xi + n / xi); xi = xiPlus1; } return xi; } // --------- 4 ------------------- (12p) // Other solutions possible int[] insert(int arr[], int[] elems, int position) { int[] tmp = new int[arr.length + elems.length]; int k = 0; int n = 0; for (int i = 0; i < tmp.length; i++) { if (position <= i && i < position + elems.length) { if (!contains(arr, elems[n])) { tmp[i] = elems[n]; } n++; } else { tmp[i] = arr[k]; k++; } } return removeZero(tmp); } // Func. decomp boolean contains(int[] arr, int elem) { for (int i : arr) { if (i == elem) { return true; } } return false; } // Func. decomp int[] removeZero(int[] arr) { int count = 0; for (int i : arr) { if (i == 0) { count++; } } int[] tmp = new int[arr.length - count]; int k = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] != 0) { tmp[k] = arr[i]; k++; } } return tmp; } // -------- 5 --------- (6p) int maxNesting(String str) { int open = 0; int close = 0; int max = 0; int tmp = 0; for (char ch : str.toCharArray()) { if (ch == '(') { open++; tmp++; if (tmp > max) { max = tmp; } } else if (ch == ')') { close++; tmp--; if( close > open){ return -1; } } else { // Skip other chars } } if (open != close) { return -1; } else { return max; } } // -------- 6 --------- (6p) // See link to image, on page close tho this link // ------- 7 ----------- public class Cell { //(3) private int row; private int col; private String content; public Cell(int row, int col) { this.row = row; this.col = col; } public void incCol() { col++; } public int getCol() { return col; } } public class Sheet { //(4p) private final Listcells = new ArrayList(); private int maxRow; private int maxCol; public Sheet(int maxRow, int maxCol) { this.maxRow = maxRow; this.maxCol = maxCol; for (int row = 0; row < maxRow; row++) { for (int col = 0; col < maxCol; col++) { cells.add(new Cell(row, col)); } } } public void insertColumn(int colNumber) { // (5p) for (Cell c : cells) { if (c.getCol() >= colNumber) { c.incCol(); } } for (int i = 0; i < maxRow; i++) { cells.add(new Cell(i, colNumber)); } maxCol++; } } // ------- 8 ----------- (8p) // NOTE: There are no cycles in the graph int distance(int n, int m) { List | l1 = getSeq(n); List l2 = getSeq(m); for (Integer i : l1) { if (l2.contains(i)) { return l1.indexOf(i) + l2.indexOf(i); } } return -1; } List getSeq(int n) { List seq = new ArrayList<>(); while (n > 1) { seq.add(n); if (n % 2 == 0) { n = n / 2; } else { n = 3 * n + 1; } } seq.add(1); return seq; } // ------- 9 ----------- (6p) b1.eqals(b2) will return true because Books equals() called. Method used equals by value. Method contains() uses equals() when searching for an object. For this to work the equals method must be overridden. Books equals is NOT overridden because method head differs, param should be Object. So NO overriding, we'll get overloading (i.e. Book has two equals). Because not overridden, Objects equals will be called i.e. equality by reference (==) used. Book b1 and b2 not same object, so false, not found. // This will not override Object's equals wrong parameter type public boolean equals(Book b) { if (b == this) { return true; } if (b == null) { return false; } return b.isbn.equals(isbn); } // This is the way it should be public boolean equals(Object b) { if (b == this) { return true; } if (b == null || b.getClass() != getClass()) { return false; } return ((Book)b).isbn.equals(isbn); } }