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.
   5   6   7   8   9   10   11   12   13   14   15