3-2 syllabus plan:

                             JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
                                                                 HYDERABAD
III Year B.Tech. CSE -II Sem T P C
                                                        OPERATING SYSTEMS
UNIT I :
Computer System and Operating System Overview: Overview of computer operating systems operating systems functions protection and security distributed systems special purpose systems operating systems structures and systems calls operating systems generation

UNIT II :
Process Management – Process concepts threads, scheduling-criteria algorithms, their evaluation,
Thread scheduling, case studies UNIX, Linux, Windows

UNIT III :
Concurrency : Process synchronization, the critical- section problem, Peterson’s Solution, synchronization Hardware, semaphores, classic problems of synchronization, monitors, Synchronization examples, atomic transactions. Case studies UNIX, Linux, Windows

UNIT IV :
Memory Management : Swapping, contiguous memory allocation, paging, structure of the page table , segmentation, virtual memory, demand paging, page-Replacement, algorithms, case studies UNIX, Linux, Windows

UNIT V :
Principles of deadlock – system model, deadlock characterization, deadlock prevention, detection and avoidance, recovery form deadlock,
I/O systems, Hardware, application interface, kernel I/O subsystem, Transforming I/O requests Hardware operation, STREAMS, performance.

UNIT VI :
File system Interface- the concept of a file, Access Methods, Directory structure, File system mounting, file sharing, protection.
File System implementation- File system structure, file system implementation, directory implementation, directory implementation, allocation methods, free-space management, efficiency and performance, case studies. UNIX, Linux, Windows

UNIT VII :
Mass-storage structure overview of Mass-storage structure, Disk structure, disk attachment disk scheduling, swap-space management, RAID structure, stable-storage implementation, Tertiary storage structure.

UNIT VIII :
Protection : Protection, Goals of Protection, Principles of Protection, Domain of protection Access Matrix, Implementation of Access Matrix, Access control, Revocation of Access Rights, Capability- Based systems, Language – Based Protection,
Security- The Security problem, program threats, system and network threats cryptography as a security tool, user authentication, implementing security defenses, firewalling to protect systems and networks, computer –security classifications, case studies UNIX, Linux, Windows

TEXT BOOKS :
1. Operating System Concepts- Abraham Silberchatz, Peter B. Galvin, Greg Gagne 7th Edition, John Wiley.
2. Operating systems- A Concept based Approach-D.M.Dhamdhere, 2nd Edition, TMH

REFERENCES :
1. Operating Systems’ – Internal and Design Principles Stallings, Fifth
Edition–2005, Pearson education/PHI
2. Operating System A Design Approach-Crowley, TMH.
3. Modern Operating Systems, Andrew S Tanenbaum 2nd edition
Pearson/PHI.

                                                    COMPILER DESIGN
UNIT – I
Overview of Compilation: Phases of Compilation – Lexical Analysis, Regular Grammar and regular expression for common programming language features, pass and Phases of translation, interpretation, bootstrapping, data structures in compilation – LEX lexical analyzer generator.

UNIT – II
Top down Parsing : Context free grammars, Top down parsing – Backtracking, LL (1), recursive descent parsing, Predictive parsing, Preprocessing steps required for predictive parsing.

UNIT – III
Bottom up parsing : Shift Reduce parsing, LR and LALR parsing, Error recovery in parsing , handling ambiguous grammar, YACC – automatic parser generator.

UNIT – IV
Semantic analysis : Intermediate forms of source Programs – abstract syntax tree, polish notation and three address codes. Attributed grammars, Syntax directed translation, Conversion of popular Programming languages language Constructs into Intermediate code forms, Type checker.

UNIT – V
Symbol Tables : Symbol table format, organization for block structures languages, hashing, tree structures representation of scope information. Block structures and non block structure storage allocation: static, Runtime stack and heap storage allocation, storage allocation for arrays, strings and records.


UNIT – VI
Code optimization : Consideration for Optimization, Scope of Optimization, local optimization, loop optimization, frequency reduction, folding, DAG representation.

UNIT – VII
Data flow analysis : Flow graph, data flow equation, global optimization, redundant sub expression elimination, Induction variable elements, Live variable analysis, Copy propagation.

UNIT – VIII
Object code generation : Object code forms, machine dependent code optimization, register allocation and assignment generic code generation algorithms, DAG for register allocation.

TEXT BOOKS :
1. Principles of compiler design -A.V. Aho . J.D.Ullman; Pearson Education.
2. Modern Compiler Implementation in C- Andrew N. Appel, Cambridge
University Press.

REFERENCES :
1. lex &yacc – John R. Levine, Tony Mason, Doug Brown, O’reilly
2. Modern Compiler Design- Dick Grune, Henry E. Bal, Cariel T. H. Jacobs,
Wiley dreamtech.
3. Engineering a Compiler-Cooper & Linda, Elsevier.
4. Compiler Construction, Louden, Thomson.

                                                          COMPUTER NETWORKS

UNIT – I
Introduction : OSI, TCP/IP and other networks models, Examples of Networks: Novell Networks ,Arpanet, Internet, Network Topologies WAN, LAN, MAN.

UNIT - II
Physical Layer : Transmission media copper, twisted pair wireless, switching and encoding asynchronous communications; Narrow band, broad band ISDN and ATM.

UNIT - III
Data link layer : Design issues, framing, error detection and correction, CRC, Elementary Protocol-stop and wait, Sliding Window, Slip, Data link layer in HDLC, Internet, ATM.

UNIT - IV
Medium Access sub layer : ALOHA, MAC addresses, Carrier sense multiple access. IEEE 802.X Standard Ethernet, wireless LANS. Bridges

UNIT - V
Network Layer : Virtual circuit and Datagram subnets-Routing algorithm shortest path routing, Flooding, Hierarchical routing, Broad cast, Multi cast, distance vector routing.

UNIT – VI
Dynamic routing – Broadcast routing. Rotary for mobility. Congestion, Control Algorithms – General Principles – of Congestion prevension policies. Internet working: The Network layer in the internet and in the ATM Networks.

UNIT –VII
Transport Layer: Transport Services, Connection management, TCP and UDP protocols; ATM AAL Layer Protocol.

UNIT – VIII
Application Layer – Network Security, Domain name system, SNMP, Electronic Mail; the World WEB, Multi Media.

TEXT BOOKS :
1. Computer Networks — Andrew S Tanenbaum, 4th Edition. Pearson
Education/PHI
2. Data Communications and Networking – Behrouz A. Forouzan.Third
Edition TMH.


REFERENCES :
1. An Engineering Approach to Computer Networks-S.Keshav, 2nd Edition,
Pearson Education
2. Understanding communications and Networks, 3rd Edition, W.A. Shay,
Thomson

                                               INFORMATION SECURITY

UNIT - I
Security Attacks (Interruption, Interception, Modification and Fabrication), Security Services (Confidentiality, Authentication, Integrity, Non-repudiation, access Control and Availability) and Mechanisms, A model for Internetwork security, Internet Standards and RFCs, Buffer overflow & format string vulnerabilities, TCP session hijacking, ARP attacks, route table modification, UDP hijacking, and man-in-the-middle attacks.

UNIT - II
Conventional Encryption Principles, Conventional encryption algorithms, cipher block modes of operation, location of encryption devices, key distribution Approaches of Message Authentication, Secure Hash Functions and HMAC.

UNIT - III
Public key cryptography principles, public key cryptography algorithms, digital signatures, digital Certificates, Certificate Authority and key management Kerberos, X.509 Directory Authentication Service.

UNIT - IV
Email privacy: Pretty Good Privacy (PGP) and S/MIME.

UNIT - V
IP Security Overview, IP Security Architecture, Authentication Header, Encapsulating Security Payload, Combining Security Associations and Key Management.

UNIT - VI
Web Security Requirements, Secure Socket Layer (SSL) and Transport Layer Security (TLS), Secure Electronic Transaction (SET).

UNIT - VII
Basic concepts of SNMP, SNMPv1 Community facility and SNMPv3.
Intruders, Viruses and related threats.

UNIT - VIII
Firewall Design principles, Trusted Systems. Intrusion Detection Systems.

TEXT BOOKS :
1. Network Security Essentials (Applications and Standards) by William
Stallings Pearson Education.
2. Hack Proofing your network by Ryan Russell, Dan Kaminsky, Rain Forest
Puppy, Joe Grand, David Ahmad, Hal Flynn Ido Dubrawsky, Steve
W.Manzuik and Ryan Permeh, wiley Dreamtech

REFERENCES :
1. Fundamentals of Network Security by Eric Maiwald (Dreamtech press)
2. Network Security - Private Communication in a Public World by Charlie
Kaufman, Radia Perlman and Mike Speciner, Pearson/PHI.
3. Cryptography and network Security, Third edition, Stallings, PHI/Pearson
4. Principles of Information Security, Whitman, Thomson.
5. Network Security: The complete reference, Robert Bragg, Mark Rhodes,
TMH
6. Introduction to Cryptography, Buchmann, Springer.

                               ARTIFICIAL INTELLIGENCE AND NEURAL NETWORKS

UNIT - I
Introduction : AI problems, foundation  of AI and history of AI intelligent agents: Agents and Environments,the concept of rationality, the nature of environments, structure of agents, problem solving agents, problemformulation.

UNIT - II
Searching : Searching for solutions, uniformed search strategies – Breadth first search, depth first Search. Search with partial information (Heuristic search) Greedy best first search, A* search Game Playing: Adversial search, Games, minimax, algorithm, optimal decisions in multiplayer games, Alpha-Beta pruning, Evaluation functions, cutting of search.

UNIT - III
Knowledge Representation & Reasons logical Agents, Knowledge – Based Agents, the Wumpus world, logic, propositional logic, Resolution patterns in propos ional logic, Resolution, Forward & Backward. Chaining.

UNIT - IV
First order logic. Inference in first order logic, propositional Vs. first order inference, unification & lifts forward chaining, Backward chaining, Resolution.

UNIT - V
Characteristics of Neural Networks, Historical Development of Neural Networks Principles, Artificial Neural Networks: Terminology, Models of Neuron, Topology, Basic Learning Laws, Pattern Recognition Problem, Basic Functional Units, Pattern Recognition Tasks by the Functional Units.

UNIT - VI
Feedforward Neural Networks:
Introduction, Analysis of pattern Association Networks, Analysis of Pattern Classification Networks, Analysis of pattern storage Networks. Analysis of Pattern Mapping Networks.

UNIT - VII
Feedback Neural Networks
Introduction, Analysis of Linear Autoassociative FF Networks, Analysis of Pattern Storage Networks.

UNIT - VIII
Competitive Learning Neural Networks & Complex pattern Recognition
Introduction, Analysis of Pattern Clustering Networks, Analysis of Feature
Mapping Networks, Associative Memory.

TEXT BOOKS :
1. Artificial Intelligence – A Modern Approach. Second Edition, Stuart Russel, Peter Norvig, PHI/ Pearson Education.
2. Artificial Neural Networks B. Yagna Narayana, PHI
REFERENCES :
1. Artificial Intelligence , 2nd Edition, E.Rich and K.Knight (TMH).
2. Artificial Intelligence and Expert Systems – Patterson PHI.
3. Expert Systems: Principles and Programming- Fourth Edn, Giarrantana/ Riley, Thomson.
4. PROLOG Programming for Artificial Intelligence. Ivan Bratka- Third Edition – Pearson Education.
5.Neural Networks Simon Haykin PHI
6. Artificial Intelligence, 3rd Edition, Patrick Henry Winston., Pearson Edition.

                                   OBJECT ORIENTED ANALYSIS AND DESIGN

UNIT - I
Introduction to UML : Importance of modeling, principles of modeling, object oriented modeling, conceptual model of the UML, Architecture, Software Development Life Cycle.

UNIT - II
Basic Structural Modeling : Classes, Relationships, common Mechanisms, and diagrams.
Advanced Structural Modeling : Advanced classes, advanced relationships, Interfaces, Types and Roles, Packages.

UNIT - III
Class & Object Diagrams : Terms, concepts, modeling techniques for Class & Object Diagrams.

UNIT- IV
Basic Behavioral Modeling-I : Interactions, Interaction diagrams.

UNIT - V
Basic Behavioral Modeling-II : Use cases, Use case Diagrams, Activity
Diagrams.

UNIT - VI
Advanced Behavioral Modeling : Events and signals, state machines, processes and Threads, time and space, state chart diagrams.

UNIT-VII
Architectural Modeling : Component, Deployment, Component diagrams and Deployment diagrams.

UNIT - VIII
Case Study : The Unified Library application.

TEXT BOOKS :
1. Grady Booch, James Rumbaugh, Ivar Jacobson : The Unified Modeling
Language User Guide, Pearson Education.
2. Hans-Erik Eriksson, Magnus Penker, Brian Lyons, David Fado: UML 2
Toolkit, WILEY-Dreamtech India Pvt. Ltd.

REFERENCE BOOKS:
1. Meilir Page-Jones: Fundamentals of Object Oriented Design in UML,
Pearson Education.
2. Pascal Roques: Modeling Software Systems Using UML2, WILEY-
Dreamtech India Pvt. Ltd.
3. Atul Kahate: Object Oriented Analysis & Design, The McGraw-Hill
Companies.
4. Mark Priestley: Practical Object-Oriented Design with UML,TATA
McGrawHill
5. Appling UML and Patterns: An introduction to Object – Oriented Analysis
and Design and Unified Process, Craig Larman, Pearson Education.

                           COMPUTER NETRWORKS AND CASE TOOLS LAB

Objective:
To Understand the functionalities of various layers of OSI model
To inculcate object oriented software design
System/ Software Requirement
Intel based desktop PCs LAN CONNECTED with minimum of 166 MHZ or faster processor with atleast 64 MB RAM and 100 MB free disk space
Tools Such as Rational Rose

Part - A
1. Implement the data link layer framing methods such as character, character stuffing and bit stuffing.
2. Implement on a data set of characters the three CRC polynomials – CRC 12, CRC 16 and CRC CCIP .
3. Implement Dijkstra ‘s algorithm to compute the Shortest path thru a graph.
4. Take an example subnet graph with weights indicating delay between nodes. Now obtain Routing table art each node using distance vector routing algorithm
5. Take an example subnet of hosts . Obtain broadcast tree for it.
6. Take a 64 bit playing text and encrypt the same using DES algorithm .
7. Write a program to break the above DES coding
8. Using RSA algorithm Encrypt a text data and Decrypt the same .

Part - B
1. The student should take up the case study of Unified Library application which is mentioned in the theory, and Model it in different views i.e Use case view, logical view, component view, Deployment view, Database design, forward and Reverse Engineering, and Generation of documentation of
the project.
2. Student has to take up another case study of his/her own interest and do the same what ever mentioned in first problem. Some of the ideas regarding case studies are given in reference books which were mentioned in theory syllabus can be referred for some idea.
Note : The analysis, design, coding, documentation, database design of mini project which will be carried out in 4th year should be done in object-oriented approach using UML and by using appropriate software which supports UML, otherwise the mini project will not be evaluated.

                        OPERATING SYSTEMS AND COMPILER DESIGN LAB

Objective :
To provide an understanding of the language translation peculiarities by designing a complete translator for a mini language.
To provide an understanding of the design aspects of operating system

Recommended Systems/Software Requirements:
Intel based desktop PC with minimum of 166 MHZ or faster processor with atleast 64 MB RAM and 100 MB free disk space
C++ complier and JDK kit

Part - A
1. Simulate the following CPU scheduling algorithms
a) Round Robin b) SJF c) FCFS d) Priority
2. Simulate all file allocation strategies
a) Sequentialb) Indexed c) Linked
3. Simulate MVT and MFT
4. Simulate all File Organization Techniques
a) Single level directory b) Two level c) Hierarchical d) DAG
5. Simulate Bankers Algorithm for Dead Lock Avoidance
6. Simulate Bankers Algorithm for Dead Lock Prevention
7. Simulate all page replacement algorithms
a) FIFO b) LRU c) LFU Etc. …
8. Simulate Paging Technique of memory management.

PART - B
Consider the following mini Language, a simple procedural high-level language, only operating on integer
data, with a syntax looking vaguely like a simple C crossed with Pascal. The syntax of the language is
defined by the following BNF grammar:
::=
::= { }
| { }
::= int ;
::= | ,
::= | [ ]
::= | ;
::= | |
| | |
::= =
| [ ] =
::= if then else endif
| if then endif
::= while do enddo
::= print ( )
::= | |
::=
::= < | <= | == | >= | > | !=
::= + | -
::= |
::= * | /
::= | | [ ]
| ( )
::= |
::= |
::= |
::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
::= 0|1|2|3|4|5|6|7|8|9
has the obvious meaning
Comments (zero or more characters enclosed between the standard C/Java-style comment brackets /
*...*/) can be inserted. The language has rudimentary support for 1-dimensional arrays. The declaration
int a[3] declares an array of three elements, referenced as a[0], a[1] and a[2]. Note also that you should
worry about the scoping of names.
A simple program written in this language is:
{ int a[3],t1,t2;
t1=2;
a[0]=1; a[1]=2; a[t1]=3;
t2=-(a[2]+t1*6)/(a[2]-t1);

if t2>5 then
print(t2);
else {
int t3;
t3=99;
t2=-25;
print(-t1+t2*t3); /* this is a comment
on 2 lines */
} endif }

1. Design a Lexical analyzer for the above language. The lexical analyzer should ignore redundant
spaces, tabs and newlines. It should also ignore comments. Although the syntax specification
states that identifiers can be arbitrarily long, you may restrict the length to some reasonable value.
2. Implement the lexical analyzer using JLex, flex or lex or other lexical analyzer generating tools.
3. Design Predictive parser for the given language
4. Design LALR bottom up parser for the above language.
5. Convert the BNF rules into Yacc form and write code to generate abstract syntax tree.
6. Write program to generate machine code from the abstract syntax tree generated by the parser. The following instruction set may be considered as target code.
The following is a simple register-based machine, supporting a total of 17 instructions. It has three distinct internal storage areas. The first is the set of 8 registers, used by the individual instructions as detailed below, the second is an area used for the storage of variables and the third is an area used
for the storage of program. The instructions can be preceded by a label. This consists of an integer in the range 1 to 9999 and the label is followed by a colon to separate it from the rest of the instruction. The numerical label can be used as the argument to a jump instruction, as detailed below.
In the description of the individual instructions below, instruction argument types are specified as follows :
R
specifies a register in the form R0, R1, R2, R3, R4, R5, R6 or R7 (or r0, r1, etc.).
L
specifies a numerical label (in the range 1 to 9999).
V
specifies a “variable location” (a variable number, or a variable location pointed to by a register - see
below).
A
specifies a constant value, a variable location, a register or a variable location pointed to by a register (an indirect address). Constant values are specified as an integer value, optionally preceded by a minus sign, preceded by a # symbol. An indirect address is specified by an @ followed by a register.
So, for example, an A-type argument could have the form 4 (variable number 4), #4 (the constant value 4), r4 (register 4) or @r4 (the contents of register 4 identifies the variable location to be accessed).
The instruction set is defined as follows:
LOAD A,R
loads the integer value specified by A into register R.
STORE R,V
stores the value in register R to variable V.
OUT R
outputs the value in register R.
NEG R
negates the value in register R.
ADD A,R
adds the value specified by A to register R, leaving the result in register R.
SUB A,R
subtracts the value specified by A from register R, leaving the result in register R.
MUL A,R
multiplies the value specified by A by register R, leaving the result in register R.
DIV A,R
divides register R by the value specified by A, leaving the result in register R.
JMP L
causes an unconditional jump to the instruction with the label L.
JEQ R,L
jumps to the instruction with the label L if the value in register R is zero.
JNE R,L
jumps to the instruction with the label L if the value in register R is not zero.
JGE R,L
jumps to the instruction with the label L if the value in register R is greater than or equal to zero.
JGT R,L
jumps to the instruction with the label L if the value in register R is greater than zero.
JLE R,L
jumps to the instruction with the label L if the value in register R is less than or equal to zero.
JLT R,L
jumps to the instruction with the label L if the value in register R is less than zero.
NOP
is an instruction with no effect. It can be tagged by a label.
STOP
stops execution of the machine. All programs should terminate by executing a STOP instruction.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. CSE -I Sem T P C
4+1* 0 4
NETWORK PROGRAMMING

UNIT-I
Introduction to Network Programming: OSI model, Unix standards, TCP and UDP & TCP connection establishment and Format, Buffer sizes and limitation, standard internet services, Protocol usage by common internet application.
UNIT-II
Sockets : Address structures, value – result arguments, Byte ordering and manipulation function and related functions Elementary TCP sockets – Socket, connect, bind, listen, accept, fork and exec function, concurrent servers. Close function and related function.
UNIT-III
TCP client server : Introduction, TCP Echo server functions, Normal startup, terminate and signal handling server process termination, Crashing and Rebooting of server host shutdown of server host.
UNIT-IV
I/O Multiplexing and socket options: I/O Models, select function, Batch input, shutdown function, poll function, TCP Echo server, getsockopt and setsockopt functions. Socket states, Generic socket option IPV6 socket option ICMPV6 socket option IPV6 socket option and TCP socket options.
UNIT-V
Elementary UDP sockets: Introduction UDP Echo server function, lost datagram, summary of UDP example, Lack of flow control with UDP, determining outgoing interface with UDP.
UNIT-VI
Elementary name and Address conversions: DNS, gethost by Name function, Resolver option, Function and IPV6 support, uname function, other networking information.
UNIT-VII
IPC : Introduction, File and record locking, Pipes, FIFOs streams and messages, Name spaces, system IPC, Message queues, Semaphores.

UNIT-VIII
Remote Login: Terminal line disciplines, Pseudo-Terminals, Terminal modes, Control Terminals, rlogin Overview, RPC Transparency Issues.

TEXT BOOKS:
1. UNIX Network Programming, Vol. I, Sockets API, 2nd Edition. - W.Richard Stevens, Pearson
Edn. Asia.
2. UNIX Network Programming, 1st Edition, - W.Richard Stevens. PHI.

REFERENCES:

UNIX Systems Programming using C++ T CHAN, PHI.
UNIX for Programmers and Users, 3rd Edition Graham GLASS, King abls, Pearson Education
Advanced UNIX Programming 2nd Edition M. J. ROCHKIND, Pearson Education
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. CSE -I Sem T P C
4+1* 0 4
WEB TECHNOLOGIES
Objectives:
This course demonstrate an in-depth understanding of the tools and Web technologies necessary for business application design and development. The course covers client side scripting like HTML, JavaScript and server side scripting like servlets, JSPs. And also XML and web servers and database interfacing.

UNIT-I:
HTML Common tags- List, Tables, images, forms, Frames; Cascading Style sheets;

UNIT-II:
Introduction to Java Scripts, Objects in Java Script, Dynamic HTML with Java Script

UNIT-III:
XML: Document type definition, XML Schemas, Document Object model, Presenting XML, Using XML Processors: DOM and SAX

UNIT-IV:
Java Beans: Introduction to Java Beans, Advantages of Java Beans, BDK
Introspection, Using Bound properties, Bean Info Interface, Constrained properties
Persistence, Customizes, Java Beans API, Introduction to EJB’s

UNIT-V:
Web Servers and Servlets: Tomcat web server, Introduction to Servelets: Lifecycle of a Serverlet, JSDK, The Servelet API, The javax.servelet Package, Reading Servelet parameters, Reading Initialization parameters. The javax.servelet HTTP package, Handling Http Request & Responses, Using Cookies-Session Tracking, Security Issues,

UNIT-VI:
Introduction to JSP: The Problem with Servelet. The Anatomy of a JSP Page, JSP Processing. JSP Application Design with MVC Setting Up and JSP Environment: Installing the Java Software Development Kit, Tomcat Server & Testing Tomcat

UNIT-VII:
JSP Application Development: Generating Dynamic Content, Using Scripting Elements Implicit JSP Objects, Conditional Processing – Displaying Values Using an Expression to Set an Attribute, Declaring Variables and Methods Error Handling and Debugging Sharing Data Between JSP pages, Requests, and Users Passing Control and Date between Pages – Sharing Session and Application Data – Memory Usage Considerations

UNIT VIII:
Database Access : Database Programming using JDBC, Studying Javax.sql.* package,Accessing a Database from a JSP Page, Application – Specific Database Actions,Deploying JAVA Beans in a JSP Page, Introduction to struts framework..
TEXT BOOKS:
1. Web Programming, building internet applications, Chris Bates 2nd edition,
WILEY Dreamtech (UNIT s 1,2 ,3)
2. The complete Reference Java 2 Fifth Edition by Patrick Naughton and Herbert Schildt. TMH (Chapters: 25) (UNIT 4)
3. Java Server Pages –Hans Bergsten, SPD O’Reilly (UNITs 5,6,7,8)
REFERENCE BOOKS:
Programming world wide web-Sebesta,Pearson
Core SERVLETS ANDJAVASERVER PAGES VOLUME 1: CORE TECHNOLOGIES By Marty Hall and Larry Brown Pearson
Internet and World Wide Web – How to program by Dietel and Nieto PHI/Pearson Education Asia.
Jakarta Struts Cookbook , Bill Siggelkow, S P D O’Reilly for chap 8.
Murach’s beginning JAVA JDK 5, Murach, SPD
An Introduction to web Design and Programming –Wang-Thomson
Web Applications Technologies Concepts-Knuckles,John Wiley
Programming world wide web-Sebesta,Pearson
Web Warrior Guide to Web Programmming-Bai/Ekedaw-Thomas
Beginning Web Programming-Jon Duckett WROX.
Java Server Pages, Pekowsky, Pearson.
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. CSE -I Sem T P C
4+1* 0 4
DATA WAREHOUSING AND DATA MINING

UNIT - I
Introduction : Fundamentals of data mining, Data Mining Functionalities, Classification of Data Mining systems, Major issues in Data Mining.
Data Preprocessing : Needs Preprocessing the Data, Data Cleaning, Data Integration and Transformation, Data Reduction, Discretization and Concept Hierarchy Generation.

UNIT – II
Data Warehouse and OLAP Technology for Data Mining Data Warehouse, Multidimensional Data Model, Data Warehouse Architecture, Data Warehouse
Implementation,Further Development of Data Cube Technology, From Data Warehousing to Data Mining.

UNIT - III
Data Mining Primitives, Languages, and System Architectures : Data Mining Primitives, Data Mining Query Languages, Designing Graphical User Interfaces Based on a Data Mining Query Language Architectures of Data Mining Systems.

UNIT - IV
Concepts Description : Characterization and Comparison : Data Generalization and Summarization- Based Characterization, Analytical Characterization: Analysis of Attribute Relevance, Mining Class Comparisons: Discriminating between Different Classes, Mining Descriptive Statistical Measures in Large Databases.

UNIT - V
Mining Association Rules in Large Databases : Association Rule Mining, Mining Single-Dimensional Boolean Association Rules from Transactional Databases, Mining Multilevel Association Rules from Transaction Databases, Mining Multidimensional Association Rules from Relational Databases and Data Warehouses, From Association Mining to Correlation Analysis, Constraint-Based Association Mining.

UNIT - VI
Classification and Prediction : Issues Regarding Classification and Prediction, Classification by Decision Tree Induction, Bayesian Classification, Classification by Backpropagation, Classification Based on Concepts from Association Rule Mining, Other Classification Methods, Prediction, Classifier Accuracy.


UNIT - VII
Cluster Analysis Introduction : Types of Data in Cluster Analysis, A Categorization of Major Clustering Methods, Partitioning Methods, Density-Based Methods, Grid-Based Methods, Model-Based Clustering Methods, Outlier Analysis.

UNIT - VIII
Mining Complex Types of Data : Multimensional Analysis and Descriptive Mining of Complex, Data Objects, Mining Spatial Databases, Mining Multimedia Databases, Mining Time-Series and Sequence Data, Mining Text Databases, Mining the World Wide Web.

TEXT BOOKS :
Data Mining – Concepts and Techniques - JIAWEI HAN & MICHELINE KAMBER Harcourt India.

REFERENCES :
1. Data Mining Introductory and advanced topics –MARGARET H DUNHAM, PEARSON EDUCATION
2. Data Mining Techniques – ARUN K PUJARI, University Press.
3. Data Warehousing in the Real World – SAM ANAHORY & DENNIS MURRAY. Pearson Edn Asia.
4 Data Warehousing Fundamentals – PAULRAJ PONNAIAH WILEY STUDENT EDITION.
5. The Data Warehouse Life cycle Tool kit – RALPH KIMBALL WILEY STUDENT EDITION.

cooks theorem

Cook’s Theorem:

Cook’s Theorem states that-
                                             Any NP problem can be converted to SAT in polynomial time.

In order to prove this, we require a uniform way of representing NP problems. Remember that what makes
a problem NP is the existence of a polynomial-time algorithm—more specifically, a Turing machine—for
checking candidate certificates. What Cook did was somewhat analogous to what Turing did when he
showed that the Entscheidungsproblem was equivalent to the Halting Problem. He showed how to encode
as Propositional Calculus clauses both the relevant facts about the problem instance and the Turing machine
which does the certificate-checking, in such a way that the resulting set of clauses is satisfiable if and only
if the original problem instance is positive. Thus the problem of determining the latter is reduced to the
problem of determining the former.
Assume, then, that we are given an NP decision problem D. By the definition of NP, there is a polyno-
mial function P and a Turing machine M which, when given any instance I of D, together with a candidate
certificate c, will check in time no greater than P (n), where n is the length of I, whether or not c is a
certificate of I.
Let us assume that M has q states numbered 0, 1, 2, . . . , q − 1, and a tape alphabet a1 , a2 , . . . , as . We
shall assume that the operation of the machine is governed by the functions T , U , and D as described in
the chapter on the Entscheidungsproblem. We shall further assume that the initial tape is inscribed with the
problem instance on the squares 1, 2, 3, . . . , n, and the putative certificate on the squares −m, . . . , −2, −1.
Square zero can be assumed to contain a designated separator symbol. We shall also assume that the machine
halts scanning square 0, and that the symbol in this square at that stage will be a1 if and only if the candidate
certificate is a true certificate. Note that we must have m ≤ P (n). This is because with a problem instance
of length n the computation is completed in at most P (n) steps; during this process, the Turing machine
head cannot move more than P (n) steps to the left of its starting point.
We define some atomic propositions with their intended interpretations as follows:

1. For i = 0, 1, . . . , P (n) and j = 0, 1, . . . , q − 1, the proposition Qij says that after i computation
steps, M is in state j.
2. For i = 0, 1, . . . , P (n), j = −P (n), . . . , P (n), and k = 1, 2, . . . , s, the proposition Sijk says that
after i computation steps, square j of the tape contains the symbol ak .

3. i = 0, 1, . . . , P (n) and j = −P (n), . . . , P (n), the proposition Tij says that after i computation steps,
the machine M is scanning square j of the tape.

Next, we define some clauses to describe the computation executed by M :

1. At each computation step, M is in at least one state. For each i = 0, . . . , P (n) we have the clause

Qi0 ∨ Qi1 ∨ · · · ∨ Qi(q−1) ,

giving (P (n) + 1)q = O(P (n)) literals altogether.

2. At each computation step, M is in at most one state. For each i = 0, . . . , P (n) and for each pair j, k
of distinct states, we have the clause
¬(Qij ∧ Qik ),

giving a total of q(q − 1)(P (n) + 1) = O(P (n)) literals altogether.

3. At each step, each tape square contains at least one alphabet symbol. For each i = 0, . . . , P (n) and
−P (n) ≤ j ≤ P (n) we have the clause

Sij1 ∨ Sij2 ∨ · · · ∨ Sijs ,

giving (P (n) + 1)(2P (n) + 1)s = O(P (n)2 ) literals altogether.

4. At each step, each tape square contains at most one alphabet symbol. For each i = 0, . . . , P (n) and
−P (n) ≤ j ≤ P (n), and each distinct pair ak , al of symbols we have the clause

¬(Sijk ∧ Sijl ),

giving a total of (P (n) + 1)(2P (n) + 1)s(s − 1) = O(P (n)2 ) literals altogether

5. At each step, the tape is scanning at least one square. For each i = 0, . . . , P (n), we have the clause

Ti(−P (n)) ∨ Ti(1−P (n)) ∨ · · · ∨ Ti(P (n)−1) ∨ TiP (n) ,

giving (P (n) + 1)(2P (n) + 1) = O(P (n)2 ) literals altogether.

6. At each step, the tape is scanning at most one square. For each i = 0, . . . , P (n), and each distinct
pair j, k of tape squares from −P (n) to P (n), we have the clause

¬(Tij ∧ Tik ),

giving a total of 2P (n)(2P (n) + 1)(P (n) + 1) = O(P (n)3 ) literals.

7. Initially, the machine is in state 1 scanning square 1. This is expressed by the two clauses

Q01 , T01 ,

giving just two literals.
8. The configuration at each step after the first is determined from the configuration at the previous step
by the functions T , U , and D defining the machine M . For each i = 0, . . . , P (n), −P (n) ≤ j ≤
P (n), k = 0, . . . , q − 1, and l = 1, . . . , s, we have the clauses

Tij ∧ Qik ∧ Sijl → Q(i+1)T (k,l)

Tij ∧ Qik ∧ Sijl → S(i+1)jU (k,l)

Tij ∧ Qik ∧ Sijl → T(i+1)(j+D(k,l))

Sijk → Tij ∨ S(i+1)jk

The fourth of these clauses ensures that the contents of any tape square other than the currently

Sijk ∧ ¬Tij → S(i+1)jk ). These clauses contribute a total of (12s + 3)(P (n) + 1)(2P (n) + 1)q =
O(P (n)2 ) literals.

9. Initially, the string ai1 ai2 . . . ain defining the problem instance I is inscribed on squares 1, 2, . . . , n
of the tape. This is expressed by the n clauses

S01i1 , S02i2 , . . . , S0nin ,

a total of n literals.

10. By the P (n)th step, the machine has reached the halt state, and is then scanning square 0, which
contains the symbol a1 . This is expressed by the three clauses

QP (n)0 , SP (n)01 , TP (n)0 ,

giving another 3 literals.

Altogether the number of literals involved in these clauses is O(P (n)3 ) (in working this out, note that q and
s are constants, that is, they depend only on the machine and do not vary with the problem instance; thus
they do not contribute to the growth of the the number of literals with increasing problem size, which is
what the O notation captures for us). It is thus clear that the procedure for setting up these clauses, given the
original machine M and the instance I of problem D, can be accomplished in polynomial time.
We must now show that we have succeeded in converting D into SAT . Suppose first that I is a positive
instance of D. This means that there is a certificate c such that when M is run with inputs c, I, it will halt
scanning symbol a1 on square 0. This means that there is some sequence of symbols that can be placed
initially on squares −P (n), . . . , −1 of the tape so that all the clauses above are satisfied. Hence those
clauses constitute a positive instance of SAT .
Conversely, suppose I is a negative instance of D. In that case there is no certificate for I, which means
that whatever symbols are placed on squares −P (n), . . . , −1 of the tape, when the computation halts the
machine will not be scanning a1 on square 0. This means that the set of clauses above is not satisfiable, and
hence constitutes a negative instance of SAT .
Thus from the instance I of problem D we have constructed, in polynomial time, a set of clauses which
constitute a positive instance of SAT if and only I is a positive instance of D. In other words, we have
converted D into SAT in polynomial time. And since D was an arbitrary NP problem it follows that any NP
problem can be converted to SAT in polynomial time.

Game tree(DAA)

Game tree

From Wikipedia, the free encyclopedia

Jump to: navigation, search

If you're looking for game tree as it's used in game theory (not combinatorial game theory), please see Extensive-form game.

In combinatorial game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position.

The first two ply of the game tree for tic-tac-toe.

The diagram shows the first two levels, or ply, in the game tree for tic-tac-toe. We consider all the rotations and reflections of positions as being equivalent, so the first player has three choices of move: in the center, at the edge, or in the corner. The second player has two choices for the reply if the first player played in the center, otherwise five choices. And so on.
The number of leaf nodes in the complete game tree is the number of possible different ways the game can be played. For example, the game tree for tic-tac-toe has 26,830 leaf nodes.
Game trees are important in artificial intelligence because one way to pick the best move in a game is to search the game tree using the minimax algorithm or its variants. The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like chess are much too large to search. Instead, a chess-playing program searches a partial game tree: typically as many ply from the current position as it can search in the time available. Except for the case of "pathological" game trees ^[1] (which seem to be quite rare in practice), increasing the search depth (i.e., the number of ply searched) generally improves the chance of picking the best move.
Two-person games can also be represented as and-or trees. For the first player to win a game, there must exist a winning move for all moves of the second player. This is represented in the and-or tree by using disjunction to represent the first player's alternative moves and using conjunction to represent all of the second player's moves.

Contents [hide] 1 Solving Game Trees 2 See also 3 References 3.1 Notes 3.2 General references

[edit] Solving Game Trees

An arbitrary game tree that has been fully colored

With a complete game tree, it is possible to "solve" the game – that is to say, find a sequence of moves that either the first or second player can follow that will guarantee either a win or tie. The algorithm can be described recursively as follows.

1. Color the final ply of the game tree so that all wins for player 1 are colored one way, all wins for player 2 are colored another way, and all ties are colored a third way.
2. Look at the next ply up. If there exists a node colored opposite as the current player, color this node for that player as well. If all immediately lower nodes are colored for the same player, color this node for the same player as well. Otherwise, color this node a tie.
3. Repeat for each ply, moving upwards, until all nodes are colored. The color of the root node will determine the nature of the game.

The diagram shows a game tree for an arbitrary game, colored using the above algorithm.
It is usually possible to solve a game (in this technical sense of "solve") using only a subset of the game tree, since in many games a move need not be analyzed if there is another move that is better for the same player (for example alpha-beta pruning can be used in many deterministic games).
Any subtree that can be used to solve the game is known as a decision tree, and the sizes of decision trees of various shapes are used as measures of game complexity.^[2]

[edit] See also

• Alpha-beta pruning
• Extensive form game
• Shannon number
• Game complexity

[edit] References

[edit] Notes

1. ^ Nau, Dana (1982). "An investigation of the causes of pathology in games". Artificial Intelligence 19: 257–278. doi:10.1016/0004-3702(82)90002-9. 
2. ^ Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 9090074880. http://fragrieu.free.fr/SearchingForSolutions.pdf. 

[edit] General references

• Hu, Te Chiang; Shing, Man-tak (2002). Combinatorial Algorithms. Courier Dover Publications. ISBN 0486419622. http://books.google.com/?id=BF5_bCN72EUC. Retrieved 2007-04-02. 
• Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin. Exploiting Graph Properties of Game Trees

Retrieved from "http://en.wikipedia.org/wiki/Game_tree"

Categories: Combinatorial game theory | Trees (graph theory)

 

 

source:

 http://en.wikipedia.org/wiki/Game_tree