#### BCA Part 2 ( Second Year )
#### C) COMPUTATIONAL METHODLOGY ------ BCA Second year
####
__SUBJECT – III
__
__PAPTER – 1 THEORY OF COMPUTER
__
__ __
UNIT – 1 : Finite Automata & Regular Expression Preliminaries :
(String, Alphabets and languages, Graphs & Trees, Inductive Proofs, Set
notation, Relations), Finite state system, Non-deterministic finite automata
with E-moves, Regular expressions, Two way finite automata with output,
application on Finite automata.
UNIT – 2 :Regular sets & Context Free Grammar
Properties of Regular Sets : The pumping lemma for regular sets,
closure properties of regular sets, decision Algorithm for sets.
Context Free Grammar : Motivation and Introduction, Context Free
Grammar, Derivation Trees, Simplification of Context Free Grammars, Chomsky
Normal Form, Greibach Normal form, Inherently ambiguous context free languages
and its existence.
UNIT – 3 Automata & Context Free Language
Push Down Automata : informal Description, definitions, pushdown Automata
and Context Free Language.
UNIT – 4 TURNING MACHINE
Introduction, The turning Machine Model, Computable languages and
functions, Techniques for Turning Machine construction, Modification of turning
Machines as enumerators, Restricted Turning Machine as enumerators, Restricted
Turning equivalent to basic model.
UNIT – 5 The Chomsky Hierarchy
The Chomsky Hierarchy ; Normal Forms for DPDA’s Closure of DCFL’s under
complementation, Predication Machines, Additional Closure Properties of DCD’s,
LR(0) grammars’ and DPDA’s.
Closure properties of families of languages : Trios and full trios,
Generalized Sequential Machine Mapping.
Other Closure properties of Trios, Abstract families of Languages
Independent of AFL’s operations.
__PAPER – 2 DATA STRUCTURE
__
Unit – 1 : introduction of Data structures
About Data structure – Information and meaning, binary and decimal
integer, concept of data types, data structure data representation /
implementation, Abstract Data Type, Sequences of Value definition, ADT for
varying length Data string.
Arrays, Records & Pointers – About arrays, records, & Pointers;
their implementation in memory Arrays as an ADT, Using One dimensional Array
& two dimensional, about records & pointers.
Linked List – Concept of singly Linked list, Operations on linked list,
inserting and removing nodes from a list, array implementation of lists,
limitation of the Array implementation over Linked List concept of Doubly
Linked list, generalized List.
Unit – 2 Stack & Queues
Stacks – definition and example, primitive operations, stack as an ADT
Implementation of stacks as any Array and Linked List, operations on stacks,
stacks stored as a Lined List, Arithmetic expressions – Infix, Postfix and
Prefix, Evaluating postfix expression, converting an expression from infix to
postfix.
Queues – Definition and example of queues, Queues as an Abstract Data
Type, Queues Stored as a Linked List,
Circular Queue, Implementation of queues as an Array and Linked list,
operations on Queues, Priority Queue & Desuetude.
UNIT – 3 Recursion
Recursive definition and process, Factorial function, Multiplication of
natural Numbers, Fabonacci sequence, Properties of recursive definition writing
recursive programs (The tower of Hanoi problem converting prefix to postfix
using recursion), Simulation recursion(Return from a function, implementing
recursive function, simulation of factorial).
UNIT – 4 Trees & Graphs
Trees – Definition of trees, Basic Terminology of trees, Binary Tree,
Binary tree traversal, Threaded Binary tree, Height Balance Tree, B-trees,
General Trees.
Graphs : Basic terminology of Graphs, Implementation of Graphs as an
arrays & linked list, Operations of Graphs, Graphs Travels.
UNIT - 5 : Sorting and Searching
Sorting – Definition of sorting, Classification of sorting,
Classification of sorting Techniques, different sorting techniques Bubble sort,
Quick Sort, Efficiency of quick sort, insertion sort, Selection sort, Merge
sort, Efficiency of quick sort, insertion sort, Selection sort, merge sort,
Heap sort.
Searching – Basic search techniques (Dictionary as an ADT, sequential
searching, efficiency of sequential searching). Searching an ordered Table
Binary search.
__PAPER – 3 NUMERICAL METHODS & ERROR ANALYSIS
__
Unit – 1 Approximation & Error in Computing
Significant digits, Data Error, Conversion Error, Round off Error,
Chopping, Symmetric Round off, truncation Error, Modeling Error, Absolute and
Relative Error, Error propagation, Conditioning & stability, Convergence of
Iterative process, Error Estimation, Minimizing the total Error.
UNIT – 2 Roots of Non – Linear Equations
Algebraic equation, Polynomial equation, transcendental equation,
Iterative method, starting & Stopping Iterative method, Iterative method,
Bisection Method, False position method, Newton Raphson Method, Secant method,
Determining all possible roots, Multiple roots of polynomial, Complex Roots
using muller’s Method.
UNIT – 3 Solution to Linear Equations
Existence of Solution Gauss Elimination method, Gauss elimination with
pivoting, Gauss Jordan Method, Round off errors and refinement, III conditioned
system Matrix inversion method
UNIT – 4 Curve Fitting
Linear interpolation Lagrange Interpolation, Spline Interpolation,
Interpolation with equidistant points, Least Square regression, Fitting
Transcendental equations, Multiple linear reression, Ill conditioning in Least
square Method.
UNIT – 5 : Integration & Differentiation
Trapezoidal Rule, Simpson 1/3 Rules, Simpson 3/8 Rules, Gaussian
Integration, Solution to differential equation (using Runge-Kutta second and
fourth order methods, Multistep method
for differential equations. (milne – simpson method, adams –bashforth
moulton method.)
BCA Part 2 Syllabus
BCA Part 2 Group A Computer Science ( COMPUTER SOFTWARE )
BCA Part 2 Group B Electronics ( Computer Hardware )
BCA Part 2 Group COMPUTATIONAL METHODOLOGY
BCA
Bachelor Of Computer Application, BCCA,
Bachelor of Commerce & Computer Application BE
IT/CS, Information technology/Computer Science MCA,
Master of Computer Application MCM,
Master of Computer Management Diploma
, Polytechnic Others,
## Basic Programming C / C++ ,
## TestingSoftware
Testing,
## Hardware & Networking CCNA, MCSE, Hardware,
Networking |