Programming - Exam Deck Flashcards
Random Number Code
Recursion code example
Thread and Concurrency: What is concurrency
- Property of running programs to execute computations “in parallel”, access to the same memory space and resources. Concurrent tasks realised as threads execute in a “pseudo” parallel fasion, with OS schduler giving them distinct “CPU time-slices”.
Binary Tree Code
Abstract Class and Interface
- An abstract class is a class whose objects cannot be instantiated but it only provides methods that should be redefined by subclasses.
- Some of its methods may be abstract, which means that they only provide a “method interface” and no implementation.
- Interface: When all the methods of an abstract class are abstract, the class could also be implemented as / becomes an interface.
Explain why making instance variables public is not a good practice in object-oriented software engineering. Which is the alternative approach to making such variables public and what does it achieve? [8 marks]
Making instance variables public “reveals” effectively the way the actual class is implemented and allows the user of the class to mistakenly change these variables wrongly and introduce inconsistent state. The correct way to use classes is through their method interface which exhibiting specific “agreed” behaviour while the implementation of this behaviour should be opaque to the user. As such instead, of making instance variables public, we keep then private and introduce methods in the class interface which can manipulate them in a controlled “correct and consistent” manner.
Write the constructor and toString methods of class Point which extends the abstract class Shape, then of class Circle which extends class Point and then of class Cylinder which extends class Circle. You should demonstrate and explain how you achieve reusability by re-using the methods of the respective superclass. [12 marks]
Explain the concepts of inheritance and composition and discuss the benefits they bring to object-oriented software engineering. [7 marks]
- Inheritance
- Through inheritance we can create a new class that extends an existing one and reuses its instance variables and methods.
- The subclass can redefine some of the methods of the superclass and provide its own implementation. With inheritance we achieve both software reusability and extensibility.
- Key words: extends, reusability and extensibility
- Composition
- Through composition, we can have objects that contain other objects through instance variables that are defined as belonging to different classes.
- Composition achieves software reusability. Both inheritance and composition promote increased software abstraction.
Write a merge method of an OrderedList class which takes as argument an external ordered list and merges it with the ordered list instance variable, keeping it ordered. OrderedList inherits from List, which includes methods such as removeFromFront and removeFromBack, and adds an insert method which inserts an Object argument in the right position to the list. [10 marks]
What is a queue data structure? Show how a Queue class can be easily implemented through inheritance from a List class. [8 marks]
- A queue is a data structure in which new elements can only be inserted from the back and removed from the front i.e. like a queue in real life.
- enqueue → insertAtBack(data);
- dequeue → removeFromFront();
*
What is concurrent program execution and how can it be supported in Java? Present briefly two example applications for which concurrent execution is necessary. [7 marks]
- Concurrency is the property of running programs to execute instructions in parallel, overlapped in time.
- Concurrency in Java can be supported by different execution threads using, for example, the Thread class.
- These threads can be started and run in parallel within a program, with the operating system scheduler giving them CPU timeslices.
- Applications
- An application where multithreading is needed is a word processor which needs to save periodically the file to the disk while allowing the human user to continue work processing.
- Another application is downloading Internet video, where playback may start before the downloading finishes.
- Key words:
- instructions in parallel, execution threads, CPU timeslices, multithreading
Write a binarySearch method that searches through an integer array for a given search key. [12 marks]
What is the computational complexity of the binary search algorithm? Explain how you arrived at your answer. [6 marks]
- The maximum number of comparisons a binary search algorithm will do given the data set splitting approach that was presented above is the first power of 2 greater than the data set size n, which can be represented as log2n.
- Given that all logarithms grow in roughly the same rate, the base 2 can be omitted resulting in complexity of O(logn) or logarithmic run time.
