Subject: COMPUTER SCIENCE AND APPLICATIONS (Code No: 87)
Unit - 1: Discrete Structures and
Optimization
Mathematical Logic: Propositional and Predicate Logic, Propositional Equivalences,
Normal Forms, Predicates and Quantifiers, Nested Quantifiers, Rules of
Inference.
Sets and Relations: Set Operations, Representation and Properties of Relations, Equivalence
Relations, Partially Ordering.
Counting, Mathematical Induction and Discrete Probability: Basics of
Counting, Pigeonhole Principle, Permutations and Combinations, Inclusion-
Exclusion Principle, Mathematical Induction, Probability, Bayes’ Theorem.
Group Theory: Groups, Subgroups, Semi Groups, Product and Quotients of Algebraic
Structures, Isomorphism, Homomorphism, Automorphism, Rings, Integral Domains,
Fields, Applications of Group Theory.
Graph Theory: Simple Graph, Multigraph, Weighted Graph, Paths and Circuits,
Shortest Paths in Weighted Graphs, Eulerian Paths and Circuits, Hamiltonian
Paths and Circuits, Planner graph, Graph Coloring, Bipartite Graphs, Trees and
Rooted Trees, Prefix Codes, Tree Traversals, Spanning Trees and Cut-Sets.
Boolean Algebra: Boolean Functions and its Representation, Simplifications of
Boolean Functions.
Optimization: Linear Programming - Mathematical Model, Graphical Solution,
Simplex and Dual Simplex Method, Sensitive Analysis; Integer Programming,
Transportation and Assignment Models, PERT-CPM: Diagram Representation,
Critical Path Calculations, Resource Levelling, Cost Consideration in Project
Scheduling.
Unit - 2 : Computer System
Architecture
Digital Logic Circuits and Components: Digital
Computers, Logic Gates, Boolean Algebra, Map Simplifications, Combinational
Circuits, Flip-Flops, Sequential Circuits, Integrated Circuits, Decoders,
Multiplexers, Registers and Counters, Memory Unit.
Data Representation: Data
Types, Number Systems and Conversion, Complements, Fixed Point Representation,
Floating Point Representation, Error Detection Codes, Computer Arithmetic -
Addition, Subtraction, Multiplication and Division Algorithms.
Register Transfer and Microoperations: Register
Transfer Language, Bus and Memory Transfers, Arithmetic, Logic and Shift
Microoperations.
Basic Computer Organization and Design: Stored
Program Organization and Instruction Codes, Computer Registers, Computer
Instructions, Timing and Control, Instruction Cycle, Memory-Reference
Instructions, Input-Output, Interrupt.
Programming the Basic Computer: Machine
Language, Assembly Language, Assembler, Program Loops, Subroutines,
Input-Output Programming.
Microprogrammed Control: Control
Memory, Address Sequencing, Design of Control Unit.
Central Processing Unit: General
Register Organization, Stack Organization, Instruction Formats, Addressing
Modes, RISC Computer, CISC Computer.
Pipeline and Vector Processing: Parallel
Processing, Pipelining, Arithmetic Pipeline, Instruction Pipeline, Vector
Processing Array Processors.
Input-Output Organization: Peripheral
Devices, Input-Output Interface, Asynchronous Data Transfer, Modes of Transfer,
Priority Interrupt, DMA, Serial Communication.
Memory Hierarchy: Main
Memory, Auxillary Memory, Associative Memory, Cache Memory, Virtual Memory,
Memory Management Hardware.
Multiprocessors: Characteristics
of Multiprocessors, Interconnection Structures, Interprocessor Arbitration,
Interprocessor Communication and Synchronization, Cache Coherence, Multicore
Processors.
Unit - 3 :
Programming Languages and Computer Graphics
Language Design and Translation Issues: Programming
Language Concepts, Paradigms and Models, Programming Environments, Virtual
Computers and Binding Times, Programming Language Syntax, Stages in
Translation, Formal Transition Models.
Elementary Data Types: Properties
of Types and Objects; Scalar and Composite Data Types.
Programming in C: Tokens,
Identifiers, Data Types, Sequence Control, Subprogram Control, Arrays,
Structures, Union, String, Pointers, Functions, File Handling, Command Line
Argumaents, Preprocessors.
Object Oriented Programming: Class,
Object, Instantiation, Inheritance, Encapsulation, Abstract Class,
Polymorphism.
Programming in C++: Tokens,
Identifiers, Variables and Constants; Data types, Operators, Control
statements, Functions Parameter Passing, Virtual Functions, Class and Objects;
Constructors and Destructors; Overloading, Inheritance, Templates, Exception
and Event Handling; Streams and Files; Multifile Programs.
Web Programming: HTML,
DHTML, XML, Scripting, Java, Servlets, Applets.
Computer Graphics: Video-Display
Devices, Raster-Scan and Random-Scan Systems; Graphics Monitors, Input Devices,
Points and Lines; Line Drawing Algorithms, Mid-Point Circle and Ellipse
Algorithms; Scan Line Polygon Fill Algorithm, Boundary-Fill and Flood-Fill.
2-D Geometrical Transforms and Viewing: Translation,
Scaling, Rotation, Reflection and Shear Transformations; Matrix Representations
and Homogeneous Coordinates; Composite Transforms, Transformations Between
Coordinate Systems, Viewing Pipeline, Viewing Coordinate Reference Frame,
Window to View-Port Coordinate Transformation, Viewing Functions, Line and
Polygon Clipping Algorithms.
3-D Object Representation, Geometric
Transformations and Viewing: Polygon Surfaces, Quadric Surfaces, Spline
Representation, Bezier and B-Spline Curves; Bezier and B-Spline Surfaces;
Illumination Models, Polygon Rendering Methods, Viewing Pipeline and
Coordinates; General Projection Transforms and Cipping.
Unit – 4 :
Database Management Systems
Database System Concepts and Architecture: Data
Models, Schemas, and Instances; Three-Schema Architecture and Data
Independence; Database Languages and Interfaces; Centralized and Client/Server
Architectures for DBMS.
Data Modeling: Entity-Relationship
Diagram, Relational Model - Constraints, Languages, Design, and Programming,
Relational Database Schemas, Update Operations and Dealing with Constraint Violations;
Relational Algebra and Relational Calculus; Codd Rules.
SQL: Data Definition and Data Types; Constraints,
Queries, Insert, Delete, and Update Statements; Views, Stored Procedures and
Functions; Database Triggers, SQL Injection.
Normalization for Relational Databases: Functional
Dependencies and Normalization; Algorithms for Query Processing and
Optimization; Transaction Processing, Concurrency Control Techniques, Database
Recovery Techniques, Object and Object-Relational Databases; Database Security
and Authorization.
Enhanced Data Models: Temporal
Database Concepts, Multimedia Databases, Deductive Databases, XML and Internet
Databases; Mobile Databases, Geographic Information Systems, Genome Data
Management, Distributed Databases and Client-Server Architectures.
Data Warehousing and Data Mining: Data
Modeling for Data Warehouses, Concept Hierarchy, OLAP and OLTP; Association
Rules, Classification, Clustering, Regression, Support Vector Machine,
K-Nearest Neighbour, Hidden Markov Model, Summarization, Dependency Modeling,
Link Analysis, Sequencing Analysis, Social Network Analysis.
Big Data Systems: Big
Data Characteristics, Types of Big Data, Big Data Architecture, Introduction to
Map-Reduce and Hadoop; Distributed File System, HDFS.
NOSQL: NOSQL and Query Optimization; Different NOSQL
Products, Querying and Managing NOSQL; Indexing and Ordering Data Sets; NOSQL
in Cloud.
Unit – 5 : System
Software and Operating System
System Software: Machine,
Assembly and High-Level Languages; Compilers and Interpreters; Loading, Linking
and Relocation; Macros, Debuggers.
Basics of Operating Systems: Operating
System Structure, Operations and Services; System Calls, Operating-System Design
and Implementation; System Boot.
Process Management: Process
Scheduling and Operations; Interprocess Communication, Communication in
Client–Server Systems, Process Synchronization, Critical-Section Problem,
Peterson’s Solution, Semaphores, Synchronization.
Threads: Multicore
Programming, Multithreading Models, Thread Libraries, Implicit Threading,
Threading Issues.
CPU Scheduling: Scheduling
Criteria and Algorithms; Thread Scheduling, Multiple-Processor Scheduling,
Real-Time CPU Scheduling.
Deadlocks: Deadlock
Characterization, Methods for Handling Deadlocks, Deadlock Prevention,
Avoidance and Detection; Recovery from Deadlock.
Memory Management: Contiguous
Memory Allocation, Swapping, Paging, Segmentation, Demand Paging, Page
Replacement, Allocation of Frames, Thrashing, Memory-Mapped Files.
Storage Management: Mass-Storage
Structure, Disk Structure, Scheduling and Management, RAID Structure.
File and Input/Output Systems: Access
Methods, Directory and Disk Structure; File-System Mounting, File Sharing,
File-System Structure and Implementation; Directory Implementation, Allocation
Methods, Free-Space Management, Efficiency and Performance; Recovery, I/O
Hardware, Application I/O Interface, Kernel I/O Subsystem, Transforming I/O
Requests to Hardware Operations.
Security: Protection,
Access Matrix, Access Control, Revocation of Access Rights, Program Threats,
System and Network Threats; Cryptography as a Security Tool, User
Authentication, Implementing Security Defenses.
Virtual Machines: Types
of Virtual Machines and Implementations; Virtualization.
Linux Operating Systems: Design
Principles, Kernel Modules, Process Management, Scheduling, Memory Management,
File Systems, Input and Output; Interprocess Communication, Network Structure.
Windows Operating Systems: Design
Principles, System Components, Terminal Services and Fast User Switching; File
System, Networking.
Distributed Systems: Types
of Network based Operating Systems, Network Structure, Communication Structure
and Protocols; Robustness, Design Issues, Distributed File Systems.
Unit – 6 :
Software Engineering
Software Process Models:
Software Process, Generic Process Model – Framework Activity, Task Set and
Process Patterns; Process Lifecycle, Prescriptive Process Models, Project
Management, Component Based Development, Aspect-Oriented Software Development,
Formal Methods, Agile Process Models – Extreme Programming (XP), Adptive
Software Development, Scrum, Dynamic System Development Model, Feature Driven
Development, Crystal, Web Engineering.
Software Requirements:
Functional and Non-Functional Requirements; Eliciting Requirements, Developing
Use Cases, Requirement Analysis and Modelling; Requirements Review, Software
Requirment and Specification (SRS) Document.
Software Design: Abstraction,
Architecture, Patterns, Separation of Concerns, Modularity, Information Hiding,
Functional Independence, Cohesion and Coupling; Object-Oriented Design, Data
Design, Architectural Design, User Interface Design, Component Level Design.
Software Quality: McCall’s
Quality Factors, ISO 9126 Quality Factors, Quality Control, Quality Assurance,
Risk Management, Risk Mitigation, Monitoring and Management (RMMM); Software
Reliability.
Estimation and Scheduling of Software Projects:
Software Sizing, LOC and FP based Estimations; Estimating Cost and Effort;
Estimation Models, Constructive Cost Model (COCOMO), Project Scheduling and
Staffing; Time-line Charts.
Software Testing:
Verification and Validation; Error, Fault, Bug and Failure; Unit and Integration
Tesing; White-box and Black-box Testing; Basis Path Testing, Control Structure
Testing, Deriving Test Cases, Alpha and Beta Testing; Regression Testing,
Performance Testing, Stress Testing.
Software Configuration Management:
Change Control and Version Control; Software Reuse, Software Re-engineering,
Reverse Engineering.
Unit – 7 : Data
Structures and Algorithms
Data Structures: Arrays
and their Applications; Sparse Matrix, Stacks, Queues, Priority Queues, Linked
Lists, Trees, Forest, Binary Tree, Threaded Binary Tree, Binary Search Tree,
AVL Tree, B Tree, B+ Tree, B* Tree, Data Structure for Sets, Graphs, Sorting
and Searching Algorithms; Hashing.
Performance Analysis of Algorithms and Recurrences:Time
and Space Complexities; Asymptotic Notation, Recurrence Relations.
Design Techniques: Divide
and Conquer; Dynamic Programming, Greedy Algorithms, Backtracking, Branch and
Bound.
Lower Bound Theory: Comparison
Trees, Lower Bounds through Reductions.
Graph Algorithms: Breadth-First
Search, Depth-First Search, Shortest Paths, Maximum Flow, Minimum Spanning
Trees.
Complexity Theory: P
and NP Class Problems; NP-completeness and Reducibility.
Selected Topics: Number
Theoretic Algorithms, Polynomial Arithmetic, Fast Fourier Transform, String
Matching Algorithms.
Advanced Algorithms: Parallel
Algorithms for Sorting, Searching and Merging, Approximation Algorithms,
Randomized Algorithms.
Unit – 8 : Theory
of Computation and Compilers
Theory of Computation: Formal
Language, Non-Computational Problems, Diagonal Argument, Russels’s Paradox.
Regular Language Models: Deterministic
Finite Automaton (DFA), Non-Deterministic Finite Automaton (NDFA), Equivalence
of DFA and NDFA, Regular Languages, Regular Grammars, Regular Expressions,
Properties of Regular Language, Pumping Lemma, Non-Regular Languages, Lexical
Analysis.
Context Free Language: Pushdown
Automaton (PDA), Non-Deterministic Pushdown Automaton (NPDA), Context Free
Grammar, Chomsky Normal Form, Greibach Normal Form, Ambiguity, Parse Tree
Representation of Derivation Trees, Equivalence of PDA’s and Context Free
Grammars; Properties of Context Free Language.
Turing Machines (TM): Standard
Turing Machine and its Variations; Universal Turing Machines, Models of
Computation and Church-Turing Thesis; Recursive and Recursively-Enumerable
Languages; Context-Sensitive Languages, Unrestricted Grammars, Chomsky
Hierarchy of Languages, Construction of TM for Simple Problems.
Unsolvable Problems and Computational Complexity:
Unsolvable Problem, Halting Problem, Post Correspondence
Problem, Unsolvable Problems for Context-Free Languages, Measuring and
Classifying Complexity, Tractable and Intractable Problems.
Syntax Analysis: Associativity,
Precedence, Grammar Transformations, Top Down Parsing, Recursive Descent
Predictive Parsing, LL(1) Parsing, Bottom up Parsing, LR Parser, LALR(1)
Parser.
Semantic Analysis: Attribute
Grammar, Syntax Directed Definitions, Inherited and Synthesized Attributes;
Dependency Graph, Evaluation Order, S-attributed and L-attributed Definitions;
Type-Checking.
Run Time System: Storage
Organization, Activation Tree, Activation Record, Stack Allocation of
Activation Records, Parameter Passing Mechanisms, Symbol Table.
Intermediate Code Generation: Intermediate
Representations, Translation of Declarations, Assignments, Control Flow,
Boolean Expressions and Procedure Calls.
Code Generation and Code Optimization: Control-flow,
Data-flow Analysis, Local Optimization, Global Optimization, Loop Optimization,
Peep-Hole Optimization, Instruction Scheduling.
Unit – 9 : Data
Communication and Computer Networks
Data Communication:
Components of a Data Communication System, Simplex, Half-Duplex and Duplex
Modes of Communication; Analog and Digital Signals; Noiseless and Noisy
Channels; Bandwidth, Throughput and Latency; Digital and Analog Transmission;
Data Encoding and Modulation Techniques; Broadband and Baseband Transmission;
Multiplexing, Transmission Media, Transmission Errors, Error Handling
Mechanisms.
Computer Networks:
Network Topologies, Local Area Networks, Metropolitan Area Networks, Wide Area
Network, Wireless Networks, Internet.
Network Models: Layered
Architecture, OSI Reference Model and its Protocols; TCP/IP Protocol Suite,
Physical, Logical, Port and Specific Addresses; Switching Techniques.
Functions of OSI and TCP/IP Layers:
Framing, Error Detection and Correction; Flow and Error Control; Sliding Window
Protocol, HDLC, Multiple Access – CSMA/CD, CSMA/CA, Reservation, Polling, Token
Passing, FDMA, CDMA, TDMA, Network Devices, Backbone Networks, Virtual LANs.
IPv4 Structure and Address Space; Classful and
Classless Addressing; Datagram, Fragmentation and Checksum; IPv6 Packet Format,
Mapping Logical to Physical Address (ARP), Direct and Indirect Network Layer
Delivery; Routing Algorithms, TCP, UDP and SCTP Protocols; Flow Control, Error
Control and Congestion Control in TCP and SCTP.
World Wide Web (WWW): Uniform
Resource Locator (URL), Domain Name Service (DNS), Resolution - Mapping Names
to Addresses and Addresses to Names; Electronic Mail Architecture, SMTP, POP
and IMAP; TELNET and FTP.
Network Security:
Malwares, Cryptography and Steganography; Secret-Key Algorithms, Public-Key
Algorithms, Digital Signature, Virtual Private Networks, Firewalls.
Mobile Technology:
GSM and CDMA; Services and Architecture of GSM and Mobile Computing; Middleware
and Gateway for Mobile Computing; Mobile IP and Mobile Communication Protocol;
Communication Satellites, Wireless Networks and Topologies; Cellular Topology,
Mobile Adhoc Networks, Wireless Transmission and Wireless LANs; Wireless
Geolocation Systems, GPRS and SMS.
Cloud Computing and IoT: SaaS,
PaaS, IaaS, Public and Private Cloud; Virtualization, Virtual Server, Cloud
Storage, Database Storage, Resource Management, Service Level Agreement, Basics
of IoT.
Unit – 10 :
Artificial Intelligence (AI)
Approaches to AI: Turing
Test and Rational Agent Approaches; State Space Representation of Problems,
Heuristic Search Techniques, Game Playing, Min-Max Search, Alpha Beta Cutoff
Procedures.
Knowledge Representation:
Logic, Semantic Networks, Frames, Rules, Scripts, Conceptual Dependency and Ontologies;
Expert Systems, Handling Uncertainty in Knowledge.
Planning: Components of a
Planning System, Linear and Non Linear Planning; Goal Stack Planning,
Hierarchical Planning, STRIPS, Partial Order Planning.
Natural Language Processing:
Grammar and Language; Parsing Techniques, Semantic Analysis and Prgamatics.
Multi Agent Systems:
Agents and Objects; Agents and Expert Systems; Generic Structure of Multiagent
System, Semantic Web, Agent Communication, Knowledge Sharing using Ontologies,
Agent Development Tools.
Fuzzy Sets: Notion of
Fuzziness, Membership Functions, Fuzzification and Defuzzification; Operations
on Fuzzy Sets, Fuzzy Functions and Linguistic Variables; Fuzzy Relations, Fuzzy
Rules and Fuzzy Inference; Fuzzy Control System and Fuzzy Rule Based Systems.
Genetic Algorithms (GA):
Encoding Strategies, Genetic Operators, Fitness Functions and GA Cycle; Problem
Solving using GA.
Artificial
Neural Networks (ANN): Supervised, Unsupervised and Reinforcement Learning; Single
Perceptron, Multi Layer Perceptron, Self Organizing Maps, Hopfield Network.
){kind=link}
0 Comments