Tweet
Right now, I've just finished my second year of my Bachelor of Engineering in Computer Science.
The university recommends textbooks for the courses, of course, but they aren't mandatory. We're given the freedom to choose our own textbooks pretty much as we please. I know that people here are much more knowledgeable about each of these areas, so I'm requesting help before making this rather large investment.
I've listed out the subject names with a short précis of each below. The detailed syllabus is given later.
Database Management System (how to design and build a database)
Data Communication (different types of modulation, information and coding theory, digital communication)
Microprocessors and Microcontrollers (the Intel Pentium, its architecture, the 8051 & PIC)
Digital Signal Processing
Theory of Computation
Database Management System
Unit I (06 Hrs)
Introduction to DBMS: Basic concepts, Advantages of a DBMS over file-processing
systems, Data abstraction, Database Languages, Data Models and Data Independence,
Components of a DBMS and overall structure of a DBMS, Multi-User DBMS
Architecture, System Catlogs
Data Modeling: Basic Concepts, entity, attributes, relationships, constraints, keys, E-R
and EER diagrams: Components of E-R Model, conventions, converting E-R diagram into
tables, EER Model components, converting EER diagram into tables
Relational Model: Basic concepts, Attributes and Domains, Codd's Rules, Relational
Integrity: Nulls, Entity, Referential Integrities, Enterprise Constraints, Views, Schema
diagram
Unit II (06 Hrs)
Relational Query Languages: Relational Algebra and Relational Calculus: Tuple
Relational and Domain Relational Calculus
Introduction to SQL: Characteristics and advantages, SQL Data Types and Literals,
DDL, DML, SQL Operators, Tables: Creating, Modifying, Deleting, Views: Creating,
Dropping, Updation using Views, Indexes, Nulls
SQL DML Queries: SELECT Query and clauses, Set Operations, Predicates and Joins,
Set membership, Tuple Variables, Set comparison, Ordering of Tuples, Aggregate
Functions, Nested Queries, Database Modification using SQL Insert, Update and Delete
Queries, concept of Stored Procedures and Triggers, Introduction to QBE and QUEL
Programmatic SQL: Embedded SQL, Dynamic SQL, ODBC
Unit III (06 Hrs)
Database Analysis and Design Techniques: Information Systems Lifecycle, Application
Lifecycle, Planning, System Definition, Requirement Analysis, Design, DBMS Selection,
Application Design: Transaction and User-Interface Design, Prototyping, Implementation,
Data Conversion and Loading, Testing, Data and Database Administration, Fact-Finding
Techniques
Relational Database Design: Purpose of Normalization, Data Redundancy and Update
Anomalies, Functional Dependencies, The Process of Normalization: INF, 2NF, 3NF, BCNF,
4NF, 5NF and DKNF
Unit IV (06 Hrs)
Storage and File Systems: Secondary Storage, RAID, File Organization, Indices, Static and
Dynamic Hashing, B-trees and B+ Trees
Introduction to Query Processing: Overview, Measures of query cost, Selection and join
operations, Evaluation of Expressions, Introduction to Query Optimization, Estimation,
Transformation of Relational Expressions
Unit V (06 Hrs)
Transaction Management: Basic concept of a Transaction, Properties of Transactions, Database
Architecture, Concept of Schedule, Serial Schedule, Serializability: Conflict and View, Cascaded
Aborts, Recoverable and Non-recoverable Schedules, Concurrency Control: Need, Locking
Methods, Deadlocks, Timestamping Methods, Optimistic Techniques, Multi-Version
Concurrency Control, Different Crash Recovery methods such as Shadow-Paging and Log-Based
Recovery: Deferred and Immediate, Checkpoints
Unit VI ' (06 Hrs)
Object-Oriented Databases: Need of OODBMS, Storing Objects in Relational Database,
Introduction to OO Data Models, Persistent Programming Languages, Pointer Swizzling
Techniques, Persistence, Object Management Group, Object Database Standard ODMG
Database Architectures: Centralized and Client-Server Architectures, Introduction to
Distributed Database systems
Data Communication
Unit I (06 Hrs)
Introduction: Communication System, Modulation, Baseband and Carrier Communication,
Amplitude modulation: DSBFC, DSBSC, SSB, QAM, Carrier Acquisition, Superheterodyne
AM Receiver, Angle Modulation: Frequency modulation, phase modulation, Analysis of FM,
Bandwidth Requirements, Equivalence between FM and PM Digital Continuous Wave
Modulation: ASK, FSK and PSK and Modems
Unit 11 (06 Hrs)
Pulse Modulation: Sampling theorem, Natural and Flat Top Sampling, PAM, Pulse Time
Modulation, Pulse Transmission over Band Limited Channel, Effect of Gaussian Type Noise
on Digital Transmission, Crosstalk, Eye Diagram Line Codes: Bipolar, Unipolar, RZ, NRZ,
Manchester, AMI
Unit III (06 Hrs)
Pulse Code Modulation: Encoder and Decoder, PCM - TDM, Tl Carrier System,
Quantization Noise, Companding, DPCM, ADPCM, Delta modulation, Slope overload and
Adaptive Delta Modulation, Scrambling, Digital Carrier Systems, Digital Multiplexing
Unit IV (06 Hrs)
Information and Coding: Measure of information, entropy, information rate, Shannon's
theorems on channel capacity, Optimum Codes, Huffman Code, Code Efficiency, Error
Control Coding, Methods of Controlling Errors, Types of Errors, Types of Codes, Linear
Block Codes: Matrix Description of Linear Block Codes, Error detection and correction
capabilities, Hamming Distance, Hamming Bound, Hamming Codes, CRC Block Codes,
Syndrome Calculation, Error Detection and Correction, Handshaking Techniques, FEC, ARQ
- Stop and Wait, Go Back N, Selective Repeat, Channel Throughput and Efficiency
UnitV (06 Hrs)
Digital Communications Technologies: SF, ESF Framing, DS1/T1, B8ZS, DSU, CSU,
HDSL, Digital Hierarchy, Digital Services, ISDN, Frame Relay, SONET, ATM, BISDN,
SMDs, Video on Demand, ADSL
Cellular Telephone Systems: Spread Spectrum Systems, DS/SS, FH/SS, Cellular Telephony,
GPS, Transmission Media, PSTN
Unit VI (06 Hrs) Computer Network: Need and Applications of Network, Network
Architecture, Protocols and Standards, OSI Model, TCP/IP Model, Network topology
(Physical & logical), Types of Networks: Peer to Peer, Client-Server, LAN: Ethernet, Token
Ring, FDDI, MAN: DQDB, SMDS, WAN: Architecture, Transmission Mechanism,
Addressing, ISDN and Broadband ISDN
Transmission Media: Guided Media - Twisted Pair, Coaxial and Fiber-optic cables,
Unguided Media (Wireless): Radio and Micro Waves, Infrared
Switching Techniques: Circuit switching, Packet switching and message switching,
Telephone network, High-Speed Digital Access: DSL, Cable Modems and Sonets
Digital Signal Processing
Unit I (08 Hrs)
Classification of Signals: Analog, Discrete-time and Digital, Basic sequences and sequence
operations. Discrete-time systems, Properties of D. T. Systems and Classification, Linear Time
Invariant Systems, impulse response, linear convolution and its properties, properties of LTI
systems: stability, causality, parallel and cascade connection, Linear constant coefficient different
equations, Eigen functions for LTI systems and frequency response, Periodic Sampling, Sampling
Theorem, Frequency Domain representation of sampling, reconstruction of a band limited Signal,
A to D conversion Process: Sampling, quantization and encoding.
Unit 11 (08 Hrs)
Representation of Sequences by Fourier Transform, Symmetry properties of F. T., F. T. theorems:
Linearity, time shifting, frequency shifting, time reversal, differentiation, Parseval’s theorem,
convolution theorem, windowing theorem, Z-transform, ROC and its properties, Inverse z
transform by inspection, partial fraction, power series expansion and complex inversion, Z
transform properties: Linearity, time shifting, multiplication by exponential sequence,
differentiation, conjugation, time reversal, convolution, initial value theorem, Unilateral Ztransform:
solution of difference equation
Unit III (08 Hrs)
Frequency Response of LTI Systems: Ideal frequency selective filters, magnitude and phase
response, group delay, System Functions for LTI Systems: Stability and causality, inverse
systems, significance of poles/zeros, Frequency Response for Rational System Functions:
Frequency Response of a single zero or pole, Frequency response from pole-zero plot using
simple geometric construction, systems with Linear phase, Generalized Linear phase systems,
Four Types of GLPS
Unit IV (08 Hrs)
Sampling the F.T., Fourier representation of finite-duration sequences: The Discrete Fourier
Transform, Properties of DFT: Linearity, circular shift, duality, symmetry, Circular Convolution,
Linear Convolution using DFT, Effective computation of DFT and FFT, Goerzel Algorithm, DIT
FFT, DIP FFT, Inverse DFT using FFT, Practical considerations in FFT implementation
Unit V (08 Hrs)
Concept of filtering, Ideal filters and approximations, specifications, IIR filter design from
continuous time filters: Characteristics of Butterworth, Cheybyshev and elliptic
approximations, impulse invariant and bilinear transformation techniques, Design examples,
FIR filter design using windows: properties of commonly used windows, incorporation of
Generalized Linear Phase, Design Examples, Design using Kaiser window, Comparison of
IIR and FIR Filters
Unit VI (08 Hrs)
Block diagrams and Signal flow graph representation of LCCDE, Basic structures for IIR
Systems: direct form, cascade form, parallel form, feedback in IIR systems, Transposed Forms,
Basic Structures for FIR Systems: direct form, cascade form, structures for linear phase FIR
Systems, Finite Register Length effect
DSP Processors Architecture and Applications of DSP: Detail Study of DSP chip architecture as
an example of ADSP 21XX series of microprocessor and their desirable features, Instruction set
of ADSP 21XX series processor and some examples
Theory of Computation
Unit I (6 Mrs)
Automata Theory: Introduction to Finite Automata, Structural Representations, Automata
and Complexity, Central Concepts to Automata Theory: Alphabets, Strings, Languages and
Problems, Finite Automata: An Informal Picture of FA, Deterministic Finite Automaton
(DFA): How a DFA processes Strings, Simpler Notations for DFA, Extending the transition
function to strings, the language of DFA, Non-deterministic Finite Automaton (NFA): NFA,
Extended transition function, the language of an NFA, Equivalence of NFA and DFA, FA
with e-transitions: Use of e-transitions, NFA with e, e-closures, Extended transitions and
languages for e-N F A , E lim inating € -transitions-Con version of NFA with e to NFA without
e, Conversion of NFA without e to DFA, Conversion of NFA with 6 to DFA (direct method),
FA with output: Moore and Mealy machines -Definition, models, inter-conversion.
Unit II (6 Hrs)
Regular Expressions (RE) and Languages: Regular Expressions - Operators of RE,
Building RE, Precedence of operators, Algebraic laws for RE, Arden's Theorem, FA and RE:
DFA to RE, RE to DFA (RE to s-NFA & e-NFA to DFA and RE to DFA-direct method), FA
limitations, Properties of Regular Languages: pumping lemma for regular languages, closure
and decision properties of regular languages, Equivalence and minimization of automata,
Application of RE: Regular expressions in Unix, GREP utilities of Unix, Lexical analysis and
finding patterns in text.
Unit III (6 Hrs)
Context Free Grammars (CFG) and Languages: Context Free Grammar- Definition,
derivations, languages of a grammar, sentential form, Parse Tree- inference, derivation and
parse tree, from inference to tree, Ambiguity in grammars and languages: removal of
ambiguity, inherent ambiguity, Properties of CFL- Normal forms- Chomsky Normal Form
and Greibach Normal Form, Eliminating unit productions, useless production, useless
symbols, and e-productions, Regular Grammar - definition, left linear and right linear
Regular Grammar, Regular Grammar and Finite Automata, FA to RG and RG to FA, Interconversion
between left linear and right linear regular grammar.
Unit IV (6 Hrs)
Push Down Automata (PDA): Definition, The Language of PDA, Equivalence of PDA's
and CFG- CFG to PDA, PDA to CFG, Deterministic Push Down Automata (DPDA)-
Regular language and DPDA, DPDA and CFL, DPDA and ambiguous grammar, Nondeterministic
Push Down Automata (NPDA), The pumping lemma for CFL, Closure
properties of CFL, Decision properties of CFL, Chomsky Hierarchy, Application of CFG:
Parser, Markup languages, XML and Document Type Definitions.
Unit V (6 Hrs) Turing Machine: Problems that computers cannot solve, The Turing
Machine(TM)-Notation, the language of TM, TM and Halting, Programming techniques to TM,
Extensions to basic TM, TM and Computers. Introduction to Post Machines, Comparison
between FA, PDA, Post Machine and TM
Unit VI (6 Hrs)
Introduction to Computational Complexity: Un-decidability: A Language that is not
recursively enumerable, An un-decidable problem that is RE, Post Correspondence Problem,
Intractable Problems* The classes P and NP, Problems solvable in polynomial time, Nondeterministic
Polynomial time, Polynomial time reduction and NP-complete problems.
Microprocessors and Microcontrollers
Unit I: Introduction to Pentium Microprocessors
Historical evolution of 80286, 386, and 486 processors, Pentium features and architecture, pin description, functional description, Pentium real mode, Pentium RISC features, Pentium super-scalar architecture pipelining, instruction paring rules, branch prediction, instruction and data caches, the floating-point unit
Unit II: Cycles and memory organisation
Initialisation and configuration, bus operations, reset, non-pipelined and pipelined read and write, memory organisation and I/O organisation, data transfer mechanism, 8-bit, 16-bit, 32-bit data-but interface
Pentium programming: programmers' model, register set, addressing modes, instruction set, data types, data transfer instructions, string instructions, arithmetic instructions, logical instructions, bit manipulation instructions, program transfer instructions, processor control instructions
Unit III: Protected Mode
Introduction, segmentation/support registers, related instruction descriptions, memory management through segmentation, logical to linear address translation, protection by segmentation, privilege level protection, related instructions, inter-privilege level transfer of control, paging support registers, descriptors, linear to physical address translation, TLB, page level protection, virtual memory
Unit IV: Multitasking, Interrupts, Exceptions, and I/O
Multitasking - support registers, related descriptors, task switching, I/O permission bitmap
Virtual Mode - features, address generation, privilege level, instruction and registers available, entering and leaving V86 mode
Interrupt structure - real, protected, and virtual 8086 modes, I/O handling in the Pentium, comparison of all three modes
Unit V: 8051 microcontrollers
Micro-controller MCS-51 family architecture, on-chip data, memory and program memory organisation - register set, register bank, SFRs, external data memory and program memory, interrupt structure, timers and their programming, serial port and programming, other features, design of minimum system using 8051 microcontroller for various applications
Unit VI: PIC microcontroller
Overview and features of PIC 16-C, PIC 16F8XX, pin diagram, capture mode, compare mode, PWM mode, block diagram, programmers' model of PIC, reset and clocking.
Memory organisation - program memory, data memory, flash, EEPROM, PIC 16F8XX addressing modes, instruction set, programming, I/O ports, interrupts, timers, ADC
The university recommends textbooks for the courses, of course, but they aren't mandatory. We're given the freedom to choose our own textbooks pretty much as we please. I know that people here are much more knowledgeable about each of these areas, so I'm requesting help before making this rather large investment.
I've listed out the subject names with a short précis of each below. The detailed syllabus is given later.
Database Management System (how to design and build a database)
Data Communication (different types of modulation, information and coding theory, digital communication)
Microprocessors and Microcontrollers (the Intel Pentium, its architecture, the 8051 & PIC)
Digital Signal Processing
Theory of Computation
Database Management System
Unit I (06 Hrs)
Introduction to DBMS: Basic concepts, Advantages of a DBMS over file-processing
systems, Data abstraction, Database Languages, Data Models and Data Independence,
Components of a DBMS and overall structure of a DBMS, Multi-User DBMS
Architecture, System Catlogs
Data Modeling: Basic Concepts, entity, attributes, relationships, constraints, keys, E-R
and EER diagrams: Components of E-R Model, conventions, converting E-R diagram into
tables, EER Model components, converting EER diagram into tables
Relational Model: Basic concepts, Attributes and Domains, Codd's Rules, Relational
Integrity: Nulls, Entity, Referential Integrities, Enterprise Constraints, Views, Schema
diagram
Unit II (06 Hrs)
Relational Query Languages: Relational Algebra and Relational Calculus: Tuple
Relational and Domain Relational Calculus
Introduction to SQL: Characteristics and advantages, SQL Data Types and Literals,
DDL, DML, SQL Operators, Tables: Creating, Modifying, Deleting, Views: Creating,
Dropping, Updation using Views, Indexes, Nulls
SQL DML Queries: SELECT Query and clauses, Set Operations, Predicates and Joins,
Set membership, Tuple Variables, Set comparison, Ordering of Tuples, Aggregate
Functions, Nested Queries, Database Modification using SQL Insert, Update and Delete
Queries, concept of Stored Procedures and Triggers, Introduction to QBE and QUEL
Programmatic SQL: Embedded SQL, Dynamic SQL, ODBC
Unit III (06 Hrs)
Database Analysis and Design Techniques: Information Systems Lifecycle, Application
Lifecycle, Planning, System Definition, Requirement Analysis, Design, DBMS Selection,
Application Design: Transaction and User-Interface Design, Prototyping, Implementation,
Data Conversion and Loading, Testing, Data and Database Administration, Fact-Finding
Techniques
Relational Database Design: Purpose of Normalization, Data Redundancy and Update
Anomalies, Functional Dependencies, The Process of Normalization: INF, 2NF, 3NF, BCNF,
4NF, 5NF and DKNF
Unit IV (06 Hrs)
Storage and File Systems: Secondary Storage, RAID, File Organization, Indices, Static and
Dynamic Hashing, B-trees and B+ Trees
Introduction to Query Processing: Overview, Measures of query cost, Selection and join
operations, Evaluation of Expressions, Introduction to Query Optimization, Estimation,
Transformation of Relational Expressions
Unit V (06 Hrs)
Transaction Management: Basic concept of a Transaction, Properties of Transactions, Database
Architecture, Concept of Schedule, Serial Schedule, Serializability: Conflict and View, Cascaded
Aborts, Recoverable and Non-recoverable Schedules, Concurrency Control: Need, Locking
Methods, Deadlocks, Timestamping Methods, Optimistic Techniques, Multi-Version
Concurrency Control, Different Crash Recovery methods such as Shadow-Paging and Log-Based
Recovery: Deferred and Immediate, Checkpoints
Unit VI ' (06 Hrs)
Object-Oriented Databases: Need of OODBMS, Storing Objects in Relational Database,
Introduction to OO Data Models, Persistent Programming Languages, Pointer Swizzling
Techniques, Persistence, Object Management Group, Object Database Standard ODMG
Database Architectures: Centralized and Client-Server Architectures, Introduction to
Distributed Database systems
Data Communication
Unit I (06 Hrs)
Introduction: Communication System, Modulation, Baseband and Carrier Communication,
Amplitude modulation: DSBFC, DSBSC, SSB, QAM, Carrier Acquisition, Superheterodyne
AM Receiver, Angle Modulation: Frequency modulation, phase modulation, Analysis of FM,
Bandwidth Requirements, Equivalence between FM and PM Digital Continuous Wave
Modulation: ASK, FSK and PSK and Modems
Unit 11 (06 Hrs)
Pulse Modulation: Sampling theorem, Natural and Flat Top Sampling, PAM, Pulse Time
Modulation, Pulse Transmission over Band Limited Channel, Effect of Gaussian Type Noise
on Digital Transmission, Crosstalk, Eye Diagram Line Codes: Bipolar, Unipolar, RZ, NRZ,
Manchester, AMI
Unit III (06 Hrs)
Pulse Code Modulation: Encoder and Decoder, PCM - TDM, Tl Carrier System,
Quantization Noise, Companding, DPCM, ADPCM, Delta modulation, Slope overload and
Adaptive Delta Modulation, Scrambling, Digital Carrier Systems, Digital Multiplexing
Unit IV (06 Hrs)
Information and Coding: Measure of information, entropy, information rate, Shannon's
theorems on channel capacity, Optimum Codes, Huffman Code, Code Efficiency, Error
Control Coding, Methods of Controlling Errors, Types of Errors, Types of Codes, Linear
Block Codes: Matrix Description of Linear Block Codes, Error detection and correction
capabilities, Hamming Distance, Hamming Bound, Hamming Codes, CRC Block Codes,
Syndrome Calculation, Error Detection and Correction, Handshaking Techniques, FEC, ARQ
- Stop and Wait, Go Back N, Selective Repeat, Channel Throughput and Efficiency
UnitV (06 Hrs)
Digital Communications Technologies: SF, ESF Framing, DS1/T1, B8ZS, DSU, CSU,
HDSL, Digital Hierarchy, Digital Services, ISDN, Frame Relay, SONET, ATM, BISDN,
SMDs, Video on Demand, ADSL
Cellular Telephone Systems: Spread Spectrum Systems, DS/SS, FH/SS, Cellular Telephony,
GPS, Transmission Media, PSTN
Unit VI (06 Hrs) Computer Network: Need and Applications of Network, Network
Architecture, Protocols and Standards, OSI Model, TCP/IP Model, Network topology
(Physical & logical), Types of Networks: Peer to Peer, Client-Server, LAN: Ethernet, Token
Ring, FDDI, MAN: DQDB, SMDS, WAN: Architecture, Transmission Mechanism,
Addressing, ISDN and Broadband ISDN
Transmission Media: Guided Media - Twisted Pair, Coaxial and Fiber-optic cables,
Unguided Media (Wireless): Radio and Micro Waves, Infrared
Switching Techniques: Circuit switching, Packet switching and message switching,
Telephone network, High-Speed Digital Access: DSL, Cable Modems and Sonets
Digital Signal Processing
Unit I (08 Hrs)
Classification of Signals: Analog, Discrete-time and Digital, Basic sequences and sequence
operations. Discrete-time systems, Properties of D. T. Systems and Classification, Linear Time
Invariant Systems, impulse response, linear convolution and its properties, properties of LTI
systems: stability, causality, parallel and cascade connection, Linear constant coefficient different
equations, Eigen functions for LTI systems and frequency response, Periodic Sampling, Sampling
Theorem, Frequency Domain representation of sampling, reconstruction of a band limited Signal,
A to D conversion Process: Sampling, quantization and encoding.
Unit 11 (08 Hrs)
Representation of Sequences by Fourier Transform, Symmetry properties of F. T., F. T. theorems:
Linearity, time shifting, frequency shifting, time reversal, differentiation, Parseval’s theorem,
convolution theorem, windowing theorem, Z-transform, ROC and its properties, Inverse z
transform by inspection, partial fraction, power series expansion and complex inversion, Z
transform properties: Linearity, time shifting, multiplication by exponential sequence,
differentiation, conjugation, time reversal, convolution, initial value theorem, Unilateral Ztransform:
solution of difference equation
Unit III (08 Hrs)
Frequency Response of LTI Systems: Ideal frequency selective filters, magnitude and phase
response, group delay, System Functions for LTI Systems: Stability and causality, inverse
systems, significance of poles/zeros, Frequency Response for Rational System Functions:
Frequency Response of a single zero or pole, Frequency response from pole-zero plot using
simple geometric construction, systems with Linear phase, Generalized Linear phase systems,
Four Types of GLPS
Unit IV (08 Hrs)
Sampling the F.T., Fourier representation of finite-duration sequences: The Discrete Fourier
Transform, Properties of DFT: Linearity, circular shift, duality, symmetry, Circular Convolution,
Linear Convolution using DFT, Effective computation of DFT and FFT, Goerzel Algorithm, DIT
FFT, DIP FFT, Inverse DFT using FFT, Practical considerations in FFT implementation
Unit V (08 Hrs)
Concept of filtering, Ideal filters and approximations, specifications, IIR filter design from
continuous time filters: Characteristics of Butterworth, Cheybyshev and elliptic
approximations, impulse invariant and bilinear transformation techniques, Design examples,
FIR filter design using windows: properties of commonly used windows, incorporation of
Generalized Linear Phase, Design Examples, Design using Kaiser window, Comparison of
IIR and FIR Filters
Unit VI (08 Hrs)
Block diagrams and Signal flow graph representation of LCCDE, Basic structures for IIR
Systems: direct form, cascade form, parallel form, feedback in IIR systems, Transposed Forms,
Basic Structures for FIR Systems: direct form, cascade form, structures for linear phase FIR
Systems, Finite Register Length effect
DSP Processors Architecture and Applications of DSP: Detail Study of DSP chip architecture as
an example of ADSP 21XX series of microprocessor and their desirable features, Instruction set
of ADSP 21XX series processor and some examples
Theory of Computation
Unit I (6 Mrs)
Automata Theory: Introduction to Finite Automata, Structural Representations, Automata
and Complexity, Central Concepts to Automata Theory: Alphabets, Strings, Languages and
Problems, Finite Automata: An Informal Picture of FA, Deterministic Finite Automaton
(DFA): How a DFA processes Strings, Simpler Notations for DFA, Extending the transition
function to strings, the language of DFA, Non-deterministic Finite Automaton (NFA): NFA,
Extended transition function, the language of an NFA, Equivalence of NFA and DFA, FA
with e-transitions: Use of e-transitions, NFA with e, e-closures, Extended transitions and
languages for e-N F A , E lim inating € -transitions-Con version of NFA with e to NFA without
e, Conversion of NFA without e to DFA, Conversion of NFA with 6 to DFA (direct method),
FA with output: Moore and Mealy machines -Definition, models, inter-conversion.
Unit II (6 Hrs)
Regular Expressions (RE) and Languages: Regular Expressions - Operators of RE,
Building RE, Precedence of operators, Algebraic laws for RE, Arden's Theorem, FA and RE:
DFA to RE, RE to DFA (RE to s-NFA & e-NFA to DFA and RE to DFA-direct method), FA
limitations, Properties of Regular Languages: pumping lemma for regular languages, closure
and decision properties of regular languages, Equivalence and minimization of automata,
Application of RE: Regular expressions in Unix, GREP utilities of Unix, Lexical analysis and
finding patterns in text.
Unit III (6 Hrs)
Context Free Grammars (CFG) and Languages: Context Free Grammar- Definition,
derivations, languages of a grammar, sentential form, Parse Tree- inference, derivation and
parse tree, from inference to tree, Ambiguity in grammars and languages: removal of
ambiguity, inherent ambiguity, Properties of CFL- Normal forms- Chomsky Normal Form
and Greibach Normal Form, Eliminating unit productions, useless production, useless
symbols, and e-productions, Regular Grammar - definition, left linear and right linear
Regular Grammar, Regular Grammar and Finite Automata, FA to RG and RG to FA, Interconversion
between left linear and right linear regular grammar.
Unit IV (6 Hrs)
Push Down Automata (PDA): Definition, The Language of PDA, Equivalence of PDA's
and CFG- CFG to PDA, PDA to CFG, Deterministic Push Down Automata (DPDA)-
Regular language and DPDA, DPDA and CFL, DPDA and ambiguous grammar, Nondeterministic
Push Down Automata (NPDA), The pumping lemma for CFL, Closure
properties of CFL, Decision properties of CFL, Chomsky Hierarchy, Application of CFG:
Parser, Markup languages, XML and Document Type Definitions.
Unit V (6 Hrs) Turing Machine: Problems that computers cannot solve, The Turing
Machine(TM)-Notation, the language of TM, TM and Halting, Programming techniques to TM,
Extensions to basic TM, TM and Computers. Introduction to Post Machines, Comparison
between FA, PDA, Post Machine and TM
Unit VI (6 Hrs)
Introduction to Computational Complexity: Un-decidability: A Language that is not
recursively enumerable, An un-decidable problem that is RE, Post Correspondence Problem,
Intractable Problems* The classes P and NP, Problems solvable in polynomial time, Nondeterministic
Polynomial time, Polynomial time reduction and NP-complete problems.
Microprocessors and Microcontrollers
Unit I: Introduction to Pentium Microprocessors
Historical evolution of 80286, 386, and 486 processors, Pentium features and architecture, pin description, functional description, Pentium real mode, Pentium RISC features, Pentium super-scalar architecture pipelining, instruction paring rules, branch prediction, instruction and data caches, the floating-point unit
Unit II: Cycles and memory organisation
Initialisation and configuration, bus operations, reset, non-pipelined and pipelined read and write, memory organisation and I/O organisation, data transfer mechanism, 8-bit, 16-bit, 32-bit data-but interface
Pentium programming: programmers' model, register set, addressing modes, instruction set, data types, data transfer instructions, string instructions, arithmetic instructions, logical instructions, bit manipulation instructions, program transfer instructions, processor control instructions
Unit III: Protected Mode
Introduction, segmentation/support registers, related instruction descriptions, memory management through segmentation, logical to linear address translation, protection by segmentation, privilege level protection, related instructions, inter-privilege level transfer of control, paging support registers, descriptors, linear to physical address translation, TLB, page level protection, virtual memory
Unit IV: Multitasking, Interrupts, Exceptions, and I/O
Multitasking - support registers, related descriptors, task switching, I/O permission bitmap
Virtual Mode - features, address generation, privilege level, instruction and registers available, entering and leaving V86 mode
Interrupt structure - real, protected, and virtual 8086 modes, I/O handling in the Pentium, comparison of all three modes
Unit V: 8051 microcontrollers
Micro-controller MCS-51 family architecture, on-chip data, memory and program memory organisation - register set, register bank, SFRs, external data memory and program memory, interrupt structure, timers and their programming, serial port and programming, other features, design of minimum system using 8051 microcontroller for various applications
Unit VI: PIC microcontroller
Overview and features of PIC 16-C, PIC 16F8XX, pin diagram, capture mode, compare mode, PWM mode, block diagram, programmers' model of PIC, reset and clocking.
Memory organisation - program memory, data memory, flash, EEPROM, PIC 16F8XX addressing modes, instruction set, programming, I/O ports, interrupts, timers, ADC
Comment