THEORY OF COMPUTATION ? ? ? ? ??L T P M C ??3 1 0 100 4
UNIT I 9
Church-Turing thesis: Turing machines ? Variants of Turing Machines ? Hilbert?s
problems. Decidability: Decidable languages ? Halting problem.
UNIT II 9
Reducibility: Undecidable problems from Language theory ? A simple Undecidable
problem ? Mapping Reducibility. Advanced topics in Computability Theory: The
Recursion Theorem ? Decidability of logical theories ? Turing Reducibility.
UNIT III 9
Time Complexity: Measuring Complexity ? The Class P ? The class NP ? NPcompleteness
? Additional NP-complete Problems.
UNIT IV 9
Space Complexity: Savitch?s Theorem ? The Class PSPACE ? PSPACE-completeness
? The classes L and NL ? NL-completeness ? NL equals coNL. Intractability: Hierarchy
Theorems ? Relativization ? Circuit Complexity.
UNIT V 9
Advanced topics in complexity theory: Approximation Algorithms ? Probabilistic
Algorithms ? Alternation ? Interactive Proof Systems ? Parallel Computation ?
Cryptography
TUTORIAL 15 ??TOTAL : 60
TEXT BOOKS:
1. Michael Sipser, Introduction to the Theory of Computation, Thomson Brook/cole,
1997.(2006)
2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata
Theory, Languages and Computation, 3/E, Pearson Education, 2009.
REFERENCES
1. Peter Linz, An Introduction to formal Languages and Automata, 4/ E, Jones &
Bartlett Pub, 2006.
2 Kamala Krithivasan, Rama R, Introduction to Formal Languages, Automata
Theory and Computation, Pearson, 2009
3. Dr. B. N. Srinivasa Murthy, Formal Languages and Automata Theory, Sanguine
Publishers, 2006.
OPEN SOURCE SOFTWARE ? ? ? ??L T P M C ?3 0 0 100 3
UNIT I INTRODUCTION 9
Introduction to Open sources ? Need of Open Sources ? Advantages of Open Sources?
Application of Open Sources. Open source operating systems: LINUX: Introduction ?
General Overview ? Kernel Mode and user mode ? Process ? Advanced Concepts ?
Scheduling ? Personalities ? Cloning ? Signals ? Development with Linux. .
UNIT II OPEN SOURCE DATABASE 9
MySQL: Introduction ? Setting up account ? Starting, terminating and writing your
ownSQL programs ? Record selection Technology ? Working with strings ? Date and
Time? Sorting Query Results ? Generating Summary ? Working with metadata ?
Usingsequences ? MySQL and Web.
UNIT III OPEN SOURCE PROGRAMMING LANGUAGES 9
PHP: Introduction ? Programming in web environment ? variables ? constants ?
data;types ? operators ? Statements ? Functions ? Arrays ? OOP ? String Manipulation
and regular expression ? File handling and data storage ? PHP and SQL database ?
PHP and LDAP ? PHP Connectivity ? Sending and receiving E-mails ? Debugging and
error handling ? Security ? Templates.
UNIT IV PYTHON 9
Syntax and Style ? Python Objects ? Numbers ? Sequences ? Strings ? Lists and
Tuples ? Dictionaries ? Conditionals and Loops ? Files ? Input and Output ? Errors and
Exceptions ? Functions ? Modules ? Classes and OOP ? Execution Environment.
UNIT V PERL 9
Perl backgrounder ? Perl overview ? Perl parsing rules ? Variables and Data ?
Statements and Control structures ? Subroutines, Packages, and Modules- Working
with Files ?Data Manipulation.
Total: 45
Text Books:
1. Remy Card, Eric Dumas and Frank Mevel, ?The Linux Kernel Book?, Wiley
Publications, 2003
2. Steve Suchring, ?MySQL Bible?, John Wiley, 2002
References:
1. Rasmus Lerdorf and Levin Tatroe, ?Programming PHP?, O?Reilly, 2002
2. Wesley J. Chun, ?Core Phython Programming?, Prentice Hall, 2001
3. Martin C. Brown, ?Perl: The Complete Reference?, 2nd Edition, Tata McGraw-Hill
Publishing Company Limited, Indian Reprint 2009.
4. Steven Holzner, ?PHP: The Complete Reference?, 2nd Edition, Tata McGraw-Hill
Publishing Company Limited, Indian Reprint 2009.
5. Vikram Vaswani, ?MYSQL: The Complete Reference?, 2nd Edition, Tata McGraw-
Hill Publishing Company Limited, Indian Reprint 2009.
OBJECT ORIENTED SYSTEM DESIGN
L T P M C
3 0 0 100 3
Unit I 9
Introduction
Introduction to Object Orientation - Development - Themes-Evidence for Usefulness of
OO Development-OO Modeling
Modeling Concepts
Modeling-Abstraction-The Three Models-Class Modeling-Object and Class Concepts-
Link and Association Concepts-Generalization and Inheritance-A Sample Class Model-
Navigation of Class Models-Practical Tips
Unit II 9
Advanced Class Modeling
Advanced Object and Class Concepts-Association Ends-N-ary Assocations-
Aggregation-Abstract Classes-Multiple Inheritance-metadata-Reification-Constraints-
Derived Data-Packages- Practical Tips
State Modeling
Events-states-Transitions and Conditions-State diagrams-state diagrams behaviorpractical
tips-Advanced state Modeling-Nested State Diagrams-Nested States-Signal
Generalization-concurrency- A sample state Model- Relation of class and state models
Interaction Modeling
Use case Models-Sequence Models- Activity Models- Use Case Relationships-
Procedural Sequence Models- special constructs for Activity Models-Class Model-State
Model-Interaction Model
Unit III 9
Analysis
Process Overview-Development stages-Development Lifecycle-System conceptiondevising
a system concept-Elaborating a concept-preparing a problem statement-
Domain analysis-overview of analysis-Domain class model-Domain state model-Domain
Interaction Model-Iterating the analysis-Application Interaction Model-Application Class
Model-Application state Model-Adding operations
Unit IV 9
Design
Overview of system Design-Estimating performance- Making a reuse plan-Breaking a
system into sub systems-identifying concurrency-Allocation of subsystems-
Management of Data Storage-Handling Global Resources-Choosing a software control
strategy-handling boundary conditions-setting Trade-off Priorities-common architectural
styles-Architecture of the ATM System
Class Design
Overview of class Design-Bridging the gap-Realizing use cases-Designing Alogrithms-
Recursing Downward-Refactoring-Design optimization-Reification of behavioradjustment
of inheritance-organizing a class design-ATM Example
Unit V 9
\Implementation
Implementation Modeling-overview of implementation-Fine-tuning classes-fine tuning
generalizations-realizing associations-oo languages-introduction abbreviated ATM
Model-implementing structure-implementing functionality-practical tips
Database
Introduction-Abbreviated ATM Model-Implementing structure-Implementing structure -
Implementing structure for the ATM Example-Implementing Functionality-Object
oriented Databases
Programming style
Object-oriented style-reusability-extensibility ? robustness - programming in large
Total : 45
TEXT BOOKS
1. Object-Oriented Modeling and Design with UML, Michael Blaha, James
Rumbaugh, Second Edition, Pearson Education,2004.
2. Object-Oriented Software Engineering using UML, Pattens, and Java second
Edition Bernd Bruegge, Robert S
3. Object-Oriented Software Engineering using UML, Pattens, and Java second
Edition Bernd Bruegge, Allen H.Dutoit(200x?)
References
1. Object Oriented System Development, Ali Bahrami, McGraw-Hill International
Edition,1999
2. Object Oriented analysis and Design, Booch G, Addison-Wesley Publishing
company,1994
NUMERICAL METHODS
L T P M C
3 1 0 100 4
UNIT I SOLUTION OF EQUATIONS AND EIGENVALUE PROBLEMS 9+3
Linear interpolation methods (method of false position) ? Newton?s method ? Statement
of Fixed Point Theorem ? Fixed point iteration: x=g(x) method ? Solution of linear
system by Gaussian elimination and Gauss-Jordon methods- Iterative methods: Gauss
Jacobi and Gauss-Seidel methods- Inverse of a matrix by Gauss Jordon method ?
Eigenvalue of a matrix by power method.
UNIT II INTERPOLATION AND APPROXIMATION 9+ 3
Lagrangian Polynomials ? Divided differences ? Interpolating with a cubic spline ?
Newton?s forward and backward difference formulas.
UNIT III NUMERICAL DIFFERENTIATION AND INTEGRATION 9+ 3
Derivatives from difference tables ? Divided differences and finite differences ?
Numerical integration by trapezoidal and Simpson?s 1/3 and 3/8 rules ? Romberg?s
method ? Two and Three point Gaussian quadrature formulas ? Double integrals using
trapezoidal and Simpson?s rules.
UNIT IV INITIAL VALUE PROBLEMS FOR ORDINARY DIFFERENTIAL
EQUATIONS 9+ 3
Single step methods: Taylor series method ? Euler and modified Euler methods ?
Fourth order Runge ? Kutta method for solving first and second order equations ?
Multistep methods: Milne?s and Adam?s predictor and corrector methods.
UNIT V BOUNDARY VALUE PROBLEMS IN ORDINARY AND PARTIAL
DIFFERENTIAL EQUATIONS 9+ 3
Finite difference solution of second order ordinary differential equation ? Finite
difference solution of one dimensional heat equation by explicit and implicit methods ?
One dimensional wave equation.
TUTORIAL 15
TOTAL : 60
TEXT BOOKS
1. Gerald, C.F, and Wheatley, P.O, ?Applied Numerical Analysis?, Sixth Edition,
Pearson Education Asia, New Delhi, 2002.
2. Balagurusamy, E., ?Numerical Methods?, Tata McGraw-Hill Pub.Co.Ltd, New
Delhi, 1999.
REFERENCES
1. Kandasamy, P., Thilagavathy, K. and Gunavathy, K., ?Numerical Methods?,
S.Chand Co. Ltd., New Delhi, 2003.
2. Burden, R.L and Faires, T.D., ?Numerical Analysis?, Seventh Edition, Thomson
Asia Pvt. Ltd., Singapore, 2002.
COMPUTER GRAPHICS
L T P M C
3 0 0 100 3
UNIT- I Introduction to Computer Graphics & Scan conversion 10
Overview of Computer Graphics, Computer Graphics Application and Software, Display
Technologies, Storage Tube Graphics Displays, Calligraphic Refresh Graphics
Displays, Raster Refresh (Raster-Scan) Graphics Displays, Cathode Ray Tube Basics,
Color CRT Raster Scan Basics, Video Basics, The Video Controller, Random-Scan
Display Processor, LCD displays.
Scan Converting Lines, Mid-point criteria, Problems of Aliasing, end-point ordering and
clipping lines, Scan Converting Circles, Scan Converting Ellipses, Filling Polygons,
edge data structure, Clipping Lines algorithms? Cyrus-Beck, Cohen-Sutherland and
Liang-Barsky, Clipping Polygons, problem with multiple components.
UNIT-II Two-Dimensional Transformations 8
Transformations and Matrices, Transformation Conventions, 2D Transformations,
Homogeneous Coordinates and Matrix Representation of 2D Transformations,
Translations and Homogeneous Coordinates, Rotation, Reflection, Scaling, Combined
Transformation, Transformation of Points, Transformation of The Unit Square, Solid
Body Transformations, Rotation About an Arbitrary Point, Reflection through an
Arbitrary Line, A Geometric Interpretation of Homogeneous Coordinates, The Windowto-
Viewport Transformations.
UNIT-III Three-Dimensional Transformations 9
Introduction, Three-Dimensional Scaling, Three-Dimensional Shearing, Three-
Dimensional Rotation, Three-Dimensional Reflection, Three-Dimensional Translation,
Multiple Transformation, Rotation about an Arbitrary Axis in Space, Reflection through
an Arbitrary Plane, Matrix Representation of 3D Transformations, Composition of 3D
Transformations, Affine and Perspective Geometry, Perspective Transformations,
Techniques for Generating Perspective Views, Vanishing Points, the Perspective
Geometry and camera models, Orthographic Projections, Axonometric Projections,
Oblique Projections, View volumes for projections.
UNIT-IV Solid Modeling & Visible-Surface Determination 9
Representing Solids, Regularized Boolean Set Operations, Primitive Instancing, Sweep
Representations, Spatial-Partitioning Representations - Octree representation, B-Reps,
Constructive Solid Geometry, Comparison of Representations.
Techniques for efficient Visible-Surface Algorithms, Categories of algorithms, Back face
removal, The z-Buffer Algorithm, Scan-line method, Painter?s algorithms (depth sorting),
Area sub-division method, BSP trees, Visible-Surface Ray Tracing, comparison of the
methods.
UNIT-V llumination and Shading & Graphics Programming using OPENGL 9
Illumination and Shading Models for Polygons, Reflectance properties of surfaces,
Ambient, Specular and Diffuse reflections, Atmospheric attenutation, Phong?s model,
Gouraud shading, some examples.
Why OpenGL, Features in OpenGL, OpenGL operations, Abstractions in OpenGL ? GL,
GLU & GLUT, 3D viewing pipeline, viewing matrix specifications, a few examples and
demos of OpenGL programs.
TOTAL :45
Text books :
1. J. D. Foley, A. Van Dam, S. K. Feiner and J. F. Hughes, Computer Graphics -
Principles and Practice, Second Edition in C, Pearson Education, 2003.
2. D. Hearn and M. Pauline Baker, Computer Graphics (C Version), Pearson
Education, 2nd Edition, 2004.
References:
1. D. F. Rogers and J. A. Adams, Mathematical Elements for Computer Graphics,
2nd Edition, McGraw-Hill International Edition, 1990.
2. F. S. Hill Jr., Computer Graphics using OpenGL, Pearson Education, 2003.
OPEN SOURCE LAB
L T P C
0 0 3 2
1. Installation in different modes (user mode, GUI, Single user, Server )
2. MySQL installation
3. Apache installation
4. PHP with Database connectivity
5. PHYTON programming
6. Perl script and CGI
7. Network simulator (NS2) installation and simple tcl scripts
OBJECT ORIENTED SYSTEM DESIGN LAB
L T P C
0 0 3 2
Solving Simple problems using CASE tools for design, testing with structure analysis
and design method and object oriented analysis and design method
i) SRS DOCUMENT (IEEE Standard)
ii) Design document
iii) Implementation
iv) Test case generation and test document preparation
1. Payroll system
2. Online shopping
3. Online voting system
4. Banking system
COMPUTER GRAPHICS LAB
L T P C
0 0 3 2
1. Implementation of Bresenham?s Algorithm
Line
Circle
Ellipse
2. 2D and 3D transformation
Translation
Rotation
Scaling
Reflection
Shearing of objects
3. Cohen Sutherland 2D clipping and windowing
Download HEre Click
Source: http://softwaretrojans.blogspot.com/2012/12/sixth-semester-cse-syllabus_11.html
north korea missile launch modesto st louis weather guinea bissau google stock google stock china gdp
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন