|UGC NET SYLLABUS (PAPER-II)||LEARN||PRACTICE||EXTERNAL RESOURCES|
|Section 1: Discrete StructuresSet Theory :Sets, Relations, Functions.|
Pigeonhole Principle, Inclusion-Exclusion Principle,
Equivalence and Partial OrderingsElementary Counting Techniques, Probability.
Measure(s) for information and Mutual informationGroup Theory :Finite fields and Error correcting / detecting codesGraph Theory :Definition, walks, paths, trails,
connected graphs, regular and bipartite graphs,
cycles and circuitsTree and rooted tree. Spanning treesEccentricity of a vertex radius and
diameter of a graph. Central Graphs.
Centre(s) of a treeHamiltonian and Eulerian graphs,
Planar graphsComptutability :Models of computation-Finite Automata,
Pushdown AutomataNon – determinism and NFA, DPDA and PDAs and
Languages accepted by these structuresGrammars, Languages, Non – computability and
Examples of non – computable problems.
|Set Theory :Introduction of Set theorySet Operations (Set theory)Power Set and its PropertiesIntroduction and types of RelationsRepresentations of Matrices and Graphs in RelationsClosure of Relations and Equivalence RelationsClasses (Injective, surjective, Bijective) of FunctionsTotal number of possible functionsNumber of possible Equivalence RelationsInclusion-Exclusion and its various ApplicationsAlgebraic StructurePartial OrdersCombinatorics BasicsThe Pigeonhole PrinciplePnC and Binomial CoefficientsGeneralized PnC Set 1Generalized PnC Set 2Random VariablesMean, Variance and Standard DeviationConditional ProbabilityBayes’s TheoremProbability Distributions Set 1 (Uniform Distribution)Probability Distributions Set 2 (Exponential Distribution)Probability Distributions Set 3 (Normal Distribution)Probability Distributions Set 4 (Binomial Distribution)Probability Distributions Set 5 (Poisson Distribution)Group Theory :Hamming CodeGraph Theory :Graph Theory Basics – Set 1Graph Theory Basics – Set 2Number of nodes and height of binary treeGraph Isomorphisms and ConnectivityPlanar Graphs and Graph ColoringEuler and Hamiltonian PathsIndependent Sets, Covering and MatchingMatching (graph theory)Comptutability :Introduction of Theory of ComputationFinite Automata IntroductionChomsky HierarchyRegular Expressions, Regular Grammar and Regular LanguagesPumping LemmaDesigning Finite Automata from Regular ExpressionNFA with epsilon move to DFA ConversionConversion from NFA to DFAMinimization of DFARegular expression from finite automataUnion & Intersection of Regular languages with CFLMealy and Moore MachinesDFA of a string with at least two 0’s and at least two 1’sStar Height of Regular Expression/LanguagePushdown AutomataPushdown Automata Acceptance by Final StateConstruct Pushdown Automata for given languagesConstruct Pushdown Automata for all length palindromeClosure Properties of Context Free LanguagesAmbiguity in Context free Grammar and Context free LanguagesSimplifying Context Free GrammarsConverting Context Free Grammar to Chomsky Normal FormConverting Context Free Grammar to Greibach Normal FormRelationship between grammar and language||Set Theory :Set TheoryCombinatoricsCombinatorics | Set 1Combinatorics | Set 2ProbabilityGroup Theory :Graph Theory :Graph TheoryComptutability :Regular languages and finite automataPractice problems on finite automataPractice problems on finite automata | Set 2Context free languages and Push-down automataRecursively enumerable sets and Turing machinesAutomata Theory | Set 1Automata Theory | Set 2Automata Theory | Set 3Automata Theory | Set 4Automata Theory | Set 5Automata Theory | Set 6||Discrete Structures :Video – NPTEL Discrete Mathematics LecturesMIT – Lecture NotesBook – ProbabilityNotes – ProbabilityVideo – NPTEL TOC LecturesVideo – TOC Lectures by Ravindrababu RavulaNotes – NFA and DFANotes – Non Regular languageNotes – PDA|
|Section 2: Data and File StructuresData Structures :Data, Information,|
Definition of data structure.
Arrays, stacks, queues, linked lists,
trees, graphs, priority queues and heapsFile Structures :Fields, records and files.
Sequential, direct, index-sequential
and relative files.
Hashing, inverted lists and multi – lists.
B trees and B+ trees
|Data Structures :ArrayStackQueueLinked ListBinary TreeBinary Search TreeHeap TreeGraph Data StructureFile Structures :Indexing in Databases | Set 1File Organization – Set 1File Organization – Set 2 (Hashing in DBMS)File Organization – Set 3B-Tree | Set 1 (Introduction)B-Tree | Set 2 (Insert)B-Tree | Set 3 (Delete)Database File Indexing – B+ Tree (Introduction)||Data Structures :ArrayStackQueueLinked ListHeapBinary TreesBinary Search TreesBalanced Binary Search TreesTree TraversalsGraphGraph TraversalsFile Structures :File structures (sequential files, indexing, B and B+ trees)Practice questions on B and B+ Trees||Data Structures :Video – NPTEL lecturesVideo – GeeksforGeeks VideosMIT – Introduction to AlgorithmsBook – CLRS Solutions ManualVisual – Data Structures and AlgorithmsFile Structures :Notes – IndexingVisual – B TreeNotes – B+ TreeVisual – B+ Tree|
|Section 3: Programming in C and C++Programming in C :Elements of C – Tokens, identifiers,|
data types in CControl structures in C.
Sequence, selection and iteration(s)Structured data types in C-arrays,
struct, union, string, and pointersO – O Programming Concepts :Class, object, instantiationInheritance, polymorphism and overloadingC++ Programming :Elements of C++ – Tokens, identifiersVariables and constants, Datatypes,
Operators, Control statementsFunctions parameter passing.
Class and objects.
Constructors and destructorsOverloading, Inheritance, Templates,
|Section 4: Operating Systems (with Case Study of Unix)Main functions of operating systems|
and multitaskingMemory Management: Virtual memory,
paging, fragmentationConcurrent Processing: Mutual exclusion.
Critical regions, lock and unlockScheduling: CPU scheduling,
I / O scheduling, Resource scheduling.
Deadlock and scheduling algorithms.
Banker’s algorithm for deadlock handlingUNIX:The Unix System: File system,
process management, bourne shell,
shell variables, command line programmingFilters and Commands: Pr, head,
tail, cut, paste, sort, uniq, tr, join, etc.,
grep, egrep, fgrep, etc., sed, awk, etc.System Calls (like): Creat, open,
close, read, write, iseek, link, unlink,
stat, fstat, umask, chmod, exec, fork,
|Introduction :What happens when we turn on computer?Introduction of Operating System – Set 1Types of Operating SystemsDual Mode operations in OSDifference between 32-bit and 64-bit operating systemsReal time systemsProcess Management | IntroductionStates of a processProcess Table and Process Control Block (PCB)Process SchedulerDifference between dispatcher and schedulerIntroduction of System CallThreadThreads and its typesMulti threading modelsBenefits of MultithreadingProcess-based and Thread-based MultitaskingUser Level thread Vs Kernel Level threadMicrokernelMonolithic Kernel and key differences from MicrokernelDifference between multitasking, multithreading and multiprocessingCPU Scheduling :Program for FCFS Scheduling | Set 1Program for FCFS Scheduling | Set 2Convoy Effect in Operating SystemsProgram for Preemptive Priority CPU SchedulingProgram for Round Robin scheduling | Set 1Shortest Job First (or SJF) scheduling | Set 1 (Non- preemptive)Shortest Job First (SJF) scheduling | Set 2 (Preemptive)Shortest Job First scheduling with predicted burst timeHighest Response Ratio Next (HRRN) SchedulingProgram for Priority Scheduling | Set 1Priority Scheduling with different arrival time – Set 2Multilevel Queue SchedulingMultilevel Feedback Queue SchedulingMultiple-Processor SchedulingMeasure the time spent in context switch?Starvation and Aging in Operating SystemsConcurrent Processing :Process Synchronization | IntroductionCritical SectionInter Process CommunicationSemaphores in operating systemMutex vs SemaphoreLock variable synchronization mechanismDeadlock :Process Management | Deadlock IntroductionDeadlock Prevention And AvoidanceDeadlock Detection And RecoveryResource Allocation Graph (RAG)Banker’s AlgorithmBanker’s Algorithm | Set 1 (Safety Algorithm)Banker’s Algorithm : Print all the safe stateDeadlock detection algorithmMemory Management :Memory management – mapping virtual address to physical addressesMemory Management | Partition Allocation MethodPagingPage Table EntriesInverted Page TableSegmentationBuddy System – Memory allocation techniqueAllocating kernel memory (buddy system and slab system)Virtual MemorySecondary memory – Hard disk drivePage Fault HandlingPage Replacement AlgorithmsTechniques to handle ThrashingOverlays in Memory ManagementSwap SpaceUnix :Unix||Introduction :Process ManagementCPU Scheduling :CPU SchedulingConcurrent Processing :Concurrency and synchronizationDeadlock :DeadlockMemory Management :Memory ManagementVirtual MemoryUnix :Unix||Operating Systems (with Case Study of Unix) :Video – NPTEL LecturesVideo – Lectures by Ravindrababu RavulaNotes – VirginiaTech Univ. Web resourceNotes – Galvin Lecture SlidesBook – William Stallings Practice Problems and SolutionsNotes – Virtual Memory and CacheNotes – Segmentation and PagingNotes – Some Interesting problems on Virtual memory|
|Section 5: Computer NetworksNetwork fundamentals :Local Area Networks (LAN),|
Metropolitan Area Networks (MAN),Wide Area Networks (WAN),
Wireless Networks, Inter NetworksReference Models :The OSI model, TCP / IP modelData Communication :Channel capacity.
Transmission media-twisted pair,
coaxial cables, fibre – optic cables,wireless transmission-radio,
microwave, infrared and millimeter waves.
Lightwave transmission.Thelephones – local loop,
trunks, multiplexing, switching,narrowband ISDN, broadband ISDN,
ATM, High speed LANS. Cellular Radio.Communication satellites-geosynchronous
and low-orbitInternetworking :Switch / Hub, Bridge, Router, Gateways,Concatenated virtual circuits, Tunnelling,
Fragmentation, FirewallsRouting :Virtual circuits and datagrams.Routing algorithms. Congestion controlNetwork Security :Cryptography-public key, secret key.Domain Name System (DNS) – Electronic Mail
and Worldwide Web (WWW).The DNS, Resource Records, Name servers.E-mail-architecture and Serves
|Network Fundamentals :Basics of Computer NetworkingNetwork TopologiesTypes of area networks – LAN, MAN and WANMANET: Mobile Ad hoc NetworkReference Models :Layers of OSI ModelTCP/IP ModelUser Datagram Protocol (UDP)Data Communication :Types of Transmission MediaTransmission Modes in Computer Networks (Simplex, Half-Duplex and Full-Duplex)Redundant link problemsDigital Subscriber Line (DSL)What is Scrambling?Difference between Unipolar, Polar and Bipolar Line Coding SchemesAnalog to digital conversionDigital to Analog ConversionAnalog to Analog Conversion (Modulation)Difference between Broadband and Baseband TransmissionInternetworking :InternetworkingNetwork Devices (Hub, Repeater, Bridge, Switch, Router, Gateways and Brouter)Introduction to FirewallRouting :Classification of Routing Algorithms | Set-1Types of routing | Set-2Classes of routing protocols | Set-3Distance vector routing v/s Link state routingFixed and Flooding Routing algorithmsRouting v/s Routed ProtocolsUnicast Routing – Link State RoutingRouting Protocols Set 1 (Distance Vector Routing)Route Poisoning and Count to infinity problemOnion RoutingRouter on a stickCircuit SwitchingPacket Switching and DelaysDifferences between Virtual Circuits & Datagram NetworksCircuit Switching VS Packet SwitchingNetwork Security :Protocols in Application LayerDNS (Domain Name Server)Address Resolution in DNSDNS Spoofing or DNS Cache poisoningWhy does DNS use UDP and not TCP?Deniel of Service and PreventionDigital Signatures and CertificatesLZW (Lempel–Ziv–Welch) Compression techniqueRC4 Encryption AlgorithmRSA Algorithm in CryptographyRSA Algorithm using Multiple Precision Arithmetic LibraryWeak RSA decryption with Chinese-remainder theoremDiffie-Hellman AlgorithmDNA CryptographyUnicodeMessage Authentication CodesHow message authentication code works?Hash Functions in System Security||Network Fundamentals :Computer NetworksReference Models :Transport Layer and TCPData Communication :Data Link LayerInternetworking :Routing :Network LayerNetwork Security :Application LayerNetwork Security||Computer Networks :Video – NPTEL LecturesVideo – Lectures by Ravindrababu RavulaNotes – Lecture Notes IIT KanpurNotes – Web Resources on Computer Networks by TanenbaumVisual – Sliding Window Animation|
|Section 6: Relational Database Design and SQLER Diagrams :E-R diagrams and|
their transformation to relational designNormalization :Normalization – 1NF, 2NF, 3NF, BCNF and 4NFLimitations of 4NF and BCNFSQL :Data Definition Language (DDL),
Data Manipulation Language (DML),
Data Control Language (DCL) commandsDatabase objects like-Views,
indexes, sequences, synonyms, data dictionary
|ER Diagrams :DBMS – Introduction | Set 1DBMS – Introduction | Set 2 (3-Tier Architecture)DBMS Architecture 2-Level, 3-LevelNeed for DBMSAdvantages of DBMS over File systemData Abstraction and Data IndependenceER ModelRecursive RelationshipsMinimization of ER DiagramEnhanced ER ModelMapping from ER Model to Relational ModelNormalization :Database Normalization | IntroductionDatabase Normalization | Normal FormsFunctional Dependency and Attribute ClosureFinding Attribute Closure and Candidate Keys using Functional DependenciesNumber of possible SuperkeysLossless DecompositionDependency Preserving DecompositionLossless Join and Dependency Preserving DecompositionHow to find the highest normal form of a relationEquivalence of Functional DependenciesArmstrong’s Axioms in Functional DependencyCanonical CoverDenormalization in DatabasesSQL :Structured Query Language (SQL)SQL | DatatypesSQL | DDL, DML, TCL and DCLSQL | TRANSACTIONSSQL | ViewsDifference between Simple and Complex View in SQLSQL | CommentsSQL | ConstraintsSQL | Creating RolesSQL indexesSQL | SEQUENCESSQL Tutorial||ER Diagrams :ER DiagramsNormalization :Normal FormsSQL :SQL||Relational Database Design and SQL :Video – NPTEL LecturesNotes – Lecture Slides Silberschatz, Korth and SudarshanNotes – Lecture Slides Raghu Ramakrishnan and Johannes GehrkeNotes – Stanford DBMS course Lecture SlidesNotes – Jeff Ullman’s Lecture SlidesNotes – Canonical Cover|
|Section 7: Computer ArithmeticPrepositional and Predicate Logic :Propositional (Boolean) Logic,|
Predicate LogicWell – formed – formulae (WFF),
Satisfiability and TautologyLogic Families :TTL, ECL and C – MOS gatesBoolean algebra
and Minimization of Boolean functionsDesign of combinational
and sequential circuitsFlip-flops – types,
race condition and comparisonRepresentation of Integers :Octal, Hex, Decimal, and Binary2’s complement
and 1’s complement arithmeticFloating point representation
|Prepositional and Predicate Logic :Representation of Boolean FunctionsProperties of Boolean algebraFunctional CompletenessIntroduction to Propositional Logic | Set 1Introduction to Propositional Logic | Set 2Propositional EquivalencesPredicates and Quantifiers | Set 1Predicates and Quantifiers | Set 2Rules of InferenceConsensus theoremLogic Families :Logic GatesProperties of Boolean algebraMinimization of Boolean FunctionsRepresentation of Boolean FunctionsCanonical and Standard FormFunctional CompletenessK-Map (Karnaugh Map)Implicants in K-MapVariable entrant map (VEM)Half AdderFull AdderHalf SubtractorFull SubtractorHalf Adder and Half Subtractor using NAND NOR gatesEncoders and DecodersEncoderBinary DecoderCombinational circuits using DecoderMultiplexersCarry Look-Ahead AdderParallel Adder & Parallel SubtractorBCD AdderMagnitude ComparatorBCD to 7 Segment DecoderProgrammable Logic ArrayProgramming Array LogicRead-Only Memory (ROM)Introduction of Sequential CircuitsFlip-flop types and their ConversionSynchronous Sequential CircuitsCounters in Digital Logicn-bit Johnson CounterRipple CounterDesign counter for given sequenceMaster Slave JK Flip FlopAsynchronous Sequential CircuitsShift RegistersRepresentation of Integers :Number System and base conversionsCode Converters – BCD(8421) to/from Excess-3Code Converters – Binary to/from Gray CodeDecimal to Binary ConversionBinary To Decimal ConversionDecimal to Octal ConversionOctal to Decimal ConversionHexadecimal to Decimal ConversionComputer Arithmetic | Set – 1Computer Arithmetic | Set – 2Floating Point RepresentationDifference between 1’s Complement and 2’s ComplementBooth’s Algorithm||Prepositional and Predicate Logic :Propositional and First Order LogicLogic Families :Digital LogicRepresentation of Integers :Number RepresentationDigital Logic & Number representation||Computer Arithmetic :Video – NPTEL LecturesVideo – Lectures by Ravindrababu RavulaNotes – Number System-SwarthmoreNotes – IEEE Standard 754 Floating Point Numbers|
|Section 8: System Software and CompilersAssembly Language Fundamentals :Assembly language fundamentals|
(8085 based assembly language programming)Assemblers-2-pass and single-pass.
Macros and macroprocessorsLoader and Linker :Loading, linking, relocation,
program relocatability. Linkage editingText editors. Programming Environments.
Debuggers and program generatorsCompiler and Basics :Compilation and Interpretation.
Bootstrap compilersPhases of compilation process.
Lex package on Unix systemParsing :Context free grammars.
Parsing and parse trees.
Representation of parse
(derivation) trees as rightmost
and leftmost derivationsBottom up parsers-shift-reduce,
operator precedence, and LR.
YACC package on Unix systemTopdown parsers-left recursion
and its removal. Recursive descent parser.
Predictive parserCode Generation and Optimization :Intermediate codes-Quadruples, Triples,
Intermediate code generation,
Code generationCode optimization
|Assembly Language Fundamentals :Pin diagram of 8085 microprocessorRegisters of 8085 microprocessorFlag register in 8085 microprocessorAddressing modes in 8085 microprocessorArithmetic instructions in 8085 microprocessorLogical instructions in 8085 microprocessorData transfer instructions in 8085 microprocessorBranching instructions in 8085 microprocessorReset Accumulator (8085 & 8086 microprocessor)Difference between CALL and JUMP instructionsLoader and Linker :Compiler and Basics :Compiler vs InterpreterIntroduction of Compiler designPhases of a CompilerSymbol Table in CompilerError Handling in Compiler DesignError detection and Recovery in CompilerLexical AnalysisC program to detect tokens in a C programFlex (Fast Lexical Analyzer Generator)Parsing :Classification of Context Free GrammarsAmbiguous GrammarWhy FIRST and FOLLOW?FIRST Set in Syntax AnalysisFOLLOW Set in Syntax AnalysisFirst and Follow sets of given grammarIntroduction to Syntax AnalysisParsing | Set 1Parsing | Set 2Parsing | Set 3Shift Reduce Parser in CompilerClassification of top down parsersOperator grammar and precedence parserSyntax Directed TranslationCode Generation and Optimization :Runtime EnvironmentsIntermediate Code GenerationThree address code in CompilerCode OptimizationIntroduction of Object CodeData flow analysis in Compiler||Assembly Language Fundamentals :MicroprocessorLoader and Linker :MCQ on Memory allocation and compilation processCompiler and Basics :Lexical analysisParsing :Parsing and Syntax directed translationCompiler Theory | Set 1Compiler Theory | Set 2Code Generation and Optimization :Code Generation and Optimization||System Software and Compilers :Video – NPTEL LecturesVideo – Lectures by Ravindrababu RavulaNotes – Bivas Mitra IITgpNotes – LR ParsingNotes – Syntax Directed TranslationNotes – Intermediate Code Generation|
|Section 9: Software EngineeringSystem Development Life Cycle (SDLC) :Steps, Water fall model,|
Prototypes, Spiral modelSoftware Metrics :Software Project ManagementSoftware Design :System design, detailed design,
function oriented design, object oriented design,
user interface designDesign level metricsCoding and Testing :Testing level metrics.
Software quality and reliabilityClean room approach,
software re engineering
|System Development Life Cycle (SDLC) :Classical Waterfall ModelIterative Waterfall ModelIncremental process modelPrototyping ModelCOCOMO ModelSpiral ModelRapid application development model (RAD)RAD Model vs Traditional SDLCSoftware Metrics :Classification of Software RequirementsProject size estimation techniquesRequirements Engineering ProcessSoftware Design :Classification of SoftwareCoding and Testing :Software Testing | BasicsBlack box testingRequirements ElicitationChallenges in eliciting requirementsProject Management ProcessCapability maturity model (CMM)System configuration managementDebugging||System Development Life Cycle (SDLC) :Software EngineeringSoftware Metrics :Software EngineeringSoftware Design :Software EngineeringCoding and Testing :Software Engineering||Software Engineering :|
|Section 10: Current Trends and TechnologyParallel Computing :Parallel virtual machine (pvm)|
and message passing interface (MPI)
libraries and callsAdvanced architectures.
Today’s fastest computersMobile Computing :Mobile connectivity – Cells, Framework,
wireless delivery technology
and switching methods,
mobile information access devices,
mobile data internetworking standards,
cellular data communication protocols,
mobile computing applicationsMobile databases – protocols, scope,
tools and technology. M-businessE – Technologies :Electronic Commerce – Framework,
Media Convergence of Applications,
Organisation ApplicationsElectronic Payment Systems – Digital Token,
Smart Cards, Credit Cards,
Risks in Electronic Payment System,
Designing Electronic Payment SystemsElectronic Data Interchange (EDI) – Concepts,
Applications, (Legal, Security and Privacy) issues,
EDI and Electronic Commerce,
Standardization and EDI,
EDI Software Implementation,
EDI Envelope for Message Transport,
Internet – Based EDIDigital Libraries and Data Warehousing – Concepts,
Types of Digital documents,
Issues behind document Infrastructure,
Corporate Data WarehousesSoftware Agents – Characteristics
and Properties of Agents,
Technology behind Software Agents
(Applets, Browsers and Software Agents)Broadband Telecommunications – Concepts,
Frame Relay, Cell Relay,
Switched Multimegabit Data Service,
Asynchronous Transfer Mode.
Main concepts in Geographical Information System (GIS),
E – cash, E – Business, ERP packagesData Warehousing – Data Warehouse environment,
architecture of a data warehouse methodology,
analysis, design, construction and administrationData Mining – Extracting models
and patterns from large databases,
data mining techniques, classification,
regression, clustering, summarization,
dependency modelling, link analysis,
mining scientific and business dataWindows Programming :Introduction to Windows programming – Win32,
Microsoft Foundation Classes (MFC),
Documents and views,
Resources, Message handling in windowsSimple Applications (in windows) – Scrolling,
splitting views, docking toolbars,
status bars, common dialogsAdvanced Windows Programming – Multiple
Document Interface (MDI), Multithreading.
Object linking and Embedding (OLE).
Active X controls. Active Template Library (ATL).
|Parallel Computing :Mobile Computing :E – Technologies :Windows Programming :||Parallel Computing :Mobile Computing :E – Technologies :Windows Programming :||Current Trends and Technology :|