Mathematical logic - Basic connectives and truth table, Statements, Logical Connectives,
Tautology, Contradiction. Logical Equivalence - The Laws of Logic, The Principle of duality,
Substitution Rules . The implication - The Contrapositive, The Converse,The Inverse.
Logical Implication - Rules of Inference. The use of Quantifiers - Open Statement, Quantifier.
Logically Equivalent – Contrapositive, Converse , Inverse , Logical equivalences and
implications for quantified statement, Implications , Negation .
The Rule of Sum – Extension of Sum Rule . The Rule of Product - Extension of Product Rule . Permutations. Combinations. The Binomial Theorem (without proof). Combination with
Repetition. The Pigeonhole Principle. The Principle of Inclusion and Exclusion Theorem
(Without Proof) - Generalisation of the Principle. Derangements.
Cartesian Product - Binary Relation. Function – domain , range-one to one function, Image Restriction. Properties of Relations- Reachability Relations, Reflexive Relations, Symmetric
Relations, Transitive relations, Anti-symmetric Relations, Partial Order relations, Equivalence
Relations, Irreflexive relations.
Partially ordered Set – Hasse Diagram, Maximal-Minimal Element, Least upper bound (lub),
Greatest Lower bound(glb) ( Topological sorting Algorithm- excluded). Equivalence Relations
and Partitions - Equivalence Class.
Lattice - Dual Lattice , Sub lattice , Properties of glb and lub , Properties of Lattice , Special
Lattice , Complete Lattice, Bounded Lattice, Completed Lattice , Distributive Lattice.
Generating Function - Definition and Examples , Calculation techniques, Exponential
generating function. First order linear recurrence relations with constant coefficients –
homogeneous, non-homogeneous Solution. Second order linear recurrence relations with
constant coefficients, homogeneous, non-homogeneous Solution.
Algebraic system-properties- Homomorphism and Isomorphism. Semigroup and monoid –
cyclic monoid , sub semi group and sub monoid, Homomorphism and Isomorphism of Semi
group and monoids. Group- Elementary properties, subgroup, symmetric group on three
symbols ,The direct product of two groups, Group Homomorphism, Isomorphism of groups,
Cyclic group . Right cosets - Left cosets . L a g r a n g e ’ s Theorem
System Life Cycle, Algorithms, Performance Analysis, Space Complexity, Time Complexity, Asymptotic Notation, Complexity Calculation of Simple Algorithms
Polynomial representation using Arrays, Sparse matrix, Stacks, Queues-Circular Queues, Priority Queues, Double Ended Queues, Evaluation of Expressions Linear Search and Binary Search
Self Referential Structures, Dynamic Memory Allocation, Singly Linked List-Operations on Linked List. Doubly Linked List, Circular Linked List, Stacks and Queues using Linked List, Polynomial representation using Linked List Memory allocation and deallocation-First-fit, Best-fit and Worst-fit allocation schemes
Trees, Binary Trees-Tree Operations, Binary Tree Representation, Tree Traversals, Binary Search Trees- Binary Search Tree Operations Graphs, Representation of Graphs, Depth First Search and Breadth First Search on Graphs, Applications of Graphs
Sorting Techniques – Selection Sort, Insertion Sort, Quick Sort, Merge Sort and Heap Sort Hashing- Hashing Techniques, Collision Resolution, Overflow handling, Hashing functions – Mid square, Division, Folding, Digit Analysis
Decimal, Binary, Octal and Hexadecimal Number Systems- Number Base Conversions. Addition, Subtraction, Multiplication and Division of binary numbers. Representation of negative numbers- Complements, Subtraction with complements. Addition and subtraction of BCD, Octal and Hexadecimal numbers. Binary codes- Decimal codes, Error detection codes, Reflected code, Character coding schemes – ASCII, EBCDIC.
Postulates of Boolean Algebra. Basic theorems and Properties of Boolean Algebra. Boolean Functions - Canonical and Standard forms. Simplification of Boolean Functions- Using Karnaugh- Map Method (upto five variables), Don’t care conditions, Product of sums Total simplification, Tabulation Method. Digital Logic Gates- Implementation of Boolean functions using basic and universal gates.
Design Procedure & Implementation of combinational logic circuits- Binary adders and subtractors, Binary Parallel adder, Carry look ahead adder, BCD adder, Code converter, Magnitude comparator, Decoder, Demultiplexer, Encoder, Multiplexer, Parity generator/ Checker.
Flip-flops- SR, JK, T and D. Triggering of flip-flops- Master slave flip- flops, Edge- triggered flip- flops. Excitation table and characteristic equation. Registers- register with parallel load. Counter design: Asynchronous counters- Binary and BCD counters, timing sequences and state diagrams. Synchronous counters- Binary Up- down counter, BCD counter.
Shift registers – Serial In Serial Out, Serial In Parallel Out, Bidirectional Shift Register with Parallel load. Ring counter. Johnson counter- timing sequences and state diagrams.
Algorithms for addition and subtraction of binary numbers in signed magnitude and 2’s complement representations. Algorithm for addition and subtraction of BCD numbers. Representation of floating point numbers, Algorithm for addition and subtraction of floating point numbers.
ROM. Programmable Logic Array(PLA)- Implementation of simple circuits using PLA.
Approaches to Software Design - Functional Oriented Design, Object Oriented Design, Case Study of Automated Fire Alarm System.
Object Modelling Using Unified Modeling Language (UML) – Basic Object Oriented concepts, UML diagrams, Use case model, Class diagram, Interaction diagram, Activity diagram, State chart diagram.
Introduction to Java - Java programming Environment and Runtime Environment, Development Platforms -Standard, Enterprise. Java Virtual Machine (JVM), Java compiler, Bytecode, Java applet, Java Buzzwords, Java program structure, Comments, Garbage Collection, Lexical Issues.
Primitive Data types - Integers, Floating Point Types, Characters, Boolean. Literals, Type Conversion and Casting, Variables, Arrays, Strings, Vector class.
Operators - Arithmetic Operators, Bitwise Operators, Relational Operators, Boolean Logical Operators, Assignment Operator, Conditional (Ternary) Operator, Operator Precedence.
Control Statements - Selection Statements, Iteration Statements and Jump Statements.
Object Oriented Programming in Java - Class Fundamentals, Declaring Objects, Object Reference, Introduction to Methods, Constructors, this Keyword, Method Overloading, Using Objects as Parameters, Returning Objects, Recursion, Access Control, Static Members, Final Variables, Inner Classes, Command Line Arguments, Variable Length Arguments.
Inheritance - Super Class, Sub Class, The Keyword super, protected Members, Calling Order of Constructors, Method Overriding, the Object class, Abstract Classes and Methods, using final with Inheritance.
Packages and Interfaces - Defining Package, CLASSPATH, Access Protection, Importing Packages, Interfaces.
Exception Handling - Checked Exceptions, Unchecked Exceptions, try Block and catch Clause, Multiple catch Clauses, Nested try Statements, throw, throws and finally. Input/Output - I/O Basics, Reading Console Input, Writing Console Output, PrintWriter Class, Object Streams and Serialization, Working with Files.
Java Library - String Handling – String Constructors, String Length, Special String Operations - Character Extraction, String Comparison, Searching Strings, Modifying Strings, using valueOf(), Comparison of StringBuffer and String.
Collections framework - Collections overview, Collections Interfaces- Collection Interface, List Interface.
Collections Class – ArrayList class. Accessing a Collection via an Iterator. Event handling - Event Handling Mechanisms, Delegation Event Model, Event Classes, Sources of Events, Event Listener Interfaces, Using the Delegation Model.
Multithreaded Programming - The Java Thread Model, The Main Thread, Creating Thread, Creating Multiple Threads, Synchronisation, Suspending, Resuming and Stopping Threads.
Swings fundamentals - Swing Key Features, Model View Controller (MVC), Swing Controls, Components and Containers, Swing Packages, Event Handling in Swings, Swing Layout Managers, Exploring Swings –JFrame, JLabel, The Swing Buttons, JTextField.
Java DataBase Connectivity (JDBC) - JDBC overview, Creating and Executing Queries – create table, delete, insert, select.
1. Implementation of Polynomials and Sparse matrices using arrays**
2. Implementation of Stack , Queues, Priority Queues, DEQUEUE and Circular Queues using arrays**
3. Application problems using stacks: Conversion of expression from one notation to another notation . **
4. Implementation of various linked list operations. **
5. Implementation of stack, queue and their applications using linked list.pression
6. Implementation of trees using linked list
7. Representation of polynomials using linked list, addition and multiplication of polynomials.
** 8. Implementation of binary trees using linked lists and arrays- creations, insertion, deletion and traversal. **
9. Implementation of binary search trees – creation, insertion, deletion, search
10. Any application programs using trees
11. Implementation of sorting algorithms – bubble, insertion, selection, quick, merge sort and heap sort.**
12. Implementation of searching algorithms – linear search, binary search.**
13. Representation of graphs and computing various parameters (in degree, out degree etc.) - adjacency list, adjacency matrix.
14. Implementation of BFS and DFS for each graph representations.**
15. Implementation of hash table using your own mapping functions and observe collisions and overflow resolving schemes.**
16. Simulation of first-fit, best-fit and worst-fit allocations.
17. Simulation of a basic memory allocator and garbage collector using doubly linked list.
[** mandatory]
The syllabus contains six sessions (A, B, C, D, E, F). Each session consists of three concrete Java exercises, out of which at least two questions are mandatory.
1) Write a Java program that checks whether a given string is a palindrome or not. Ex: MALAYALAM is palindrome.
2) Write a Java Program to find the frequency of a given character in a string. **
3) Write a Java program to multiply two given matrices. **
(B) Object Oriented Programming Concepts: Problem on the use of constructors, inheritance, method overloading & overriding, polymorphism and garbage collection:
4) Write a Java program which creates a class named 'Employee' having the following members: Name, Age, Phone number, Address, Salary. It also has a method named 'printSalary( )' which prints the salary of the Employee. Two classes 'Officer' and 'Manager' inherits the 'Employee' class. The 'Officer' and 'Manager' classes have data members 'specialisation' and 'department' respectively. Now, assign name, age, phone number, address and salary to an officer and a manager by making an object of both of these classes and print the same. (Exercise to understand inheritance). **
5) Write a java program to create an abstract class named Shape that contains an empty method named numberOfSides( ). Provide three classes named Rectangle, Triangle and Hexagon such that each one of the classes extends the class Shape. Each one of the classes contains only the method numberOfSides( ) that shows the number of sides in the given geometrical structures. (Exercise to understand polymorphism). **
6) Write a Java program to demonstrate the use of garbage collector.
7) Write a file handling program in Java with reader/writer.
8) Write a Java program that read from a file and write to file by handling all file related exceptions. **
9) Write a Java program that reads a line of integers, and then displays each integer, and the sum of all the integers (Use String Tokenizer class of java.util). **
10) Write a Java program that shows the usage of try, catch, throws and finally. **
11) Write a Java program that implements a multi-threaded program which has three threads. First thread generates a random integer every 1 second. If the value is even, second thread computes the square of the number and prints. If the value is odd the third thread will print the value of cube of the number.
12) Write a Java program that shows thread synchronisation. **
13) Write a Java program that works as a simple calculator. Arrange Buttons for digits and the + - * % operations properly. Add a text field to display the result. Handle any possible exceptions like divide by zero. Use Java Swing. **
14) Write a Java program that simulates a traffic light. The program lets the user select one of three lights: red, yellow, or green. When a radio button is selected, the light is turned on, and only one light can be on at a time. No light is on when the program starts. **
15) Write a Java program to display all records from a table using Java Database Connectivity (JDBC). (F) Standard Searching and Sorting Algorithms using data structures and algorithms learned from course Data Structures (CST 201):
16) Write a Java program for the following: **
1) Create a doubly linked list of elements.
2) Delete a given element from the above list.
3) Display the contents of the list after deletion.
17) Write a Java program that implements Quick sort algorithm for sorting a list of names in ascending order. **
18) Write a Java program that implements the binary search algorithm.
[** Mandatory]