CLASS XII

There will be two papers in the subject: half and full adders. majority circuit etc.,
Paper I: Theory........... 3 hours .... 70 marks SOP and POS representation; Maxterms &
Minterms, Canonical and Cardinal
Paper II: Practical ....... . 3 hours ... .30 marks
representation, reduction using · Karnaugh
PAPER I -THEORY - 70 MARKS maps and Boolean algebra.
SECTION A
2. Computer Hardware
1. Boolean Algebra
(a) Elementary logic gates (NOT, AND, OR,
~opositional logic, well formed formulae, NAND, NOR, XOR, XNOR) and their use in
truth values and interpretation of well formed circuits.
formulae (wft), truth tables, satisfiable,
unsatisfiable and valid formulae. Equivalence (b) Applications of Boolean algebra and logic
laws and their use in simplifying wffs. gates to half adders, fulJ adders, encoders,
decoders, multiplexers, NANO, NOR as
Propositional variables; the common logical universal gates.
connectives · (~ (not)(negation), A
(and)(conjunction), V (or)(disjunction), ~ Show the co"espondence between Boolean
(implication). ¢:? {hiconditional); definition methods and the co"esponding switching
of a well-formed formula (wjj); · circuits or gates. Show that NAND and NOR
'representation of simple word problems as gates are universal by converting some circuits
wjf (this can be used for motivation); the to purely NAND or NOR gates.
values true and false; inte1pretation of a wff;
truth tables; satisfiable, unsatisfiable and SECTIONB
validformuiae.
· The programming element in the syllabus (Sections B
_/quivalence laws: commu_(ativiff of A. V,· and C) is 3:imed at algorithmic·problem solving and
(lSsociqtivity r>f II. v,· distrilfutivity; De not merely .r ote learning of Jaya syntax. The Java
Morgan •s laws; law of implication (p ~ q = version used should be 5.0 or later. .For prognunming,
~p V q); law of biconditional ((p ¢=> q) = the [Link] use any text editor and the javac and
(p ~ q) A (q ~ p)); identity (p = p); law of java programs or any other development
negation (~ (~p) = p); law of excluded environment: for example, BlueJ, Eclipse, NetBeans
middle (p ~p = true); law of contradiction etc. BlueJ is strongly recommended for ·its simplicity,
(pA-p = false); tautology and ·contingency ease of use and because it is very well suited for an
simplification rules for A. V. Converse, 'objects first' approach.
inverse and contra positive. Chain rule, 3. Implementation of algorithms to solve
Modus po_nens. problems
(b) Binary valued quantities; basic postulates The students are required to do lab assignments
./ of Boolean algebra; operations AND, OR and in the computer lab concurrently with the
NOT; truth tables. lectures. Programming assignments shouJd be
done such that each major topic is covered in at
( c) Basic theorems of Boolean algebra least one assignment. Assignment problems
/ (e.g. duality, idempotence, coID:Mutati~ity, should be designed so that they are sufficiently
associativity, distributivity, operations with 0 challenging. Students must do algorithm design,
and 1, complements, absorption, inv?lu~on); address correctness issues, implement and
De Morgan's theorem and its appbcations; execute the algorithm in Java and debug where
reducing Boolean expressions to sum of necessary.
products and product of sums forms;
Self explanatory.
Kamaugh maps (up to four variables).
Verify the laws of Boolean algebra using
truth tables. Inputs, outputs for circuits like
268
4. Programming in Java (Review of Class XI methods (number problems, finding roots of
Sections B and C) algebraic equations etc.).
Note that items 4 to 13 should be introduced _10. Arrays, Strings
almost simultaneously along with classes and Structured data types - arrays (single and multi-
their definitions. dimensional), address calculations, strings.
. While reviewing, ensure that new higher order Example algorithms that use structured data types
problems are solved using these constructs. (e.g. searching, finding maximum/minimum,
sorting techniques, solving systems of linear
5. Objects equations, substring, concatenation, length,
(a) Objects as data (attributes) + behaviour access to char in string, etc.).
(methods); object as an instance of a class. Storing many data elements of the same type
Constructors. requires structured data types - like arrays.
(b) Analysis of some real-world programming Access in arrays is constant time and does not
examples in terms of objects and classes. depend on the number of elements. Address
calculation (row major and column major),
(c) Basic input/output using Scanner and Printer Sorting techniques (bubble, selection, insertion).
classes from JDK; input/output exceptions. Structured data types can be defined by classes -
Tokens in an input stream, concept of . String. Introduce the Java library String class
whitespace, extracting tokens from an input and the basic operations on strings (accessing
stream (String Tokenizer class). individual characters, various substring
6. Primitive values, Wrapper classes, Types and operations, concatenation, replacement, index of
casting operations). The class StringBuffer should be
·introduced for those applications that involve
· ·· · int, short, long, heavy manipulation ofstrings.
nding . .

r-user..:· ~~~.. C _ii!•• ,,-·_ -,._ .. , ..-,,,_.,_.,11-,....,J-~

,.:,.;__,_:,-_,,..,.,. ~ ~
-
. ConcepCor recursion; ~unple ~ ·' 1
defined typ~s. Changing types through user (e.g. factorial, GCD, binary search, conversion of
- defined casting and automatic type coercion for representations of numbers between different
some primitive types. bases).
7. Variables, Expressions Many problems can be solved very elegantly by
Variables as names for values; named constants observing that the solution can be composed of
(final), expressions· (arithmetic and logical) and solutions to 'smaller' versions of the same
their evaluation (operators, associativity, problem with the base version having a known
precedence). Assignment operation; difference simple solution. Recursion can be initially
between left hand side and right hand side of motivated by using recursive equations to define
assignment. · certain methods. These definitions are fairly
·obvious and are easy to understand The
8. Statements, Scope definitions can be directly converted to a
Statements; conditional (if, if else, if else if, program. Emphasize that any recursion must
switch case, ternary operator), looping (for, have a base case. Otherwise. the computation
while, do while, continue, break); · grouping can go Into an Infinite lf!OP• ·
statements in blocks, scope and visibility of The tower of Hanoi is a very good a11mplt1 of
• variables. . how recursion giv• a v«,y slmplt1 and t1legan1
9. Methoda solution whsn as non-~/vt1 sol"tlons are
quite comp/a.
Methods {as abauaQtiona for complex. user
de!mcd operationa on objects), formal arguments
and actual . .-pmonts in methods; different
behaviour of lfflmltive and object atpments.
Static method an.4 vlri•1>1ea. Tho tlili Operator.
Exam~lea of algorithmic p,blean aolwig ualng
 SEC TIO NC (b) Single linked list (Algorithm and
prog ramm ing), bina ry trees, tree traversals
Inheritance, Interface, Polymorphism, Data
(Conceptual).
structures, Computational complexity
The following should be covered for each
12. Inheritance, Interfaces and Polymorphism
data structure:
(a) Inheritance; supe r and deriv ed classes;
Linked List (single): insertion, del(!tion,
mem ber access in ~eriv ed classes; reversal, extracting an element or a sublist.
redefinition of variables and methods in
checking emptiness.
subclasses; abstract classes; class Object;
Binary trees: apart from the definition the
prote cted visibility. Subclass poly morp hism
following concepts should be covered: root,
and dynamic binding.
internal nodes, external nodes (leaves),
Emphasize inheritance as a mechanism to
height (tree, node), depth (tree~ node), level,
reuse a class by extending it. Inheritance
size, degree, siblings, sub tree,
should not normally be used just to reuse
completeness, balancing, traversals (pre,
some methods defined in a class but only
post and in-order).
when th~re is a genuine specialization (or
subclass) relationship between objects of the 14. Complexity and Big O notation
super class and that of the derived class.
Concrete computational complexity; concept of
(b) Inter faces in Java; impl emen ting interfaces
input size; estimating complexity in terms of
throu gh a class; interfaces for user defined
methods; importance of dominant term;
impl emen tatio n of behaviour. constants, best, average and wors t case.
Motivation for interface: often Big O notation for computational complexity;
reusable classes some parts when of the exact
creating analysis of complexity of example algorithms
implementation can only be provided by th e using the big O notation (e.g. Various searching
fina l end user. For example, in a class that and sorting algorithms, algorithm for solution of
so:·ts reco rds of__!fifk_re•n~!_ linear equations etc.).
t ..Jt:[Link]~s~.~t:!.!h£e~ ex'.!:.!a:!k!'
.ct__ ~:c- -==- -"""= ,,,__ ~-::. -.;-,.- ~,. ,.,
comparis,m opef a:tion ca~-only [Link]· ,. I -~-- -=- ~.. .:.:.
6y ·the eni;l useA , [Link] o~l~ he/she knows . ·PAP ER 11: PRACTICAL -30 M<\RI(S
which field(s) will be used for doing the ·This p~~ r of three ~ours' d~at i~n ~Wbe evaluated
comparison and whether. sorting should be in · , .,
by the Visiting Exaiµiner appoqtt!'d local ly ~ -and
ascending or descending order be [Link] by approved by·CISCE.
the user of the class. -
The pape r shall consist of three programming
Emphasize the difference between the Java
language construct interface and the word prob lems from which a candidate has to attempt any
inte,face often used to describe the set of one. The practical consists of the two parts: ,
method prototypes of a class . I. Planning Session
13. Data structures 2. Examination Session
(a) Basi c data structures (stack, qu~ue, c~rcular The total time to be spent on the Planning session and
queue dequeue); implementation drrectly the Examination session is three hours.
' ·· A maximum of 90 minutes is pennitted ~or
through classes; definition · tbrg
0
~
h an
Planning session and 90 minutes for the Exanunat1on
~e
interface and multiple implementati~ns by
implementing the interface. ~onverSion of session.
Infix to Prefix and Postfix notations. Candidates are to be permitted to proceed to the
Basic algorithms and programs using the Examination Session only after the 90 minutes of
above data structures. the Planning Session are over.
Data structures should be defined as abstr_a~t Planning Session
data types with a we/I-defined interface (it 18 The candidates will be required to prepare an
instructive to define them using the Java algorithm and a hand written Java program to solve
inte,face construct). the problem.
Examination Session
EQUIPMENT
The program handed in at the end of the Planning
session shall be returned to the candidates. The There should be enough computers to provide for a
candidates will be required to key-in and execute the teaching schedule where at least three-fourths of the
Java program on seen and unseen inputs individually time available is used for programming.
on the Computer and show execution to the Visiting Schools should have equipment/platforms such that
Examiner. A printout of the program listing including all the software required for practical work runs
output results should be attached to the answer script properly, i.e. it should run at acceptable speeds.
containing the algorithm and handwritte n program.
This should be returned to the examiner. The Since hardware and software evolve and change very
program should be sufficiently documente d so that rapidly, the schools may have to upgrade them as
the algorithm, representation and development required.
process is clear from reading the program. Large Following are the recommended specifications as of
differences between the planned program and the now:
printout will result in loss of marks.
The Facilities:
Teachers should maintain a record of all the
assignments done as part of the practical work • A lecture cum demonstration room with a
through the year and give it due credit at the time of MULTIMEDIA PROJECTOR/ an LCD and
cumulative evaluation at the end of the year. Students O.H.P. attached to the computer.
are expected to do a minimum .of twenty-five
assignments for the year. • A white board with white board markers should
be available.
EVALUA TION: • A fully equipped Computer Laboratory that
Marks (out of a total of 30) should be distributed as allows one f Omputer per student.
given below: ·' .
__ •· Int~met co~ection for [Link] the World
r

C9 n~ ~\uati on_ _ .
~ -",V ~ ~fa~ '..__,.,~
Candidates will be required · to submit a work file
containing the practical work related to programming • The computers should have a minimum of
assignments done during the year. 1 GB RAM and a P IV or higher processor. The
done 10 marks basic requirement is that it should run the
Programming assignments
(Internal operating system and Java programming system
throughout the year
(Java compiler, Java runtime environment, Java
Evaluation
assignments done 5 marks development environment) at acceptable speeds.
Programming
throu hout the ear Visitin Examiner • Good Quality printers.
Terminal Evaluation Software:
Solution to programming problem on 15 Marks
• Any suitable Operating System can be used.
the computer
• JDK 6 or later.
Marks should be given for choice of algorithm and
implementation strategy, documentation, correct • Documentation for the JDK version being used.
output on known inputs mentioned in the question • A suitable text editor. A development
paper, correct output for unknown inputs available environment with a debugger is preferred
only to the examiner. (e.g. BlueJ, Eclipse, NetBeans). BlueJ is
NOTE: recommended for its ease of use and simplicity.
Algorithm should be expressed clearly using any
standard scheme such as a pseudo code.