Examples of Algorithmic Problem Solving Using Functions (Various Number Theoretic Problems, Finding Roots of Algebraic Equations)

Boolean Algebra

• Propositional Logic
• Well Formed Formulae
• Truth Values and Interpretation of Well Formed Formulae
• Truth Tables
• Satisfiable
• Unsatisfiable
• Valid Formulae
• Equivalence Laws and Their Use in Simplifying Well Formed Formulaes
• Binary-valued Quantities
• Basic Postulates of Boolean Algebra Operations AND, OR and NOT
• Basic Theorems of Boolean Algebra (Eg. Duality, Idempotence, Commutativity, Associativity, Distributivity, Operations with 0 and 1, Complements, Absorption, Involution)
• DeMorgan’S Law/Theorem and Their Applications
• Reducing Boolean Expression (SOP and POS) to Its Minimal Form
• Use of Karnaugh Map for Minimization of Boolean Expressions (Up to 4 Variables)

Computer Hardware

• Elementary Logic Gates (NOT, AND, OR, NAND, NOR, XOR, XNOR) and Their Use in Circuits
• Applications of Boolean Algebra and Logic Gates to Half Adders, Full Adders, Encoders, Decoders, Multiplexers, NAND, NOR as Universal Gates

Implementation of Algorithms to Solve Problems

Programming in Java (Review of Class Xi Sections B and C)

Objects

• Objects as Data (Attributes) + Behaviour (Methods Or Functions)
• Object as an Instance of a Class
• Introduction to Constructors
• Analysis of Some Real World Programming Examples in Terms of Objects and Classes

Primitive Values, Wrapper Classes, Types and Casting

• Primitive Values and Types - int, short, long, float, double, boolean, char
• Corresponding Wrapper Classes for Each Primitive Type
• Class as Type of the Object
• Class as Mechanism for User Defined Types
• Changing Types Through User Defined Casting and Automatic Type Coercion for Some Primitive Types

Variables, Expressions

• Variables as Names for Values
• Expressions (Arithmetic and Logical) and Their Evaluation (Operators, Associativity, Precedence)
• Assignment Operation
• Difference Between Left Hand Side and Right Hand Side of Assignment

Statements, Scope

• JAVA - Statements
• Conditional (If, If-then-else, Switchbreak, ?: Ternary Operator)
• Looping (For, While-do, Do-while, Continue, Break)
• Grouping Statements in Blocks
• Scope and Visibility of Variables

Functions

• Functions/Methods (As Abstractions for Complex User Defined Operations on Objects)
• Functions as Mechanisms for Side Effects
• Formal Arguments and Actual Arguments in Functions
• Different Behaviour of Primitive and Object Arguments
• Static Functions and Variables
• The "This" Variable
• Examples of Algorithmic Problem Solving Using Functions (Various Number Theoretic Problems, Finding Roots of Algebraic Equations)

Arrays, Strings

• Structured Data Types - Arrays (Single and Multi-dimensional), Strings
• Example Algorithms that Use Structured Data Types (E.G. Searching, Finding Maximum/Minimum, Sorting Techniques, Solving Systems of Linear Equations, Substring, Concatenation, Length, Access to Char in String, Etc.)
• Basic Concept of a Virtual Machine
• Java Virtual Machine
• Compilation and Execution of Java Programs (The Javac and Java Programs)
• Compile Time and Run Time Errors
• Basic Concept of an Exception
• The Exception Class
• Catch and Throw
• Class as a Contract
• Separating Implementation from Interface
• Encapsulation
• Private and Public Limited Company
• Interfaces in Java
• Implementing Interfaces Through a Class
• Interfaces for User Defined Implementation of Behaviour
• Basic Input/Output Using Scanner and Printer Classes from JDK
• Files and Their Representation Using the File Class
• File Input/Output
• Input/Output Exceptions
• Tokens in an Input Stream
• Concept of Whitespace
• Extracting Tokens from an Input Stream (StringTokenizer Class)

Recursion

• Concept of Recursion
• Simple Recursive Functions (e.g. Factorial, GCD, Binary Search, Conversion of Representations of Numbers Between Different Bases)
• Recursive Sorting Techniques

Inheritance and Polymorphism

• Inheritance
• Base and Derived Classes
• Member Access in Derived Classes
• Redefinition of Variables and Functions in Subclasses
• Abstract Classes
• Class Object
• Protected Visibility
• Subclass Polymorphism and Dynamic Binding

Data Structures

• Basic Data Structures (Stack, Queue, Dequeue)
• Implementation Directly Through Classes
• Definition Through an Interface and Multiple Implementations by Implementing the Interface
• Basic Algorithms and Programs Using the Above Data Structures
• Conversion of Infix to Prefix and Post Fix Notations
• Recursive Data Structures - Single Linked List (Algorithm and Programming), Binary Trees, Tree Traversals (Conceptual)

Complexity and Big O Notation

• Concrete Computational Complexity
• Concept of Input Size
• Estimating Complexity in Terms of Functions
• Importance of Dominant Term
• Best, Average and Worst Case
• Big O Notation for Computational Complexity
• Analysis of Complexity of Example Algorithms Using the Big O Notation (Eg. Various Searching and Sorting Algorithms, Algorithm for Solution of Linear Equations Etc.)