Atal Bihari Vajpayee Vishwavidyalaya v semester Syllabus
BCS-501 THEORY OF COMPUTATION
Core Course:11 Marks: 100 Total Credit: 06
Course Outcome: At the end of course, Students will be able to
Discuss properties of different grammars and languages.
Solveproblems related to string membership to an automata and respective Language.
Create grammar for specific language.
Identify language accepted by particular automata.
Design optimum automata for particular language.
UNIT-I
Introduction: Introduction of alphabets, Strings and Languages; Automata, Finite automata (FA), Deterministic Finite Automata (DFA) -Formal definition, simplified notations (state transition diagram, transition table), Non-deterministic Finite Automata (NFA -Formal Definition, Acceptability of a String by a DFA & NFA), Minimizing number of state of a DFA.
UNIT-II
Finite Automata with output: Moore and Mealy Machine, Procedure for Transforming a Mealy Machine into a Moore Machine and vice versa. Formal language: Definition of a Grammar, Derivations and the Language Generated by a Grammar, Chomsky Classification of Languages, Languages and Their Relation, Recursive and Recursively Enumerable Sets, Operations on Languages, Languages and Automata.
UNIT-III
Regular expressions (RE): Definition, FA and RE, Transition System Containing A-moves, NFAs with A-moves and Regular Expressions, NFA to DFA conversion, Algebraic Method Using Arden's Theorem, Construction of Finite Automata Equivalent to a Regular Expression and vice versa, Equivalence of two FA, Equivalence of two RE. Regular Sets: Pumping Lemma for Regular Sets, Application of Pumping Lemma, Closure Properties of Regular Sets, Regular Sets and Regular Grammars, Closure Properties of Regular languages, emptiness, finiteness, membership.
UNIT-IV
Context-free Grammars (CFGs): Formal definition, sentential forms, leftmost and rightmost derivations, The language of CFG, Derivation tree, Ambiguity in grammars and Languages, Ambiguity in CFG, Simplification of CFG, Normal Forms for CFG (Chomsky Normal Form, Greibach Normal Form), Pumping Lemma for Context-free Languages, Closure Properties of CFG’s.
UNIT-V
Pushdown Automata (PDA):Formal definition, acceptance by PDA, PDAs and CFGs, CFG to PDA, PDA to CFG, DPDAs -Definition, DPDAs and Regular Languages, DPDAs, and CFLs, Languages of DPDAs, DPDAs
Context Sensitive Grammar: Definition, Linear Bounded Automata, Turing Machines -Formal definition and behavior, Transition diagrams, acceptance by TM, Multi tape Turing Machine, Universal Turing Machine, Halting Problem of Turing Machine.
TEXT/REFERENCE BOOKS:
1. “Elements of The Theory of Computation”, H.R.Lewis& C.H. Papadimitriou, P.H.I.
2. “Introduction To Automata Theory, Language and Computation” J.E.Hopcroft, R.MotwaniJ.D.Ullman, Pearson Education
3. “Theory of Computer Science(Automata, Languages And Computation)”, K.L.P.Mishra, N.Chandrasekaran:,PHI
4. “Introduction to languages and Theory of Computation”, John Martin, McGraw Hill
5. “Introduction To Computer Theory”, D.A.Cohen (J.Wiley
BCS-502 PROGRAMMING IN JAVA
Core Course: 12 Marks: 100 Total Credit: 06
Course Outcome: At the end of course, Students will be able to
Explain the object-oriented concepts and JAVA.
Implement, compile, test and run Java programs comprising more than one class, to address a particular software problem.
Demonstrate the principles of object oriented programming.
Create multi-threaded programs and event handling mechanisms
Develop simple GUI interfaces for a computer program to interact with users.
UNIT-1
Overview of JAVA: The genesis of java, An overview of java, Java virtual machine (JVM), Java development kit (JDK), Java Vs C++, Data types, Literals, Variables, and Arrays, Operators, Control statements.
UNIT-II
Introducing Class: Class fundamentals, Closer look at Methods and class ,Nested and inner class ,Exploring Java lang, String handling ,Constructor ,this keyword, Garbage collection and finalize() method. Writing simple JAVA program.
UNIT-III
Inheritance: Basics ,Types of inheritance ,Access specifier ,using super, method overriding ,Abstract class ,constructor in multilevel inheritance ,using final with inheritance ,Dynamic method dispatch .
UNIT-IV
Package and Interface: Defining package, CLASSPATH, Access protection, Importing package, Defining and implementing interface, Variable in interface, Extending interface, Nested interface.
UNIT-V
Exception handling and Multithreading: Using try and catch ,multiple catch classes, Nested try statements , throw ,throws and finally ,Built in exception ,Uncaught exception , Creating own exception class , Java Thread Model: Main thread ,Creating own Thread ,Life cycle of thread, Thread priorities ,Synchronization and messaging, Interthread communication ,Suspending ,Resuming and stopping thread.
TEXT/REFERENCE BOOK
1. Java: The complete reference By Naughton P and schildtH. ,Osborne Tata Mcgraw-Hill.
2. Java Programming By E.Balguruswami
3. Core JAVA for beginners By RashmiKantaDas ,Vikas Publication.
4. Core JAVA : A Comprehensive Study by Mahesh P. Matha , PHI publication
BCS-504 NUMERICAL METHODS
Discipline Specific Elective DSE:1 Marks: 100 Total Credit: 06
Course Outcome: At the end of course, Students will be able to
To provide suitable and effective methods called Numerical Methods, for obtaining approximate representative numerical results of the problems.
To solve complex mathematical problems using only simple arithmetic operations. The approach involves formulation of mathematical models of physical situations that can be solved with arithmetic operations
Make use of analytical methods to solve higher order differential equations.
Apply elementary probability theory and solve related problems. Classify partial differential equations and solve them by exact methods.
Apply the knowledge of numerical methods in modelling and solving engineering problems. Note: Scientific calculators are allowed for this subject.
UNIT–I
Algebraic and Transcendental Equations: Errors and precision, errors due to round off, Solution of Algebraic and Transcendental Equations, Bisection Method, Method of False Position, Newton-Raphson Method.
UNIT-II
Interpolation: Introduction, Newton’s Backward Interpolation formula, Newton’s Forward Interpolation formula, Gausses forward Interpolation Formula, Gausses Backward Interpolation formula, Lagrange’s Interpolation formula, Newton divided difference formula.
UNIT–III
Curve Fitting:
Graphical method, Laws reducible to the linear laws, Principal of least square, Method of least
squares, fitting a curve of type y= a+bx2
, y= ax+bx2
, y=ax+b/x, y= ax2+bx, y=axb
, y=aebx etc.
Method of group averages.
UNIT-IV
Numerical Differentiation: Forward Difference formula, Backward Difference formula, Numerical Integration : Quadrature formulae , Errors in Quadrature formulae, Rombergs Method, Euler –Maclaurin formula.
UNIT–V
Numerical solution of Ordinary Differential equations: Picards method, Taylors series method, Eulers method, Modified Eulers method, Runges method, Runge-kutta method
TEXT /REFERENCE BOOKS:
1. “Numerical Analysis”, S.S. Sastry, PHI
2. “Numerical Method in Engineering and Science”, Dr. B.S. Grewal, Khanna Publishers,2010
3. “Computer Oriented Numerical Methods”, Rajaraman, PHI
4. “Numerical Computations”, Venkataraman
5. “Computer Oriented Numerical Methods”, Stoer, Bullrich, Springer Verlag, 1980.
BCS-505 MICROPROCESSOR
Discipline Specific Elective DSE:1 Marks: 100 Total Credit: 06
Course Outcome: At the end of course, Students will be able to
Understand and device techniques for faster execution of instructions, improve speed of operations and enhance performance of microprocessors.
Assess and solve basic binary math operations using the microprocessor and explain the microprocessor’s and Microcontroller’s internal architecture and its operation within the area of manufacturing and performance
Compare accepted standards and guidelines to select appropriate Microprocessor (8085 & 8086) and Microcontroller to meet specified performance requirements.
Analyze assembly language programs; select appropriate assemble into machine a cross assembler utility of a microprocessor and microcontroller.
Design electrical circuitry to the Microprocessor I/O ports in order to interface the processor to external devices.
Evaluate assembly language programs and download the machine code that will provide solutions real‐world control problems.
UNIT-I
Introduction to Microprocessor: Fundamental definition of Microprocessor, evolution of Microprocessor, Microprocessor Instruction set and Computer Languages, From large scale to single chip microcontrollers, Von Neumann and Harvard architecture, RISC vs. CISC, Application: Microprocessor Controlled Temperature System.
UNIT-II
8086 Architecture: Register organization of 8086, Architecture, signal description of 8086, Physical memory organization , General Bus operation, I/O addressing capability, Special processor activities, Minimum mode 8086 system and timings, Maximum Mode 8086 system and timings, The processor 8088.
UNIT-III
8086/8088 instruction set and assembler directives: Machine language instruction format, Addressing mode of 8086, Instruction set of 8086/8088, Assembler directives and operators.
UNIT-IV
Special architectural features: Stack structure of 8086/8088, interrupt and interrupt services routine, interrupt cycle of 8086/8088, Non maskable interrupt, Maskable interrupt.
UNIT-V
Intel I Processor: Case study of Intel i series of processors
TEXT BOOKS:
1. “Microprocessors Architecture, Programming and Applications”, Ramesh S. Goanker, Wiley Eastern, 1994 or (Latest Edition)
REFERENCE BOOKS:
1. “Micro Processors & Interfacing”, Douglas U. Hall, 2007.“The 8088 and 8086 Micro Processors”, 4th Edition, PHI, 2003.
2. “Micro Computer System 8086/8088 Family Architecture, Programming and Design”, Liu and GA Gibson, 2nd Edition, PHI
3. “Introduction to Microprocessors”, Aditya P. Mathur, TMH, 1995
BCS-506 MACHINELEARNING
Discipline Specific Elective DSE:2 (Group-A) Marks: 100 Total Credit: 04
Course Outcome: At the end of course, Students will be able to
● Learn, understand, and practice machine learning approaches, which include the study of modern computing technologies and scaling up machine learning techniques.
● Select and implement machine learning techniques and computing environment that are suitable for the applications under consideration.
● Apply various machine learning algorithms to solve real world problems.
● Write program to implement machine learning based models.
● Solve the problems related to liner regression, classification etc.
UNIT-I
Introduction: Concept of Machine Learning, Applications of Machine Learning, Key elements of Machine Learning, Supervised vs. Unsupervised Learning, Traditional programming Vs. Machine learning Statistical Learning: Bayesian Method, The Naïve Bayes Classifier.
UNIT-II
Linear Regression: Prediction using Linear Regression, Gradient Descent, Linear Regression with one variable, Linear Regression with multiple variables, Polynomial Regression, Feature Scaling/Selection.
UNIT-III
Logistic Regression: Classification using Logistic Regression, Logistic Regression vs. Linear Regression, Logistic Regression with one variable and with multiple variables.
UNIT-IV
Regularization: Regularization and its utility: The problem of Over fitting, Application of Regularization in Linear and Logistic Regression, Regularization and Bias/Variance. Neural Networks: Introduction, Model Representation, Gradient Descentvs. Perceptron Training, Stochastic Gradient Descent, Multilayer Perceptrons, Multiclass Representation, Backpropagation Algorithms.
UNIT V
Machine learning tools: Introduction of MATLAB, WEKA as machine learning tools,Using GUI of MATLAB and WEKA to develop Machine learning based models. Write programs to Implementmachine learning models.
TEXT/REFRENCE BOOKS:
1. Ethem Alpaydin,"Introduction to MachineLearning"2nd Edition, TheMIT Press, 2009.
2. TomM.Mitchell,"MachineLearning",FirstEditionbyTataMcGraw-HillEducation,2013.
3. ChristopherM. Bishop, "Pattern Recognition andMachineLearning"bySpringer, 2007.
4. MevinP.Murphy,"MachineLearning:AProbabilisticPerspective"byTheMITPress,2012.
5. S.N. shivanandan and pai, willey publication.
6. Neural network and Learning Machines, Simon Haykin, Pearson Education, 2011
BCS-507 MACHINE LEARNING LAB
Discipline Specific Elective DSE: 2 (Group-A) Marks: 100 Total Credit: 02
Course Outcome: At the end of course, Students will be able to
Understand complexity of Machine Learning algorithms and their limitations;
Applying common Machine Learning algorithms in practice and implementing their own.
Perform experiments in Machine Learning using real-world data.
Design and implement machine learning solutions to classification, regression, and clustering problems; and be able to evaluate and interpret the results of the algorithms.
Understand modern notions in data analysis oriented computing.
1. Use command to compute the size of a matrix, size/length of a particular row/column, load data from a text file, store matrix data to a text file, finding out variables and their features in the current scope.
2. Perform basic operations on matrices (like addition, subtraction, multiplication) and
3. Display specific rows or columns of the matrix.
4. Perform other matrix operations like converting matrix data to absolute values, taking the negative of matrix values, additing/removing rows/columns from a matrix, finding the maximum or minimum values in a matrix or in a row/column, and finding the sum of some/all elements in a matrix.
5. Create various type of plots/charts like histograms, plot based on sine/cosine function based on data from a matrix. Further label different axes in a plot and data in a plot.
6. Generate different subplots from a given plot and color plot data.
7. Use conditional statements and different type of loops based on simple example/s.
8. Perform vectorized implementation of simple matrix operation like finding the transpose of a matrix, adding, subtracting or multiplying two matrices.
9. Implement Linear Regression problem. For example, based on a dataset comprising of existing set of prices and area/size of the houses, predict the estimated price of a given house.
10. Based on multiple features/variables perform Linear Regression. For example, based on a number of additional features like number of bedrooms, servant room, number of balconies, number of houses of years a house has been built – predict the price of a house.
11. Implement a classification/ logistic regression problem. For example based on different features of students data, classify, whether a student is suitable for a particular activity. Based on the available dataset, a student can also implement another classification problem like checking whether an email is spam or not.
12. Use somefunction for regularization of dataset based on problem 14.
13. Use some function for neural networks, like Stochastic Gradient Descent or backpropagation - algorithm to predict the value of a variable based on the dataset of problem
Note: List of experiments may be changed by the concern teacher.
BCS-508 INTRODUCTIONTO DATA SCIENCE
Discipline Specific Elective DSE:2 (Group-B) Marks: 100 Total Credit: 04
Course Outcome: At the end of course, Students will be able to
Describe what Data Science is and the skill sets needed to be a data scientist.
Explain in basic terms what Statistical Inference means. Identify probability distributions commonly used as foundations for statistical modelling. Fit a model to data.
Use R to carry out basic statistical modelling and analysis.
Explain the significance of exploratory data analysis (EDA) in data science. Apply basic tools(plots, graphs, summary statistics) to carry out EDA.
Employ cutting edge tools and technologies to analyze Big Data.
UNIT-I
Data Scientist’s Tool Box: Turning data into actionable knowledge, introduction to the tools that will beused in buildingdata analysis software: version control, markdown, git, GitHub, R, and RStudio.
UNIT-II
R Programming Basics: Overview of R, R data types and objects, reading and writing data, Control structures, functions, scoping rules, dates and times, Loop functions, debugging tools, Simulation, code profiling
UNIT-III
Getting andCleaning Data: Obtaining data from the web, from APIs, from databases and from colleagues in various formats. Basicsofdata cleaning and makingdata―tidy.
UNIT-IV
Exploratory Data Analysis: Essential exploratory techniques for summarizing data, applied before formal modeling commences, eliminating or sharpening potential hypotheses about the world that can be addressed by the data, common multivariate statistical techniques used to Visualize highdimensional data.
UNIT-V
ReproducibleResearch: Concepts and tools behind reporting modern data analyses in a reproducible manner, To write a document using R markdown, integrate live R code into a literate statistical program, compile R markdown documents using knitr and related tools, and organizeadata analysis so that it is reproducible and accessibleto other
TEXT/REFERENCE BOOKS:
1. Rachel Schutt, Cathy O'Neil, "Doing Data Science: Straight Talk from theFrontiline"bySchroff/O'Reilly, 2013
. 2. FosterProvost,TomFawcett,"DataScienceforBusiness"WhatYouNeedtoKnowAbout DataMining andData-AnalyticThinking" byO'Reilly, 2013.
3. JohnW.Foreman,"DataSmart:UsingdataSciencetoTransformInformationintoInsight"byJoh n Wiley&Sons, 2013.
4. IanAyres,"SuperCrunchers:WhyThinking-by-NumbersIstheNewWaytoBeSmart"Ist Editionby Bantam,2007.
5.EricSeigel,"PredictiveAnalytics:ThePowertoPredictwhoWillClick,Buy,Li st e,orDie", 1 Edition, byWiley, 2013
BCS-509 INTRODUCTIONTO DATA SCIENCE LAB
Discipline Specific Elective DSE:2 (Group-B) Marks: 100 Total Credit: 02
Course Outcome: At the end of course, Students will be able to
Describe what Data Science is and the skill sets needed to be a data scientist.
Explain in basic terms what Statistical Inference means.
Identify probability distributionscommonly used as foundations for statistical modelling.
Use R to carry out basic statistical modelling and analysis.
Explain the significance of exploratory data analysis (EDA) in data science. Apply basic tools(plots, graphs, summary statistics) to carry out EDA.
1. Write a program that prints “Hello World‘ to the screen.
2. Write a program that asks the user for a number n and prints the sum of the numbers 1to n
3. Write a program that prints a multiplication table for numbers up to 12.
4. Write a function that returns the largest element in a list.
5. Write a function that computes the running total of a list.
6. Write a function that tests whether a string is a palindrome.
7. Implement linear search.
8. Implement binary search.
9. Implement matrices addition , subtraction and Multiplication
10. Fifteen students were enrolled in a course. There ages were: 20 20 20 20 20 21 21 21 22 22 22 22 23 23 23
i. Find the median age of all students under 22 years
ii. Find the median age of all students
iii. Find the mean age of all students
iv. Find the modal age for all students
v. Two more students enter the class. The age of both students is 23. What is now mean, mode and median ?
11. Following table gives a frequency distribution of systolic blood pressure. Compute all themeasures of dispersion.
Midpoint 95.5 105.5 115.5 125.5 135.5 145.5 155.5 165.5 175.5
Number 5 8 22 27 17 9 5 5 2
12.Obtain probability distribution of , where X is number of spots showing when a sixsidedsymmetric die (i.e. all six faces of the die are equally likely) is rolled. Simulate random samplesof sizes 40, 70 and 100 respectively and verify the frequency interpretation of probability.
13.Make visual representations of data using the base, lattice, and ggplot2 plotting systems in R,apply basic principles of data graphics to create rich analytic graphics from available datasets.
14. Use Git / Github software to create Github account. Also, create a repo using Github.
Note: List of experiments may be changed by the concern teacher..