Page 10 - Computer science 868 Class 12
P. 10
Motivation for interface: often when creating reusable classes some parts of the exact
implementation can only be provided by the final end user. For example, in a class that sorts records
of different types the exact comparison operation can only be provided by the end user. Since only
he/she knows which field(s) will be used for doing the comparison and whether sorting should be
in ascending or descending order be given by the user of the class.
Emphasize the difference between the Java language construct interface and the word interface
often used to describe the set of method prototypes of a class.
13. Data Structures
(a) Basic data structures (stack, linear queue); implementation directly through classes. Conversion
of Infix to Prefix and Postfix notations.
Basic algorithms and programs using the above data structures.
Data structures should be defined as abstract data types with a well-defined interface (it is
instructive to define them using the Java interface construct).
(b) Single linked list (Algorithm and programming), binary trees, tree traversals (Conceptual).
The following should be covered for each data structure:
Linked List (single): insertion, deletion, reversal, extracting an element or a sublist, checking
emptiness.
Binary trees: apart from the definition the following concepts should be covered: root, internal
nodes, external nodes (leaves), height (tree, node), depth (tree, node), level, size, degree, siblings,
sub tree, completeness, balancing, traversals (pre, post and in-order).
14. Complexity and Big O notation
Concrete computational complexity; concept of input size; estimating complexity in terms of methods;
importance of dominant term; constants, best, average and worst case.
Big O notation for computational complexity; analysis of complexity of example algorithms using the
big O notation (e.g. Various searching and sorting algorithms, algorithm for solution of linear equations
etc.).
PAPER II: PRACTICAL – 30 MARKS
This paper of three hours’ duration will be evaluated by the Visiting Examiner appointed locally and approved
by the Council.
The paper shall consist of three programming problems from which a candidate has to attempt any one.
The practical consists of the two parts:
1. Planning Session
2. Examination Session
The total time to be spent on the Planning session and the Examination session is three hours. A maximum
of 90 minutes is permitted for the Planning session and 90 minutes for the Examination session.

