rajcode

imp links for IT PROFESSIONALS

2011-06-14T23:38:00.000-07:00

.net MobileMMIT : Microsoft Mobile Internet Toolkit (.NET Mobile)An extension of the .NET framework providing a simple and a quick way to build Wireless applications.Here it is possible to build a Wireless application using any of the framework services like Web Services, ADO .NET…http://www.academictutorials.com//dotnet-mobile/ADO TutorialADO : ActiveX Data Objects.Microsoft ADO is a Component object model object for accessing data sources.ADO provides a layer between programming languages and databases, which allows a developer to write programs which access data, without knowing how the database is implemented. http://www.academictutorials.com//ado/ADO.NETADO.NET-Active-x Data Objects.NETADO.NET is an object-oriented set of libraries that allows you to interact with the data sources.Here we will look at ADO.NET as a way to interact with a data base.ADO.NET is the new database technology of the .NET platform, and it builds on Microsoft ActiveX Data Objects (ADO). ADO is alanguage-neutral object model that is the keystone of Microsoft's Universal Data Access strategy. http://www.academictutorials.com//ado.net/ AJAX TutorialAJAX - Asynchronous JavaScript Technology and XML It is a scripting technique for silently loading new data from the server.http://www.academictutorials.com//ajax/ASP TutorialAn Active Server Page is a web page that includes program code that is processed on a Microsoft web server before the page is sent to the user.http://www.academictutorials.com//asp/ASP.Net ASP.NET is a set of web application development technologies marketed by Microsoft. Microsoft has completely rebuilt ASP.NET, based on the Common Language Runtime (CLR) shared by all Microsoft .NET applications. Programmers can write ASP.NET code using any of the different programming languages supported by the .NET Framework, usually C#, Visual Basic.NET, or JScript .NET, but also including open-source languages such as Perl and Python.http://www.academictutorials.com//asp.net/C TutorialHow to start programming with C language.In 1972, C was developed at Bell Laboratories by Dennis Ritchie.C is a simple programming language with a relatively simple to understand syntax and few keywords. http://www.academictutorials.com//c/C# : C SharpC-Sharp Before we start explaining what .Net is? Lets discuss about Internet on business organization. There are three phases of Internet..NET is the Microsoft Web services strategy to connect information, people, systems,and devices through software. Integrated across the Microsoft platform, .NET technology provides the ability to quickly build, deploy, manage, and use connected, security-enhanced solutions with Web services.http://www.academictutorials.com//c-sharp.net/C++ TutorialStart programming in C++.C++ is an extension of the C Programming Language. C Programming language was been developed in the Bells Labs in the year 1969-1973. UNIX Operating system was also been developed at the same time. In the year 1983 Bjarne Stroustrup created the C++ in the Bells Labs.http://www.academictutorials.com//cpp/ Communication Skills Communication SkillsTalking is very easy, but communication, that means an exchange or communion with the other person, requires the greater skill.This guide will teach how to overcome the communication barriers and also hone the communication skills. http://www.academictutorials.com//communication-skills/ Corporate Communication Corporate CommunicationThe Corporate communication will involve much more than just motivating the employees and then dispensing the good PR.A Power of Corporate Communication shows the managers and the executives how to communicate effectively with the fellow employees. The effective corporate communication does requires the carefully formulated and the implemented program.http://www.academictutorials.com//corporate-communication/CSS TutorialCSS is a useful and efficient tool for specifying the presentation of HTML webpagesIt can control almost all the details of their appearance, from simply styling the content (colour, bold, etc.) to completely controlling the page layout. http://www.academictutorials.com//css/Data Structures Using CData Structures Using CHere you can know how the data structures are represented in the computerYou can learn about Stacks, Queues, Trees, Graphs, and many more which are related with the data structures. Here we have used C programming language to demonstrate some examples.http://www.academictutorials.com//data-structure/DHTML TutorialDHTML : Dynamic HTML.It is an extension of HTML that enables, among other things, the inclusion of small animations and dynamic menus in Web pages.DHTML is the combination of HTML, Cascading Style Sheets, and Javascript used to create dynamic Web content which can move, hide, or animate as a result of user events. http://www.academictutorials.com//dhtml/DTD TutorialDTD : Document Type Definition. It is a document that describes the structure of a Web page written in XML.The description of the structure and the rules a document must satisfy for an SGML or XML document type. The DTD comprises the formal declaration of the elements that make up a document, their mutual coherence, meaning and documentation as drawn up for a document type (or document or information model). You can store a DTD at the beginning of a document or externally in a separate file.http://www.academictutorials.com//dtd/E4X TutorialIt is a programming language extension that adds native XML support to ECMAscript. E4X does this by providing access to the XML document in a form that feels natural for ECMAscript programmers. http://www.academictutorials.com//e4x/EJB TutorialEJB : Enterprise Java Beans It is a component architecture for the development and deployment of object-oriented, distributed, enterprise-level applications.Applications written using the Enterprise JavaBeans architecture are scalable, transactional, multi-user and secure.http://www.academictutorials.com//ejb/Flash TutorialFlash is a popular authoring software developed by Macromedia.It is a vector graphic animation technology that requires a plug-in but is browser-independent.It is used to create vector graphics-based animation programs with full-screen navigation interfaces, graphic illustrations, and simple interactivity in an antialiased, resizable file format that is small enough to stream across a normal modem connection. http://www.academictutorials.com//flash/HTML DOM TutorialDOM : Document Object Model. The Document Object Model is a platform- and language-neutral interface that will allow programs and scripts to dynamically access and update the content, structure and style of documents.http://www.academictutorials.com//html-dom/HTML TutorialHTML is not a programming language, but rather a markup language.In this HTML tutorial you will learn how to use HTML to create your own Web site.http://www.academictutorials.com//html/Java TutorialJava is an object-oriented programming language.It is developed initially by James Gosling and colleagues at Sun Microsystems.Initially called Oak (named after the oak trees outside Gosling's office). Java is multi-platformhttp://www.academictutorials.com//java/ JavaScript Tutorial JavaScript is a script language - a system of programming codes, created by Netscape, that can be embedded into the HTML of a web page to add functionality.http://www.academictutorials.com//javascript/JMS TutorialJava messaging service.Java Message Service(JMS) specification v1.0.1 was released in October 1998, by JavaSoftThe JMS is an API for accessing enterprise messaging systems from Java. Message Oriented Middleware(MOM) provides a mechanism for integrating applications in a flexible, loosely coupled manner by providing asynchronous data delivery between applications in an indirect way through an intermediary. http://www.academictutorials.com//jms/JMX TutorialJMX-Java Management ExtensionsJava Management Extensions provides the tools for building Web-based, distributed, dynamic and modular solutions for managing and monitoring devices, applications, and service-driven networks.It was developed by Java Community Process (JCP). http://www.academictutorials.com//jmx/JSP TutorialJSP : Java Server Pages It is a server side scripting language. JSP are normal HTML with Java code pieces embedded in them. A JSP compiler is used to generate a Servlet from the JSP page.http://www.academictutorials.com//jsp/Leadership SkillsLeadership SkillsLeadership quality incorporates many of the diverse skills and the qualities, and for many of the people it does not come naturally.Good leader is a one who can find balance in managing, disciplining, delegating, instructing , encouraging, and sympathizing. As the manager/leader, all the eyes are on you.http://www.academictutorials.com//leadership-skills/Media TutorialMultimedia is presenting data in more than one medium, such as combining text, graphics and sound.It is the systems that support the interactive use of text, audio, still images, video, and graphics. Most forms of multimedia require a lot of disk space.http://www.academictutorials.com//media/ Microsoft.Net A Microsoft operating system platform that incorporates applications, a suite of tools and services and a change in the infrastructure of the company's Web strategy.http://www.academictutorials.com//microsoft.net/Negotiation SkillsNegotiation SkillsA complex sales situations should be navigated by the sales professionals who do know how to successfully handle the challenge.Negotiate Success do provides the proven methods to overcome the objections without relying on the price as a solution.http://www.academictutorials.com//negotiation-skills/PERL TutorialPERL : Practical Extraction and Reporting Language.It is a programming language developed by Larry Wall.It is an open source server side programming language extensively used for web scripts and to process data passed via the Common Gateway Interface from HTML forms etc.Perl scripts are not embedded within HTML pages and do not download to the web browser but reside on the server.And often used for creating CGI programs.http://www.academictutorials.com//perl/PHP TutorialPHP : Hypertext Preprocessor .It is a server-side, cross-platform, HTML embedded scripting language that lets web developers to create dynamic web pages.PHP is an alternative to Microsoft's Active Server Page (ASP) technology. As with ASP, the PHP script is embedded within a Web page along with its HTML. Before the page is sent to a user that has requested it, the Web server calls PHP to interpret and perform the operations called for in the PHP script. http://www.academictutorials.com//php/Project ManagementProject ManagementAn Effective project management will facilitates smooth running of the horizontally oriented work in the organisations which are traditionally vertically oriented.Projects do require a co-operation of the line managers both across a departments involved and throughout a various levels of the seniority. In situations a project team member is having only one boss, a project manager.http://www.academictutorials.com//project-management/RDF TutorialRDF : Resource Description Framework.RDF is a general framework for how to describe any Internet resource such as a Web site and its content.It is a general framework for describing a Web site's metadata, or the information about the information on the site. It provides interoperability between applications that exchange machine-understandable information on the Web. http://www.academictutorials.com//rdf/RSS TutorialRSS : Really Simple Syndication orRich Site SummaryIt allows you to organize or syndicate your site content .RSS files can be automatically updated. It is written in XML-based formate.http://www.academictutorials.com//rss/Schema TutorialSchema is a description of the structure and rules a document must satisfy for an XML document type.XML Schema is XML-based alternative to DTD.http://www.academictutorials.com//schema/Servlets TutorialJava servlets allow users to run Java code on the server and send HTML pages to a browser.The Java Servlet API allows a software developer to add dynamic content to a web server using the Java platform. The generated content is commonly HTML, but may be other data such as XML.http://www.academictutorials.com//servlets/SMIL TutorialSMIL : Synchronized Media Integration Language.It is a markup language designed to present multiple media files together. It is developed by the Word Wide Web Consortium (W3C). http://www.academictutorials.com//smil/SOAP TutorialSOAP : Simple Object Access Protocol . SOAP is a lightweight XML based protocol . It is a standard for exchanging XML-based messages over a computer network, normally using HTTP.SOAP consists of three parts: an envelope that defines a framework for describing what is in a message and how to process it, a set of encoding rules for expressing instances of application-defined datatypes, and a convention for representing remote procedure calls and responses.http://www.academictutorials.com//soap/SQL TutorialSQL : Structured Query Language .It is a language that provides an interface to relational database systems.SQL was developed by IBM in the 1970s for use in System R.SQL is a de facto standard, as well as an ISO and ANSI standard.. It is a special-purpose, nonprocedural language that supports the definition, manipulation, and control of data in relational database management systems.http://www.academictutorials.com//sql/Struts TutorialApache Struts is an open-source framework for developing J2EE web applications.It was originally created by Craig McClanahan and donated to the Apache Foundation in May, 2000. It is formerly located under the Apache Jakarta Project and known as Jakarta Struts.Website : struts.apache.org http://www.academictutorials.com//struts/ SVG TutorialSVG : Scalable Vector Graphics. SVG is a language for describing two-dimensional graphics in XML.Like HTML, SVG is written in plain text and rendered by the browser, except that in this case, it is not just text that is rendered but also shapes and images, which can be animated and made interactive. SVG is written in XML (Extensible Markup Language) and developed by the World Wide Web Consortium.http://www.academictutorials.com//svg/TCP/IP TutorialTransmission Control Protocol/Internet Protocol A protocol for communication between computers, used as a standard for transmitting data over networks and as the basis for standard Internet protocols. TCP and IP were developed by a Department of Defense (DOD) research project to connect a number different networks designed by different vendors into a network of networks (the "Internet").http://www.academictutorials.com//tcp-ip/Team WorkTeam WorkAs the work becomes more and more complex, managers will often finds that more work can be achieved quicker with less effort and less time.This group of workers under the manager will form a team. http://www.academictutorials.com//teamwork/ Time Management Time ManagementOur life revolves around the passing of the time. The time cannot be paused, bought, or can be changed, but we can do learn to use it in better way. Time is one of the scarcest resources and unlike the money or the energy, is irreplaceable.http://www.academictutorials.com//time-management/VB.NETVB.NET-Visual Basic.NETThe next generation of Visual Basic,Visual Basic .NET is designed to be the easiest and most productive tool for creating .NET applications, including Windows applications, Web Services, and Web applications. Visual Basic .NET also allows optional use of new language features.http://www.academictutorials.com//vb.net/VBScript TutorialVBScript is a scripting language. VBScript was created by Microsoft to use either as a client-side scripting language for the Microsoft Internet Explorer (versions 3.0 and later) or as a server-side scripting language with the Microsoft Internet Information Server (versions 3.0 and later). A primary advantage for using the server-side approach is that the VBScript is processed by the server before it is transmitted to the client.http://www.academictutorials.com//vbscript/Visual Basic TutorialVB-Visual BasicVISUAL BASIC is a high level programming language and it evolved from the earlier DOS version called BASIC.VISUAL BASIC is a events driven and VISUAL Programming Language.The codes look a bit like English Language and different software companies produced different version of BASIC, such as Microsoft QBASIC, QUICKBASIC, GWBASIC, IBM BASICA and so on. http://www.academictutorials.com//vb/W3C TutorialWorld Wide Web Consortium It was created in October 1994 by Tim Berners-Lee, the original architect of the World Wide Web. W3C is the governing body for web standards and its mission is to create standards and specifications for the World Wide Web. http://www.academictutorials.com//w3c/WAP TutorialWAP : Wireless Application Protocol It is a secure specification that allows users to access information instantly via handheld wireless devices such as mobile phones, pagers, two-way radios, smartphones and communicators.WAP was conceived by four companies: Ericsson, Motorola, Nokia, and Unwired Planet (today called Phone.com).http://www.academictutorials.com//wap/Web BrowsersWeb Browser is programme used to access the Internet services and resources available through the World Wide Web.It is a client program that initiates requests to a Web server and displays the information that the server returns. Web browsers often provide a graphical interface that lets users click icons, buttons, and menu options to view and navigate Web pages.http://www.academictutorials.com//web-browsers/Web BuildingKnow how to build a professional website.http://www.academictutorials.com//web-building/Web CareersSimple steps to get the C.V. into shape.How to get the bigger paycheck?Reasons why others dont like you at work!!http://www.academictutorials.com//web-careers/Web HostingIt is an arrangement where you allow an agency to host your website for you on their Web Server for a fee.The World Wide Web is a massive collection of web sites, all hosted on computers (called web servers) all over the world. The web server (computer) where your web site's html files, graphics, etc. reside is known as the web host.Web hosting clients simply upload their web sites to a shared (or dedicated) webserver, which the ISP maintains to ensure a constant, fast connection to the Internet. http://www.academictutorials.com//web-hosting/ Web QualityHow to build your website to the highest quality?Learn to use latest web standards.How to make web site more accessible and readable?http://www.academictutorials.com//web-quality/Web SemanticThe semantic of something = The meaning of something.The Semantic Web is a mesh of information linked up in such a way as to be easily processable by machines, on a global scale.http://www.academictutorials.com//web-semantic/ Web Services Tutorial Web Services define a platform-independent standard based on XML to communicate within distributed systems.XML is used to tag the data.SOAP is used to transfer the data.WSDL is used for describing the services available. UDDI is used for listing what services are available.http://www.academictutorials.com//web-services/WMLScript TutorialWMLScript : Wireless Markup Language ScriptScripting language for WAP devices.It is a scripting language used to program the mobile device. WMLScript is an extended subset of the JavaScript TM scripting language, but less powerful. http://www.academictutorials.com//wmlscript/ WSDL TutorialWSDL : Web Services Description Language . It is an XML format for describing network services as a set of endpoints operating on messages containing either document-oriented or procedure-oriented information. WSDL was developed jointly by Microsoft and IBM. http://www.academictutorials.com//wsdl/XForms TutorialXForms is an XML format for the specification of user interfaces. XForms Give
Strong typing for easier input validation
XML format for input data
Much more internationalizable and localizable
Scriptless actions
More device independenthttp://www.academictutorials.com//xforms/XHTML TutorialXHTML is the next generation of HTML and is a hybrid between HTML and XML.XML was designed to describe data. HTML was designed to display data.XHTML is much stricter than HTML. Not all browers support XML so XHTML provides an intermediary soluton and can be interpreted by XML and HTML browsers. http://www.academictutorials.com//xhtml/XLink TutorialXLink : XML Linking Language It allows elements to be inserted into XML documents in order to create and describe links between resources.eXtended Links is a W3C Recommendation ( http://www.w3.org/TR/xlink )http://www.academictutorials.com//xlink/ XML DOM TutorialDOM (Document Object Model) represents documents as a hierarchy of Node objects. Some of these Node objects may have child nodes of various types, while others are 'leaf' nodes which can have nothing below them. http://www.academictutorials.com//xml-dom/ XML TutorialExtensible Markup Language. A flexible way to create common information formats and share both the format and the data on the World Wide Web, intranets, and elsewhere. XML is a formal recommendation from the World Wide Web Consortium (W3C) similar to the language of today's Web pages, the Hypertext Markup Language (HTML). http://www.academictutorials.com//xml/XML Web ServicesA Web Service (XML Web Service) is a unit of code that can be activated using HTTP requests.A major advantage of the Web services architecture is, it allows programs written in different languages on different platforms to communicate with each other in a standards-based way.http://www.academictutorials.com//xml-web-services/XPath TutorialXPath : XML Path LanguageXPath is a language for addressing parts of an XML document, designed to be used by both XSLT and Xpointer.It also provides basic facilities for manipulation of strings, numbers and booleans. http://www.academictutorials.com//xpath/XPointer TutorialXpointer - XML Pointer Language, is the language to be used as the basis for a fragment identifier for any URI reference that locates a resource of Internet media type text/xml or application/xml .It has a string-based syntax. XPointer consists of a description that comes after the # symbol in a URL.http://www.academictutorials.com//xpointer/XQuery TutorialXQuery is the query language for XML. It provides a mechanism to extract and manipulate data from XML documents or any data source that can be viewed as XML such as relational databases or office documents. Just as SQL is a query language that queries relational tables to create new relational tables, XQuery queries XML documents to create new XML documents.XQuery uses XPath syntax to address specific parts of an XML document.http://www.academictutorials.com//xquery/XSL TutorialXSL : EXtensible Stylesheet Language, a language for specifying style sheets for XML documents..XSL Transformation (XSLT) is used with XSL to describe how an XML document is transformed into another document. Similar to CSS, it defines the specification for an XML document's presentation and appearance. Both CSS and XSL provide a platform-independent method for specifying the document's presentation style.http://www.academictutorials.com//xsl/XSL-FO TutorialXSL-FO : XSL Formatting Objects It is an XML markup language for document formatting.XSL-FO is part of XSLhttp://www.academictutorials.com//xsl-fo/XSLT TutorialXSLT : Extensible Stylesheet Language Transformation. It is a language for transforming XML documents into other XML documents.XSLT is designed for use as part of XSL, which is a stylesheet language for XML. http://www.academictutorials.com//xslt/

Compiler Design N otes for B.Tech CSE and IT student

2011-04-20T22:28:00.000-07:00

UNIT – I

OVERVIEW OF COMPILATION: Phases of CompilationLexical 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.

A compiler is a computer program (or set of programs) that transforms source code written in a programming language (the source language) into another computer language (the target language, often having a binary form known as object code). The most common reason for wanting to transform source code is to create an executable program
The phases of compiler can be broadly classified into
The Front End ( Language specific ), and the Back End ( Machine specific )parts of compilation
Also known as Analysis-Synthesis model of compilation
Compiler structure

- Front end phases are known as analysis phases
- Back end phases are known as synthesis phases
. Each phase has a well defined work
. Each phase handles a logical activity in the process of compilation
The Analysis-Synthesis model:
The front end phases are Lexical, Syntax and Semantic analyses. These form the "analysis phase" as you can well see these all do some kind of analysis. The Back End phases are called the "synthesis phase" as they synthesize the intermediate and the target language and hence the program from the representation created by the Front End phases. The advantages are that not only can lots of code be reused, but also since the compiler is well structured - it is easy to maintain & debug. Compiler is retarget able.
. Source and machine independent code optimization is possible.
. Optimization phase can be inserted after the front and back end phases have been developed and deployed. Also known as Analysis-Synthesis model of compilation

Final Compiler structure

Also since each phase handles a logically different phase of working of a compiler parts of the code can be reused to make new compilers. E.g., in a C compiler for Intel & Athlon the front ends will be similar. For a same language, lexical, syntax and semantic analyses are similar, code can be reused. Also in adding optimization, improving the performance of one phase should not affect the same of the other phase; this is possible to achieve in this model.
Bootstrapping .
. A compiler can be characterized by three languages: the source language (S), the target language (T), and the implementation language (I)
. The three language S, I, and T can be quite different. Such a compiler is called cross-compiler
Compilers are of two kinds: native and cross
Native compilers are written in the same language as the target language. For example, SMM is a compiler for the language S that is in a language that runs on machine M and generates output code that runs on machine M.
Cross compilers are written in different language as the target language. For example, SNM is a compiler for the language S that is in a language that runs on machine N and generates output code that runs on machine M.
Lexical Analysis
. Recognize tokens and ignore white spaces, comments
Generates token stream
. Error reporting . Model using regular expressions
. Recognize using Finite State Automata
The first phase of the compiler is lexical analysis. The lexical analyzer breaks a sentence into a sequence of words or tokens and ignores white spaces and comments. It generates a stream of tokens from the input. This is modeled through regular expressions and the structure is recognized through finite state automata. If the token is not valid i.e., does not fall into any of the identifiable groups, then the lexical analyzer reports an error. Lexical analysis thus involves recognizing the tokens in the source program and reporting errors, if any. We will study more about all these processes in the subsequent slides
Regular Expression Notation ....
. If r and s are regular expressions denoting the languages L(r) and L(s) then
. (r)(s) is a regular expression denoting L(r) U L(s)
. (r)(s) is a regular expression denoting L(r)L(s)
. (r)* is a regular expression denoting (L(r))*
. (r) is a regular expression denoting L(r )
How to specify tokens
Examples

My email address ska@iitk.ac.in
. S = letter U {@, . }
. Letter a b . z A B . Z
. Name letter +
. Address name '@' name '.' name '.' name
Finite Automata
. Regular expression are declarative specifications
. Finite automata is an implementation
. A finite automata consists of
- An input alphabet belonging to S
- A set of states S
- A set of transitions statei statej
- A set of final states F
- A start state n
. Transition s1 s2 is read:
in state s1 on input a go to state s2
. If end of input is reached in a final state then accept
Pictorial notation
. A state . A final state
. Transition
. Transition from state i to state j on an input a
How to recognize tokens
. Consider
relop < <= = <> >= >
id letter(letterdigit)*
num digit + ('.' digit + )? (E('+''-')? digit + )?
delim blank tab newline
ws delim +
. Construct an analyzer that will return pairs
We now consider the following grammar and try to construct an analyzer that will return pairs.
relop < = = <> = >
id letter (letter digit)*
num digit+ ('.' digit+)? (E ('+' '-')? digit+)?
delim blank tab newline
ws delim+

Essay type questions:
1. Explain the different phases of a compiler, showing the output of each phase,
using the example of the following statement:
position : = initial + rate * 60
2.Compare compiler and interpreter with suitable diagrams.
3. Explain the different phases of a compiler.
4. Write a short notes on token specification.

5. Explain how input buffering helps lexical analyzer in compilation process.
6. Construct a DFA for (0 * + 1 *) 011.
7. Write a lex program to identify comments in the program.
8.What is LEX? Explain, in detail, different sections of LEX program.
9. Write regular expressions for the following patterns
The set of words having a,e,i,o,u appearing in that order, although not
necessarily consecutively.
10. Explain the bootstrapping process with suitable diagrams.

Short answer questions:
1.Define compilers?
2.Define Interpreter?
3.Write about preprocessors?
4.Write the declaration of Macro function?
5.what is the pass and phase?
6.Write the role of Lexical analyzer?
7.What are the components are there for Lexical analyzer?
8.Write the structure of Lex?
9.What is the lex?
10. W h i ch o f th e f o l l ow i n g s t r i n g h as l e n g t h 0 ?
( a) s ( b ) a ( c ) a b c ( d ) ∈
11. If input alphabet is a then closure of a is
( a) { ∈ , a , a a } ( b ) { ∈ } ( c ) { a , a a - - - - - - } ( d ) { ∈ , a , a a , - - - - }
12. . A p p l i c a t i on o f F i n i te a u to m ata i s
( a) s c a n n e r ( b ) L e x i c a l an a l y z e r ( c ) s e m a nt i c a n al y z e r ( d ) p a rs e r

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.

Notes:Context free grammars
T- a set of tokens (terminal symbols)
V- a set of non terminal symbols
p- a set of productions of the form nonterminal String of terminals & non terminals
s- a start symbol
. A grammar derives strings by beginning with a start symbol and repeatedly replacing a non terminal by the right hand side of a production for that non terminal.
. The strings that can be derived from the start symbol of a grammar G form the language L(G) defined by the grammar.
we review the definition of a context free grammar and introduce terminology for talking about parsing. A context free grammar has four components:
A set of tokens , known as terminal symbols. Terminals are the basic symbols from which strings are formed.
A set of non-terminals . Non-terminals are syntactic variables that denote sets of strings. The non-terminals define sets of strings that help define the language generated by the grammar.
A set of productions . The productions of a grammar specify the manner in which the terminals and non-terminals can be combined to form strings. Each production consists of a non-terminal called the left side of the production, an arrow, and a sequence of tokens and/or on- terminals, called the right side of the production.
A designation of one of the non-terminals as the start symbol , and the set of strings it denotes is the language defined by the grammar.
The strings are derived from the start symbol by repeatedly replacing a non-terminal (initially the start symbol) by the right hand side of a production for that non-terminal.
Example:
list list + digit
list - digit
digit digit 0 1 . 9
is the grammar for a string of digits separated by + or -.
Derivation
list list + digit
list - digit + digit
digit - digit + digit
9 - digit + digit
9 - 5 + digit
9 - 5 + 2
Therefore, the string 9-5+2 belongs to the language specified by the grammar.

Parse tree for 9-5+2
Ambiguity
. A Grammar can have more than one parse tree for a string
Consider grammar
string string + string
string - string
0 1 . 9
. String 9-5+2 has two parse trees
A grammar is said to be an ambiguous grammar if there is some string that it can generate in more than one way (i.e., the string has more than one parse tree or more than one leftmost derivation). A language is inherently ambiguous if it can only be generated by ambiguous grammars.
For example, consider the following grammar:
string string + string
string - string
0 1 . 9
In this grammar, the string 9-5+2 has two possible parse trees as shown in the below fig..
Ambiguity .
. Ambiguity is problematic because meaning of the programs can be incorrect
. Ambiguity can be handled in several ways
- Enforce associativity and precedence
- Rewrite the grammar (cleanest way)
. There are no general techniques for handling ambiguity
. It is impossible to convert automatically an ambiguous grammar to an unambiguous one
Ambiguity is harmful to the intent of the program. The input might be deciphered in a way which was not really the intention of the programmer, as shown above in the 9-5+2 example. Though there is no general technique to handle ambiguity i.e., it is not possible to develop some feature which automatically identifies and removes ambiguity from any grammar. However, it can be removed, broadly speaking, in the following possible ways:-
Parsing
. Process of determination whether a string can be generated by a grammar
. Parsing falls in two categories:
- Top-down parsing: Construction of the parse tree starts at the root (from the start symbol) and proceeds towards leaves (token or terminals)
- Bottom-up parsing: Construction of the parse tree starts from the leaf nodes (tokens or terminals of the grammar) and proceeds towards root (start symbol)
Parsing is the process of analyzing a continuous stream of input (read from a file or a keyboard, for example) in order to determine its grammatical structure with respect to a given formal grammar. The task of the parser is essentially to determine if and how the input can be derived from the start symbol within the rules of the formal grammar. This can be done in essentially two ways:
. Top-down parsing - A parser can start with the start symbol and try to transform it to the input. Intuitively, the parser starts from the largest elements and breaks them down into incrementally smaller parts. LL parsers are examples of top-down parsers. We will study about these in detail in the coming slides.
. Bottom-up parsing - A parser can start with the input and attempt to rewrite it to the start symbol. Intuitively, the parser attempts to locate the most basic elements, then the elements containing these, and so on. LR parsers are examples of bottom-up parsers. We will study about these in detail in the coming slides.
TOP DOWN PARSING :
construct a parse tree for a string, we initially create a tree consisting of a single node (root node) labeled by the start symbol. Thereafter, we repeat the following steps to construct the of parse tree by starting at the root labeled by start symbol:
. At node labeled with non terminal A select one of the production of A and construct the children nodes.. Find the next node at which subtree is constructed.
Parse array [ num dotdot num ] of integer
. Cannot proceed as non terminal "simple" never generates a string beginning with token "array". Therefore, requires back-tracking.
. Back-tracking is not desirable, therefore, take help of a "look-ahead" token. The current token is treated as look- ahead token. ( restricts the class of grammars )
To construct a parse tree corresponding to the string array [ num dotdot num ] of integer , we start with the start symbol type . Then, we use the production type à simple to expand the tree further and construct the first child node. Now, finally, the non-terminal simple should lead to the original string. But, as we can see from the grammar, the expansion of the non-terminal simple never generates a string beginning with the token "array". So, at this stage, we come to know that we had used the wrong production to expand the tree in the first step and we should have used some other production. So, we need to backtrack now. This backtracking tends to cause a lot of overhead during the parsing of a string and is therefore not desirable. To overcome this problem, a " look-ahead " token can be used. In this method, the current token is treated as look-ahead token and the parse tree is expanded by using the production which is determined with the help of the look-ahead token.
Left recursion
. A top down parser with production A A α may loop forever
. From the grammar A A α b left recursion may be eliminated by transforming the grammar to
A b R
R α R ε
Left recursion is an issue of concern in top down parsers. A grammar is left-recursive if we can find some non-terminal A which will eventually derive a sentential form with itself as the left-symbol. In other words, a grammar is left recursive if it has a non terminal A such that there is a derivation
A + A a for some string a . These derivations may lead to an infinite loop. Removal of left recursion:
For the grammar A A a ß , left recursion can be eliminated by transforming the original grammar as:
A ß R
R a R ε

This slide shows the parse trees corresponding to the string ßa * using the original grammar (with left factoring) and the modified grammar (without left factoring).
Example
. Consider grammar for arithmetic expressions
E E + T T
T T * F F
F ( E ) id
. After removal of left recursion the grammar becomes
E T E'
E' + T E' ε
T F T'
T' * F T' ε
F ( E ) id
As another example, a grammar having left recursion and its modified version with left recursion removed has been shown.
Removal of left recursion
The general algorithm to remove the left recursion follows. Several improvements to this method have been made. For each rule of the form
A A a1 A a2 ... A a m β 1 β 2 .. β n
Where:
. A is a left-recursive non-terminal.
. a is a sequence of non-terminals and terminals that is not null ( a≠ε ).
. ß is a sequence of non-terminals and terminals that does not start with A .
Replace the A-production by the production:
A β 1 A' β2 A' ... βn A'
And create a new non-terminal
A' a1 A' a2 A' ... am A' ε
This newly created symbol is often called the "tail", or the "rest".
Left recursion hidden due to many productions
.Left recursion may also be introduced by two or more grammar rules. For example
S Aa b
A Ac Sd ε
there is a left recursion because
S Aa Sda
. In such cases, left recursion is removed systematically
- Starting from the first rule and replacing all the occurrences of the first non terminal symbol
- Removing left recursion from the modified grammar
What we saw earlier was an example of immediate left recursion but there may be subtle cases where left recursion occurs involving two or more productions. For example in the grammar
S A a b
A A c S d e
there is a left recursion because
S A a S d a
More generally, for the non-terminals A 0, A 1,..., An , indirect left recursion can be defined as being of the form:
An A1 a 1 .
A1 A2 a2
. .
A n An a(n+1) .
Where a 1 , a2 ,..., a n are sequences of non-terminals and terminals.
Following algorithm may be used for removal of left recursion in general case:
Input : Grammar G with no cycles or e -productions.
Output: An equivalent grammar with no left recursion .
Algorithm:
Arrange the non-terminals in some order A1 , A2 , A3 ..... An .
for i := 1 to n do begin
replace each production of the form Ai Ajγ
by the productions A i d1 γ d2 γ ........... dkγ
where Aj d1 d2 ......... dk are all the current Aj -productions;
end
eliminate the immediate left recursion among the Ai-productions.
end.
Removal of left recursion due to many productions .
. After the first step (substitute S by its rhs in the rules) the grammar becomes
S Aa b
A Ac Aad bd ε
. After the second step (removal of left recursion) the grammar becomes
S Aa b
A bdA' A'
A' cA' adA' ε
After the first step (substitute S by its R.H.S. in the rules), the grammar becomes
S A a b
A A c A a d b d ε
After the second step (removal of left recursion from the modified grammar obtained after the first step), the grammar becomes
S A a b
A b d A' A'
A' c A' a d A' ε
Left factoring
. In top-down parsing when it is not clear which production to choose for expansion of a symbol
defer the decision till we have seen enough input.
In general if A αβ1 αβ2
defer decision by expanding A to a A'
we can then expand A' to β1 or β2
. Therefore A αβ1 αβ2
transforms to
A α A'
A' β1 β2
Left factoring is a grammar transformation that is useful for producing a grammar suitable for predictive parsing. The basic idea is that when it is not clear which of two or more alternative productions to use to expand a non-terminal A, we defer the decision till we have seen enough input to make the right choice.
In general if A α ß 1 α ß 2 , we defer decision by expanding A to a A'.
and then we can expand A ' to ß1 or ß1
Therefore A α ß1 α ß2 transforms to
A α A'
A ' ß1 ß2
Predictive parsers
. A non recursive top down parsing method
. Parser "predicts" which production to use
. It removes backtracking by fixing one production for every non-terminal and input token(s)
. Predictive parsers accept LL(k) languages
- First L stands for left to right scan of input
- Second L stands for leftmost derivation
- k stands for number of lookahead token
. In practice LL(1) is used
In general, the selection of a production for a non-terminal may involve trial-and-error; that is, we may have to try a production and backtrack to try another production if the first is found to be unsuitable. A production is unsuitable if, after using the production, we cannot complete the tree to match the input string. Predictive parsing is a special form of recursive-descent parsing, in which the current input token unambiguously determines the production to be applied at each step. After eliminating left recursion and left factoring, we can obtain a grammar that can be parsed by a recursive-descent parser that needs no backtracking . Basically, it removes the need of backtracking by fixing one production for every non-terminal and input tokens. Predictive parsers accept LL(k) languages where:
. First L : The input is scanned from left to right.
. Second L : Leftmost derivations are derived for the strings.
. k : The number of lookahead tokens is k.
However, in practice, LL(1) grammars are used i.e., one lookahead token is used.
Predictive parsing
. Predictive parser can be implemented by maintaining an external stack
Parse table is a two dimensional array M[X,a] where "X" is a non terminal and "a" is a terminal of the grammar
It is possible to build a non recursive predictive parser maintaining a stack explicitly, rather than implicitly via recursive calls. A table-driven predictive parser has an input buffer, a stack, a parsing table, and an output stream. The input buffer contains the string to be parsed, followed by $, a symbol used as a right end marker to indicate the end of the input string. The stack contains a sequence of grammar symbols with a $ on the bottom, indicating the bottom of the stack. Initially the stack contains the start symbol of the grammar on top of $. The parsing table is a two-dimensional array M [X,a] , where X is a non-terminal, and a is a terminal or the symbol $ . The key problem during predictive parsing is that of determining the production to be applied for a non-terminal. The non-recursive parser looks up the production to be applied in the parsing table.
Algoritm:
Example
. Consider the grammar
E T E'
E' +T E' ε
T F T'
T' * F T' ε
F ( E ) id
As an example, we shall consider the grammar shown.
Parse table for the grammar
Blank entries are error states. For example E cannot derive a string starting with '+'
A predictive parsing table for the grammar in the previous slide is shown. In the table, the blank entries denote the error states; non-blanks indicate a production with which to expand the top nonterminal on the stack
. Constructing parse table
. Table can be constructed if for every non terminal, every lookahead symbol can be handled by at most one production
. First( a ) for a string of terminals and non terminals a is
- Set of symbols that might begin the fully expanded (made of only tokens) version of a
. Follow(X) for a non terminal X is
- set of symbols that might follow the derivation of X in the input stream
The construction of the parse table is aided by two functions associated with a grammar G. These functions, FIRST and FOLLOW , allow us to fill in the entries of a predictive parsing table for G, whenever possible. If α is any string of grammar symbols, FIRST ( α ) is the set of terminals that begin the strings derived from α . If α * ε , then ε is also in FIRST( α ).
If X is a non-terminal, FOLLOW ( X ) is the set of terminals a that can appear immediately to the right of X in some sentential form, that is, the set of terminals a such that there exists a derivation of the form S * α A a ß for some α and ß . Note that there may, at some time, during the derivation, have been symbols between A and a , but if so, they derived ε and disappeared. Also, if A can be the rightmost symbol in some sentential form, then $ is in FOLLOW(A).
Example
. For the expression grammar
E T E'
E' +T E' ε
T F T'
T' * F T' ε
F ( E ) id
First(E) = First(T) = First(F) = { (, id }
First(E') = {+, ε }
First(T') = { *, ε }
Consider the grammar shown above. For example, id and left parenthesis are added to FIRST(F) by rule (3) in the definition of FIRST with i = 1 in each case, since FIRST(id) = {id} and FIRST{'('} = { ( } by rule (1). Then by rule (3) with i = 1, the production T = FT' implies that id and left parenthesis are in FIRST(T) as well. As another example, e is in FIRST(E') by rule (2).
Compute follow sets
1. Place $ in follow(S)
2. If there is a production A a B ß then everything in first( ß ) (except ε ) is in follow(B)
3. If there is a production A a B then everything in follow(A) is in follow(B)
4. If there is a production A a B ß and First( ß ) contains e then everything in follow(A) is in follow(B)
Since follow sets are defined in terms of follow sets last two steps have to be repeated until follow sets converge
To compute FOLLOW ( A ) for all non-terminals A , apply the following rules until nothing can be added to any FOLLOW set:
1. Place $ in FOLLOW(S), where S is the start symbol and $ is the input right endmarker.
2. If there is a production A a Bß, then everything in FIRST(ß) except for e is placed in FOLLOW(B).
3. If there is a production A a ß, or a production A a Bß where FIRST(ß) contains e (i.e., ß * e ), then everything in FOLLOW(A) is in FOLLOW(B).
Error handling
. Stop at the first error and print a message
- Compiler writer friendly
- But not user friendly
. Every reasonable compiler must recover from errors and identify as many errors as possible
. However, multiple error messages due to a single fault must be avoided
. Error recovery methods
- Panic mode
- Phrase level recovery
- Error productions
- Global correction
Error handling and recovery is also one of the important tasks for a compiler. Errors can occur at any stage during the compilation. There are many ways in which errors can be handled. One way is to stop as soon as an error is detected and print an error message. This scheme is easy for the programmer to program but not user friendly. Specifically, a good parser should, on encountering a parsing error, issue an error message and resume parsing in some way, repairing the error if possible. However, multiple error messages due to a single fault are undesirable and tend to cause confusion if displayed. Error recovery is thus a non trivial task. The following error recovery methods are commonly used:
1. Panic Mode
2. Phrase level recovery
3. Error productions
4. Global correction
Panic mode
. Simplest and the most popular method
. Most tools provide for specifying panic mode recovery in the grammar
. When an error is detected
- Discard tokens one at a time until a set of tokens is found whose role is clear
- Skip to the next token that can be placed reliably in the parse tree
Let us discuss each of these methods one by one. Panic mode error recovery is the simplest and most commonly used method. On discovering the error, the parser discards input symbols one at a time until one of the designated set of synchronizing tokens is found. The synchronizing tokens are usually delimiters, such as semicolon or end , whose role in the source program is clear. The compiler designer must select the synchronizing tokens appropriate for the source language, of course.
Panic mode .
. Consider following code
begin
a = b + c;
x = p r ;
h = x < 0;
end;
. The second expression has syntax error
. Panic mode recovery for begin-end block skip ahead to next ';' and try to parse the next expression
. It discards one expression and tries to continue parsing
. May fail if no further ';' is found
Consider the code shown in the example above. As we can see, the second expression has a syntax error. Now panic mode recovery for begin-end block states that in this situation skip ahead until the next ' ; ' is seen and try to parse the following expressions thereafter i.e., simply skip the whole expression statement if there is an error detected. However, this recovery method might fail if no further ' ; ' is found. While panic-mode correction often skips a considerable amount of input without checking it for additional errors, it has the advantage of simplicity and, unlike some other methods to be considered later, it is guaranteed not to go into an infinite loop. In situations where multiple errors in the same statement are rare, this method may be quite adequate.
Phrase level recovery
. Make local correction to the input
. Works only in limited situations
- A common programming error which is easily detected
- For example insert a ";" after closing "}" of a class definition
. Does not work very well!
Phrase level recovery is implemented by filling in the blank entries in the predictive parsing table with pointers to error routines. These routines may change, insert, or delete symbols on the input and issue appropriate error messages. They may also pop from the stack. It basically makes local corrections to the input; that is, it may replace a prefix of the remaining input by some string that allows the parser to continue. A typical local correction would be to replace a comma by a semicolon, delete an extraneous semicolon, or insert a missing semicolon. This type of replacement can correct any input string and has been used in several error-repairing compilers. However, its major drawback is the difficulty it has in coping with situations in which the actual error has occurred before the point of detection.
Error productions
. Add erroneous constructs as productions in the grammar
. Works only for most common mistakes which can be easily identified
. Essentially makes common errors as part of the grammar
. Complicates the grammar and does not work very well
If we have a good idea of the common errors that might be encountered, we can augment the grammar for the language at hand with productions that generate the erroneous constructs. We then use the grammar augmented by these error productions to construct a parser. If an error production is used by a parser, we can generate appropriate error diagnostics to indicate the error construct that has been recognized in the input. The main drawback of this approach is that it tends to complicate the grammar and thus does not work very well.
Global corrections
. Considering the program as a whole find a correct "nearby" program
. Nearness may be measured using certain metric
. PL/C compiler implemented this scheme: anything could be compiled!
. It is complicated and not a very good idea!
Ideally, we would like a compiler to make as few changes as possible in processing the incorrect input string. There are algorithms for choosing a minimal sequence of changes to obtain globally least-cost correction. Given an incorrect input string x and a grammar G, these algorithms will find a parse tree for a related string y such that the number of insertions, deletions, and changes of tokens required to transform x into y is as small as possible. Unfortunately, these methods are in general too costly to implement in terms of time and space, so these techniques are currently only of theoretical interest
Error Recovery in LL(1) parser
. Error occurs when a parse table entry M[A,a] is empty
. Skip symbols in the input until a token in a selected set (synch) appears
. Place symbols in follow(A) in synch set. Skip tokens until an element in follow(A) is seen. Pop(A) and continue parsing
. Add symbol in first(A) in synch set. Then it may be possible to resume parsing according to A if a symbol in first(A) appears in input.
Let us consider error recovery in an LL(1) parser by panic-mode recovery method. An error occurs when the terminal on top of the stack does not match the next input symbol or when non-terminal A is on top of the stack, a is the next input symbol, and the parsing table entry M[A, a ] is empty. Panic-mode error recovery is based on the idea of skipping symbols on the input until a token in a selected set of synchronizing tokens appears. Its effectiveness depends on the choice of synchronizing set. The sets should be chosen so that the parser recovers quickly from errors that are likely to occur in practice. Some heuristics are as follows:
1. As a starting point, we can place all symbols in FOLLOW(A) into the synchronizing set for non-terminal A. If we skip tokens until an element of FOLLOW(A) is seen and pop A from the stack, it is likely that parsing can continue.
2. If we add symbols in FIRST(A) to the synchronizing set for non-terminal A, then it may be possible to resume parsing according to A if a symbol in FIRST(A) appears in the input.
Error Recovery in LL(1) parser
. Error occurs when a parse table entry M[A,a] is empty
. Skip symbols in the input until a token in a selected set (synch) appears
. Place symbols in follow(A) in synch set. Skip tokens until an element in follow(A) is seen. Pop(A) and continue parsing
. Add symbol in first(A) in synch set. Then it may be possible to resume parsing according to A if a symbol in first(A) appears in input.
Let us consider error recovery in an LL(1) parser by panic-mode recovery method. An error occurs when the terminal on top of the stack does not match the next input symbol or when non-terminal A is on top of the stack, a is the next input symbol, and the parsing table entry M[A, a ] is empty. Panic-mode error recovery is based on the idea of skipping symbols on the input until a token in a selected set of synchronizing tokens appears. Its effectiveness depends on the choice of synchronizing set. The sets should be chosen so that the parser recovers quickly from errors that are likely to occur in practice. Some heuristics are as follows:
1. As a starting point, we can place all symbols in FOLLOW(A) into the synchronizing set for non-terminal A. If we skip tokens until an element of FOLLOW(A) is seen and pop A from the stack, it is likely that parsing can continue.
2. If we add symbols in FIRST(A) to the synchronizing set for non-terminal A, then it may be possible to resume parsing according to A if a symbol in FIRST(A) appears in the input.
Essay type questions:
1.What is recursive descent parser? Construct recursive descent parser for the
following grammar.
E à E + TT T à TFF F à F_ab
2. What is ambiguous grammar? Eliminate ambiguities for the grammar:
Eà E + EE_E(E)id.

3. Consider the following grammar.
Sà 0A1B0 1 Aà 0S1B 1 B à 0A1 S
Construct leftmost derivations and parse trees for the following sentences
i. 0101 ii. 1100101
4. Construct predictive parsing table for the following grammar.
Eà T E′ E′ à +T E′ε T à F T′ T′ à ∗FT′ε F à (E)id
5. Write an algorithm for construction of predictive parsing table.
6. Consider the following grammar
E à T + ET Tà V_TV Và id
Write down the procedures for the nonterminals of the grammar to make a
recursive descent parser
7.Remove tha left Recursion for the following grammar
E à T E′ E′ à +T E′ε T à F T′ T′ à ∗FT′ε F à (E)id
8. Write about top down parsing .and What are the limitations of recursive descent porser.
9. Consider the following grammar
Sà (L) a L à L, S S
Construct leftmost derivations and parse trees for the following sentences:
i. (a,(a,a)) ii. (a,((a,a),(a,a))).
10. What are the difficulties in top down parsing? Explain in detail.
Short answer questions:
1. Define Context free grammar?
2.What is Top down parsing?
3.What is Backtracking,?
4.Expand the LL (1)?
5.Define recursive descent parsing?
6. What is predictive parsing
7What is Left most derivation?
8.What is Right most derivation?
9.What is a Parser?
10.Define parse tree?
11. What Left Recursion?
12.What is a Left Factoring?
13.Draw the structure of Parse table?
14. A g r am m a r i s a d e v i c e
( a) c a n ’ t s ay ( b ) c o gn i t i ve ( c ) a c c e p t d)None
15. A ny s t r i n g of t e r m i n al s t h at c an b e g e n e r a te d by t h e f o l l ow i n g C FG i s S → X Y X → a x b X a Y → Ya Y b a
( a) h a s a t l e as t on e b ( b ) h a s a t l e as t two a ’ s ( c ) h a s n o c o n s e c ut i ve a ’ s or b ’ s
( d ) s h o u l d e n d i n a ’ a ’

UNIT III
BOTTOM UP PARSING: Shift Reduce parsing, LR and LALR parsing, Error recovery in parsing,
handling ambiguous grammar, YACCautomatic
parser generator

Bottom up parsing
. Construct a parse tree for an input string beginning at leaves and going towards root OR
. Reduce a string w of input to start symbol of grammar
Consider a grammar
S aABe
A Abc b
B d
And reduction of a string
a b b c d e
a A b c d e
a A d e
a A B e
S
Right most derivation
S a A B e
a A d e
a A b c d e
a b b c d e
We will now study a general style of bottom up parsing, also known as shift-reduce parsing. Shift-reduce parsing attempts to construct a parse tree for an input string beginning at the leaves (the bottom) and working up towards the root (the top). We can think of the process as one of "reducing" a string w to the start symbol of a grammar. At each reduction step a particular substring matching the right side of a production is replaced by the symbol on the left of that production, and if the substring is chosen correctly at each step, a rightmost derivation is traced out in reverse. For example, consider the grammar
S aABe
A Abc b
B d
The sentence a b b c d e can be reduced to S by the following steps:
a b b c d e
a A b c d e
a A d e
a A B e
S
These reductions trace out the following right-most derivation in reverse:
S a A B e
a A d e
a A b c d e
a b b c d e
Shift reduce parsing
. Split string being parsed into two parts
- Two parts are separated by a special character "."
- Left part is a string of terminals and non terminals
- Right part is a string of terminals
. Initially the input is .w
A convenient way to implement a shift reduce parser is by using an input buffer to hold the string w to be parsed. At any stage, the input string is split into two parts which are separated by the character ' . '. The left part consists of terminals and non-terminals while the right part consists of terminals only. Initially, the string " .w " is on the input.
Shift reduce parsing .
. Bottom up parsing has two actions
. Shift : move terminal symbol from right string to left string
if string before shift is a .pqr
then string after shift is a p.qr
.Reduce : immediately on the left of "." identify a string same as RHS of a production and replace it by LHS
if string before reduce action is aß .pqr
and A ß is a production
then string after reduction is a A.pqr
There are two primary operations of a shift-reduce parser namely (1) shift and (2) reduce. In a shift action, the next input symbol is shifted from right string to the left string. For example, if string before shift is " a .pqr " then string after shift would be " a p.qr " . In a reduce action, the parser identifies a string which is same as the RHS of a production and replace it by the non-terminal at LHS. For example, if string before reduce action is " aß .pqr " and A ß is a production, then string after reduction is " a A.pqr " .
Bottom up parsing .
. A more powerful parsing technique
. LR grammars - more expensive than LL
. Can handle left recursive grammars
. Can handle virtually all the programming languages
. Natural expression of programming language syntax
. Automatic generation of parsers (Yacc, Bison etc.)
. Detects errors as soon as possible
. Allows better error recovery
Bottom-up parsing is a more powerful parsing technique. Listed are some of the advantages of bottom-up parsing: . A more powerful parsing technique . It is capable of handling almost all the programming languages. . It can fastly handle left recursion in the grammar. . It allows better error recovery by detecting errors as soon as possible.

LR parsing
. Input contains the input string. . Stack contains a string of the form S 0 X 1 S1 X2 ..X n Sn where each Xi is a grammar symbol and each S i is a state. . Tables contain action and goto parts. . action table is indexed by state and terminal symbols. . goto table is indexed by state and non terminal symbols.
Actions in an LR (shift reduce) parser
. Assume Si is top of stack and ai is current input symbol
. Action [Si ,a i ] can have four values
1. shift ai to the stack and goto state Sj
2. reduce by a rule
3. Accept
4. error
Example

Consider the grammar And its parse table
E E + T T T T * F F F ( E ) id

Constructing parse table
Augment the grammar
. G is a grammar with start symbol S
. The augmented grammar G' for G has a new start symbol S' and an additional production S' S
. When the parser reduces by this rule it will stop with accept
The first step in the process of constructing the parse table, is to augment the grammar to include one more rule. The input is accepted by the parser, only when it reduces with this rule. We add a new start symbol in the augmented grammar (say S' ) and another rule ( S' S ), where S is the start symbol in the original grammar. The parser stops and accepts only when it reduces with this rule.
LR(0) items
. An LR(0) item of a grammar G is a production of G with a special symbol "." at some position of the right side
. Thus production A XYZ gives four LR(0) items
A .XYZ
A X.YZ
A XY.Z
A XYZ.
. An item indicates how much of a production has been seen at a point in the process of parsing
- Symbols on the left of "." are already on the stacks
- Symbols on the right of "." are expected in the input
An LR(0) item represents a production in such a way, that you keep track of the input already read (i.e., present on the stack) and the input yet to be expected. Consider a typical example A Y.XZ , here the special symbol " . " means that the expression to the left of it (i.e., Y ) is present on the stack, while the one of its right is yet expected to complete this production.
Example
Grammar:
I 2 : goto(I 0 ,T)
I6 : goto(I1 ,+)
I9 : goto(I6 ,T)
E ' E
E T.
E E + .T
E E + T.
E E+T T
T T. *F
T .T * F
T T. * F
T T*F F
I3 : goto(I0 ,F)
T .F
goto(I6 ,F) is I 3
F (E) id
T F.
F .(E)
goto(I6 ,( ) is I4
I 0 : closure(E ' .E)
I4 : goto( I0 ,( )
F .id
goto(I6 ,id) is I5
E ' .E
F (.E)
I 7 : goto(I2 ,*)
I 10 : goto(I 7 ,F)
E .E + T
E .E + T
T T * .F
T T * F.
E .T
E .T
F .(E)
goto(I7 ,( ) is I4
T .T * F
T .T * F
F .id
goto(I7 ,id) is I5
T .F
T .F
I 8 : goto(I4 ,E)
I 11 : goto(I8 ,) )
F .(E)
F .(E)
F (E.)
F (E).
F .id
F .id
E E. + T
goto(I8 ,+) is I6
I 1 : goto(I0 ,E)
I5 : goto( I0 ,id)
goto(I4 ,T) is I2
goto(I9 ,*) is I 7
E ' E.
F id.
goto(I 4 ,F) is I3

E E. + T

goto(I 4 ,( ) is I4

goto(I4 ,id) is I5

Let's take an example here. We have earlier calculated the closure I0 . Here, notice that we need to calculate goto (I0 ,E), goto(I0 ,T), goto(I 0 , F) , goto (I0 , ( ) and goto(I0 , id). For calculating goto(I0 , E), we take all the LR(0) items in I 0 , which expect E as input (i.e. are of the form A α .E ß ), and advance ".". Closure is then taken of this set. Here, goto(I 0 , E) will be closure { E ' E. , E E.+T }. The closure adds no item to this set, and hence goto(I 0 , E)={ E ' E. , E E.+T }.

Essay type questions:

1. Construct SLR parsing table for the following grammar.
Sà ASb A à SAa
2. Construct LALR parsing table for the following grammar
S à CC C à cCd
3. What are the common conflicts that can be encountered in shift - reduce
parser.
4. Construct SLR parsing table for the following grammar.
R à R ′′ R RR R∗ (R) a b
5.Explain about the Shift Reduced parser.
6. Explain canonical LR parsing.
7. What is an operator grammar? Give an example.
8. What are the common conflicts that can be encountered in shift - reduce
parser.
9. Explain the stack implementation of shift reduce parsing method with an
example.
10. Define handle. Give suitable example
Short answer questions:
1.What is Bottom up parsing?
2. Define Shift Reduce parsing?
3.What is LR parser?
4.What is SLR parser?
5.Define CLR parser?
6.Define LALR parsing?
7.What is Error recovery in parsing?
8.Define ambiguous grammar?
9.Write the structure of YACC?
10.What is automatic parser generator?
11.Write the role of Parser?
12.What is the use of parser?
13.How to avoid the ambiguity in a grammar?
14.Which parser is stronger in all LR family?
15.Write the formula for finding the look ahead symbol in CLR parser ?

UNIT IV
SEMANTIC ANALYSIS: Intermediate forms of source Programs abstract syntax tree,
Polish notation and 3 address codes. Attributed grammars, SDT,
Conversion of popular programming languages language Constructs into Intermediate code forms, Type checker.

Abstract Syntax Tree/DAG
. Condensed form of a parse tree
. useful for representing language constructs
. Depicts the natural hierarchical structure of the source program
- Each internal node represents an operator
- Children of the nodes represent operands
- Leaf nodes represent operands
. DAG is more compact than abstract syntax tree because common sub expressions are eliminated
A syntax tree depicts the natural hierarchical structure of a source program. Its structure has already been discussed in earlier lectures.
DAGs are generated as a combination of trees: operands that are being reused are linked together, and nodes may be annotated with variable names (to denote assignments). This way, DAGs are highly compact, since they eliminate local common sub-expressions. On the other hand, they are not so easy to optimize, since they are more specific tree forms. However, it can be seen that proper building of DAG for a given sequence of instructions can compactly represent the outcome of the calculation.
An example of a syntax tree and DAG has been given in the next slide .
a := b * -c + b * -c
You can see that the node " * " comes only once in the DAG as well as the leaf " b ", but the meaning conveyed by both the representations (AST as well as the DAG) remains the same.

Postfix notation is a way of writing algebraic expressions without the use of parentheses or rules of operator precedence. The expression above would be written as AB+CD-/ in postfix notation. (Don't panic! We'll explain this in a moment.) Postfix notation had its beginnings in the work of Jan L ukasiewicz * (1878-1956), a Polish logician, mathematician, and philosopher. L ukasiewicz developed a parenthesis-free prefix notation that came to be called Polish notation and a postfix notation now called Reverse Polish Notation or RPN. From these ideas, Charles Hamblin developed a postfix notation for use in computers. L ukasiewicz's work dates from about 1920. Hamblin's work on postfix notation was in the mid-1950's. Calculators, notably those from Hewlett-Packard, used various postfix formats beginning in the 1960s. Postfix notation is a linearized representation of a syntax tree; it is a list of nodes of the tree which appear immediately after its children. You must read the three points written in the slide above to see how postfix expressions are made corresponding to a set of expressions.
Three address code
. It is a sequence of statements of the general form X := Y op Z where
- X, Y or Z are names, constants or compiler generated temporaries
- op stands for any operator such as a fixed- or floating-point arithmetic operator, or a logical operator
Three address code is a sequence of statements of the general form: x := y op z where x, y and z are names, constants, or compiler generated temporaries. op stands for any operator, such as a fixed or floating-point arithmetic operator, or a logical operator or boolean - valued data. Compilers use this form in their IR.

Three address instructions
. Assignment
. Function
- x = y op z
- param x
- x = op y
- call p,n
- x = y
- return y
. Jump

- goto L
. Pointer
- if x relop y goto L
- x = &y
.Indexed assignment
- x = *y
- x = y[i]
- *x = y
- x[i] = y

The various types of the three-address codes. Statements can have symbolic label and there are statements for flow of control. A symbolic label represents the index of a three-address statement in the array holding intermediate code. Actual indices can be substituted for the labels either by making a separate pass, or by using backpatching.
Declarations
For each name create symbol table entry with information like type and relative address
P {offset=0} D

D D ; D

D id : T
enter(id.name, T.type, offset);

offset = offset + T.width
T integer
T.type = integer; T.width = 4
T real
T.type = real; T.width = 8

In the translation scheme nonterminal P generates a sequence of declarations of the form id : T . Before the first declaration is considered, offset is set to 0. As each new name is seen, that name is entered in the symbol table with the offset equal to the current value of offset, and offset is incremented by the width of the data object denoted by the name.
Names in the Symbol table
S id := E
{p = lookup(id.place);
if p <> nil then emit(p := E.place)
else error}
E id
{p = lookup(id.name);
if p <> nil then E.place = p
else error}
Type conversion within assignments
E E1 + E2
E.place= newtmp;
if E1 .type = integer and E2 .type = integer
then emit(E.place ':=' E 1 .place 'int+' E 2 .place);
E.type = integer;
.
similar code if both E1 .type and E2 .type are real
.
else if E 1 .type = int and E2 .type = real
then
u = newtmp;
emit(u ':=' inttoreal E 1 .place);
emit(E.place ':=' u 'real+' E2 .place);
E.type = real;
.
similar code if E1 .type is real and E2 .type is integer
Boolean Expressions
. compute logical values
. change the flow of control
. boolean operators are: and or not
Boolean expressions are used to compute logical values and as conditional expressions in statements that alter flow of control such as if-then statements. Boolean expressions are composed of the Boolean operators and, or, not - applied to boolean variables or relational expressions.
Relational expressions are of the form E1 relop E2 where E1 and E2 are arithmetic expressions. Boolean expressions can be generated by the following grammar-
E -> E or E E and E not E (E) id relop id true false
Syntax directed translation of boolean expressions
E E 1 or E2
E.place := newtmp
emit(E.place ':=' E 1 .place 'or' E2 .place)
E E1 and E 2
E.place:= newtmp
emit(E.place ':=' E 1 .place 'and' E2 .place)
E not E1
E.place := newtmp
emit(E.place ':=' 'not' E1 .place)
E (E1 ) E.place = E1 .place
E id1 relop id2
E.place := newtmp
emit(if id1.place relop id2.place goto nextstat+3)
emit(E.place = 0) emit(goto nextstat+2)
emit(E.place = 1)
E true
E.place := newtmp
emit(E.place = '1')
E false
E.place := newtmp
emit(E.place = '0')
In the above scheme, nextstat gives the index of the next three address code in the output sequence and emit increments nextstat after producing each three address statement.
Example: Code for a < b or c < d and e < f

100: if a < b goto 103
if e < f goto 111
101: t1 = 0
109: t3 = 0
102: goto 104
110: goto 112
103: t1 = 1
111: t3 = 1
104:
112:
if c < d goto 107
t4 = t2 and t3
105: t2 = 0
113: t5 = t1 or t 4
106: goto 108

107: t2 = 1

108:

A relational expression a < b is equivalent to the conditional statement if a < b then 1 else 0 and three address code for this expression is:
100: if a < b goto 103.
101: t = 0
102: goto 104
103: t = 1
104:
It is continued from 104 in the same manner as the above written block.

S if E then S1 else S2
E.true = newlabel
E.false = newlabel
S 1 .next = S.next
S2 .next = S.next
S.code = E.code
gen(E.true ':')
S 1 .code
gen(goto S.next)
gen(E.false ':')
S 2 .code
For if-then-else
S -> if E then S1 else S2
E.true = newlabel
E.false = newlabel
S1.next = S.next
S2.next = S.next
S.code = E.code gen(E.true ':') S1.code gen('goto' S.next) gen(E.false ':') S2.code
In the above code, the labels E.true and E.false created are associated with the first three address code instructions for S1 and S2 respectively, so that if E is true, jump to S1 occurs and if E is false jump to S2 occurs. An explicit goto S.next is required after the code of S1 to ensure that after execution of code for S1 control moves to the statement after S instead of falling through the code of S2, in case E is true.

S while E do S 1
S.begin = newlabel
E.true = newlabel
E.false = S.next
S 1 .next = S.begin
S.ocde = gen(S.begin ':')
E.code
gen(E.true ':')
S 1 .code
gen(goto S.begin)
For while-do
S -> while E do S1
S.begin = newlabel
E.true = newlabel
E.false = S.next
S1.next = S.begin
S.code = gen(S.begin ':') E.code gen(E.true ':') S1.code gen(goto S.begin)
Control flow translation of boolean expression

E E1 or E 2
E1 .true := E.true

E 1 .false := newlabel

E2 .true := E.true

E2 .false := E.false

E.code := E 1 .code gen(E 1 .false) E2 .code
E E 1 and E2
E 1 .true := new label

E 1 false := E.false

E2 .true := E.true

E2 false := E.false

E.code := E 1 .code gen(E1 .true) E2 .code
Case Statement
. switch expression
begin
case value: statement
case value: statement
..
case value: statement
default: statement
end
.evaluate the expression
. find which value in the list of cases is the same as the value of the expression
. - Default value matches the expression if none of the values explicitly mentioned in the cases matches the expression
. execute the statement associated with the value found

Essay type questions:
1.Write a S - attributed grammar to connect the fopllowing grammar with prefix
rotator
Là E E à E+T E-T T T à T*F T/F F
F à P " F P P à (E) P à id.
2. Write short notes on the following:
(a) S-attributed definitions.(b) I-attributed definitions.(c) Dependency graph.

3. What is a syntax tree? Write syntax directed definition for constructing a
syntax tree for an expression. The grammar for an expression is given below.
E à E + T E − T T T à (E) id num
4. Write a note on polymorphic functions.
5. Construct triples of an expression: a _ −(b + c).
6. Write a note on the specification of a simple type checker
7. Write a detail notes on type conversion
8.Construct a Quadruple form for the following expression :x:=b*-c + b*-c
9.Write about three address form with example?
10.Write about abstract syntax tree, Polishing notation and DAG?

Short answer questions?
1. Write the role of Semantic Analysis?
2.What is the role of Intermediate forms of source Programs?
3. what is a abstract syntax tree?
4.Define polish notation?
5.What are the three address forms?
6.Define Attributed grammar?
7.What is a Syntax directed translation?
8.What is the Syntax directed definition?
9.What are the programming languages language Constructs
10.What is Type checker?
11.Define Type expression?
12.What is the role of Intermediate code generator?
13.What is the type conversion?
14.Write the difference between S-Attribute and I-Attribute?
15.What is the L-Attributed Grammar?
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 for arrays, strings and records.

Symbol Table
. Compiler uses symbol table to keep track of scope and binding information about names
. symbol table is changed every time a name is encountered in the source; changes to table occur
- if a new name is discovered
- if new information about an existing name is discovered
. Symbol table must have mechanism to:
- add new entries
- find existing information efficiently
. Two common mechanism:
- linear lists, simple to implement, poor performance
- hash tables, greater programming/space overhead, good performance
. Compiler should be able to grow symbol table dynamically
. if size is fixed, it must be large enough for the largest program
A compiler uses a symbol table to keep track of scope and binding information about names. It is filled after the AST is made by walking through the tree, discovering and assimilating information about the names. There should be two basic operations - to insert a new name or information into the symbol table as and when discovered and to efficiently lookup a name in the symbol table to retrieve its information.
Two common data structures used for the symbol table are -
1. Linear lists:- simple to implement, poor performance.
2. Hash tables:- greater programming/space overhead, good performance.
Ideally a compiler should be able to grow the symbol table dynamically, i.e., insert new entries or information as and when needed. But if the size of the table is fixed in advance then ( an array implementation for example), then the size must be big enough in advance to accommodate the largest possible program.
Symbol Table Entries
. each entry for a declaration of a name
. format need not be uniform because information depends upon the usage of the name
. each entry is a record consisting of consecutive words
. to keep records uniform some entries may be outside the symbol table
. information is entered into symbol table at various times
- keywords are entered initially
- identifier lexemes are entered by lexical analyzer
. symbol table entry may be set up when role of name becomes clear
. attribute values are filled in as information is available
For each declaration of a name, there is an entry in the symbol table. Different entries need to store different information because of the different contexts in which a name can occur. An entry corresponding to a particular name can be inserted into the symbol table at different stages depending on when the role of the name becomes clear. The various attributes that an entry in the symbol table can have are lexeme, type of name, size of storage and in case of functions - the parameter list etc.
Data Structures
. List data structure
- simplest to implement
- use a single array to store names and information
- search for a name is linear
- entry and lookup are independent operations
- cost of entry and search operations are very high and lot of time goes into book keeping
. Hash table
- The advantages are obvious

Representing Scope Information
. entries are declarations of names
. when a lookup is done, entry for appropriate declaration must be returned
. scope rules determine which entry is appropriate
. maintain separate table for each scope
. symbol table for a procedure or scope is compile time equivalent an activation record
. information about non local is found by scanning symbol table for the enclosing procedures
. symbol table can be attached to abstract syntax of the procedure (integrated into intermediate representation)
most closely nested scope rule can be implemented in data structures discussed so far
. give each procedure a unique number
. blocks must also be numbered
. procedure number is part of all local declarations
. name is represented as a pair of number and name
. names are entered in symbol table in the order they occur
. most closely nested rule can be created in terms of following operations:
- lookup: find the most recently created entry
- insert: make a new entry
- delete: remove the most recently created entry
Most closely nested scope rules can be implemented by adapting the data structures discussed in the previous section. Each procedure is assigned a unique number. If the language is block-structured, the blocks must also be assigned unique numbers. The name is represented as a pair of a number and a name. This new name is added to the symbol table. Most scope rules can be implemented in terms of following operations:
a) Lookup - find the most recently created entry.
b) Insert - make a new entry.
c) Delete - remove the most recently created entry.
Symbol table structure
. Assign variables to storage classes that prescribe scope, visibility, and lifetime
- scope rules prescribe the symbol table structure
- scope: unit of static program structure with one or more variable declarations
- scope may be nested
. Pascal: procedures are scoping units
. C: blocks, functions, files are scoping units
. Visibility, lifetimes, global variables
. Common (in Fortran)
. Automatic or stack storage
. Static variables
storage class : A storage class is an extra keyword at the beginning of a declaration which modifies the declaration in some way. Generally, the storage class (if any) is the first word in the declaration, preceding the type name. Ex. static, extern etc.
Scope: The scope of a variable is simply the part of the program where it may be accessed or written. It is the part of the program where the variable's name may be used. If a variable is declared within a function, it is local to that function. Variables of the same name may be declared and used within other functions without any conflicts. For instance,
int fun1() { int a; int b; .... } int fun2() { int a; int c; .... } Visibility: The visibility of a variable determines how much of the rest of the program can access that variable. You can arrange that a variable is visible only within one part of one function, or in one function, or in one source file, or anywhere in the program
Local and Global variables: A variable declared within the braces {} of a function is visible only within that function; variables declared within functions are called local variables. On the other hand, a variable declared outside of any function is a global variable , and it is potentially visible anywhere within the program
Automatic Vs Static duration: How long do variables last? By default, local variables (those declared within a function) have automatic duration : they spring into existence when the function is called, and they (and their values) disappear when the function returns. Global variables, on the other hand, have static duration : they last, and the values stored in them persist, for as long as the program does. (Of course, the values can in general still be overwritten, so they don't necessarily persist forever.) By default, local variables have automatic duration. To give them static duration (so that, instead of coming and going as the function is called, they persist for as long as the function does), you precede their declaration with the static keyword: static int i; By default, a declaration of a global variable (especially if it specifies an initial value) is the defining instance. To make it an external declaration, of a variable which is defined somewhere else, you precede it with the keyword extern: extern int j; Finally, to arrange that a global variable is visible only within its containing source file, you precede it with the static keyword: static int k; Notice that the static keyword can do two different things: it adjusts the duration of a local variable from automatic to static, or it adjusts the visibility of a global variable from truly global to private-to-the-file.

Activation Tree
The flow of control of the call quicksort(1,9) would be like
Execution begins ..
enter readarray
exit readarray
enter quicksort(1,9)
enter partition(1,9)
exit partition(1,9)
enter quicksort(1,3)
exit quicksort(1,3)
enter quicksort(5,9)
exit quicksort(5,9)
exit quicksort(1,9)
Execution terminates When the information is represented as an activation tree we get the tree as shown.
Storage organization

The runtime storage might be subdivided into
- Target code
- Data objects
- Stack to keep track of procedure activation
- Heap to keep all other information

This kind of organization of run-time storage is used for languages such as Fortran, Pascal and C. The size of the generated target code, as well as that of some of the data objects, is known at compile time. Thus, these can be stored in statically determined areas in the memory. Pascal and C use the stack for procedure activations. Whenever a procedure is called, execution of an activation gets interrupted, and information about the machine state (like register values) is stored on the stack. When the called procedure returns, the interrupted activation can be restarted after restoring the saved machine state. The heap may be used to store dynamically allocated data objects, and also other stuff such as activation information (in the case of languages where an activation tree cannot be used to represent lifetimes). Both the stack and the heap change in size during program execution, so they cannot be allocated a fixed amount of space. Generally they start from opposite ends of the memory and can grow as required, towards each other, until the space available has filled up.
Activation Record
. temporaries: used in expression evaluation
. local data: field for local data
. saved machine status: holds info about machine status before procedure call
. access link : to access non local data
. control link : points to activation record of caller
. actual parameters: field to hold actual parameters
. returned value : field for holding value to be returned

The activation record is used to store the information required by a single procedure call. Not all the fields shown in the figure may be needed for all languages. The record structure can be modified as per the language/compiler requirements. For Pascal and C, the activation record is generally stored on the run-time stack during the period when the procedure is executing. Of the fields shown in the figure, access link and control link are optional (e.g. Fortran doesn't need access links). Also, actual parameters and return values are often stored in registers instead of the activation record, for greater efficiency. The activation record for a procedure call is generated by the compiler. Generally, all field sizes can be determined at compile time. However, this is not possible in the case of a procedure which has a local array whose size depends on a parameter. The strategies used for storage allocation in such cases will be discussed in the coming slides.
Storage Allocation Strategies
. Static allocation: lays out storage at compile time for all data objects
. Stack allocation: manages the runtime storage as a stack
. Heap allocation :allocates and de-allocates storage as needed at runtime from heap
These represent the different storage-allocation strategies used in the distinct parts of the run-time memory organization (as shown in slide 8). We will now look at the possibility of using these strategies to allocate memory for activation records. Different languages use different strategies for this purpose. For example, old FORTRAN used static allocation, Algol type languages use stack allocation, and LISP type languages use heap allocation.
Static allocation
. Names are bound to storage as the program is compiled
. No runtime support is required
. Bindings do not change at run time
. On every invocation of procedure names are bound to the same storage
. Values of local names are retained across activations of a procedure
These are the fundamental characteristics of static allocation. Since name binding occurs during compilation, there is no need for a run-time support package. The retention of local name values across procedure activations means that when control returns to a procedure, the values of the locals are the same as they were when control last left.
Stack Allocation
Figure shows the activation records that are pushed onto and popped for the run time stack as the control flows through the given activation tree. First the procedure is activated. Procedure readarray 's activation is pushed onto the stack, when the control reaches the first line in the procedure sort . After the control returns from the activation of the readarray , its activation is popped. In the activation of sort , the control then reaches a call of qsort with actuals 1 and 9 and an activation of qsort is pushed onto the top of the stack. In the last stage the activations for partition (1,3) and qsort (1,0) have begun and ended during the life time of qsort (1,3), so their activation records have come and gone from the stack, leaving the activation record for qsort (1,3) on top.
Calling Sequence
.A call sequence allocates an activation record and enters information into its field
A call sequence allocates an activation record and enters information into its fields. A return sequence restores the state of the machine so that the calling sequence can continue execution. Calling sequence and activation records differ, even for the same language. The code in the calling sequence is often divided between the calling procedure and the procedure it calls. There is no exact division of runtime tasks between the caller and the callee. As shown in the figure, the register stack top points to the end of the machine status field in the activation record. This position is known to the caller, so it can be made responsible for setting up stack top before control flows to the called procedure. The code for the callee can access its temporaries and the local data using offsets from stack top.
Heap Allocation
. Stack allocation cannot be used if:
- The values of the local variables must be retained when an activation ends
- A called activation outlives the caller
. In such a case de-allocation of activation record cannot occur in last-in first-out fashion
. Heap allocation gives out pieces of contiguous storage for activation records
There are two aspects of dynamic allocation -:
. Runtime allocation and de-allocation of data structures.
. Languages like Algol have dynamic data structures and it reserves some part of memory for it.
If a procedure wants to put a value that is to be used after its activation is over then we cannot use stack for that purpose. That is language like Pascal allows data to be allocated under program control. Also in certain language a called activation may outlive the caller procedure. In such a case last-in-first-out queue will not work and we will require a data structure like heap to store the activation. The last case is not true for those languages whose activation trees correctly depict the flow of control between procedures.
Pieces may be de-allocated in any order
. Over time the heap will consist of alternate areas that are free and in use
. Heap manager is supposed to make use of the free space
. For efficiency reasons it may be helpful to handle small activations as a special case
. For each size of interest keep a linked list of free blocks of that size
Initializing data-structures may require allocating memory but where to allocate this memory. After doing type inference we have to do storage allocation. It will allocate some chunk of bytes. But in language like lisp it will try to give continuous chunk. The allocation in continuous bytes may lead to problem of fragmentation i.e. you may develop hole in process of allocation and de-allocation. Thus storage allocation of heap may lead us with many holes and fragmented memory which will make it hard to allocate continuous chunk of memory to requesting program. So we have heap mangers which manage the free space and allocation and de-allocation of memory. It would be efficient to handle small activations and activations of predictable size as a special case as described in the next slide. The various allocation and de-allocation techniques used will be discussed later.
Access to non-local names
. Scope rules determine the treatment of non-local names
. A common rule is lexical scoping or static scoping (most languages use lexical scoping)
The scope rules of a language decide how to reference the non-local variables. There are two methods that are commonly used:
1. Static or Lexical scoping: It determines the declaration that applies to a name by examining the program text alone. E.g., Pascal, C and ADA.
2. Dynamic Scoping: It determines the declaration applicable to a name at run time, by considering the current activations. E.g., Lisp
Block
. Blocks can be nested
. The property is referred to as block structured
. Scope of the declaration is given by most closely nested rule
- The scope of a declaration in block B includes B
- If a name X is not declared in B then an occurrence of X is in the scope of declarator X in B ' such that
. B ' has a declaration of X
. B ' is most closely nested around B
Blocks contains its own local data structure. Blocks can be nested and their starting and ends are marked by a delimiter. They ensure that either block is independent of other or nested in another block. That is, it is not possible for two blocks B1 and B2 to overlap in such a way that first block B1 begins, then B2, but B1 end before B2. This nesting property is called block structure. The scope of declaration in a block-structured language is given by the most closely nested rule: 1. The scope of a declaration in a block B includes B. 2. If a name X is not declared in a block B, then an occurrence of X in B is in the scope of a declaration of X in an enclosing block B ' such that . B ' has a declaration of X, and . B ' is more closely nested around B then any other block with a declaration of X.
There are two methods of implementing block structure:
1. Stack Allocation : This is based on the observation that scope of a declaration does not extend outside the block in which it appears, the space for declared name can be allocated when the block is entered and de-allocated when controls leave the block. The view treat block as a "parameter less procedure" called only from the point just before the block and returning only to the point just before the block.
2. Complete Allocation : Here you allocate the complete memory at one time. If there are blocks within the procedure, then allowance is made for the storage needed for declarations within the books. If two variables are never alive at the same time and are at same depth they can be assigned same storage
Lexical scope without nested procedures
. A procedure definition cannot occur within another
. Therefore, all non local references are global and can be allocated at compile time
. Any name non-local to one procedure is non-local to all procedures
. In absence of nested procedures use stack allocation
. Storage for non locals is allocated statically
. A non local name must be local to the top of the stack
. Stack allocation of non local has advantage:
- Non locals have static allocations
- Procedures can be passed/returned as parameters
In languages like C nested procedures are not allowed. That is, you cannot define a procedure inside another procedure. So, if there is a non- local reference to a name in some function then that variable must be a global variable. The scope of a global variable holds within all the functions except those in which the variables have been re-declared. Storage for all names declared globally can be allocated statically. Thus their positions will be known at compile time. In static allocation, we use stack allocation. Any other name must be a local of the activation at the top of the stack, accessible through the top pointer. Nested procedures cause this scheme to fail because a non-local may then refer to a local of parent variable which may be buried deep in the stack and not at the top of stack. An important benefit of static allocation for non- locals is that declared procedures can freely be passed as parameters and returned as results (a function is passed in C by passing a pointer to it).
Add 1 to depth as we go from enclosing to enclosed procedure
Access to non-local names
. Include a field 'access link' in the activation record
. If p is nested in q then access link of p points to the access link in most recent activation of q
Nesting Depth : The notion of nesting depth is used to implement lexical scope. The main program is assumed to be at nesting depth 1 and we add 1 to the nesting depth as we go from an enclosing to an enclosed procedure.
Access Links : To implement the lexical scope for nested procedures we add a pointer called an access link to each activation record. If a procedure p is nested immediately within q in the source text, then the access link in an activation record for p points to the access link in the record for most recent activation of q .
Displays
. Faster access to non locals
. Uses an array of pointers to activation records
. Non locals at depth i is in the activation record pointed to by d[i]

Faster access to non locals than with access links can be obtained using an array d of pointers to activation records, called a display. We maintain display so that storage for a non local a at nesting depth i is in the activation record pointed to by display element d[i].
The display changes when a new activation occurs, and it must be reset when control returns from the new activation. When a new activation record for a procedure at nesting depth i is set up, we first save the value of d[i] in the new activation record and then set d[i] to point to the new activation record. Just before an activation ends , d[i] is reset to the saved value.
Dynamic Scope
. Binding of non local names to storage do not change when new activation is set up
. A non local name a in the called activation refers to same storage that it did in the calling activation
In dynamic scope , a new activation inherits the existing bindings of non local names to storage. A non local name a in the called activation refers to the same storage that it did in the calling activation. New bindings are set up for the local names of the called procedure, the names refer to storage in the new activation record.
Dynamic Scope
. Deep Access
- Dispense with access links
- use control links to search into the stack
- term deep access comes from the fact that search may go deep into the stack
. Shallow Access
- hold current value of each name in static memory
- when a new activation of p occurs a local name n in p takes over the storage for n
- previous value of n is saved in the activation record of p
We will discuss two approaches to implement dynamic scope. They bear resemblance to the use of access links and displays, respectively, in the implementation of the lexical scope.
1. Deep Access : Dynamic scope results if access links point to the same activation records that control links do. A simple implementation is to dispense with access links and use control links to search into the stack, looking for the first activation record containing storage for the non- local name. The term deep access comes from the fact that search may go deep into the stack. The depth to which the search may go depends on the input of the program and cannot be determined at compile time.
2. Shallow Access : Here the idea is to hold the current value of each name in static memory. When a new activation of a procedure p occurs, a local name n in p takes over the storage for n. The previous value of n is saved in the activation record for p and is restored when the activation of p ends.
Parameter Passing
. Call by value
- actual parameters are evaluated and their rvalues are passed to the called procedure
- used in Pascal and C
- formal is treated just like a local name
- caller evaluates the actual parameters and places rvalue in the storage for formals
- call has no effect on the activation record of caller
This is, in a sense, the simplest possible method of passing parameters. The actual parameters are evaluated and their r-values are passed to the called procedure. Call-by-value is used in C, and Pascal parameters are usually passed this way. Call-by-Value can be implemented as follows:
1. A formal parameter is treated just like a local name, so the storage for the formals is in the activation record of the called procedure.
2. The caller evaluates the actual parameters and places their r-values in the storage for the formals. A distinguishing feature of call-by-value is that operations on the formal parameters do not affect values in the activation record of the caller.
Parameter Passing .
. Call by reference (call by address)
- the caller passes a pointer to each location of actual parameters
- if actual parameter is a name then lvalue is passed
- if actual parameter is an expression then it is evaluated in a new location and the address of that location is passed
When the parameters are passed by reference (also known as call-by-address or call-by location), the caller passes to the called procedure a pointer to the storage address of each actual parameter.
1. If an actual parameter is a name or an expression having an l-value, then that l-value itself is passed.
2. However, if the actual parameter is an expression, like a + b or 2, that has no l-value, then the expression is evaluated in a new location, and the address of that location is passed.
A reference to a formal parameter in the called procedure becomes, in the target code, an indirect reference through the pointer passed to the called procedure.
Parameter Passing .
. Copy restore (copy-in copy-out, call by value result)
- actual parameters are evaluated, rvalues are passed by call by value, lvalues are determined before the call
- when control returns, the current rvalues of the formals are copied into lvalues of the locals
This is a hybrid form between call-by-value and call-by-reference (also known as copy-in copy-out or value-result).
1. Before control flows to the called procedure, the actual parameters are evaluated. The r-values of the actuals are passed to the called procedure as in call-by-value. In addition, however, the l-values of those actual parameters having l-values are determined before the call.
2. When the control returns, the current r-values of the formal parameters are copied back into the l-values of the actuals, using the l-values computed before the call. Only the actuals having l-values are copied.
Parameter Passing .
. Call by name (used in Algol)
- names are copied
- local names are different from names of calling procedure
swap(i,a[i])
temp = i
i = a[i]
a[i] = temp
This is defined by the copy-rule as used in Algol.
1. The procedure is treated as if it were a macro; that is, its body is substituted for the call in the caller, with the actual parameters literally substituted for the formals. Such a literal substitution is called macro-expansion or inline expansion.
2. The local names of the called procedure are kept distinct from the names of the calling procedure. We can think of each local of the called procedure being systematically renamed into a distinct new name before macro-expansion is done.
3. The actual parameters are surrounded by parentheses if necessary to preserve their integrity.
Language Facility for Dynamic Storage Allocation
. Storage is usually taken from heap
. Allocated data is retained until deallocated
. Allocation can be either explicit or implicit
- Pascal : explicit allocation and de-allocation by new() and dispose()
- Lisp : implicit allocation when cons is used, and de- allocation through garbage collection
Static storage allocation is usually done on the stack, as this is a convenient way to take care of the normal scoping rules, where the most recent values have to be considered, and when the scope ends, their values have to be removed. But for dynamic allocation, no such prior information regarding the use of the variables is available. So we need the maximum possible flexibility in this. For this a heap is used. For the sake of a more efficient utilization of memory, the stack grows downwards and the heap grows upwards, starting from different ends of the available memory. This makes sure that all available memory is utilized. Pascal allows for explicit allocation and de-allocation of memory. This can be done by using the new() and dispose() functions. However, in Lisp, continuous checking is done for free memory. When less than 20 percent of the memory is free, then garbage collection is performed. In garbage collection, cells that can no longer be accessed are de-allocated. (Storage that has been allocated but can no longer be accessed is called 'garbage'.)
Essay type questions:
1. Explain the Indirection in symbol table entries with an example.

2. Explain the Self organizing in symbol tables with an example
3. Draw and explain the symbol table organization for C language with a program
block.
4. Explain the importance of the following attributes of a symbol table.
(a) Variable name
(b) Object time address
5. What is heap storage allocation? Explain in detail.
6. Compare three different storage allocation strategies.
7. Write an algorithm to perform the table lookup and insertion operation for hashed
symbol table.
8. Explain about implicit and explicit storage requests.

9. Explain the importance of the following attributes of a symbol table.
(a) Type of a symbol table
(b) Link field.
10. What is an ordered and unordered symbol table? What is the function of
symbol table in the compliation process? Explain.
Short answer questions:
1. Draw the Symbol table format?
2 What is the Block structured language?
3.What is the Non Block structured language?
4. Explain the organization for block structures languages?
5. What is the hashing?
6. Write the structures of tree representation of scope information?
7. Write the difference between Block structures and non block structures?
8. Write the examples of between Block structures and non block structure languages?
9. What is the storage allocation ?
10. What are the allocation strategies in symbol table?
11. Write various storage organizations?
12. What is the scope information?
UNIT VI
CODE OPTIMIZATION: Consideration for Optimization, Scope of Optimization, local
optimization, loop optimization, frequency reduction, folding, DAG representation.

Essay type questions:
1. Explain different principal sources of optimization technique with suitable exam-
ples.

2. What is code optimization? What are its advantages?
3. What is DAG? Construct the DAG for the following basic block
D := B_C E :=A+B B := B+C A := E-D

4. What is a DAG. Explain its applications.
5. What are the problems in optimizing compiler design?

6. Write the three-address code for the following code.
begin
PROD: = 0;
I: =1;
do
begin
PROD:=PROD + A[I]∗B[I];
I:=I+1;
End
while I<=20
end
7. Write an algorithm for partition of basic blocks.
8. Explain briefly about folding.

9. What are the legal evaluation orders and names for the values at the nodes
for the DAG of problem (a).
i. Assuming A, B and C are alive at the end of the basic block?
ii. Assuming only A is live at the end?
10. Explain in detail the Optimization technique “strength reduction”.
Short answer questions:
1. Write what are the Consideration for Optimization?
2.What is the Scope of Optimization?
3. What are the local optimization techniques?
4. What are the loop optimization techniques?
5.What is the Dag?
6.What is the frequency reduction?
7.What is the Reduction in strength?
8.What is the constant folding?
9.What is the Copy propagation?
10.What is the Call by value?
11.What is the copy in copy out?
12.What is the Call by Name?
13.Define Optimization?
14.What is the role of optimization?
15.How the optimization is cause effect on machine code?

UNIT VII
DATA FLOW ANALYSIS: Flow graph, data flow equation, global optimization, redundant sub
expression elimination, Induction variable elements, Live variable analysis, Copy propagation

Essay type questions:
1. Write and explain live variable analysis algorithm.

2. Explain reducible and non-reducible flow graphs with an example.

3. Explain the use of algebraic transformations with an example

4. Explain natural loops and inner loops of a flow graph with an example.

5. What are the applications of du and ud chains.

6. Explain in detail the procedure that eliminate global common sub - expression.

7. Generate the flow-graphs for the following expressions:
S-> id: = E S; S if E then S else S do S while E
E-> id + id id

8. What is an Induction variable? Explain with an example.
9. Consider the following program which counts the primes form 2 to n using the sieve
method on a suitably large array
begin
read n
for i : = 2 to n do
a[i] : = true / * initialize */
count: = 0;
for i : 2 to n ** .5 do
if a [i] then /* i is a prime */
begin
count := count +1
for j : = 2 * i to n by i do
a[j] : =false
/ * j is divisible by i */
end ;
print count
end
(a) Propagate out copy statements wherever possible.
(b) Is loop jumping possible? If so, do it.
(c) Eliminate the induction variables wherever possible.

10.Discuss how induction variables can be detected and how transformation can
be applied.
Short answer questions:
1.What is Flow graph?
2.Define copy propagation?
3.What is data flow equation?
4.What are the global optimization techniques?
5.How the redundant sub expression eliminated?
6.What is Induction variable?
7.What is the Live variable?
8.What is the use of Copy propagation?
9.What is the role of DFE?
10.What is the use of global optimization?

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

Essay type questions:
1. Explain the different issues in the design of a code generator.

2. Explain the concept of object code forms.

3. Generate optimal machine code for the following C program.
main()
{
int p,q[15];
while (p<=15) q[p] =1
}

4. State and explain different machine dependent code optimization techniques.

5. Describe, how addressing modes can be used for reducing the memory access
Time.

6. Generate code for the following C statements:
i. s= f(a) + f(a) + f(a) ii. s= f(a) /g(b,c) iii. s= f(f(a)) iv. s= ++f(a)

7. Generate the code sequence using Code generation algorithm for the following
expression W:=(A-B)+(A-C)+(A-C)

8. Discribe various Register allocation optimization techniques with an example.

9. Explain the concept of label tree of code generation.

10. What are the various addressing modes available? Give some example machine
instructions which reduces memory access time.

Short answer question:
1. What is the scope of Object code form?
2.What is an Object code?
3.What is machine dependent code ?
4.What is machine independent code ?
5.What is the Direct acyclic graph?
6.What is the role of DAG in Object code?
7.What is the register allocation ?
8.What is the use of assignment generic code generation algorithm?
9.Explain about DAG for register allocation?
10.What is the label tree ?

Artificial Intelligence Notes for JNTU BTECH CSE Students

2010-04-10T03:49:00.000-07:00

Introduction to Agent
1 Introduction to Agents
An agent acts in an environment.
EnvironmentPerceptsActionsAgentEnvironmentPerceptsActionsAgentAgent
An agent perceives its environment through sensors. The complete set of inputs at a given time is called a percept. The current percept, or a sequence of percepts can influence the actions of an agent. The agent can change the environment through actuators or effectors. An operation involving an effector is called an action. Actions can be grouped into action sequences. The agent can have goals which it tries to achieve.
Thus, an agent can be looked upon as a system that implements a mapping from percept sequences to actions.
A performance measure has to be used in order to evaluate an agent.
An autonomous agent decides autonomously which action to take in the current situation to maximize progress towards its goals.
1.3.1.1 Agent Performance
An agent function implements a mapping from perception history to action. The behaviour and performance of intelligent agents have to be evaluated in terms of the agent function.
The ideal mapping specifies which actions an agent ought to take at any point in time.
The performance measure is a subjective measure to characterize how successful an agent is. The success can be measured in various ways. It can be measured in terms of speed or efficiency of the agent. It can be measured by the accuracy or the quality of the solutions achieved by the agent. It can also be measured by power usage, money, etc.
1.3.1.2 Examples of Agents
1. Humans can be looked upon as agents. They have eyes, ears, skin, taste buds, etc. for sensors; and hands, fingers, legs, mouth for effectors.

2. Robots are agents. Robots may have camera, sonar, infrared, bumper, etc. for sensors. They can have grippers, wheels, lights, speakers, etc. for actuators.
Some examples of robots are Xavier from CMU, COG from MIT, etc.
Xavier Robot (CMU)

Then we have the AIBO entertainment robot from SONY.
Aibo from SONY
3. We also have software agents or softbots that have some functions as sensors and some functions as actuators. Askjeeves.com is an example of a softbot.
4. Expert systems like the Cardiologist is an agent.
5. Autonomous spacecrafts.
6. Intelligent buildings.

1.3.1.3 Agent Faculties
The fundamental faculties of intelligence are
• Acting
• Sensing
• Understanding, reasoning, learning

Blind action is not a characterization of intelligence. In order to act intelligently, one must sense. Understanding is essential to interpret the sensory percepts and decide on an action. Many robotic agents stress sensing and acting, and do not have understanding.
1.3.1.4 Intelligent Agents
An Intelligent Agent must sense, must act, must be autonomous (to some extent),. It also
must be rational.
AI is about building rational agents. An agent is something that perceives and acts.
A rational agent always does the right thing.
1. What are the functionalities (goals)?
2. What are the components?
3. How do we build them?

1.3.1.5 Rationality
Perfect Rationality assumes that the rational agent knows all and will take the action that maximizes her utility. Human beings do not satisfy this definition of rationality.
Rational Action is the action that maximizes the expected value of the performance measure given the percept sequence to date.
However, a rational agent is not omniscient. It does not know the actual outcome of its actions, and it may not know certain aspects of its environment. Therefore rationality must take into account the limitations of the agent. The agent has too select the best action to the best of its knowledge depending on its percept sequence, its background knowledge and its feasible actions. An agent also has to deal with the expected outcome of the actions where the action effects are not deterministic.
1.3.1.6 Bounded Rationality
“Because of the limitations of the human mind, humans must use approximate methods to handle many tasks.” Herbert Simon, 1972
Evolution did not give rise to optimal agents, but to agents which are in some senses locally optimal at best. In 1957, Simon proposed the notion of Bounded Rationality: that property of an agent that behaves in a manner that is nearly optimal with respect to its goals as its resources will allow.
Under these promises an intelligent agent will be expected to act optimally to the best of its abilities and its resource constraints.

1.3.2 Agent Environment
Environments in which agents operate can be defined in different ways. It is helpful to view the following definitions as referring to the way the environment appears from the point of view of the agent itself.
1.3.2.1 Observability
In terms of observability, an environment can be characterized as fully observable or partially observable.
In a fully observable environment all of the environment relevant to the action being considered is observable. In such environments, the agent does not need to keep track of the changes in the environment. A chess playing system is an example of a system that operates in a fully observable environment.
In a partially observable environment, the relevant features of the environment are only partially observable. A bridge playing program is an example of a system operating in a partially observable environment.
1.3.2.2 Determinism
In deterministic environments, the next state of the environment is completely described by the current state and the agent’s action. Image analysis systems are examples of this kind of situation. The processed image is determined completely by the current image and the processing operations.
If an element of interference or uncertainty occurs then the environment is stochastic. Note that a deterministic yet partially observable environment will appear to be stochastic to the agent. Examples of this are the automatic vehicles that navigate a terrain, say, the Mars rovers robot. The new environment in which the vehicle is in is stochastic in nature.
If the environment state is wholly determined by the preceding state and the actions of multiple agents, then the environment is said to be strategic. Example: Chess. There are two agents, the players and the next state of the board is strategically determined by the players’ actions.
1.3.2.3 Episodicity
An episodic environment means that subsequent episodes do not depend on what actions occurred in previous episodes.
In a sequential environment, the agent engages in a series of connected episodes.
1.3.2.4 Dynamism
Static Environment: does not change from one state to the next while the agent is

considering its course of action. The only changes to the environment are those caused by the agent itself.
• A static environment does not change while the agent is thinking.
• The passage of time as an agent deliberates is irrelevant.
• The agent doesn’t need to observe the world during deliberation.

A Dynamic Environment changes over time independent of the actions of the agent -- and thus if an agent does not respond in a timely manner, this counts as a choice to do nothing
1.3.2.5 Continuity
If the number of distinct percepts and actions is limited, the environment is discrete, otherwise it is continuous.
1.3.2.6 Presence of Other agents
Single agent/ Multi-agent
A multi-agent environment has other agents. If the environment contains other intelligent agents, the agent needs to be concerned about strategic, game-theoretic aspects of the environment (for either cooperative or competitive agents)
Most engineering environments do not have multi-agent properties, whereas most social and economic systems get their complexity from the interactions of (more or less) rational agents.
1.3.3 Agent architectures
We will next discuss various agent architectures.
1.3.3.1 Table based agent
In table based agent the action is looked up from a table based on information about the agent’s percepts. A table is simple way to specify a mapping from percepts to actions. The mapping is implicitly defined by a program. The mapping may be implemented by a rule based system, by a neural network or by a procedure.
There are several disadvantages to a table based system. The tables may become very large. Learning a table may take a very long time, especially if the table is large. Such systems usually have little autonomy, as all actions are pre-determined.
1.3.3.2. Percept based agent or reflex agent
In percept based agents,
1. information comes from sensors - percepts
2. changes the agents current state of the world
3. triggers actions through the effectors

Such agents are called reactive agents or stimulus-response agents. Reactive agents have no notion of history. The current state is as the sensors see it right now. The action is based on the current percepts only.
The following are some of the characteristics of percept-based agents.
• Efficient
• No internal representation for reasoning, inference.
• No strategic planning, learning.
• Percept-based agents are not good for multiple, opposing, goals.

1.3.3.3 Subsumption Architecture
We will now briefly describe the subsumption architecture (Rodney Brooks, 1986). This architecture is based on reactive systems. Brooks notes that in lower animals there is no deliberation and the actions are based on sensory inputs. But even lower animals are capable of many complex tasks. His argument is to follow the evolutionary path and build simple agents for complex worlds.
The main features of Brooks’ architecture are.
• There is no explicit knowledge representation
• Behaviour is distributed, not centralized
• Response to stimuli is reflexive
• The design is bottom up, and complex behaviours are fashioned from the combination of simpler underlying ones.
• Individual agents are simple

The Subsumption Architecture built in layers. There are different layers of behaviour. The higher layers can override lower layers. Each activity is modeled by a finite state machine.
The subsumption architecture can be illustrated by Brooks’ Mobile Robot example.

The system is built in three layers.
1. Layer 0: Avoid Obstacles
2. Layer1: Wander behaviour
3. Layer 2: Exploration behaviour

Layer 0 (Avoid Obstacles) has the following capabilities:
• Sonar: generate sonar scan
• Collide: send HALT message to forward
• Feel force: signal sent to run-away, turn

Layer1 (Wander behaviour)
• Generates a random heading
• Avoid reads repulsive force, generates new heading, feeds to turn and forward

Layer2 (Exploration behaviour)
• Whenlook notices idle time and looks for an interesting place.
• Pathplan sends new direction to avoid.
• Integrate monitors path and sends them to the path plan.

1.3.3.4 State-based Agent or model-based reflex agent
State based agents differ from percept based agents in that such agents maintain some sort of state based on the percept sequence received so far. The state is updated regularly based on what the agent senses, and the agent’s actions. Keeping track of the state requires that

the agent has knowledge about how the world evolves, and how the agent’s actions affect the world.
Thus a state based agent works as follows:
• information comes from sensors - percepts
• based on this, the agent changes the current state of the world
• based on state of the world and knowledge (memory), it triggers actions through the effectors

1.3.3.5 Goal-based Agent
The goal based agent has some goal which forms a basis of its actions.
Such agents work as follows:
• information comes from sensors - percepts
• changes the agents current state of the world
• based on state of the world and knowledge (memory) and goals/intentions, it chooses actions and does them through the effectors.

Goal formulation based on the current situation is a way of solving many problems and search is a universal problem solving mechanism in AI. The sequence of steps required to solve a problem is not known a priori and must be determined by a systematic exploration of the alternatives.
1.3.3.6 Utility-based Agent
Utility based agents provides a more general agent framework. In case that the agent has multiple goals, this framework can accommodate different preferences for the different goals.
Such systems are characterized by a utility function that maps a state or a sequence of states to a real valued utility. The agent acts so as to maximize expected utility
1.3.3.7 Learning Agent
Learning allows an agent to operate in initially unknown environments. The learning element modifies the performance element. Learning is required for true autonomy
1.4 Conclusion
In conclusion AI is a truly fascinating field. It deals with exciting but hard problems. A goal of AI is to build intelligent agents that act so as to optimize performance.
• An agent perceives and acts in an environment, has an architecture, and is implemented by an agent program.
• An ideal agent always chooses the action which maximizes its expected performance, given its percept sequence so far.
• An autonomous agent uses its own experience rather than built-in knowledge of the environment by the designer.
• An agent program maps from percept to action and updates its internal state.

• Reflex agents respond immediately to percepts.
• Goal-based agents act in order to achieve their goal(s).
• Utility-based agents maximize their own utility function.
• Representing knowledge is important for successful agent design.
• The most challenging environments are partially observable, stochastic, sequential, dynamic, and continuous, and contain multiple intelligent agents.

AI notes for JNTU BTECH CSE students.

2010-04-09T23:04:00.000-07:00

Introduction

Introduction
1.1 Instructional Objectives
– Understand the definition of artificial intelligence
– Understand the different faculties involved with intelligent behavior
– Examine the different ways of approaching AI
– Look at some example systems that use AI
– Trace briefly the history of AI
– Have a fair idea of the types of problems that can be currently solved by computers and those that are as yet beyond its ability.

We will introduce the following entities:
• An agent
• An intelligent agent
• A rational agent

We will explain the notions of rationality and bounded rationality.
We will discuss different types of environment in which the agent might operate.
We will also talk about different agent architectures.
On completion of this lesson the student will be able to
• Understand what an agent is and how an agent interacts with the environment.
• Given a problem situation, the student should be able to
o identify the percepts available to the agent and
o the actions that the agent can execute.
• Understand the performance measures used to evaluate an agent

The student will become familiar with different agent architectures
• Stimulus response agents
• State based agents
• Deliberative / goal-directed agents
• Utility based agents

The student should be able to analyze a problem situation and be able to
• identify the characteristics of the environment
• Recommend the architecture of the desired agent

Lesson 1
Introduction to AI
1.1.1 Definition of AI
What is AI ?
Artificial Intelligence is concerned with the design of intelligence in an artificial device.
The term was coined by McCarthy in 1956.
There are two ideas in the definition.
1. Intelligence
2. artificial device

What is intelligence?
– Is it that which characterize humans? Or is there an absolute standard of judgement?
– Accordingly there are two possibilities:
– A system with intelligence is expected to behave as intelligently as a human
– A system with intelligence is expected to behave in the best possible manner
– Secondly what type of behavior are we talking about?
– Are we looking at the thought process or reasoning ability of the system?
– Or are we only interested in the final manifestations of the system in terms of its actions?

Given this scenario different interpretations have been used by different researchers as defining the scope and view of Artificial Intelligence.
1. One view is that artificial intelligence is about designing systems that are as intelligent as humans.
This view involves trying to understand human thought and an effort to build machines that emulate the human thought process. This view is the cognitive science approach to AI.

2. The second approach is best embodied by the concept of the Turing Test. Turing held that in future computers can be programmed to acquire abilities rivaling human intelligence. As part of his argument Turing put forward the idea of an 'imitation game', in which a human being and a computer would be interrogated under conditions where the interrogator would not know which was which, the communication being entirely by textual messages. Turing argued that if the interrogator could not distinguish them by questioning, then it would be unreasonable not to call the computer intelligent. Turing's 'imitation game' is now usually called 'the Turing test' for intelligence.

Turing Test
Consider the following setting. There are two rooms, A and B. One of the rooms contains a computer. The other contains a human. The interrogator is outside and does not know which one is a computer. He can ask questions through a teletype and receives answers from both A and B. The interrogator needs to identify whether A or B are humans. To pass the Turing test, the machine has to fool the interrogator into believing that it is human. For more details on the Turing test visit the site http://cogsci.ucsd.edu/~asaygin/tt/ttest.html
3. Logic and laws of thought deals with studies of ideal or rational thought process and inference. The emphasis in this case is on the inferencing mechanism, and its properties. That is how the system arrives at a conclusion, or the reasoning behind its selection of actions is very important in this point of view. The soundness and completeness of the inference mechanisms are important here.

4. The fourth view of AI is that it is the study of rational agents. This view deals with building machines that act rationally. The focus is on how the system acts and performs, and not so much on the reasoning process. A rational agent is one that acts rationally, that is, is in the best possible manner.

1.1.2 Typical AI problems
While studying the typical range of tasks that we might expect an “intelligent entity” to perform, we need to consider both “common-place” tasks as well as expert tasks.
Examples of common-place tasks include
– Recognizing people, objects.
– Communicating (through natural language).
– Navigating around obstacles on the streets

These tasks are done matter of factly and routinely by people and some other animals.
Expert tasks include:
• Medical diagnosis.
• Mathematical problem solving
• Playing games like chess

These tasks cannot be done by all people, and can only be performed by skilled specialists.
Now, which of these tasks are easy and which ones are hard? Clearly tasks of the first type are easy for humans to perform, and almost all are able to master them. The second range of tasks requires skill development and/or intelligence and only some specialists can perform them well. However, when we look at what computer systems have been able to achieve to date, we see that their achievements include performing sophisticated tasks like medical diagnosis, performing symbolic integration, proving theorems and playing chess.
On the other hand it has proved to be very hard to make computer systems perform many routine tasks that all humans and a lot of animals can do. Examples of such tasks include navigating our way without running into things, catching prey and avoiding predators. Humans and animals are also capable of interpreting complex sensory information. We are able to recognize objects and people from the visual image that we receive. We are also able to perform complex social functions.
Intelligent behaviour
This discussion brings us back to the question of what constitutes intelligent behaviour. Some of these tasks and applications are:
􀂃 Perception involving image recognition and computer vision
􀂃 Reasoning
􀂃 Learning
􀂃 Understanding language involving natural language processing, speech processing
􀂃 Solving problems
􀂃 Robotics

1.1.3 Practical Impact of AI
AI components are embedded in numerous devices e.g. in copy machines for automatic correction of operation for copy quality improvement. AI systems are in everyday use for identifying credit card fraud, for advising doctors, for recognizing speech and in helping complex planning tasks. Then there are intelligent tutoring systems that provide students with personalized attention
Thus AI has increased understanding of the nature of intelligence and found many applications. It has helped in the understanding of human reasoning, and of the nature of intelligence. It has also helped us understand the complexity of modeling human reasoning.
1.1.4 Approaches to AI
Strong AI aims to build machines that can truly reason and solve problems. These machines should be self aware and their overall intellectual ability needs to be indistinguishable from that of a human being. Excessive optimism in the 1950s and 1960s concerning strong AI has given way to an appreciation of the extreme difficulty of the problem. Strong AI maintains that suitably programmed machines are capable of cognitive mental states.
Weak AI: deals with the creation of some form of computer-based artificial intelligence that cannot truly reason and solve problems, but can act as if it were intelligent. Weak AI holds that suitably programmed machines can simulate human cognition.
Applied AI: aims to produce commercially viable "smart" systems such as, for example, a security system that is able to recognise the faces of people who are permitted to enter a particular building. Applied AI has already enjoyed considerable success.
Cognitive AI: computers are used to test theories about how the human mind works--for example, theories about how we recognise faces and other objects, or about how we solve abstract problems.
1.1.5 Limits of AI Today
Today’s successful AI systems operate in well-defined domains and employ narrow, specialized knowledge. Common sense knowledge is needed to function in complex, open-ended worlds. Such a system also needs to understand unconstrained natural language. However these capabilities are not yet fully present in today’s intelligent systems.
What can AI systems do
Today’s AI systems have been able to achieve limited success in some of these tasks.
• In Computer vision, the systems are capable of face recognition
• In Robotics, we have been able to make vehicles that are mostly autonomous.
• In Natural language processing, we have systems that are capable of simple machine translation.
• Today’s Expert systems can carry out medical diagnosis in a narrow domain
• Speech understanding systems are capable of recognizing several thousand words continuous speech
• Planning and scheduling systems had been employed in scheduling experiments with

the Hubble Telescope.
• The Learning systems are capable of doing text categorization into about a 1000 topics
• In Games, AI systems can play at the Grand Master level in chess (world champion), checkers, etc.

What can AI systems NOT do yet?
• Understand natural language robustly (e.g., read and understand articles in a newspaper)
• Surf the web
• Interpret an arbitrary visual scene
• Learn a natural language
• Construct plans in dynamic real-time domains
• Exhibit true autonomy and intelligence

1.2 AI History
Intellectual roots of AI date back to the early studies of the nature of knowledge and reasoning. The dream of making a computer imitate humans also has a very early history.
The concept of intelligent machines is found in Greek mythology. There is a story in the 8th century A.D about Pygmalion Olio, the legendary king of Cyprus. He fell in love with an ivory statue he made to represent his ideal woman. The king prayed to the goddess Aphrodite, and the goddess miraculously brought the statue to life. Other myths involve human-like artifacts. As a present from Zeus to Europa, Hephaestus created Talos, a huge robot. Talos was made of bronze and his duty was to patrol the beaches of Crete.
Aristotle (384-322 BC) developed an informal system of syllogistic logic, which is the basis of the first formal deductive reasoning system.
Early in the 17th century, Descartes proposed that bodies of animals are nothing more than complex machines.
Pascal in 1642 made the first mechanical digital calculating machine.
In the 19th century, George Boole developed a binary algebra representing (some) "laws of thought."
Charles Babbage & Ada Byron worked on programmable mechanical calculating machines.
In the late 19th century and early 20th century, mathematical philosophers like Gottlob Frege, Bertram Russell, Alfred North Whitehead, and Kurt Gödel built on Boole's initial logic concepts to develop mathematical representations of logic problems.
The advent of electronic computers provided a revolutionary advance in the ability to
study intelligence.
In 1943 McCulloch & Pitts developed a Boolean circuit model of brain. They wrote the paper “A Logical Calculus of Ideas Immanent in Nervous Activity”, which explained how it is possible for neural networks to compute.
Marvin Minsky and Dean Edmonds built the SNARC in 1951, which is the first randomly wired neural network learning machine (SNARC stands for Stochastic Neural-Analog Reinforcement Computer).It was a neural network computer that used 3000 vacuum tubes and a network with 40 neurons.
In 1950 Turing wrote an article on “Computing Machinery and Intelligence” which articulated a complete vision of AI. For more on Alan Turing see the site http://www.turing.org.uk/turing/
Turing’s paper talked of many things, of solving problems by searching through the space of possible solutions, guided by heuristics. He illustrated his ideas on machine intelligence by reference to chess. He even propounded the possibility of letting the machine alter its own instructions so that machines can learn from experience.
In 1956 a famous conference took place in Dartmouth. The conference brought together the founding fathers of artificial intelligence for the first time. In this meeting the term “Artificial Intelligence” was adopted.
Between 1952 and 1956, Samuel had developed several programs for playing checkers. In 1956, Newell & Simon’s Logic Theorist was published. It is considered by many to be the first AI program. In 1959, Gelernter developed a Geometry Engine. In 1961 James Slagle (PhD dissertation, MIT) wrote a symbolic integration program, SAINT. It was written in LISP and solved calculus problems at the college freshman level. In 1963, Thomas Evan's program Analogy was developed which could solve IQ test type analogy problems.
In 1963, Edward A. Feigenbaum & Julian Feldman published Computers and Thought, the first collection of articles about artificial intelligence.
In 1965, J. Allen Robinson invented a mechanical proof procedure, the Resolution Method, which allowed programs to work efficiently with formal logic as a representation language. In 1967, the Dendral program (Feigenbaum, Lederberg, Buchanan, Sutherland at Stanford) was demonstrated which could interpret mass spectra on organic chemical compounds. This was the first successful knowledge-based program for scientific reasoning. In 1969 the SRI robot, Shakey, demonstrated combining locomotion, perception and problem solving.
The years from 1969 to 1979 marked the early development of knowledge-based systems
In 1974: MYCIN demonstrated the power of rule-based systems for knowledge representation and inference in medical diagnosis and therapy. Knowledge representation
schemes were developed. These included frames developed by Minski. Logic based languages like Prolog and Planner were developed.
In the 1980s, Lisp Machines developed and marketed.
Around 1985, neural networks return to popularity
In 1988, there was a resurgence of probabilistic and decision-theoretic methods
The early AI systems used general systems, little knowledge. AI researchers realized that specialized knowledge is required for rich tasks to focus reasoning.
The 1990's saw major advances in all areas of AI including the following:
• machine learning, data mining
• intelligent tutoring,
• case-based reasoning,
• multi-agent planning, scheduling,
• uncertain reasoning,
• natural language understanding and translation,
• vision, virtual reality, games, and other topics.

Rod Brooks' COG Project at MIT, with numerous collaborators, made significant progress in building a humanoid robot
The first official Robo-Cup soccer match featuring table-top matches with 40 teams of interacting robots was held in 1997. For details, see the site http://murray.newcastle.edu.au/users/students/2002/c3012299/bg.html
In the late 90s, Web crawlers and other AI-based information extraction programs become essential in widespread use of the world-wide-web.
Interactive robot pets ("smart toys") become commercially available, realizing the vision of the 18th century novelty toy makers.
In 2000, the Nomad robot explores remote regions of Antarctica looking for meteorite samples.
We will now look at a few famous AI system that has been developed over the years.
1. ALVINN:
Autonomous Land Vehicle In a Neural Network
In 1989, Dean Pomerleau at CMU created ALVINN. This is a system which learns to control vehicles by watching a person drive. It contains a neural network whose input is a 30x32 unit two dimensional camera image. The output layer is a representation of the direction the vehicle should travel.
The system drove a car from the East Coast of USA to the west coast, a total of about
2850 miles. Out of this about 50 miles were driven by a human, and the rest solely by the system.
2. Deep Blue
In 1997, the Deep Blue chess program created by IBM, beat the current world chess champion, Gary Kasparov.
3. Machine translation
A system capable of translations between people speaking different languages will be a remarkable achievement of enormous economic and cultural benefit. Machine translation is one of the important fields of endeavour in AI. While some translating systems have been developed, there is a lot of scope for improvement in translation quality.
4. Autonomous agents
In space exploration, robotic space probes autonomously monitor their surroundings, make decisions and act to achieve their goals.
NASA's Mars rovers successfully completed their primary three-month missions in April, 2004. The Spirit rover had been exploring a range of Martian hills that took two months to reach. It is finding curiously eroded rocks that may be new pieces to the puzzle of the region's past. Spirit's twin, Opportunity, had been examining exposed rock layers inside a crater.
5. Internet agents
The explosive growth of the internet has also led to growing interest in internet agents to
monitor users' tasks, seek needed information, and to learn which information is most useful
For more information the reader may consult AI in the news:
http://www.aaai.org/AITopics/html/current.html

Theory of Relational Database Design for JNTU BTech CSE and IT students and FAQ for ORACLE developers

2010-03-11T22:14:00.000-08:00

1 Informal Design Guidelines for Relational Databases
What is relational database design?
The grouping of attributes to form "good" relation schemas

Two levels of relation schemas:
- The logical "user view" level
- The storage "base relation" level

Design is concerned mainly with base relations

What are the criteria for "good" base relations?
We first discuss informal guidelines for good relational design
Then we discuss formal concepts of functional dependencies and normal forms
1NF (First Normal Form)
2NF (Second Normal Form)
3NF (Third Normal Form)
BCNF (Boyce-Codd Normal Form)
Semantics of the Relation Attributes

GUIDELINE 1: Informally, each tuple in a relation should represent one
entity or relationship instance. (Applies to individual relations and
their attributes).

- Attributes of different entities (EMPLOYEEs, DEPARTMENTs, PROJECTs)
should not be mixed in the same relation

- Only foreign keys should be used to refer to other entities

- Entity and relationship attributes should be kept apart as much as possible.

Bottom Line: Design a schema that can be explained easily relation by
relation.
Redundant Information in Tuples and Update Anomalies

- Mixing attributes of multiple entities may cause problems

- Information is stored redundantly wasting storage

- Problems with update anomalies:
- Insertion anomalies
- Deletion anomalies
Modification anomalies

EXAMPLE OF AN UPDATE ANOMALY:

Consider the relation:
EMP_PROJ ( Emp#, Proj#, Ename, Pname, No_hours)

Update Anomaly: Changing the name of project number P1 from “Billing”
to “Customer-Accounting” may cause this update to be made for all 100
employees working on project P1.

Insert Anomaly: Cannot insert a project unless an employee is assigned to .
Inversely- Cannot insert an employee unless an he/she
is assigned to a project.

Delete Anomaly: When a project is deleted, it will result in
deleting all the employees who work on that project. Alternately, if
an employee is the sole employee on a project, deleting that employee
would result in deleting the corresponding project.
GUIDELINE 2: Design a schema that does not suffer from the insertion,
deletion and update anomalies. If there are any present, then note
them so that applications can be made to take them into account

Null Values in Tuples

GUIDELINE 3: Relations should be designed such that their tuples will
have as few NULL values as possible

- Attributes that are NULL frequently could be placed in separate
relations (with the primary key)

- Reasons for nulls:
a. attribute not applicable or invalid
b. attribute value unkown (may exist)
c. value known to exist, but unavailable
Spurious Tuples

- Bad designs for a relational database may result in erroneous
results for certain JOIN operations

- The "lossless join" property is used to guarantee meaningful results
for join operations

GUIDELINE 4: The relations should be designed to satisfy the lossless
join condition. No spurious tuples should be generated by doing a
natural-join of any relations.

- There are two important properties of decompositions: (a)
non-additive or losslessness of the corresponding join, (b)
preservation of the functional dependencies. Note that property (a) is
extremely important and cannot be sacrificed. property (b) is less
stringent and may be sacrificed.
Functional Dependencies

- Functional dependencies (FDs) are used to specify formal measures
of the "goodness" of relational designs

- FDs and keys are used to define normal forms for relations

- FDs are constraints that are derived from the meaning and
interrelationships of the data attributes

- A set of attributes X functionally determines a set of attributes Y
if the value of X determines a unique value for Y

- X -> Y holds if whenever two tuples have the same value for X, they
must have the same value for Y

- For any two tuples t1 and t2 in any relation instance r(R):
If t1[X]=t2[X], then t1[Y]=t2[Y]

- X -> Y in R specifies a constraint on all relation instances r(R)

- Written as X -> Y; can be displayed graphically on a relation schema
as in Figures. ( denoted by the arrow: ).

- FDs are derived from the real-world constraints on the attributes

Examples of FD constraints:
- social security number determines employee name
SSN -> ENAME

- project number determines project name and location
PNUMBER -> {PNAME, PLOCATION}

- employee ssn and project number determines the hours per week that
the employee works on the project
{SSN, PNUMBER} -> HOURS

- An FD is a property of the attributes in the schema R

- The constraint must hold on every relation instance r(R)

- If K is a key of R, then K functionally determines all attributes in
R (since we never have two distinct tuples with t1[K]=t2[K])
Introduction to Normalization-
Normalization: Process of decomposing unsatisfactory "bad" relationsby breaking up their attributes into smaller relations-
Normal form: Condition using keys and FDs of a relation to certifywhether a relation schema is in a particular normal form- 2NF, 3NF, BCNF based on keys and FDs of a relation schema
- 4NF based on keys, multi-valued dependencies : MVDs; 5NF based onkeys, join dependencies : JDs
First Normal Form- Disallows composite attributes, multivalued attributes, and nestedrelations; attributes whose values for an individual tuple arenon-atomic
Second Normal Form- Uses the concepts of FDs, primary keyDefinitions:- Prime attribute - attribute that is member of the primary key K- Full functional dependency - a FD Y -> Z where removal of anyattribute from Y means the FD does not hold any more
Examples: - {SSN, PNUMBER} -> HOURS is a full FD since neither SSN -> HOURS nor PNUMBER -> HOURS hold - {SSN, PNUMBER} -> ENAME is not a full FD (it is called apartialdependency ) since SSN -> ENAME also holds-
A relation schema R is in second normal form (2NF) if everynon-prime attribute A in R is fully functionally dependent on theprimary key-
R can be decomposed into 2NF relations via the process of 2NF normalization
Third Normal FormDefinition:- Transitive functional dependency - a FD X -> Z that can be derivedfrom two FDs X -> Y and Y -> Z Examples:
- SSN -> DMGRSSN is a transitive FD since SSN -> DNUMBER and DNUMBER -> DMGRSSN hold - SSN -> ENAME is non-transitive since there is no set of attributes X where SSN -> X and X -> ENAME-
A relation schema R is in third normal form (3NF) if it is in 2NFand no non-prime attribute A in R is transitively dependent on theprimary keyR can be decomposed into 3NF relations via the process of 3NF normalization
NOTE:In X -> Y and Y -> Z, with X as the primary key, we consider this aproblem only if Y is not a candidate key. When Y is a candidate key,there is no problem with the transitive dependency .E.g., Consider EMP (SSN, Emp#, Salary ).Here, SSN -> Emp# -> Salary and Emp# is a candidate key.
BCNF (Boyce-Codd Normal Form)- A relation schema R is in Boyce-Codd Normal Form (BCNF) if whenever
an FD X -> A holds in R, then X is a superkey of R-
Each normal form is strictly stronger than the previous one: Every 2NF relation is in 1NF Every 3NF relation is in 2NF Every BCNF relation is in 3NF- There exist relations that are in 3NF but not in BCNF- The goal is to have each relation in BCNF (or 3NF)

CSE PREVIOUS PAPERS

2009-05-10T21:52:00.000-07:00

CLICK HERE TO DOWN LOAD PAPER

INFORMATION TECHNOLOGY SYLLABUS FOR JNTU BTECH

2009-05-08T01:57:00.001-07:00

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD.

B. TECH. INFORMATION TECHNOLOGY

I Year

COURSE STRUCTURE
__________________________________________________________________________________
Code Subject T P/D C
__________________________________________________________________________________
English 2+1* - 4
Mathematics – I 3+1* - 6
Mathematical Methods 3+1* - 6
Applied Physics 2+1* - 4
C Programming and Data Structures 3+1* - 6
Basic Electrical Engineering 2+1* - 4
Electronic Devices and Circuits 3+1* - 6
Engineering Drawing - 3 4
Computer Programming Lab - 3 4
Electrical and Electronics Lab - 3 4
English Language Communication Skills Lab - 3 4
IT Work-Shop - 3 4
Total 20 15 56
___________________________________________________________________________________

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD.

B. TECH. INFORMATION TECHNOLOGY

II YEAR I Semester

COURSE STRUCTURE

Code Subject T P C
______________________________________________________________________________________
Probability and Statistics 4+1* 0 4
Mathematical Foundations of Computer Science 4+1* 0 4
Advanced Data Structures and Algorithms 4+1 * 0 4
Digital Logic Design 4+1 * 0 4
Unix and Shell Programming 4+1 * 0 4
Managerial Economics and Financial Analysis 4+1* 0 4
Advanced Data Structures and Algorithms Lab 0 3 2
Unix and Shell Programming Lab 0 3 2

Total 30 6 28
_____________________________________________________________________________________

II YEAR II Semester

COURSE STRUCTURE

Code Subject T P C
______________________________________________________________________________________
Object Oriented Programming 4+1* 0 4
Computer Organization 4+1 * 0 4
Database Management systems 4+1 * 0 4
Operating System 4+1 * 0 4
Environmental Studies 4+1 * 0 4
Software Engineering 4+1 * 0 4
Object Oriented Programming Lab 0 3 2
Database Management Systems Lab 0 3 2

Total 30 6 28
______________________________________________________________________________________

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD.

B. TECH. INFORMATION TECHNOLOGY

III YEAR I Semester

COURSE STRUCTURE

Code Subject T P C
______________________________________________________________________________________
Automata and Compiler Design 4+1* 0 4
Data Communication Systems 4+1* 0 4
Microprocessor and Interfacing 4+1 * 0 4
Computer Graphics 4+1 * 0 4
Distributed Databases 4+1 * 0 4
Software Testing Methodologies 4+1 * 0 4
Advanced English Communication Skills Lab 0 3 2
Microprocessors and interfacing Lab 0 3 2
Total 30 6 28
______________________________________________________________________________________

III YEAR II Semester

COURSE STRUCTURE

Code Subject T P C
______________________________________________________________________________________
Web Technologies 4+1* 0 4
Computer Networks 4+1 * 0 4
E-Commerce 4+1 * 0 4
Middleware Technologies 4+1 * 0 4
Data Warehousing and Data Mining 4+1 * 0 4
Object Oriented Analysis and Design 4+1 * 0 4
Computer Networks and Case Tools Lab 0 3 2
Web Technologies Lab 0 3 2
Total 30 6 28
______________________________________________________________________________________

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD.

B. TECH. INFORMATION TECHNOLOGY

IV YEAR I Semester
COURSE STRUCTURE

Code Subject T P C
______________________________________________________________________________________
Multimedia and Application Development 4+1* 0 4
Embedded Systems 4+1 * 0 4
Network Programming 4+1* 0 4
Mobile Computing 4+1 * 0 4

ELECTIVE - I : 4+1* 0 4
Information Retrieval Systems
Information Security
Virtual Reality
Human Computer Interaction

ELECTIVE - II : 4+1* 0 4
Software Project Management
Advanced computing concepts
Image Processing
Network Programming lab 0 3 2
Multimedia and Application Development Lab 0 3 2
Total 30 6 28
______________________________________________________________________________________

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD.

B. TECH. INFORMATION TECHNOLOGY

IV YEAR II Semester
COURSE STRUCTURE

Code Subject T P C
______________________________________________________________________________________
Management Science 4+1* 0 4

ELECTIVE - III : 4+1* 0 4
Multimedia Databases
Network Management Systems
Biometrics

ELECTIVE – IV : 4+1* 0 4
Bio-informatics
Design Patterns
Pattern Recognition
Industry Oriented Mini Project 0 0 2
Seminar 0 0 2
Project Work 0 0 10
Comprehensive Viva 0 0 2

Total 15 – 28
______________________________________________________________________________________

Note : All End Examinations (Theory and Practical) are of three hours duration.
* - Tutorial T – Theory P – Practical C - Credits

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
2+1* 0 4
ENGLISH

1. INTRODUCTION :
In view of the growing importance of English as a tool for global communication and the consequent emphasis on training students to acquire communicative competence, the syllabus has been designed to develop linguistic and communicative competence of Engineering students. The prescribed books and the exercises are meant to serve broadly as students’ handbooks.
In the English classes, the focus should be on the skills of reading, writing, listening and speaking and for this the teachers should use the text prescribed for detailed study. For example, the students should be encouraged to read the texts/selected paragraphs silently. The teachers can ask comprehension questions to stimulate discussion and based on the discussions students can be made to write short paragraphs/essays etc.
The text for non-detailed study is for extensive reading/reading for pleasure by the students. Hence, it is suggested that they read it on their own with topics selected for discussion in the class. The time should be utilized for working out the exercises given after each section , as also for supplementing the exercises with authentic materials of a similar kind for example, from newspaper articles, advertisements, promotional material etc.. However, the stress in this syllabus is on skill development and practice of language skills.

2. OBJECTIVES:
a. To improve the language proficiency of the students in English with emphasis on LSRW skills.
b. To equip the students to study academic subjects with greater facility through the theoretical and practical components of the English syllabus.
c. To develop the study skills and communication skills in formal and informal situations.

3. SYLLABUS :
Listening Skills:
Objectives
1. To enable students to develop their listening skill so that they may appreciate its role in the LSRW skills approach to language and improve their pronunciation
2. To equip students with necessary training in listening so that can comprehend the speech of people of different backgrounds and regions
Students should be given practice in listening to the sounds of the language to be able to recognise them, to distinguish between them to mark stress and recognise and use the right intonation in sentences.
• Listening for general content
• Listening to fill up information
• Intensive listening
• Listening for specific information

Speaking Skills :
Objectives
1. To make students aware of the role of speaking in English and its contribution to their success.
2. To enable students to express themselves fluently and appropriately in social and professional contexts.

• Oral practice
• Describing objects/situations/people
• Role play – Individual/Group activities (Using exercises from all the nine units of the prescribed text: Learning English : A Communicative Approach.)
• Just A Minute(JAM) Sessions.

Reading Skills:
Objectives
1. To develop an awareness in the students about the significance of silent reading and comprehension.
2. To develop the ability of students to guess the meanings of words from context and grasp the overall message of the text, draw inferences etc.

• Skimming the text
• Understanding the gist of an argument
• Identifying the topic sentence
• Inferring lexical and contextual meaning
• Understanding discourse features
• Recognizing coherence/sequencing of sentences

NOTE : The students will be trained in reading skills using the prescribed text for detailed study.
They will be examined in reading and answering questions using ‘unseen’ passages which
may be taken from the non-detailed text or other authentic texts, such as
magazines/newspaper articles.

Writing Skills :
Objectives
1. To develop an awareness in the students about writing as an exact and formal skill
2. To equip them with the components of different forms of writing, beginning with the lower order ones.

• Writing sentences
• Use of appropriate vocabulary
• Paragraph writing
• Coherence and cohesiveness
• Narration / description
• Note Making
• Formal and informal letter writing
• Editing a passage

4. TEXTBOOKS PRESCRIBED:
In order to improve the proficiency of the student in the acquisition of the four skills mentioned above, the following texts and course content, divided into Eight Units, are prescribed:

For Detailed study
1. LEARNING ENGLISH: A Communicative Approach, Hyderabad: Orient Longman, 2006. (Six Selected Lessons)
For Non-detailed study
2. WINGS OF FIRE: An Autobiography – APJ Abdul Kalam, Abridged version with Exercises, Universities Press (India) Pvt. Ltd., 2004.
A. STUDY MATERIAL:
Unit –I
1. Astronomy from LEARNING ENGLISH: A Communicative Approach, Orient Longman, 2005.
2. Chapters 1-4 from Wings of Fire: An Autobiography – APJ Abdul Kalam, an abridged version with Exercises, Universities Press (India) Pvt. Ltd.,2004
Unit –II
3. Information Technology from LEARNING ENGLISH: A Communicative Approach, Orient Longman, 2005.
4. Chapters 5-8 from Wings of Fire: An Autobiography – APJ Abdul Kalam, an abridged version with Exercises, Universities Press (India) Pvt. Ltd.,2004
Unit –III
5. Humour from LEARNING ENGLISH: A Communicative Approach, Orient Longman, 2005.
6. Chapters 9-12 from Wings of Fire: An Autobiography – APJ Abdul Kalam, an abridged version with Exercises., Universities Press (India) Pvt. Ltd.,2004
Unit –IV
7. Environment from LEARNING ENGLISH: A Communicative Approach, Orient Longman, 2005.
8. Chapters 13-16 from Wings of Fire: An Autobiography – APJ Abdul Kalam, an abridged version with Exercises, Universities Press (India) Pvt. Ltd.,2004

Unit –V
9. Inspiration from LEARNING ENGLISH: A Communicative Approach, Orient Longman, 2005.
10. Chapters 17-20 from Wings of Fire: An Autobiography – APJ Abdul Kalam, an abridged version with Exercises, Universities Press (India) Pvt. Ltd.,2004.
Unit – VI
11. Human Interest from LEARNING ENGLISH: A Communicative Approach, Orient Longman, 2005.
12. Chapters 21-24 from Wings of Fire: An Autobiography – APJ Abdul Kalam, an abridged version with Exercises, Universities Press (India) Pvt. Ltd., 2004.
* Exercises from the lessons not prescribed shall also be used for classroom tasks.
Unit – VII
Exercises on
Reading and Writing Skills
Reading Comprehension
Situational dialogues
Letter writing
Essay writing
Unit – VIII
Practice Exercises on Remedial Grammar covering
Common errors in English, Subject-Verb agreement, Use of Articles and Prepositions,
Tense and aspect
Vocabulary development covering
Synonyms & Antonyms, one-word substitutes, prefixes & suffixes, Idioms & phrases, words often confused.
REFERENCES :
1. Strengthen Your English, Bhaskaran & Horsburgh, Oxford University Press
2. Basic Communication Skills for Technology, Andrea J Rutherfoord, Pearson Education Asia.
3. Murphy’s English Grammar with CD, Murphy, Cambridge University Press
4. English Skills for Technical Students by Orient Longman
5. Everyday Dialogues in English by Robert J. Dixson, Prentice-Hall of India Ltd., 2006.
6. English For Technical Communication, Vol. 1 & 2, by K. R. Lakshmi Narayanan, Sci tech. Publications.
7. A Hand book of English for Engineers & Technologists by Dr. P. Eliah, B. S. Publications.
8. Developing Communication Skills by Krishna Mohan & Meera Benerji (Macmillan)
9. Speaking and Writing for Effective Business Communication, Francis Soundararaj, MacMillan India Ltd., 2007.
10. The Oxford Guide to Writing and Speaking, John Seely, Oxford

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
3+1* 0 6
MATHEMATICS – I

UNIT – I
Differential equations of first order and first degree – exact, linear and Bernoulli. Applications to Newton’s Law of cooling, Law of natural growth and decay, orthogonal trajectories.

UNIT – II
Non-homogeneous linear differential equations of second and higher order with constant coefficients with RHS term of the type e , Sin ax, cos ax, polynomials in x, e V(x), xV(x), method of variation of parameters.

UNIT – III
Rolle’s Theorem – Lagrange’s Mean Value Theorem – Cauchy’s mean value Theorem – Generalized Mean Value theorem (all theorems without proof) Functions of several variables – Functional dependence- Jacobian- Maxima and Minima of functions of two variables with constraints and without constraints

UNIT – IV
Radius, Centre and Circle of Curvature – Evolutes and Envelopes Curve tracing – Cartesian , polar and Parametric curves.

UNIT – V
Applications of integration to lengths, volumes and surface areas in Cartesian and polar coordinates multiple integrals - double and triple integrals – change of variables – change of order of integration.

UNIT – VI
Sequences – series – Convergences and divergence – Ratio test – Comparison test – Integral test – Cauchy’s root test – Raabe’s test – Absolute and conditional convergence

UNIT – VII
Vector Calculus: Gradient- Divergence- Curl and their related properties of sums- products- Laplacian and second order operators. Vector Integration - Line integral – work done – Potential function – area- surface and volume integrals Vector integral theorems: Green’s theorem-Stoke’s and Gauss’s Divergence Theorem (With out proof). Verification of Green’s - Stoke’s and Gauss’s Theorems.

UNIT – VIII
Laplace transform of standard functions – Inverse transform – first shifting Theorem, Transforms of derivatives and integrals – Unit step function – second shifting theorem – Dirac’s delta function – Convolution theorem – Periodic function - Differentiation and integration of transforms-Application of Laplace transforms to ordinary differential equations Partial fractions-Heaviside’s Partial fraction expansion theorem.

Text Books:
1. A text Book of Engineering Mathematics, Vol-1 T. K. V. Iyengar, B. Krishna Gandhi and Others, S. Chand & Company.
2. A text Book of Engineering Mathematics, C. Sankaraiah, V. G. S. Book Links.
3. A text Book of Engineering Mathematics, Shahnaz Bathul, Right Publishers.
4. A text Book of Engineering Mathematics, P. Nageshwara Rao, Y. Narasimhulu & N. Prabhakar Rao, Deepthi Publications.

References:
1. A text Book of Engineering Mathematics, B. V. Raman, Tata Mc Graw Hill.
2. Advanced Engineering Mathematics, Irvin Kreyszig, Wiley India Pvt. Ltd.
3. A text Book of Engineering Mathematics, Thamson Book Collection.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
3+1* 0 6
MATHEMATICAL METHODS
UNIT – I
Matrices and Linear systems of equations: Elementary row transformations-Rank-Echelon form, Normal form – Solution of Linear Systems – Direct Methods- LU Decomposition- LU Decomposition from Gauss Elimination –Solution of Tridiagonal Systems-Solution of Linear Systems

UNIT – II
Eigen values, eigen vectors – properties – Cayley-Hamilton Theorem - Inverse and powers of a matrix by Cayley-Hamilton theorem – Diagonolization of matrix. Calculation of powers of matrix – Modal and spectral matrices.

UNIT – III
Real matrices – Symmetric, skew - symmetric, orthogonal, Linear Transformation – Orthogonal Transformation. Complex matrices: Hermitian, Skew-Hermitian and Unitary – Eigen values and eigen vectors of complex matrices and their properties. Quadratic forms- Reduction of quadratic form to canonical form – Rank - Positive, negative definite - semi definite - index - signature - Sylvester law.

UNIT – IV
. Solution of Algebraic and Transcendental Equations: Introduction – The Bisection Method – The Method of False Position – The Iteration Method – Newton-Raphson Method.

Interpolation: Introduction- Errors in Polynomial Interpolation – Finite differences- Forward Differences- Backward differences –Central differences – Symbolic relations and separation of symbols-Differences of a polynomial-Newton’s formulae for interpolation – Central difference interpolation Formulae – Gauss Central Difference Formulae –Interpolation with unevenly spaced points-Lagrange’s Interpolation formula.

UNIT – V
Curve fitting: Fitting a straight line –Second degree curve-exponentional curve-power curve by method of least squares. Numerical Differentiation and Integration– Trapezoidal rule – Simpson’s 1/3 Rule –Simpson’s 3/8 Rule.

UNIT – VI
Numerical solution of Ordinary Differential equations: Solution by Taylor’s series-Picard’s Method of successive Approximations-Euler’s Method-Runge-Kutta Methods –Predictor-Corrector Methods- Adams- Moulton Method –Milne’s Method.

UNIT – VII
Fourier Series: Determination of Fourier coefficients – Fourier series – even and odd functions – Fourier series in an arbitrary interval – even and odd periodic continuation – Half-range Fourier sine and cosine expansions. Fourier integral theorem (only statement)– Fourier sine and cosine integrals. Fourier transform – Fourier sine and cosine transforms – properties – inverse transforms – Finite Fourier transforms.

UNIT – VIII
Formation of partial differential equations by elimination of arbitrary constants and arbitrary functions –solutions of first order linear (Lagrange) equation and nonlinear (standard type) equations. Method of separation of variables. z-transform – inverse z-transform - properties – Damping rule – Shifting rule – Initial and final value theorems. Convolution theorem – Solution of difference equation by z-transforms.
Text Books:
1. Mathematical Methods, T. K. V. Iyengar, B. Krishna Gandhi and Others, S. Chand & Company.
2. Mathematical Methods, C. Sankaraiah, V. G. S. Book Links.
3. A text book of Mathematical Methods, V. Ravindranath, A. Vijayalaxmi, Himalaya Publishers.
4. A text book of Mathematical Methods, Shahnaz Bathul, Right Publisshers.
References:
1. A text Book of Engineering Mathematics, B. V. Raman, Tata Mc Graw Hill.
2. Advanced Engineering Mathematics, Irvin Kreyszig, Wiley India Pvt. Ltd.
3. Numerical Methods for Scientific and Engineering Computation, M. K. Jain, S. R. K. Iyengar & R. K. Jain, New Age International Publishers.
4. Elementary Numerical Analysis, Aitkinson & Han, Wiely India, 3rd Edition, 2006

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
2+1* 0 4
APPLIED PHYSICS
UNIT I

BONDING IN SOLIDS : Introduction - Types of bonding in solids - Estimation of cohesive energy – Madelung constant.

CRYSTAL STRUCTURES AND X-RAY DIFFRACTION: Introduction -Space lattice - Basis - Unit cell - Lattice parameter - Bravais lattices – Crystal systems - Structure and packing fractions of Simple cubic - Body centered cubic – Face centered cubic crystals - Directions and planes in crystals – Miller indices - Separation between successive [h k l] planes - Diffraction of X-rays by crystal planes - Bragg’s law - Laue method - Powder method.

UNIT II

PRINCIPLES OF QUANTUM MECHANICS: Waves and particles - Planck’s quantum theory – de Broglie hypothesis – Matter waves - Davisson and Germer experiment – G. P. Thomson experiment – Heisenberg uncertainty principle - Schrödinger’s time independent wave equation - Physical significance of the wave function - Particle in one dimensional potential box.

UNIT III

ELECTRON THEORY OF METALS: Classical free electron theory - Mean free path - Relaxation time and drift velocity - Quantum free electron theory - Fermi-Dirac distribution (analytical) and its dependence on temparature – Fermi energy – Electron scattering and resistance.

BAND THEORY OF SOLIDS: Bloch theorem - Kronig-Penney model (qualitative treatment) - Origin of energy band formation in solids – Classification of materials into conductors, semi conductors & insulators - Concept of effective mass of an electron.

UNIT IV
DIELECTRIC PROPERTIES: Introduction - Dielectric constant - Electronic, ionic and orientational polarizations - Internal fields in solids – Clausius - Mossotti equation – Dielectrics in alternating fields – Frequency dependence of the polarizability - Ferro and Piezo electricity.

MAGNETIC PROPERTIES : Permeability - Magnetization - Origin of magnetic moment – Classification of magnetic materials - Dia, para and ferro magnetism - Hysteresis curve - Soft and hard magnetic materials.

UNIT V

SEMICONDUCTORS : Introduction - Intrinsic semiconductor and carrier concentration – Equation for conductivity - Extrinsic semiconductor and carrier concentration - Drift and diffusion - Einstein’s equation - Hall effect – Direct & indirect band gap semiconductors.

SUPERCONDUCTIVITY: General properties - Meissner effect - Penetration depth - Type I and Type II superconductors - Flux quantization – DC and AC Josephson effect –BCS Theory - Applications of superconductors.

UNIT VI

LASERS: Introduction - Characteristics of Lasers - Spontaneous and stimulated emission of radiation - Einstein’s coefficients - Population inversion - Ruby laser - Helium-Neon Laser – CO2 laser -Semiconductor Laser – Applications of lasers.

UNIT VII
FIBER OPTICS AND HOLOGRAPHY: Introduction - Principle of optical fiber - Acceptance angle and acceptance cone - Numerical aperture – Types of optical fibers and refractive index profiles – Attenuation in optical fibers - Application of optical fibers – Basic principles of holography – Construction and reconstruction of image on hologram – Applications of holography.

UNIT VIII
SCIENCE & TECHNOLOGY OF NANOMATERIALS: Introduction to Nano materials - Basic principles of Nanoscience & Technology – Fabrication of nano materials – Physical & chemical properties of nanomaterials – Carbon nanotubes – Applications of nanotechnology.

TEXTBOOKS:
1. Applied Physics 2nd edition by Dr. P. Appala Naidu & Dr. M. Chandra Shekar, V.G.S. Book links.
2. Introduction to Solid State Physics by C. Kittel ; Wiley Eastern Ltd.
3. Nanotechnology by Mark Ratner and Daniel Ratner; Pearson Education.

REFERENCES:
1. Materials Science and Engineering by V. Raghavan; Prentice-Hall India.
2. Materials Science by M. Arumugam; Anuradha Agencies.
3. Solid State Physics by N.W. Ashcroft & N. David Merwin; Thomson Learning.
4. Materials Science by M.S.Vijaya & G. Rangarajan; Tata McGraw Hill.
5. Solid State Physics by P.K. Palanisamy; Scitech Publications (India) Pvt. Ltd.
6. Nano Materials by A.K. Bandyopadhyay, New Age International Publishers.
7. Applied Physics by P.K.Mittal; I.K. International.
8. Applied Physics by K. Vijay Kumar & T. Sreekanth; S. Chand & Company Ltd.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
3+1* 0 6
C PROGRAMMING AND DATA STRUCTURES

UNIT - I
Algorithm / pseudo code, flowchart, program development steps, structure of C program, A Simple C program, identifiers, basic data types and sizes, Constants, variables, arithmetic, relational and logical operators, increment and decrement operators, conditional operator, bit-wise operators, assignment operators, expressions, type conversions, conditional expressions, precedence and order of evaluation.

Input-output statements, statements and blocks, if and switch statements, loops- while, do-while and for statements, break, continue, goto and labels, programming examples.

UNIT - II
Designing structured programs, Functions, basics, parameter passing, storage classes- extern, auto, register, static, scope rules, block structure, user defined functions, standard library functions, recursive functions, header files, C preprocessor, example c programs.

UNIT - III
Arrays- concepts, declaration, definition, accessing elements, storing elements, arrays and functions, two-dimensional and multi-dimensional arrays, applications of arrays. pointers- concepts, initialization of pointer variables, pointers and function arguments, address arithmetic, Character pointers and functions, pointers to pointers, pointers and multidimensional arrays, dynamic memory managements functions, command line arguments, c program examples.

UNIT - IV
Derived types- structures- declaration, definition and initialization of structures, accessing structures, nested structures, arrays of structures, structures and functions, pointers to structures, self referential structures, unions, typedef, bitfields, C program examples.

UNIT - V
Input and output – concept of a file, text files and binary files, streams, standard I/o, Formatted I/o, file I/o operations, error handling, C program examples.

UNIT - VI
Searching – Linear and binary search methods, sorting – Bubble sort, selection sort, Insertion sort, Quick sort, merge sort.

UNIT – VII
Introduction to data structures, singly linked lists, doubly linked lists, circular list, representing stacks and queues in C using arrays and linked lists, infix to post fix conversion, postfix expression evaluation.

UNIT - VIII
Trees- Binary tress, terminology, representation, traversals, graphs- terminology, representation, graph traversals (dfs & bfs)

TEXT BOOKS :
1. Computer science, A structured programming approach using C, B.A. Forouzan and R.F. Gilberg, Third edition, Thomson.
2. DataStructures Using C – A.S.Tanenbaum, Y. Langsam, and M.J. Augenstein, PHI/Pearson education.
REFERENCES :
1. C& Data structures – P. Padmanabham, B.S. Publications.
2. The C Programming Language, B.W. Kernighan, Dennis M.Ritchie,
PHI/Pearson Education
3. C Programming with problem solving, J.A. Jones & K. Harrow,
dreamtech Press
4. Programming in C – Stephen G. Kochan, III Edition, Pearson Eductaion.
5. Data Structures and Program Design in C, R.Kruse, C.L. Tondo, BP Leung, Shashi M, Second Edition, Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
3+1* 0 6
BASIC ELECTRICAL ENGINEERING

UNIT - I
Introduction to Electrical Engineering : Essence of electricity, Conductors, semiconductors and insulators (elementary treatment only); Electric field; electric current, potential and potential difference, electromotive force, electric power, ohm’s law, basic circuit components, electromagnetism related laws,
Magnetic field due to electric current flow ,force on a current carrying conductor placed in a magnetic field, Faradays laws of electromagnetic induction. Types of induced EMF’s, Kirchhoff’s laws. Simple problems.

UNIT-II
Network Analysis : Basic definitions, types of elements , types of sources, resistive networks, inductive networks, capacitive networks, series parallel circuits, star delta and delta star transformation , Network theorems- Superposition , Thevenins’s, Maximum power transfer theorems and simple problems.

UNIT-III
Magnetic Circuits : Basic definitions, analogy between electric and magnetic circuits, magnetization characteristics of Ferro magnetic materials, self inductance and mutual inductance, energy in linear magnetic systems, coils connected in series, attracting force of electromagnets.

UNIT-IV
Alternating Quantities : Principle of ac voltages , waveforms and basic definitions, relationship between frequency, speed and number of poles, root mean square and average values of alternating currents and voltage, form factor and peak factor, phasor representation of alternating quantities, the J operator and phasor algebra, analysis of ac circuits with single basic network element, single phase series circuits, single phase parallel circuits, single phase series parallel circuits, power in ac circuits.

UNIT-V
Transformers : Principles of operation, Constructional Details, Ideal Transformer and Practical Transformer, Losses, Transformer Test, Efficiency and Regulation Calculations (All the above topics are only elementary
treatment and simple problems).

UNIT-VI
Direct current machines : Principle of operation of dc machines, armature windings, e.m.f equation in a dc machine, Torque production in a dc machine, Operation of a dc machine as a generator, operation of a dc machine as a motor.

UNIT-VII
A.C Machines : Three phase induction motor, principle of operation, slip and rotor frequency, torque (simple problems). Synchronous Machines: Principle of operation, EMF equation (Simple problems on EMF). Synchronous
motor principle and operation (Elementary treatment only)

UNIT VIII
Basic Instruments : Introduction, classification of instruments, operating principles, essential features of measuring instruments, Moving coil permanent magnet (PMMC) instruments, Moving Iron of Ammeters
and Voltmeters (elementary Treatment only)

TEXT BOOKS :
1. Basic Electrical Engineering - By M.S.Naidu and S. Kamakshiah – TMH.
2. Basic Electrical Engineering –By T.K.Nagasarkar and M.S. Sukhija Oxford University Press.

REFERENCES :
1. Theory and Problems of Basic Electrical Engineering by D.P.Kothari & I.J. Nagrath PHI.
2. Principles of Electrical Engineering by V.K Mehta, S.Chand Publications.
3. Essentials of Electrical and Computer Engineering by David V. Kerns, JR. J. David Irwin Pearson.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
3+1* 0 6
ELECTRONIC DEVICES AND CIRCUITS

UNIT-I
ELECTRON DYNAMICS AND CRO: Motion of charged particles in electric and magnetic fields. Simple problems involving electric and magnetic fields only. Electrostatic and magnetic focusing. Principles of CRT, deflection sensitivity (Electrostatic and magnetic deflection), Parallel Electric and Magnetic fields, Perpendicular Electric and Magnetic fields.

UNIT- II
JUNCTION DIODE CHARACTERISTICS : Review of semi conductor Physics – n and p –type semi conductors, Mass Action Law, Continuity Equation, Hall Effect, Fermi level in intrinsic and extrinsic semiconductors, Open-circuited p-n junction, The p-n junction Energy band diagram of PN diode, PN diode as as a rectifier (forward bias and reverse bias), The current components in p-n diode, Law of junction, Diode equation, Volt-ampere characteristics of p-n diode, Temperature dependence of VI characteristic, Transition and Diffusion capacitances, Step graded junction, Breakdown Mechanisms in Semi Conductor (Avalanche and Zener breakdown) Diodes, Zener diode characteristics, Characteristics of Tunnel Diode with the help of energy band diagrams, Varactar Diode, LED, LCD. And photo diode

UNIT- III
RECTIFIERS, FILTERS AND REGULATORS : Half wave rectifier, ripple factor, full wave rectifier, Harmonic components in a rectifier circuit, Inductor filter, Capacitor filter, L- section filter, P- section filter, Multiple L- section and Multiple Psection filter, and comparison of various filter circuits in terms of ripple factors, Simple circuit of a regulator using zener diode, Series and Shunt voltage regulators

UNIT- IV
TRANSISTOR and FET CHARACTERISTICS : Junction transistor, Transistor current components, Transistor as an amplifier, Transistor construction, Detailed study of currents in a transistor, Transistor alpha, Input and Output characteristics of transistor in Common Base, Common Emitter, and Common collector configurations, Relation between Alpha and Beta, typical transistor junction voltage values, JFET characteristics (Qualitative and Quantitative discussion), Small signal model of JFET, MOSFET characterisitics (Enhancement and depletion mode), Symbols of MOSFET, Comparison of Transistors, Introduction to SCR and UJT.

UNIT-V
BIASING AND STABILISATION : BJT biasing, DC equivalent model, criteria for fixing operating point, Fixed bias, Collector to base bias, Self bias techniques for stabilization, Stabilization factors, (S, S', S'’), Compensation techniques, (Compensation against variation in VBE, Ico,) Thermal run away, Thermal stability,

UNIT- VI
AMPLIFIERS : Small signal low frequency transistor amplifier circuits: h-parameter representation of a transistor, Analysis of single stage transistor amplifier using h-parameters: voltage gain, current gain, Input impedance and Output impedance. Comparison of transistor configurations in terms of AI , Ri , Av , Ro,

UNIT- VII
FEEDBACK AMPLIFIERS : Concept of feedback, Classification of feedback amplifiers, General characteristics of negative feedback amplifiers, Effect of Feedback on input and output characteristics, Voltage series, voltage shunt, current series, and current shunt feedback amplifiers with discrete components and their analysis

UNIT-VIII
OSCILLATORS : Condition for oscillations. RC-phase shift oscillators with Transistor and FET, Hartley and Colpitts oscillators, Wein bridge oscillator, Crystal oscillators, Frequency and amplitude stability of oscillators,

TEXT BOOKS :

1. Electronic Devices and Circuits – J.Millman, C.C.Halkias, and Satyabratha Jit Tata McGraw Hill, 2nd Ed., 2007.
2. Electronic Devices and Circuits – R.L. Boylestad and Louis Nashelsky, Pearson/Prentice Hall,9th Edition,2006.

REFERENCES :

1. Electronic Devices and Circuits – T.F. Bogart Jr., J.S.Beasley and G.Rico, Pearson Education, 6th edition, 2004.
2. Principles of Electronic Circuits – S.G.Burns and P.R.Bond, Galgotia Publications, 2nd Edn.., 1998.
3. Microelectronics – Millman and Grabel, Tata McGraw Hill, 1988.
4. Electronic Devices and Circuits – Dr. K. Lal Kishore, B.S. Publications, 2nd Edition, 2005.
5. Electronic Devices and Circuits- Prof GS N Raju I K International Publishing House Pvt .Ltd 2006

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
0 3 4
ENGINEERING DRAWING

UNIT – I
Introduction to engineering graphics – construction of ellipse, parabola and hyperbola – cylindrical curves.

UNIT – II
Orthographic projections of points, lines and planes – axis inclined to one planes and inclined to both the planes.

UNIT – III
Orthographic projections of solids :
Cylinder, cone, prism, pyramid and sphere positions and axis inclined to both the planes.

UNIT – IV
Isomeric projections of lines, planes and simple solids

UNIT – V
Conversion of orthographic views into isometric views and vice-versa.

TEXT BOOKS :
1. Engineering drawings By N.D.Bhatt
2 Engineering graphics By K.L. Narayana & P.Kannayya

REFERENCES:-
1. Engineering drawing and graphics: Venugopal/ New age
2. Engineering drawing : Johle / TMH

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
0 3 4
COMPUTER PROGRAMMING LAB
Objectives:
• To make the student learn a programming language.
• To teach the student to write programs in C solve the problems
• To Introduce the student to simple linear and non linear data structures such as lists, stacks, queues, trees and graphs.

Recommended Systems/Software Requirements:

• Intel based desktop PC
• ANSI C Compiler with Supporting Editors

Week l.
a) Write a C program to find the sum of individual digits of a positive integer.
b) A Fibonacci Sequence is defined as follows: the first and second terms in the sequence are 0 and 1. Subsequent terms are found by adding the preceding two terms in the sequence. Write a C program to generate the first n terms of the sequence.
c) Write a C program to generate all the prime numbers between 1 and n, where n is a value supplied by the user.

Week 2.
a) Write a C program to calculate the following Sum:
Sum=1-x2/2! +x4/4!-x6/6!+x8/8!-x10/10!
b) Write a C program toe find the roots of a quadratic equation.

Week 3
a) Write C programs that use both recursive and non-recursive functions
i) To find the factorial of a given integer.
ii) To find the GCD (greatest common divisor) of two given integers.
iii) To solve Towers of Hanoi problem.

Week 4
a) The total distance travelled by vehicle in ‘t’ seconds is given by distance = ut+1/2at2 where ‘u’ and ‘a’ are the initial velocity (m/sec.) and acceleration (m/sec2). Write C program to find the distance travelled at regular intervals of time given the values of ‘u’ and ‘a’. The program should provide the flexibility to the user to select his own time intervals and repeat the calculations for different values of ‘u’ and ‘a’.
b) Write a C program, which takes two integer operands and one operator form the user, performs the operation and then prints the result. (Consider the operators +,-,*, /, % and use Switch Statement)

Week 5
a) Write a C program to find both the larges and smallest number in a list of integers.
b) Write a C program that uses functions to perform the following:
i) Addition of Two Matrices
ii) Multiplication of Two Matrices

Week 6
a) Write a C program that uses functions to perform the following operations:
i) To insert a sub-string in to given main string from a given position.
ii) To delete n Characters from a given position in a given string.
b) Write a C program to determine if the given string is a palindrome or not

Week 7
a) Write a C program that displays the position or index in the string S where the string T begins, or – 1 if S doesn’t contain T.
b) Write a C program to count the lines, words and characters in a given text.

Week 8
a) Write a C program to generate Pascal’s triangle.
b) Write a C program to construct a pyramid of numbers.

Week 9
Write a C program to read in two numbers, x and n, and then compute the sum of this geometric progression:
1+x+x2+x3+………….+xn
For example: if n is 3 and x is 5, then the program computes 1+5+25+125.
Print x, n, the sum
Perform error checking. For example, the formula does not make sense for negative exponents – if n is less than 0. Have your program print an error message if n<0, then go back and read in the next pair of numbers of without computing the sum. Are any values of x also illegal ? If so, test for them too.

Week 10
a) 2’s complement of a number is obtained by scanning it from right to left and complementing all the bits after the first appearance of a 1. Thus 2’s complement of 11100 is 00100. Write a C program to find the 2’s complement of a binary number.
b) Write a C program to convert a Roman numeral to its decimal equivalent.

Week 11
Write a C program that uses functions to perform the following operations:
i) Reading a complex number
ii) Writing a complex number
iii) Addition of two complex numbers
iv) Multiplication of two complex numbers
(Note: represent complex number using a structure.)

Week 12
a) Write a C program which copies one file to another.
b) Write a C program to reverse the first n characters in a file.
(Note: The file name and n are specified on the command line.)

Week 13
Write a C program that uses functions to perform the following operations on singly linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal

Week 14
Write a C program that uses functions to perform the following operations on doubly linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal in both ways

Week 15
Write C programs that implement stack (its operations) using
i) Arrays ii) Pointers

Week 16
Write C programs that implement Queue (its operations) using
i) Arrays ii) Pointers

Week 17
Write a C program that uses Stack operations to perform the following:
i) Converting infix expression into postfix expression
ii) Evaluating the postfix expression

Week 18
Write a C program that uses functions to perform the following:
i) Creating a Binary Tree of integers
ii) Traversing the above binary tree in preorder, inorder and postorder.

Week 19
Write C programs that use both recursive and non recursive functions to perform the following searching operations for a Key value in a given list of integers :
i) Linear search ii) Binary search

Week 20
Write C programs that implement the following sorting methods to sort a given list of integers in ascending order:
i) Bubble sort ii) Quick sort

Week 21
Write C programs that implement the following sorting methods to sort a given list of integers in ascending order:
i) Insertion sort ii) Merge sort

Week 22
Write C programs to implement the Lagrange interpolation and Newton- Gregory forward interpolation.

Week 23
Write C programs to implement the linear regression and polynomial regression algorithms.

Week 24
Write C programs to implement Trapezoidal and Simpson methods.

Text Books
1. C programming and Data Structures, P. Padmanabham, Third Edition, BS Publications
2. Data Structures: A pseudo code approach with C, second edition R.F. Gilberg and B.A. Forouzan
3. Programming in C, P.Dey & M. Ghosh, Oxford Univ.Press.
4. C and Data Structures, E Balaguruswamy, TMH publications.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
0 3 4
ELECTRICAL AND ELECTRONICS LAB
PART - A
1. Serial and Parallel Resonance – Timing, Resonant frequency, Bandwidth and Q-factor determination for RLC network.
2. Time response of first order RC/RL network for periodic non-sinusoidal inputs – time constant and steady state error determination.
3. Two port network parameters – Z-Y Parameters, chain matrix and analytical verification.
4. Verification of Superposition and Reciprocity theorems.
5. Verification of maximum power transfer theorem. Verification on DC, verification on AC with
Resistive and Reactive loads.
6. Experimental determination of Thevenin’s and Norton’s equivalent circuits and verification by direct test.
7. Magnetization characteristics of D.C. Shunt generator. Determination of critical field resistance.
8. Swinburne’s Test on DC shunt machine (Predetermination of efficiency of a given DC Shunt machine working as motor and generator).
9. Brake test on DC shunt motor. Determination of performance Characteristics.
10. OC & SC tests on Single-phase transformer (Predetermination of efficiency and regulation at given power factors and determination of equivalent circuit).
11. Brake test on 3-phase Induction motor (performance characteristics).
12. Regulation of alternator by synchronous impedance method

PART - B
1. Identification, Specifications and Testing of R, L, C Components (colour codes), Potentiometers, Switches (SPDT, DPDT and DIP), Coils, Gang Condensers, Relays, Bread Boards. Identification and Specifications of active devices, Diodes, BJTs, Lowpower JFETs, MOSFETs, LEDs, LCDs, SCR, UJT, Linear and Digital ICs.
2. PN Junction Diode Characteristics (Forward bias, Reverse bias)
3. Zener Diode Characteristics
4. Transistor CE Characteristics (Input and Output)
5. Rectifier without Filters (Full wave & Half wave)
6. Rectifier with Filters (Full wave & half wave)
7. SCR Characteristics
8. FET Characteristics
9. CE and CC Amplifier
10. Feedback Amplifier (Voltage Series/Current series)
11. RC Phase Shift Oscillator
12. Hartely/Colpitts Oscillator

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
0 3 4
ENGLISH LANGUAGE COMMUNICATION SKILLS LAB

The Language Lab focuses on the production and practice of sounds of language and familiarises the students with the use of English in everyday situations and contexts.
Objectives:
1. To expose the students to a variety of self-instructional, learner-friendly modes of language learning.
2. To help the students cultivate the habit of reading passages from the computer monitor, thus providing them with the required facility to face computer-based competitive exams such GRE, TOEFL, GMAT etc.
3. To enable them to learn better pronunciation through stress on word accent, intonation, and rhythm.
4. To train them to use language effectively to face interviews, group discussions, public speaking.
5. To initiate them into greater use of the computer in resume preparation, report writing, format-making etc.
SYLLABUS :
The following course content is prescribed for the English Language Laboratory sessions:
1. Introduction to the Sounds of English- Vowels, Diphthongs & Consonants.
2. Introduction to Stress and Intonation.
3. Situational Dialogues / Role Play.
4. Oral Presentations- Prepared and Extempore.
5. ‘Just A Minute’ Sessions (JAM).
6. Describing Objects / Situations / People.
7. Information Transfer
8. Debate
9. Telephoning Skills.
10. Giving Directions.
Minimum Requirement:
The English Language Lab shall have two parts:
i) The Computer aided Language Lab for 60 students with 60 systems, one master console, LAN facility and English language software for self- study by learners.
ii) The Communication Skills Lab with movable chairs and audio-visual aids with a P.A System, a T. V., a digital stereo –audio & video system and camcorder etc.
System Requirement ( Hardware component):
Computer network with Lan with minimum 60 multimedia systems with the following specifications:
i) P – IV Processor
a) Speed – 2.8 GHZ
b) RAM – 512 MB Minimum
c) Hard Disk – 80 GB
ii) Headphones of High quality
Suggested Software:
• Cambridge Advanced Learners’ English Dictionary with CD.
• The Rosetta Stone English Library
• Clarity Pronunciation Power – Part I
• Mastering English in Vocabulary, Grammar, Spellings, Composition
• Dorling Kindersley series of Grammar, Punctuation, Composition etc.
• Language in Use, Foundation Books Pvt Ltd with CD.
• Oxford Advanced Learner’s Compass, 7th Edition
• Learning to Speak English - 4 CDs
• Microsoft Encarta with CD
• Murphy’s English Grammar, Cambridge with CD
 English in Mind, Herbert Puchta and Jeff Stranks with Meredith Levy, Cambridge

Books Suggested for English Language Lab Library (to be located within the lab in addition to the CDs of the text book which are loaded on the systems):
1. Spoken English (CIEFL) in 3 volumes with 6 cassettes, OUP.
2. English Pronouncing Dictionary Daniel Jones Current Edition with CD.
3. Spoken English- R. K. Bansal and J. B. Harrison, Orient Longman 2006 Edn.
4. English Language Communication : A Reader cum Lab Manual Dr A Ramakrishna Rao, Dr G Natanam & Prof SA Sankaranarayanan, Anuradha Publications, Chennai
5. Speaking English Effectively by Krishna Mohan & NP Singh (Macmillan)
6. A Practical Course in English Pronunciation, (with two Audio cassettes) by J. Sethi, Kamlesh Sadanand & D.V. Jindal, Prentice-Hall of India Pvt. Ltd., New Delhi.
7. A text book of English Phonetics for Indian Students by T.Balasubramanian (Macmillan)
8. English Skills for Technical Students, WBSCTE with British Council, OL

DISTRIBUTION AND WEIGHTAGE OF MARKS
English Language Laboratory Practical Paper:
1. The practical examinations for the English Language Laboratory shall be conducted as per the University norms prescribed for the core engineering practical sessions.
2. For the Language lab sessions, there shall be a continuous evaluation during the year for 25 sessional marks and 50 year-end Examination marks. Of the 25 marks, 15 marks shall be awarded for day-to-day work and 10 marks to be awarded by conducting Internal Lab Test(s). The year- end Examination shall be conducted by the teacher concerned with the help of another member of the staff of the same department of the same institution.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
I Year B.Tech. IT T P C
0 3 4
IT WORKSHOP

Objectives :
The IT Workshop for engineers is a 6 training lab course spread over 90 hours. The modules include training on PC Hardware, Internet & World Wide Web and Productivity tools including Word, Excel, Power Point and Publisher.
PC Hardware introduces the students to a personal computer and its basic peripherals, the process of assembling a personal computer, installation of system software like MS Windows , Linux and the required device drivers. In addition hardware and software level troubleshooting process, tips and tricks would be covered.
Internet & World Wide Web module introduces the different ways of hooking the PC on to the internet from home and workplace and effectively usage of the internet. Usage of web browsers, email, newsgroups and discussion forums would be covered. In addition, awareness of cyber hygiene, i.e., protecting the personal computer from getting infected with the viruses, worms and other cyber attacks would be introduced.
Productivity tools module would enable the students in crafting professional word documents, excel spread sheets, power point presentations and personal web sites using the Microsoft suite of office tools and LaTeX.

PC Hardware
Week 1 – Task 1 : Identify the peripherals of a computer, components in a CPU and its functions. Draw the block diagram of the CPU along with the configuration of each peripheral and submit to your instructor.

Week 2 – Task 2 : Every student should disassemble and assemble the PC back to working condition. Lab instructors should verify the work and follow it up with a Viva. Also students need to go through the video which shows the process of assembling a PC. A video would be given as part of the course content.

Week 3 – Task 3 : Every student should individually install MS windows on the personal computer. Lab instructor should verify the installation and follow it up with a Viva.

Week 4 – Task 4 : Every student should install Linux on the computer. This computer should have windows installed. The system should be configured as dual boot with both windows and Linux. Lab instructors should verify the installation and follow it up with a Viva

Week 5 – Task 5 : Several mini tasks would be that covers Basic commands in Linux and Basic system administration in Linux which includes: Basic Linux commands in bash, Create hard and symbolic links, Text processing, Using wildcards

Week 6 – Task 6 : Hardware Troubleshooting : Students have to be given a PC which does not boot due to improper assembly or defective peripherals. They should identify the problem and fix it to get the computer back to working condition. The work done should be verified by the instructor and followed up with a Viva

Week 7 – Task 7 : Software Troubleshooting : Students have to be given a malfunctioning CPU due to system software problems. They should identify the problem and fix it to get the computer back to working condition. The work done should be verified by the instructor and followed up with a Viva.

Week 8 – Task 8 : The test consists of various systems with Hardware / Software related troubles, Formatted disks without operating systems.

Internet & World Wide Web
Week 9 - Task 1 : Orientation & Connectivity Boot Camp : Students should get connected to their Local Area Network and access the Internet. In the process they configure the TCP/IP setting. Finally students should demonstrate, to the instructor, how to access the websites and email. If there is no internet connectivity preparations need to be made by the instructors to simulate the WWW on the LAN.

Week 10 - Task 2 : Web Browsers, Surfing the Web : Students customize their web browsers with the LAN proxy settings, bookmarks, search toolbars and pop up blockers. Also, plug-ins like Macromedia Flash and JRE for applets should be configured.

Week 11 - Task 3 : Search Engines & Netiquette : Students should know what search engines are and how to use the search engines. A few topics would be given to the students for which they need to search on Google. This should be demonstrated to the instructors.

Week 12 - Task 4 : Cyber Hygiene : Students would be exposed to the various threats on the internet and would be asked to configure their computer to be safe on the internet. They need to first install an anti virus software, configure their personal firewall and windows update on their computer. Then they need to customize their browsers to block pop ups, block active x downloads to avoid viruses and/or worms.

Week 13 Module Test A test which simulates all of the above tasks would be crafted and given to the
students.

LaTeX and Word
Week 14 – Word Orientation : The mentor needs to give an overview of LaTeX and Microsoft/ equivalent (FOSS) tool word : Importance of LaTeX and MS/ equivalent (FOSS) tool Word as word Processors, Details of the four tasks and features that would be covered in each, Using LaTeX and word – Accessing, overview of toolbars, saving files, Using help and resources, rulers, format painter in word.
Task 1 : Using LaTeX and word to create project certificate. Features to be covered:-Formatting Fonts in word, Drop Cap in word, Applying Text effects, Using Character Spacing, Borders and Colors, Inserting Header and Footer, Using Date and Time option in both LaTeX and Word.

Week 15 - Task 2 : Creating project abstract Features to be covered:-Formatting Styles, Inserting table, Bullets and Numbering, Changing Text Direction, Cell alignment, Footnote, Hyperlink, Symbols, Spell Check , Track Changes.

Week 16 - Task 3 : Creating a Newsletter : Features to be covered:- Table of Content, Newspaper columns, Images from files and clipart, Drawing toolbar and Word Art, Formatting Images, Textboxes and Paragraphs

Week 17 - Task 4 : Creating a Feedback form - Features to be covered- Forms, Text Fields, Inserting objects, Mail Merge in Word.

Week 18 - LaTeX and Word Module Test - Replicate the given document inclusive of all features

Excel
Week 19 - Excel Orientation : The mentor needs to tell the importance of MS/ equivalent (FOSS) tool Excel as a Spreadsheet tool, give the details of the four tasks and features that would be covered in each. Using Excel –
Accessing, overview of toolbars, saving excel files, Using help and resources
Task 1 : Creating a Scheduler - Features to be covered:- Gridlines, Format Cells, Summation, auto fill, Formatting Text

Week 20 - Task 2 : Calculating GPA - .Features to be covered:- Cell Referencing, Formulae in excel – average, std.deviation, Charts, Renaming and Inserting worksheets, Hyper linking, Count function, LOOKUP/VLOOKUP

Week 21 - Task 3 : Performance Analysis - Features to be covered:- Split cells, freeze panes, group and outline, Sorting, Boolean and logical operators, Conditional formatting

Week 22 - Task 4 : Cricket Score Card - Features to be covered:-Pivot Tables, Interactive Buttons, Importing Data, Data Protection, Data Validation

Week 23 – Excel Module Test - Replicate the given document inclusive of all features

LaTeX and MS/equivalent (FOSS) tool Power Point
Week 24 - Task1 : Students will be working on basic power point utilities and tools which help them create basic power point presentation. Topic covered during this week includes :- PPT Orientation, Slide Layouts, Inserting Text, Word Art, Formatting Text, Bullets and Numbering, Auto Shapes, Lines and Arrows in both LaTeX and Powerpoint.

Week 25 - Task 2 : Second week helps students in making their presentations interactive.Topic covered during this week includes : Hyperlinks, Inserting –Images, Clip Art, Audio, Video, Objects, Tables and Charts

Week 26 - Task 3 : Concentrating on the in and out of Microsoft power point and presentations in LaTeX. Helps them learn best practices in designing and preparing power point presentation. Topic covered during this week includes :- Master Layouts (slide, template, and notes), Types of views (basic, presentation, slide slotter, notes etc), Inserting – Background, textures, Design Templates, Hidden slides.

Week 27 - Task 4 : Entire week concentrates on presentation part of LaTeX and power point. Topic covered during this week includes -Using Auto content wizard, Slide Transition, Custom Animation, Auto Rehearsing

Week 28 - Task 5 : Power point test would be conducted. Students will be given model power point presentation which needs to be replicated (exactly how it’s asked).

Publisher
Week 29 : Help students in preparing their personal website using Microsoft/ equivalent (FOSS) tool publisher. Topic covered during this week includes - Publisher Orientation, Using Templates, Layouts, Inserting text objects, Editing text objects, Inserting Tables, Working with menu objects, Inserting pages, Hyper linking, Renaming, deleting, modifying pages, Hosting website.

REFERENCES :
1. Comdex Information Technology course tool kit Vikas Gupta, WILEY Dreamtech
2. The Complete Computer upgrade and repair book,3rd edition Cheryl A Schmidt, WILEY Dreamtech
3. Introduction to Information Technology, ITL Education Solutions limited, Pearson Education.
4. PC Hardware and A+Handbook – Kate J. Chase PHI (Microsoft)
5. LaTeX Companion – Leslie Lamport, PHI/Pearson.
6. All LaTeX and others related material is available at
(a) www.sssolutions.in and
(b) www.sontisoftsolutions.org

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT I-Sem T P C
4+1* 0 4
PROBABILITY AND STATISTICS
UNIT-I
Probability: Sample space and events – Probability – The axioms of probability – Some
Elementary theorems - Conditional probability – Baye’s theorem.

UNIT-II
Random variables – Discrete and continuous – Distribution – Distribution function. Distribution

UNIT-III
Binomial and poison distributions Normal distribution – related properties.

UNIT-IV
Sampling distribution: Populations and samples - Sampling distributions of mean (known and unknown) proportions, sums and differences.

UNIT-V
Estimation: Point estimation – interval estimation - Bayesian estimation.

UNIT-VI
Test of Hypothesis – Means– Hypothesis concerning one and two means– Type I and Type II errors. One tail, two-tail tests.
UNIT-VII
Tests of significance – Student’s t-test, F-test, test. Estimation of proportions.

UNIT-VIII
Queuing Theory: Pure Birth and Death Process M/M/1 Model and Simple Problems.

Text Books:
1. Probability & Statistics, T. K. V. Iyengar, B. Krishna Gandhi and Others, S. Chand & Company.
2. A text book of Probability & Statistics, Shahnaz Bathul, V. G. S. Book Links.

References:
1. Probability & Statistics, Arnold O. Allen, Academic Press.
2. Probability & Statistics for Engineers, Miller and John E. Freund, Prentice Hall of India.
3. Probability & Statistics, Mendan Hall, Beaver Thomson Publishers.
4. Probability & Statistics, D. K. Murugeson & P. Guru Swamy, Anuradha Publishers.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT I-Sem T P C
4+1* 0 4
MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

UNIT-I
Mathematical Logic : Statements and notations, Connectives, Well formed formulas, Truth Tables, tautology, equivalence implication, Normal forms.

UNIT-II
Predicates : Predicative logic, Free & Bound variables, Rules of inference, Consistency, proof of contradiction, Automatic Theorem Proving.

UNIT-III
Set Theory : Properties of binary Relations, equivalence, compatibility and partial ordering relations, Hasse diagram. Functions: Inverse Function Comports of functions, recursive Functions, Lattice and its Properties, Pigeon hole principles and its application.

UNIT-IV
Algebraic structures : Algebraic systems Examples and general properties, Semi groups and monads, groups sub groups’ homomorphism, Isomorphism.

UNIT-V
Elementary Combinatorics: Basis of counting, Combinations & Permutations, with repetitions, Constrained repetitions, Binomial Coefficients, Binomial Multinomial theorems, the principles of Inclusion – Exclusion.

UNIT-VI
Recurrence Relation : Generating Functions, Function of Sequences Calculating Coefficient of generating function, Recurrence relations, Solving recurrence relation by substitution and Generating funds. Characteristics roots solution of In homogeneous Recurrence Relation.

UNIT-VII
Graph Theory : Representation of Graph, DFS, BFS, Spanning Trees, planar Graphs

UNIT-VIII
Graph Theory and Applications, Basic Concepts Isomorphism and Sub graphs, Multi graphs and Euler circuits, Hamiltonian graphs, Chromatic Numbers

TEXT BOOKS :
1. Discrete and Combinational Mathematics- An Applied Introduction-5th Edition – Ralph. P.Grimaldi.Pearson Education
2. Discrete Mathematical Structures with applications to computer science Trembly J.P. & Manohar .P, TMH
3.Discrete Mathematics and its Applications, Kenneth H. Rosen, Fifth Edition.TMH.

REFERENCES :
1. Discrete Mathematics with Applications, Thomas Koshy, Elsevier
2. Discrete Mathematical Structures, Bernand Kolman, Roberty C. Busby, Sharn Cutter Ross, Pearson Education/PHI.
3. Discrete Mathematical structures Theory and application-Malik & Sen
4. Discrete Mathematics for Computer science, Garry Haggard and others, Thomson.
5. Discrete Mathematics for Computer Scientists & Mathematicians, J.L. Mott, A. Kandel, T.P. Baker Prentice Hall.
6. Logic and Discrete Mathematics, Grass Man & Trembley, Person Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD.
II Year B.Tech. IT I-Sem T P C
4+1* 0 4
ADVANCED DATA STRUCTURES AND ALGORITHMS

Unit I:-
C++ Class Overview- Class Definition, Objects, Class Members, Access Control, Class Scope, Constructors and destructors, parameter passing methods, Inline functions, static class members, this pointer, friend functions, dynamic memory allocation and deallocation (new and delete), exception handling.

Unit II:-
Function Overloading, Operator Overloading, Generic Programming- Function and class templates, Inheritance basics, base and derived classes, inheritance types, base class access control, runtime polymorphism using virtual functions, abstract classes, streams I/O.

Unit III:-
Algorithms, performance analysis-time complexity and space complexity,O-notation, Omega notation and Theta notation, Review of basic data structures - the list ADT, stack ADT, queue ADT, implementation using template classes in C++, sparse matrix representation.

Unit IV:-
Dictionaries, linear list representation, skip list representation, operations- insertion, deletion and searching, hash table representation, hash functions, collision resolution-separate chaining, open addressing-linear probing, quadratic probing, double hashing, rehashing,extendible hashing, comparison of hashing and skip lists.

Unit V:-
Priority Queues – Definition, ADT, Realizing a Priority Queue using Heaps, Definition, insertion, Deletion, Application-Heap Sort, External Sorting- Model for external sorting, Multiway merge, Polyphase merge.

Unit VI:-
Search trees (part I) : Binary search trees, definition, ADT, implementation, operations-searching,
insertion and deletion, Balanced search trees- AVL trees, definition, height of an AVL tree, representation, operations-insertion, deletion and searching.

Search trees (part II) : Introduction to Red –Black trees and Splay Trees, B-Trees-B-Tree of order m, height of a B-Tree, insertion, deletion and searching, Comparison of Search Trees.

Unit VII:-
Divide and Conquer- General method, applications – Binary search, merge sort, quick sort, Strassen’s matrix multiplication
Efficient non recursive tree traversal algorithms, Biconnected components. Disjoint set operations, union and find algorithms.

Unit VIII:-
Greedy method and Dynamic programming : General method (Greedy), Minimum cost spanning trees, Job sequencing with deadlines, General method (Dynamic Programming), Optimal binary search trees, 0/1 knapsack problem, Ordering Matrix Multiplications

TEXT BOOKS :
1. Data Structures and Algorithm Analysis in C++, Mark Allen Weiss, Pearson
Education, second edition.
2. Data structures, Algorithms and Applications in C++,S.Sahni,University press (India)
pvt ltd, 2nd edition, Orient Longman pvt.ltd.
REFERENCE :
1. Data structures and Algorithms in C++, Michael T.Goodrich, R.Tamassia and
D.Mount, Seventh Edition Wiley student edition, John Wiley and Sons.
2. Data Structures and Algorithms in C++, Third Edition, Adam Drozdek, Thomson
3. Problem solving with C++, The OOP, Fourth edition, W.Savitch, Pearson education.
4. C++, The Complete Reference, 4th Edition, Herbert Schildt, TMH.
5. Data structures using C and C++, Langsam, Augenstein and Tanenbaum, PHI/Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT I-Sem T P C
4+1* 0 4
DIGITAL LOGIC DESIGN
UNIT - I
BINARY SYSTEMS : Digital Systems, Binary Numbers, Number base conversions, Octal and Hexadecimal Numbers, complements, Signed binary numbers, Binary codes, Binary Storage and Registers, Binary logic.

UNIT - II
BOOLEAN ALGEBRA AND LOGIC GATES : Basic Definitions, Axiomatic definition of Boolean Algebra, Basic theorems and properties of Boolean algebra, Boolean functions canonical and standard forms, other logic operations, Digital logic gages, integrated circuits.

UNIT - III
GATE – LEVEL MINIMIZATION : The map method, Four-variable map, Five-Variable map, product of sums simplification Don’t-care conditions, NAND and NOR implementation other Two-level implementnations, Exclusive – Or function, Hardward Description language (HDL).

UNIT - IV
COMBINATIONAL LOGIC : Combinational Circuits, Analysis procedure Design procedure, Binary Adder-Subtractor Decimal Adder, Binary multiplier, magnitude comparator, Decoders, Encoders, Multiplexers, HDL for combinational circuits.

UNIT - V
SYNCHRONOUS SEQUENTIAL LOGIC : Sequential circuits, latches, Flip-Flops Analysis of clocked sequential circuits, HDL for sequential circuits, State Reduction and Assignment, Design Procedure.

UNIT - VI
Registers, shift Registers, Ripple counters synchronous counters, other counters, HDL for Registers and counters.

UNIT - VII
Introduction, Random-Access Memory, Memory Decoding, Error Detection and correction Read-only memory, Programmable logic Array programmable Array logic, Sequential Programmable Devices.

UNIT - VIII
ASYNCHRONOUS SEQUENTIAL LOGIC : Introduction, Analysis Procedure, Circuits with Latches, Design Procedure, Reduciton of state and Flow Tables, Race-Free state Assignment Hazards, Design Example.

TEXT BOOKS :
1. DIGITAL DESIGN – Third Edition , M.Morris Mano, Pearson Education/PHI.
2. FUNDAMENTALS OF LOGIC DESIGN, Roth,5th Edition,Thomson.

REFERENCES :
1. Switching and Finite Automata Theory by Zvi. Kohavi, Tata McGraw Hill.
2. Switching and Logic Design, C.V.S. Rao, Pearson Education
3. Digital Principles and Design – Donald D.Givone, Tata McGraw Hill, Edition.
4. Fundamentals of Digital Logic & Micro Computer Design , 5TH Edition, M.
Rafiquzzaman John Wiley

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT I-Sem T P C
4+1* 0 4
UNIX AND SHELL PROGRAMMING

Unit I:
Introduction to Unix:- Architecture of Unix, Features of Unix , Unix Commands – PATH, man, echo, printf, script, passwd, uname, who, date, stty, pwd, cd, mkdir, rmdir, ls, cp, mv, rm, cat, more, wc, lp, od, tar, gzip.

Unit II :
Unix Utilities:- Introduction to unix file system, vi editor, file handling utilities, security by file permissions, process utilities, disk utilities, networking commands, unlink, du, df, mount, umount, find, unmask, ulimit, ps, w, finger, arp, ftp, telnet, rlogin.Text processing utilities and backup utilities , detailed commands to be covered are tail, head , sort, nl, uniq, grep, egrep, fgrep, cut, paste, join, tee, pg, comm, cmp, diff, tr, awk, cpio

Unit III :
Introduction to Shells :
Unix Session, Standard Streams, Redirection, Pipes, Tee Command, Command Execution, Command-Line Editing, Quotes, Command Substitution, Job Control, Aliases, Variables, Predefined Variables, Options, Shell/Environment Customization.
Filters :
Filters and Pipes, Concatenating files, Display Beginning and End of files, Cut and Paste, Sorting, Translating Characters, Files with Duplicate Lines, Count characters, Words or Lines, Comparing Files.

Unit IV :
Grep :
Operation, grep Family, Searching for File Content.
Sed :
Scripts, Operation, Addresses, commands, Applications, grep and sed.

Unit V :
awk:
Execution, Fields and Records, Scripts, Operations, Patterns, Actions, Associative Arrays, String Functions, String Functions, Mathematical Functions, User – Defined Functions, Using System commands in awk, Applications, awk and grep, sed and awk.

Unit VI :
Interactive Korn Shell :
Korn Shell Features, Two Special Files, Variables, Output, Input, Exit Status of a Command, eval Command, Environmental Variables, Options, Startup Scripts, Command History, Command Execution Process.
Korn Shell Programming :
Basic Script concepts, Expressions, Decisions: Making Selections, Repetition, special Parameters and Variables, changing Positional Parameters, Argument Validation, Debugging Scripts, Script Examples.

Unit VII :
Interactive C Shell :
C shell features, Two Special Files, Variables, Output, Input, Exit Status of a Command, eval Command, Environmental Variables, On-Off Variables, Startup and Shutdown Scripts, Command History, Command Execution Scripts.
C Shell Programming :
Basic Script concepts, Expressions, Decisions: Making Selections, Repetition, special Parameters and Variables, changing Positional Parameters, Argument Validation, Debugging Scripts, Script Examples.

Unit VIII :
File Management :
File Structures, System Calls for File Management – create, open, close, read, write, lseek, link, symlink, unlink, stat, fstat, lstat, chmod, chown, Directory API – opendir, readdir, closedir, mkdir, rmdir, umask.

TEXT BOOKS :
1. Unix and shell Programming Behrouz A. Forouzan, Richard F. Gilberg.Thomson
2. Your Unix the ultimate guide, Sumitabha Das, TMH. 2nd Edition.

REFERENCES :
1. Unix for programmers and users, 3rd edition, Graham Glass, King Ables, Pearson Education.
2. Unix programming environment, Kernighan and Pike, PHI. / Pearson Education
3. The Complete Reference Unix, Rosen, Host, Klee, Farber, Rosinski, Second Edition, TMH.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT I-Sem T P C
4+1* 0 4
MANAGERIAL ECONOMICS AND FINANCIAL ANALYSIS

Unit I Introduction to Managerial Economics:
Definition, Nature and Scope of Managerial Economics–Demand Analysis: Demand Determinants, Law of Demand and its exceptions.

Unit II Elasticity of Demand:
Definition, Types, Measurement and Significance of Elasticity of Demand. Demand Forecasting, Factors governing demand forecasting, methods of demand forecasting (survey methods, statistical methods, expert opinion method, test marketing, controlled experiments, judgmental approach to demand forecasting)

Unit III Theory of Production and Cost Analysis:
Production Function – Isoquants and Isocosts, MRTS, Least Cost Combination of Inputs, Cobb-Douglas Production function, Laws of Returns, Internal and External Economies of Scale.
Cost Analysis: Cost concepts, Opportunity cost, Fixed vs. Variable costs, Explicit costs Vs. Implicit costs, Out of pocket costs vs. Imputed costs. Break-even Analysis (BEA)-Determination of Break-Even Point (simple problems)- Managerial Significance and limitations of BEA.

Unit IV Introduction to Markets & Pricing Policies:
Market structures: Types of competition, Features of Perfect competition, Monopoly and Monopolistic Competition. Price-Output Determination in case of Perfect Competition and Monopoly.
Objectives and Policies of Pricing- Methods of Pricing: Cost Plus Pricing, Marginal Cost Pricing, Sealed Bid Pricing, Going Rate Pricing, Limit Pricing, Market Skimming Pricing, Penetration Pricing, Two-Part Pricing, Block Pricing, Bundling Pricing, Peak Load Pricing, Cross Subsidization.

Unit V Business & New Economic Environment:
Characteristic features of Business, Features and evaluation of Sole Proprietorship, Partnership, Joint Stock Company, Public Enterprises and their types, Changing Business Environment in Post-liberalization scenario.

Unit VI Capital and Capital Budgeting:
Capital and its significance, Types of Capital, Estimation of Fixed and Working capital requirements, Methods and sources of raising finance.
Nature and scope of capital budgeting, features of capital budgeting proposals, Methods of Capital Budgeting: Payback Method, Accounting Rate of Return (ARR) and Net Present Value Method (simple problems)

Unit VII Introduction to Financial Accounting:
Double-Entry Book Keeping, Journal, Ledger, Trial Balance- Final Accounts (Trading Account, Profit and Loss Account and Balance Sheet with simple adjustments).

Unit VIII Financial Analysis through ratios:
Computation, Analysis and Interpretation of Liquidity Ratios (Current Ratio and quick ratio), Activity Ratios (Inventory turnover ratio and Debtor Turnover ratio), Capital structure Ratios (Debt- Equity ratio, Interest Coverage ratio), and Profitability ratios (Gross Profit Ratio, Net Profit ratio, Operating Ratio, P/E Ratio and EPS).

TEXT BOOKS:

1. Aryasri: Managerial Economics and Financial Analysis, 2/e, TMH, 2005.
2. Varshney & Maheswari: Managerial Economics, Sultan Chand, 2003.

REFERENCES:

1. Ambrish Gupta, Financial Accounting for Management, Pearson Education, New Delhi.
2. H. Craig Peterson & W. Cris Lewis, Managerial Economics, PHI, 4th Ed.
3. Suma Damodaran, Managerial Economics, Oxford University Press.
4. Lipsey & Chrystel, Economics, Oxford University Press.
5. S. A. Siddiqui & A. S. Siddiqui, Managerial Economics & Financial Analysis, New age International Space Publications.
6. Domnick Salvatore: Managerial Economics In a Global Economy, 4th Edition, Thomson.
7. Narayanaswamy: Financial Accounting—A Managerial Perspective, PHI.
8. Raghunatha Reddy & Narasimhachary: Managerial Economics& Financial Analysis, Scitech.
9. S.N.Maheswari & S.K. Maheswari, Financial Accounting, Vikas.
10. Truet and Truet: Managerial Economics:Analysis, Problems and Cases, Wiley.
11. Dwivedi:Managerial Economics, 6th Ed., Vikas.

Prerequisites: Nil

Objective: To explain the basic principles of managerial economics, accounting and current business environment underlying business decision making.

Codes/Tables: Present Value Tables need to be permitted into the examinations Hall.

Question Paper Pattern: 5 Questions to be answered out of 8 questions.
Each question should not have more than 3 bits.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT I-Sem T P C
0 3 2
ADVANCED DATA STRUCTURES AND ALGORITHMS LAB

Objectives:
• To make the student learn a object oriented way of solving problems.
• To make the student write ADTS for all data structures.
• To make the student learn different algorithm design techniques.

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++ compiler and STL Recommended

Week1- C++ programs to implement the following using an array.
a) Stack ADT b) Queue ADT
Week2- Write C++ programs to implement the following using a singly linked list.
a) Stack ADT b) Queue ADT
Week3- Write C++ programs to implement the deque (double ended queue) ADT using
a doubly linked list and an array.
Week 4-Write a C++ program to perform the following operations:
a) Insert an element into a binary search tree.
b) Delete an element from a binary search tree.
c) Search for a key element in a binary search tree.
Week5-.Write C++ programs that use non-recursive functions to traverse the given
binary tree in
a) Preorder b) inorder and c) postorder.
Week6-.Write C++ programs for the implementation of bfs and dfs for a given graph.
Week7- Write C++ programs for implementing the following sorting methods:
a) Merge sort b) Heap sort
Week8-.Write a C++ program to perform the following operations
a) Insertion into a B-tree b) Deletion from a B-tree
Week9-.Write a C++ program to perform the following operations
a) Insertion into an AVL-tree b) Deletion from an AVL-tree
Week10-Write a C++ program to implement Kruskal’s algorithm to generate a
minimum cost spanning tree.
Week11-Write a C++ program to implement Prim’s algorithm to generate a minimum
cost spanning tree.
Week12-.Write a C++ program to implement all the functions of a dictionary (ADT)
using hashing.

(Note: Use Class Templates In the above Programs)

TEXT BOOKS :
1.Data Structures and Algorithms in C++, Third Edition, Adam Drozdek, Thomson.
2.Data Structures using C++, D.S. Malik, Thomson

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD

II Year B.Tech. IT I-Sem T P C
0 3 2
UNIX AND SHELL PROGRAMMING LAB
Objectives:
• To teach students various unix utilities and shell scripting

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 LAN Connected
• Any flavour of Unix / Linux

Week1
Session-1
a)Log into the system
b)Use vi editor to create a file called myfile.txt which contains some
text.
c)correct typing errors during creation.
d)Save the file
e)logout of the system

Session-2
a)Log into the system
b)open the file created in session 1
c)Add some text
d)Change some text
e)Delete some text
f)Save the Changes
g)Logout of the system

Week2
a)Log into the system
b)Use the cat command to create a file containing the following data. Call it mytable use tabs to separate the fields.

1425 Ravi 15.65
4320 Ramu 26.27
6830 Sita 36.15
1450 Raju 21.86
c)Use the cat command to display the file, mytable.
d)Use the vi command to correct any errors in the file, mytable.
e)Use the sort command to sort the file mytable according to the first field. Call the sorted file my table (same name)
f)Print the file mytable
g)Use the cut and paste commands to swap fields 2 and 3 of mytable. Call it my table (same name)
h)Print the new file, mytable
i)Logout of the system.

Week3
1) a)Login to the system
b)Use the appropriate command to determine your login shell
c)Use the /etc/passwd file to verify the result of step b.
d)Use the who command and redirect the result to a file called myfile1. Use the more command to see the contents of myfile1.
e)Use the date and who commands in sequence (in one line) such that the output of date will display on the screen and the output of who will be redirected to a file called myfile2. Use the more command to check the contents of myfile2.

2) a)Write a sed command that deletes the first character in each line in a
file.
b)Write a sed command that deletes the character before the last character in each line in a file.
c)Write a sed command that swaps the first and second words in each line in a file.

Week4
a)Pipe your /etc/passwd file to awk, and print out the home directory of each user.
b)Develop an interactive grep script that asks for a word and a file name and then tells how many lines contain that word.
c)Repeat
d)Part using awk

Week5
a)Write a shell script that takes a command –line argument and reports on whether it is directory, a file, or something else.
b)Write a shell script that accepts one or more file name as arguments and converts all of them to uppercase, provided they exist in the current directory.
c)Write a shell script that determines the period for which a specified user is working on the system.

Week6
a)Write a shell script that accepts a file name starting and ending line numbers as arguments and displays all the lines between the given line numbers.
b)Write a shell script that deletes all lines containing a specified word in one or more files supplied as arguments to it.

Week7
a)Write a shell script that computes the gross salary of a employee according to the following rules:
i)If basic salary is < 1500 then HRA =10% of the basic and DA =90% of the basic.
ii)If basic salary is >=1500 then HRA =Rs500 and DA=98% of the basic
The basic salary is entered interactively through the key board.
b)Write a shell script that accepts two integers as its arguments and computers the value of first number raised to the power of the second number.

Week8
a)Write an interactive file-handling shell program. Let it offer the user the choice of copying, removing, renaming, or linking files. Once the user has made a choice, have the program ask the user for the necessary information, such as the file name, new name and so on.
b)Write shell script that takes a login name as command – line argument and reports when that person logs in
c)Write a shell script which receives two file names as arguments. It should check whether the two file contents are same or not. If they are same then second file should be deleted.

Week9
a)Write a shell script that displays a list of all the files in the current directory to which the user has read, write and execute permissions.
b)Develop an interactive script that ask for a word and a file name and then tells how many times that word occurred in the file.
c)Write a shell script to perform the following string operations:
i)To extract a sub-string from a given string.
ii)To find the length of a given string.

Week10
Write a C program that takes one or more file or directory names as command line input and reports the following information on the file:
i)File type
ii)Number of links
iii)Read, write and execute permissions
iv)Time of last access
(Note : Use stat/fstat system calls)

Week11
Write C programs that simulate the following unix commands:
a)mv
b)cp
(Use system calls)

Week12
Write a C program that simulates ls Command
(Use system calls / directory API)

TEXT BOOKS

1)Introduction to UNIX & SHELL programming, M.G. Venkatesh Murthy, Pearson Education.
2)Unix concepts and applications, Fourth Edition, Sumitabha Das, TMH.
3)Unix for programmers and users, 3rd edition, Gaham Glass & K. Ables, pearson education.
4)Unix and shell Programming –A text book, B.A. Forouzan & R.F. Giberg, Thomson.
5)Beginning shell scripting, E. Foster – Johnson & other, Wile Y- India.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT II-Sem T P C
4+1* 0 4
OBJECT ORIENTED PROGRAMMING
UNIT I :
Object oriented thinking :- Need for oop paradigm, A way of viewing world – Agents, responsibility, messages, methods, classes and instances, class hierarchies (Inheritance), method binding, overriding and exceptions, summary of oop concepts, coping with complexity, abstraction mechanisms.

UNIT II :
Java Basics History of Java, Java buzzwords, datatypes, variables, scope and life time of variables, arrays, operators, expressions, control statements, type conversion and costing, simple java program, classes and objects – concepts of classes, objects, constructors, methods, access control, this keyword, garbage collection, overloading methods and constructors, parameter passing, recursion, string handling.

UNIT III :
Inheritance – Hierarchical abstractions, Base class object, subclass, subtype, substitutability, forms of inheritance- specialization, specification, construction, extension, limitation, combination, benefits of inheritance, costs of inheritance. Member access rules, super uses, using final with inheritance, polymorphism- method overriding, abstract classes.

UNIT IV :
Packages and Interfaces : Defining, Creating and Accessing a Package, Understanding CLASSPATH, importing packages, differences between classes and interfaces, defining an interface, implementing interface, applying interfaces, variables in interface and extending interfaces.
Exploring packages – Java.io, java.util.

UNIT V :
Exception handling and multithreading - Concepts of exception handling, benefits of exception handling, Termination or resumptive models, exception hierarchy, usage of try, catch, throw, throws and finally, built in exceptions, creating own exception sub classes. Differences between multi threading and multitasking, thread life cycle, creating threads, synchronizing threads, daemon threads, thread groups.

UNITVI :
Event Handling : Events, Event sources, Event classes, Event Listeners, Delegation event model, handling mouse and keyboard events, Adapter classes, inner classes.The AWT class hierarchy, user interface components- labels, button, canvas, scrollbars, text components, check box, check box groups, choices, lists panels – scrollpane, dialogs, menubar, graphics, layout manager – layout manager types – boarder, grid, flow, card and grib bag.

UNIT VII :
Applets – Concepts of Applets, differences between applets and applications, life cycle of an applet, types of applets, creating applets, passing parameters to applets.
Swing – Introduction, limitations of AWT, MVC architecture, components, containers, exploring swing- JApplet, JFrame and JComponent, Icons and Labels, text fields, buttons – The JButton class, Check boxes, Radio buttons, Combo boxes, Tabbed Panes, Scroll Panes, Trees, and Tables.

UNIT VIII :
Networking – Basics of network programming, addresses, ports, sockets, simple client server program, multiple clients, Java .net package
Packages – java.util,

TEXT BOOKS :

1. Java; the complete reference, 7th editon, Herbert schildt, TMH.
2. Understanding OOP with Java, updated edition, T. Budd, pearson eduction.

REFERENCES :

1. An Introduction to programming and OO design using Java, J.Nino and F.A. Hosch, John wiley & sons.
2. An Introduction to OOP, second edition, T. Budd, pearson education.
3. Introduction to Java programming 6th edition, Y. Daniel Liang, pearson education.
4. An introduction to Java programming and object oriented application development, R.A. Johnson- Thomson.
5. Core Java 2, Vol 1, Fundamentals, Cay.S.Horstmann and Gary
Cornell, seventh Edition, Pearson Education.
6 .Core Java 2, Vol 2, Advanced Features, Cay.S.Horstmann and Gary
Cornell, Seventh Edition, Pearson Education
7. Object Oriented Programming through Java, P. Radha Krishna,
University Press.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT II-Sem T P C
4+1* 0 4
COMPUTER ORGANIZATION

UNIT I :
BASIC STRUCTURE OF COMPUTERS : Computer Types, Functional unit, Basic OPERATIONAL concepts, Bus structures, Software, Performance, multiprocessors and multi computers. Data Representation. Fixed Point Representation. Floating – Point Representation. Error Detection codes.

UNIT II :
REGISTER TRANSFER LANGUAGE AND MICROOPERATIONS : Register Transfer language.Register Transfer Bus and memory transfers, Arithmetic Mircrooperatiaons, logic micro operations, shift micro operations, Arithmetic logic shift unit. Instruction codes. Computer Registers Computer instructions
– Instruction cycle.
Memory – Reference Instructions. Input – Output and Interrupt. STACK organization. Instruction formats. Addressing modes. DATA Transfer and manipulation. Program control. Reduced Instruction set computer.

UNIT III :
MICRO PROGRAMMED CONTROL : Control memory, Address sequencing, microprogram example, design of control unit Hard wired control. Microprogrammed control

UNIT IV :
COMPUTER ARITHMETIC : Addition and subtraction, multiplication Algorithms, Division Algorithms, Floating – point Arithmetic operations. Decimal Arithmetic unit Decimal Arithmetic operations.

UNIT V :
THE MEMORY SYSTEM : Basic concepts semiconductor RAM memories. Read-only memories Cache memories performance considerations, Virtual memories secondary storage. Introduction to RAID.

UNIT-VI
INPUT-OUTPUT ORGANIZATION : Peripheral Devices, Input-Output Interface, Asynchronous data transfer Modes of Transfer, Priority Interrupt Direct memory Access, Input –Output Processor (IOP) Serial communication; Introduction to peripheral component, Interconnect (PCI) bus. Introduction to
standard serial communication protocols like RS232, USB, IEEE1394.

UNIT VII :
PIPELINE AND VECTOR PROCESSING : Parallel Processing, Pipelining, Arithmetic Pipeline, Instruction Pipeline, RISC Pipeline Vector Processing, Array Processors.

UNIT VIII :
MULTI PROCESSORS : Characteristics or Multiprocessors, Interconnection Structures, Interprocessor Arbitration. InterProcessor Communication and Synchronization Cache Coherance. Shared Memory Multiprocessors.

TEXT BOOKS :
1. Computer Organization – Carl Hamacher, Zvonks Vranesic, SafeaZaky, Vth Edition, McGraw Hill.
2. Computer Systems Architecture – M.Moris Mano, IIIrd Edition, Pearson/PHI

REFERENCES :
1. Computer Organization and Architecture – William Stallings Sixth Edition, Pearson/PHI
2. Structured Computer Organization – Andrew S. Tanenbaum, 4th Edition PHI/Pearson
3. Fundamentals or Computer Organization and Design, - Sivaraama Dandamudi Springer Int. Edition.
4. Computer Architecture a quantitative approach, John L. Hennessy and David A. Patterson, Fourth Edition Elsevier
5.Computer Architecture: Fundamentals and principles of Computer Design, Joseph D. Dumas II, BS Publication.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT II-Sem T P C
4+1* 0 4
DATABASE MANAGEMENT SYSTEMS

UNIT I :
Data base System Applications, data base System VS file System – View of Data – Data Abstraction –Instances and Schemas – data Models – the ER Model – Relational Model – Other Models – Database Languages – DDL – DML – database Access for applications Programs – data base Users and Administrator – Transaction Management – data base System Structure – Storage Manager – the Query Processor

UNIT II :
History of Data base Systems. Data base design and ER diagrams – Beyond ER Design Entities, Attributes and Entity sets – Relationships and Relationship sets – Additional features of ER Model – Concept Design with the ER Model – Conceptual Design for Large enterprises.

UNIT III :
Introduction to the Relational Model – Integrity Constraint Over relations – Enforcing Integrity constraints – Querying relational data – Logical data base Design – Introduction to Views – Destroying /altering Tables and Views.
Relational Algebra – Selection and projection set operations – renaming – Joins – Division – Examples of Algebra overviews – Relational calculus – Tuple relational Calculus – Domain relational calculus – Expressive Power of Algebra and calculus.

UNIT IV :
Form of Basic SQL Query – Examples of Basic SQL Queries – Introduction to Nested Queries – Correlated Nested Queries Set – Comparison Operators – Aggregative Operators – NULL values – Comparison using Null values – Logical connectivity’s – AND, OR and NOT – Impact on SQL Constructs – Outer Joins – Disallowing NULL values – Complex Integrity Constraints in SQL Triggers and Active Data bases.

UNIT V :
Schema refinement – Problems Caused by redundancy – Decompositions – Problem related to decomposition – reasoning about FDS – FIRST, SECOND, THIRD Normal forms – BCNF – Lossless join Decomposition – Dependency preserving Decomposition – Schema refinement in Data base Design – Multi valued Dependencies – FORTH Normal Form.

UNIT VI :
Transaction Concept- Transaction State- Implementation of Atomicity and Durability – Concurrent – Executions – Serializability- Recoverability – Implementation of Isolation – Testing for serializability- Lock –Based Protocols – Timestamp Based Protocols- Validation- Based Protocols – Multiple Granularity.

UNIT VII :
Recovery and Atomicity – Log – Based Recovery – Recovery with Concurrent Transactions – Buffer Management – Failure with loss of nonvolatile storage-Advance Recovery systems- Remote Backup systems.

UNIT VIII :
Data on External Storage – File Organization and Indexing – Cluster Indexes, Primary and Secondary Indexes – Index data Structures – Hash Based Indexing – Tree base Indexing – Comparison of File Organizations – Indexes and Performance Tuning- Intuitions for tree Indexes – Indexed Sequential Access Methods (ISAM) – B+ Trees: A Dynamic Index Structure.

TEXT BOOKS :
1. Data base Management Systems, Raghurama Krishnan, Johannes Gehrke, TATA McGrawHill 3rd Edition
2. Data base System Concepts, Silberschatz, Korth, McGraw hill, V edition.

REFERENCES :
1. Data base Systems design, Implementation, and Management, Peter Rob & Carlos Coronel 7th Edition.
2. Fundamentals of Database Systems, Elmasri Navrate Pearson Education
3. Introduction to Database Systems, C.J.Date Pearson Education

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT II-Sem T P C
4+1* 0 4
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.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT II-Sem T P C
4+1* 0 4
ENVIRONMENTAL STUDIES
UNIT I :
Multidisciplinary nature of Environmental Studies: Definition, Scope and Importance – Need for Public Awareness.

UNIT II :
Natural Resources : Renewable and non-renewable resources – Natural resources and associated problems – Forest resources – Use and over – exploitation, deforestation, case studies – Timber extraction – Mining, dams and other effects on forest and tribal people – Water resources – Use and over utilization of surface and ground water – Floods, drought, conflicts over water, dams – benefits and problems - Mineral resources: Use and exploitation, environmental effects of extracting and using mineral resources,
case studies. - Food resources: World food problems, changes caused by agriculture and overgrazing, effects of modern agriculture, fertilizer-pesticide problems, water logging, salinity, case studies. – Energy resources: Growing energy needs, renewable and non-renewable energy sources use of alternate energy sources. Case studies. Land resources: Land as a resource, land degradation, man induced landslides, soil erosion and desertification. Role of an individual in conservation of natural resources. Equitable use of resources for sustainable lifestyles.

UNIT III :
Ecosystems : Concept of an ecosystem. - Structure and function of an ecosystem. - Producers, consumers and decomposers. - Energy flow in the ecosystem - Ecological succession. - Food chains, food webs and ecological pyramids. - Introduction, types, characteristic features, structure and function of the following ecosystem:
a. Forest ecosystem
b. Grassland ecosystem
c. Desert ecosystem
d. Aquatic ecosystems (ponds, streams, lakes, rivers, oceans, estuaries)

UNIT IV :
Biodiversity and its conservation : Introduction - Definition: genetic, species and ecosystem diversity. - Bio-geographical classification of India - Value of biodiversity: consumptive use, productive use, social, ethical, aesthetic and option values - . Biodiversity at global, National and local levels. - . India as a megadiversity nation - Hot-sports of biodiversity - Threats to biodiversity: habitat loss, poaching of wildlife, manwildlife conflicts. - Endangered and endemic species of India - Conservation of biodiversity: In-situ and Exsitu conservation of biodiversity.
UNIT V :
Environmental Pollution : Definition, Cause, effects and control measures of a. Air pollution
b. Water pollution
c. Soil pollution
d. Marine pollution
e. Noise pollution
f. Thermal pollution
g. Nuclear hazards
Solid waste Management : Causes, effects and control measures of urban and industrial wastes. – Role of an individual in prevention of pollution. - Pollution case studies. - Disaster management: floods, earthquake, cyclone and landslides.

UNIT VI :
Social Issues and the Environment : From Unsustainable to Sustainable development -Urban problems related to energy -Water conservation, rain water harvesting, watershed management -Resettlement and rehabilitation of people; its problems and concerns. Case Studies -Environmental ethics: Issues and possible solutions. -Climate change, global warming, acid rain, ozone layer depletion, nuclear accidents and holocaust. Case Studies. -Wasteland reclamation. -Consumerism and waste products. -Environment
Protection Act. -Air (Prevention and Control of Pollution) Act. -Water (Prevention and control of Pollution) Act -Wildlife Protection Act -Forest Conservation Act -Issues involved in enforcement of environmental
legislation. -Public awareness.

UNIT VII :
Human Population and the Environment : Population growth, variation among nations. Population explosion - Family Welfare Programme. -Environment and human health. -Human Rights. -Value Education.
-HIV/AIDS. -Women and Child Welfare. -Role of information Technology in Environment and human health. -Case Studies.

UNIT VIII :
Field work : Visit to a local area to document environmental assets River /forest grassland/hill/mountain -Visit to a local polluted site - Urban/Rural/industrial/ Agricultural Study of common plants, insects, birds. -
Study of simple ecosystems-pond, river, hill slopes, etc.

TEXT BOOK:
1 Textbook of Environmental Studies for Undergraduate Courses by Erach Bharucha for University Grants Commission.
2 Environmental Studies by R. Rajagopalan, Oxford University Press.

REFERENCE:

1 Textbook of Environmental Sciences and Technology by M. Anji Reddy, BS Publication.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT II-Sem T P C
4+1* 0 4
SOFTWARE ENGINEERING

UNIT I :
Introduction to Software Engineering : The evolving role of software, Changing Nature of Software, Software myths.
A Generic view of process : Software engineering- A layered technology, a process framework, The Capability Maturity Model Integration (CMMI), Process patterns, process assessment, personal and team process models.

UNIT II :
Process models : The waterfall model, Incremental process models, Evolutionary process models, The Unified process.
Software Requirements : Functional and non-functional requirements, User requirements, System requirements, Interface specification, the software requirements document.

UNIT III :
Requirements engineering process : Feasibility studies, Requirements elicitation and analysis, Requirements validation, Requirements management.
System models : Context Models, Behavioral models, Data models, Object models, structured methods.

UNIT IV :
Design Engineering : Design process and Design quality, Design concepts, the design model.
Creating an architectural design : Software architecture, Data design, Architectural styles and patterns, Architectural Design.

UNIT V :
Object-Oriented Design : Objects and object classes, An Object-Oriented design process, Design evolution.
Performing User interface design : Golden rules, User interface analysis and design, interface analysis, interface design steps, Design evaluation.

UNIT VI :
Testing Strategies : A strategic approach to software testing, test strategies for conventional software, Black-Box and White-Box testing, Validation testing, System testing, the art of Debugging.
Product metrics : Software Quality, Metrics for Analysis Model, Metrics for Design Model, Metrics for source code, Metrics for testing, Metrics for maintenance.

UNIT VII :
Metrics for Process and Products : Software Measurement, Metrics for software quality.
Risk management : Reactive vs. Proactive Risk strategies, software risks, Risk identification, Risk projection, Risk refinement, RMMM, RMMM Plan.

UNIT VIII :
Quality Management : Quality concepts, Software quality assurance, Software Reviews, Formal technical reviews, Statistical Software quality Assurance, Software reliability, The ISO 9000 quality standards.

TEXT BOOKS :
1. Software Engineering, A practitioner’s Approach- Roger S. Pressman, 6th edition.McGrawHill International Edition.
2. Software Engineering- Sommerville, 7th edition, Pearson education.

REFERENCES :
1. Software Engineering- K.K. Agarwal & Yogesh Singh, New Age International Publishers
2. Software Engineering, an Engineering approach- James F. Peters, Witold Pedrycz, John Wiely.
3. Systems Analysis and Design- Shely Cashman Rosenblatt,Thomson Publications.
4. Software Engineering principles and practice- Waman S Jawadekar, The McGraw-Hill Companies.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT II-Sem T P C
0 3 2
OBJECT ORIENTED PROGRAMMING LAB
Objectives:
• To make the student learn a object oriented way of solving problems.
• To teach the student to write programs in Java to solve the problems

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
• JDK Kit. Recommended

Week1 :
a) Write a Java program that prints all real solutions to the quadratic equation ax2 + bx + c = 0. Read in a, b, c and use the quadratic formula. If the discriminant b2 -4ac is negative, display a message stating that there are no real solutions.
b) The Fibonacci sequence is defined by the following rule:
The fist two values in the sequence are 1 and 1. Every subsequent value is the sum of the two values preceding it. Write a Java program that uses both recursive and non recursive functions to print the nth value in the Fibonacci sequence.

Week 2 :
a) Write a Java program that prompts the user for an integer and then prints out all prime numbers up to that integer.
b) Write a Java program to multiply two given matrices.
c) Write a Java Program that reads a line of integers, and then displays each integer, and the sum of all the integers (Use StringTokenizer class of java.util)

Week 3 :
a) Write a Java program that checks whether a given string is a palindrome or not. Ex: MADAM is a palindrome.
b) Write a Java program for sorting a given list of names in ascending order.
c) Write a Java program to make frequency count of words in a given text.

Week 4 :
a) Write a Java program that reads a file name from the user, then displays information about whether the file exists, whether the file is readable, whether the file is writable, the type of file and the length of the file in bytes.
b) Write a Java program that reads a file and displays the file on the screen, with a line number before each line.
c) Write a Java program that displays the number of characters, lines and words in a text file.

Week 5 :
a) Write a Java program that:
i) Implements stack ADT.
ii) Converts infix expression into Postfix form
iii) Evaluates the postfix expression
Week 6 :
a) Develop an applet that displays a simple message.
b) Develop an applet that receives an integer in one text field, and computes its factorial Value and returns it in another text field, when the button named “Compute” is clicked.

Week 7 :
Write a Java program that works as a simple calculator. Use a grid layout to arrange buttons for the digits and for the +, -,*, % operations. Add a text field to display the result.

Week 8 :
a) Write a Java program for handling mouse events.

Week 9 :
a) Write a Java program that creates three threads. First thread displays “Good Morning” every one second, the second thread displays “Hello” every two seconds and the third thread displays “Welcome” every three seconds.
b) Write a Java program that correctly implements producer consumer problem using the concept of inter thread communication.

Week 10 :
Write a program that creates a user interface to perform integer divisions. The user enters two numbers in the textfields, Num1 and Num2. The division of Num1 and Num2 is displayed in the Result field when the Divide button is clicked. If Num1 or Num2 were not an integer, the program would throw a NumberFormatException. If Num2 were Zero, the program would throw an ArithmeticException Display the exception in a message dialog box.

Week 11 :
Write a Java program that implements a simple client/server application. The client sends data to a server. The server receives the data, uses it to produce a result, and then sends the result back to the client. The client displays the result on the console. For ex: The data sent from the client is the radius of a circle, and the result produced by the server is the area of the circle. (Use java.net)

Week 12 :
a) Write a java program that simulates a traffic light. The program lets the user select one of three lights: red, yellow, or green. When a radio button is selected, the light is turned on, and only one light can be on at a time No light is on when the program starts.
b) Write a Java program that allows the user to draw lines, rectangles and ovals.

Week 13 :
a) Write a java program to create an abstract class named Shape that contains an empty method named numberOfSides ( ).Provide three classes named Trapezoid, Triangle and Hexagon such that each one of the classes extends the class Shape. Each one of the classes contains only the method numberOfSides ( ) that shows the number of sides in the given geometrical figures.
b) Suppose that a table named Table.txt is stored in a text file. The first line in the file is the header, and the remaining lines correspond to rows in the table. The elements are seperated by commas. Write a java program to display the table using JTable component.

TEXT BOOKS :
1. Java How to Program, Sixth Edition, H.M.Dietel and P.J.Dietel, Pearson
Education/PHI
2. Introduction to Java programming, Sixth edition, Y.Daniel Liang, Pearson Education
3. Big Java, 2nd edition, Cay Horstmann, Wiley Student Edition, Wiley India Private Limited.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
II Year B.Tech. IT II-Sem T P C
0 3 2
DATABASE MANAGEMENT SYSTEMS LAB
Objectives:
• To teach the student database design and query and PL/SQL.

Recommended Systems/Software Requirements:

• Intel based desktop PC
• Mysql /Oracle latest version Recommended

1) Creation, altering and droping of tables and inserting rows into a table (use constraints while creating tables) examples using SELECT command.
2) Queries (along with sub Queries) using ANY, ALL, IN, EXISTS, NOTEXISTS, UNION, INTERSET, Constraints.
Example:- Select the roll number and name of the student who secured fourth rank in the class.
3) Queries using Aggregate functions (COUNT, SUM, AVG, MAX and MIN), GROUP BY, HAVING and Creation and dropping of Views.
4) Queries using Conversion functions (to_char, to_number and to_date), string functions (Concatenation, lpad, rpad, ltrim, rtrim, lower, upper, initcap, length, substr and instr), date functions (Sysdate, next_day, add_months, last_day, months_between, least, greatest, trunc, round, to_char, to_date)
5) i)Creation of simple PL/SQL program which includes declaration section, executable section and exception –Handling section (Ex. Student marks can be selected from the table and printed for those who secured first class and an exception can be raised if no records were found)
ii)Insert data into student table and use COMMIT, ROLLBACK and SAVEPOINT in PL/SQL block.

6) Develop a program that includes the features NESTED IF, CASE and CASE expression. The program can be extended using the NULLIF and COALESCE functions.
7) http://books.google.co.in/books?id=XGryS2ajfhoC&pg=PA27&lpg=PA27&dq=Creation+of+simple+PL/SQL+program+which+includes+declaration+section,+executable+section+and+exception+%E2%80%93Handling+section&source=bl&ots=AmketMCdY5&sig=zoOdQEvUCDfR8UewvLC9S5vKT1o&hl=en&sa=X&oi=book_result&resnum=3&ct=result#PPA47,M1.
8) Programs development using creation of procedures, passing parameters IN and OUT of PROCEDURES.
9) Program development using creation of stored functions, invoke functions in SQL Statements and write complex functions.
10) Program development using creation of package specification, package bodies, private objects, package variables and cursors and calling stored packages.
11) Develop programs using features parameters in a CURSOR, FOR UPDATE CURSOR, WHERE CURRENT of clause and CURSOR variables.
12) Develop Programs using BEFORE and AFTER Triggers, Row and Statement Triggers and INSTEAD OF Triggers

TEXT BOOKS :

1)ORACLE PL/SQL by example. Benjamin Rosenzweig, Elena Silvestrova, Pearson
Education 3rd Edition
2)ORACLE DATA BASE LOG PL/SQL Programming SCOTT URMAN, Tata Mc-
Graw Hill.
3)SQL & PL/SQL for Oracle 10g, Black Book, Dr.P.S. Deshpande.
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT I-Sem T P C
4+1* 0 4
AUTOMATA AND COMPILER DESIGN
UNIT-I
Formal Language and Regular Expressions : Languages, Definition Languages regular expressions, Finite Automata – DFA, NFA. Conversion of regular expression to NFA, NFA to DFA. Applications of Finite Automata to lexical analysis, lex tools.

UNIT-II
Context Free grammars and parsing : Context free grammars, derivation, parse trees, ambiguity LL(K) grammars and LL(1) parsing

UNIT-III
Bottom up parsing handle pruning LR Grammar Parsing, LALR parsing, parsing ambiguous grammars, YACC programming specification.

UNIT-IV
Semantics : Syntax directed translation, S-attributed and L-attributed grammars, Intermediate code – abstract syntax tree, translation of simple statements and control flow statements.

UNIT-V
Context Sensitive features – Chomsky hierarchy of languages and recognizers. Type checking, type conversions, equivalence of type expressions, overloading of functions and operations.

UNIT-VI
Run time storage : Storage organization, storage allocation strategies scope access to now local names, parameters, language facilities for dynamics storage allocation.

UNIT-VII
Code optimization : Principal sources of optimization, optimization of basic blocks, peephole optimization, flow graphs, Data flow analysis of flow graphs.

UNIT-VIII
Code generation : Machine dependent code generation, object code forms, generic code generation algorithm, Register allocation and assignment. Using DAG representation of Block.

TEXT BOOKS :
1. Introduction to Theory of computation.Sipser,2nd Edition,Thomson.
2. Compilers Principles, Techniques and Tools Aho, Ullman, Ravisethi, Pearson
Education.

REFERENCES :
1. Modern Compiler Construction in C , Andrew W.Appel Cambridge University
Press.
2. Compiler Construction, LOUDEN, Thomson.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT I-Sem T P C
4+1* 0 4
DATA COMMUNICATION SYSTEMS

Unit I :
INTRODUCTION TO DATA COMMUNICATIONS AND NETWORKING: Standards Organizations for Data Communications, Layered Network Architecture, Open Systems Interconnection, Data Communications Circuits, Serial and parallel Data Transmission, Data communications Circuit Arrangements, Data communications Networks, Alternate Protocol Suites.
SIGNALS, NOISE, MODULATION, AND DEMODULATION :
Signal Analysis, Electrical Noise and Signal-to-Noise Ratio, Analog Modulation Systems, Information Capacity, Bits, Bit Rate, Baud, and M-ary Encoding, Digital Modulation.

Unit II :
METALLIC CABLE TRANSMISSION MEDIA :
Metallic Transmission Lines, Transverse Electromagnetic Waves, Characteristics of Electromagnetic Waves, Transmission Line Classifications, Metallic Transmission Line Types, Metallic Transmission Line Equivalent Circuit, Wave Propagation on Metallic Transmission Lines, Metallic Transmission Line Losses.
OPTICAL FIBER TRANSMISSION MEDIA :
Advantages of Optical Fiber Cables, Disadvantages of Optical Fiber Cables, Electromagnetic spectrum, Optical Fiber Communications System Block Diagram, Optical Fiber construction, The Physics of Light, Velocity of Propagation, Propagation of Light Through an Optical fiber Cable, Optical Fiber Modes and Classifications, Optical Fiber Comparison, Losses in Optical Fiber Cables, Light sources, Light Detectors, Lasers.

Unit III :
DIGITAL TRANSMISSION :
Pulse Modulation, Pulse code Modulation, Dynamic Range, Signal Voltage –to-Quantization Noise Voltage Ration, Linear Versus Nonlinear PCM Codes, Companding, PCM Line Speed, Delta Modulation PCM and Differential PCM.
MULTIPLEXING AND T CARRIERS :
Time- Division Multiplexing, T1 Digital Carrier System, North American Digital Multiplexing Hierarchy, Digital Line Encoding, T Carrier systems, European Time- Division Multiplexing, Statistical Time – Division Multiplexing, Frame Synchronization, Frequency- Division Multiplexing, Wavelength- Division Multiplexing, Synchronous Optical Network

Unit IV :
WIRLESS COMMUNICATIONS SYSTEMS :
Electromagnetic Polarization, Rays and Wavefronts, Electromagnetic Radiation, Spherical Wavefront and the Inverse Square Law, wave Attenuation and Absorption, Optical Properties of Radio Waves, Terrestrial Propagation of Electromagnetic Waves, Skip Distance, Free-Space Path Loss, Microwave Communications Systems, Satellite Communications Systems.

Unit V :
TELEPHONE INSTRUMENTS AND SIGNALS:
The Subscriber Loop, Standard Telephone Set, Basic Telephone Call Procedures, Call Progress Tones and Signals, Cordless Telephones, Caller ID, Electronic Telephones, Paging systems.
THE TELEPHONE CIRCUIT:
The Local Subscriber Loop, Telephone Message- Channel Noise and Noise Weighting, Units of Powers Measurement, Transmission Parameters and Private-Line Circuits, Voice-Frequency Circuit Arrangements, Crosstalk.

Unit VI :
CELLULAR TELEPHONE SYSTEMS:
First- Generation Analog Cellular Telephone, Personal Communications system, Second-Generation Cellular Telephone Systems, N-AMPS, Digital Cellular Telephone, Interim Standard, North American Cellular and PCS Summary, Global system for Mobile Communications, Personal Communications Satellite System.

Unit VII:
DATA COMMUNICATIONS CODES, ERROR CONTROL, AND DATA FORMATS:
Data Communications Character Codes, Bar Codes, Error Control, Error Detection, Error Correction, Character Synchronization.
DATA COMMUNICATIONS EQUIPMENT:
Digital Service Unit and Channel Service Unit, Voice- Band Data Communication Modems, Bell Systems- Compatible Voice- Band Modems, Voice- Band Modern Block Diagram, Voice- Band Modem Classifications, Asynchronous Voice-Band Modems, Synchronous Voice-Band Modems, Modem Synchronization, ITU-T Voice- Band Modem Specifications, 56K Modems, Modem Control: The AT Command Set, Cable Modems, Probability of Error and Bit Error Rate.

Unit VIII:
DATA –LINK PROTOCOLS:
Data –Link Protocol Functions, Character –and Bit- Oriented Protocols, Data Transmission Modes, Asynchronous Data – Link Protocols, Synchronous Data – Link Protocols, Synchronous Data – Link Control, High – Level Data – Link Control.

TEXT BOOKS:
1. Introduction to Data Communications and Networking, Wayne Tomasi, Pearson Education.

Reference Books
1. Data Communications and Networking, Behrouz A Forouzan, Fourth Edition.TMH.
2. Computer Communications and Networking Technologies, Gallow,
Second Edition Thomson
3. Computer Networking and Internet, Fred Halsll, Lingana Gouda Kulkarni, Fifth Edition, Pearson Education

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT I-Sem T P C
4+1* 0 4
MICROPROCESSORS AND INTERFACING
UNIT-I
An over view of 8085, Architecture of 8086 Microprocessor. Special functions of General purpose registers. 8086 flag register and function of 8086 Flags. Addressing modes of 8086. Instruction set of 8086. Assembler directives, simple programs, procedures, and macros.

UNIT-II
Assembly language programs involving logical, Branch & Call instructions, sorting, evaluation of arithmetic expressions, string manipulation.

UNIT-III
Pin diagram of 8086-Minimum mode and maximum mode of operation. Timing diagram. Memory interfacing to 8086 (Static RAM & EPROM). Need for DMA. DMA data transfer Method. Interfacing with 8237/8257.

UNIT-IV
8255 PPI – various modes of operation and interfacing to 8086. Interfacing Keyboard, Displays, 8279 Stepper Motor and actuators. D/A and A/D converter interfacing.

UNIT-V
Interrupt structure of 8086. Vector interrupt table. Interrupt service routines. Introduction to DOS and BIOS interrupts. 8259 PIC Architecture and interfacing cascading of interrupt controller and its importance.

UNIT-VI
Serial data transfer schemes. Asynchronous and Synchronous data transfer schemes. 8251 USART architecture and interfacing. TTL to RS 232C and RS232C to TTL conversion. Sample program of serial data transfer. Introduction to High-speed serial communications standards, USB.

UNIT-VII
Advanced Micro Processors - Introduction to 80286, Salient Features of 80386, Real and Protected Mode Segmentation & Paging, Salient Features of Pentium, Branch Prediction, Overview of RISC Processors.

UNIT-VIII
8051 Microcontroller Architecture, Register set of 8051, Modes of timer operation, Serial port operation, Interrupt structure of 8051, Memory and I/O interfacing of 8051.

TEXT BOOKS :
1. Advanced microprocessor and Peripherals - A.K.Ray and K.M.Bhurchandi, TMH, 2000.
2. Micro Controllers – Deshmukh, Tata McGraw Hill Edition.

REFERENCES :
1. Micro Processors & Interfacing – Douglas U. Hall, 2007.
2. The 8088 and 8086 Micro Processors – PHI, 4th Edition, 2003.
3. Micro Computer System 8086/8088 Family Architecture, Programming and Design - By Liu and GA Gibson, PHI, 2nd Ed.,

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT I-Sem T P C
4+1* 0 4
COMPUTER GRAPHICS
UNIT I :
Introduction, Application areas of Computer Graphics, overview of graphics systems, video-display devices, raster-scan systems, random scan systems, graphics monitors and work stations and input devices
(p.nos 22-90 of text book-1).

UNIT II :
Output primitives : Points and lines, line drawing algorithms, mid-point circle and ellipse algorithms.Filled area primitives: Scan line polygon fill algorithm, boundary-fill and flood-fill algorithms (p.nos 103-123,137- 145,147-150,164-171 of text book-1, p.nos. 72-99 of text book-2).

UNIT III :
2-D geometrical transforms : Translation, scaling, rotation, reflection and shear transformations, matrix representations and homogeneous coordinates, composite transforms, transformations between coordinate systems. (p.nos 204-227 of text book-1).

UNIT IV :
2-D viewing : The viewing pipeline, viewing coordinate reference frame, window to view-port coordinate transformation, viewing functions, Cohen-Sutherland and Cyrus-beck line clipping algorithms, Sutherland –Hodgeman polygon clipping algorithm(p.nos 237-249,257-261 of text book -1, p.nos. 111-126 of text book-2).

UNIT V :
3-D object representation : Polygon surfaces, quadric surfaces, spline representation, Hermite curve, Bezier curve and B-Spline curves, Bezier and B-Spline surfaces. Basic illumination models, polygon rendering methods. (p.nos 324-331,340-342, 347-364, 516-531, 542-546 of text book-1, p.nos 473-529,721-739 of text book-2).

UNIT VI :
3-D Geometric transformations : Translation, rotation, scaling, reflection and shear transformations, composite transformations.
3-D viewing : Viewing pipeline, viewing coordinates, view volume and general projection transforms and clipping (p.nos 427-443, 452-481 of text book -1).

UNIT VII :
Visible surface detection methods : Classification, back-face detection, depth-buffer, scan-line, depth sorting, BSP-tree methods, area sub-division and octree methods(p.nos 489-505 of text book -1, Chapter 15 of of text book-2).

UNIT VIII :
Computer animation : Design of animation sequence, general computer animation functions, raster animation, computer animation languages, key frame systems, motion specifications. ( p.nos 604-616 of text book -1, chapter 21 of text book-2).

TEXT BOOKS :
1. “Computer Graphics C version”, Donald Hearn and M.Pauline Baker, Pearson Education.
2. “Computer Graphics Principles & practice”, second edition in C, Foley, VanDam, Feiner and Hughes, Pearson Education.

REFERENCES :
1. “Computer Graphics”, second Edition, Donald Hearn and M.Pauline Baker, PHI/Pearson Education.
2. “Computer Graphics Second edition”, Zhigand xiang, Roy Plastock, Schaum’s outlines, Tata Mc- Graw hill edition.
3. Procedural elements for Computer Graphics, David F Rogers, Tata Mc Graw hill, 2nd edition.
4. “Principles of Interactive Computer Graphics”, Neuman and Sproul, TMH.
5. Principles of Computer Graphics, Shalini Govil, Pai, 2005, Springer.
6. Computer Graphics, Steven Harrington, TMH

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT I-Sem T P C
4+1* 0 4
DISTRIBUTED DATABASES
UNIT - I
Features of Distributed versus Centralized Databases, Principles Of Distributed Databases , Levels Of Distribution Transparency, Reference Architecture for Distributed Databases , Types of Data Fragmentation, Integrity Constraints in Distributed Databases.

UNIT – II
Translation of Global Queries to Fragment Queries, Equivalence Transformations for Queries, Transforming Global Queries into Fragment Queries, Distributed Grouping and Aggregate Function Evaluation, Parametric Queries.

UNIT – III
Optimization of Access Strategies, A Framework for Query Optimization, Join Queries, General Queries.

UNIT – IV
The Management of Distributed Transactions, A Framework for Transaction Management , Supporting Atomicity of Distributed Transactions, Concurrency Control for Distributed Transactions, Architectural Aspects of Distributed Transactions.

UNIT - V
Concurrency Control, Foundation of Distributed Concurrency Control, Distributed Deadlocks, Concurrency Control based on Timestamps, Optimistic Methods for Distributed Concurrency Control.

UNIT – VI
Reliability, Basic Concepts, Nonblocking Commitment Protocols, Reliability and concurrency Control, Determining a Consistent View of the Network, Detection and Resolution of Inconsistency, Checkpoints and Cold Restart, Distributed Database Administration, Catalog Management in Distributed Databases,
Authorization and Protection

UNIT - VII
Architectural Issues, Alternative Client/Server Architectures, Cache Consistency Object Management, Object Identifier Management, Pointer Swizzling, Object Migration, Distributed Object Storage, Object Query Processing, Object Query Processor Architectures, Query Processing Issues, Query Execution , Transaction Management, Transaction Management in Object DBMSs , Transactions as Objects.

UNIT - VIII
Database Integration, Scheme Translation, Scheme Integration, Query Processing Query Processing Layers in Distributed Multi-DBMSs, Query Optimization Issues. Transaction Management Transaction and Computation Model Multidatabase Concurrency Control, Multidatabase Recovery, Object Orientation And Interoperability Object Management Architecture CORBA and Database Interoperability Distributed Component Model COM/OLE and Database Interoperability, PUSH-Based Technologies

TEXT BOOKS :
1. Distributed Database Principles & Systems, Stefano Ceri, Giuseppe Pelagatti
McGraw-Hill
REFERENCES:
1. Principles of Distributed Database Systems, M.Tamer Ozsu, Patrick Valduriez
– Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT I-Sem T P C
4+1* 0 4
SOFTWARE TESTING METHODOLOGIES
UNIT - I
Introduction : Purpose of testing, Dichotomies, model for testing, consequences of bugs, taxonomy of bugs

UNIT - II
Flow graphs and Path testing : Basics concepts of path testing, predicates, path predicates and achievable paths, path sensitizing, path instrumentation, application of path testing.

UNIT - III
Transaction Flow Testing : Transaction flows, transaction flow testing techniques. Dataflow testing:- Basics of dataflow testing, strategies in dataflow testing, application of dataflow testing.

UNIT - IV
Domain Testing:-domains and paths, Nice & ugly domains, domain testing, domains and interfaces testing, domain and interface testing, domains and testability.

UNIT - V
Paths, Path products and Regular expressions : Path products & path expression, reduction procedure, applications, regular expressions & flow anomaly detection.

UNIT - VI
Logic Based Testing : Overview, decision tables, path expressions, kv charts, specifications.

UNIT - VII
State, State Graphs and Transition testing : State graphs, good & bad state graphs, state testing, Testability tips.

UNIT VIII :
Graph Matrices and Application : Motivational overview, matrix of graph, relations, power of a matrix, node reduction algorithm, building tools.
Usage of JMeter and Winrunner tools for functional / Regression testing, creation of test script for unattended testing, synchronization of test case, Rapid testing, Performance testing of a data base application and HTTP connection for website access.

TEXT BOOKS :
1. Software Testing techniques - Baris Beizer, Dreamtech, second edition.
2. Software Testing Tools – Dr.K.V.K.K.Prasad, Dreamtech.

REFERENCES :
1. The craft of software testing - Brian Marick, Pearson Education.
2. Software Testing Techniques – SPD(Oreille)
3. Software Testing in the Real World – Edward Kit, Pearson.
4. Effective methods of Software Testing, Perry, John Wiley.
5. Art of Software Testing – Meyers, John Wiley.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT I-Sem T P C
0 3 2
ADVANCED ENGLISH COMMUNICATION SKILLS LAB

1. Introduction
The introduction of the English Language Lab is considered essential at 3rd year level. At this stage the students need to prepare themselves for their careers which may require them to listen to, read, speak and write in English both for their professional and interpersonal communication in the globalised context.

The proposed course should be an integrated theory and lab course to enable students to use ‘good’ English and perform the following:
• Gather ideas and information, to organise ideas relevantly and coherently.
• Engage in debates.
• Participate in group discussions.
• Face interviews.
• Write project/research reports/technical reports.
• Make oral presentations.
• Write formal letters.
• Transfer information from non-verbal to verbal texts and vice versa.
• To take part in social and professional communication.
2. Objectives:
This Lab focuses on using computer-aided multimedia instruction for language development to meet the following targets:
• To improve the students’ fluency in English, through a well-developed vocabulary and enable them to listen to English spoken at normal conversational speed by educated English speakers and respond appropriately in different socio-cultural and professional contexts.
• Further, they would be required to communicate their ideas relevantly and coherently in writing.
3. Syllabus:
The following course content is prescribed for the Advanced Communication Skills Lab:

 Functional English - starting a conversation – responding appropriately and relevantly – using the right body language – role play in different situations.
 Vocabulary building – synonyms and antonyms, word roots, one-word substitutes, prefixes and suffixes, study of word origin, analogy, idioms and phrases.
 Group Discussion – dynamics of group discussion , intervention, summarizing, modulation of voice, body language, relevance, fluency and coherence.
 Interview Skills – concept and process, pre-interview planning, opening strategies, answering strategies, interview through tele and video-conferencing.
 Resume’ writing – structure and presentation, planning, defining the career objective, projecting ones strengths and skill-sets, summary, formats and styles, letter-writing.
 Reading comprehension – reading for facts, guessing meanings from context, scanning, skimming, inferring meaning, critical reading.
 Technical Report writing – Types of formats and styles, subject matter – organization, clarity, coherence and style, planning, data-collection, tools, analysis.
4. Minimum Requirement:
The English Language Lab shall have two parts:
i) The Computer aided Language Lab for 60 students with 60 systems, one master console, LAN facility and English language software for self- study by learners.
ii) The Communication Skills Lab with movable chairs and audio-visual aids with a P.A System, a T. V., a digital stereo –audio & video system and camcorder etc.
System Requirement ( Hardware component):
Computer network with Lan with minimum 60 multimedia systems with the following specifications:
iii) P – IV Processor
a) Speed – 2.8 GHZ
b) RAM – 512 MB Minimum
c) Hard Disk – 80 GB
iv) Headphones of High quality

5. Suggested Software:
The software consisting of the prescribed topics elaborated above should be procured and used.

Suggested Software:
• Clarity Pronunciation Power – part II
• Oxford Advanced Learner’s Compass, 7th Edition
• DELTA’s key to the Next Generation TOEFL Test: Advanced Skill Practice.
• Lingua TOEFL CBT Insider, by Dreamtech
• TOEFL & GRE( KAPLAN, AARCO & BARRONS, USA, Cracking GRE by CLIFFS)
• The following software from ‘train2success.com’
 Preparing for being Interviewed,
 Positive Thinking,
 Interviewing Skills,
 Telephone Skills,
 Time Management
 Team Building,
 Decision making

• English in Mind, Herbert Puchta and Jeff Stranks with Meredith Levy, Cambridge

6. Books Recommended:
1. Effective Technical Communication, M. Ashraf Rizvi, Tata Mc. Graw-Hill Publishing Company Ltd.
2. A Course in English communication by Madhavi Apte, Prentice-Hall of India, 2007.
3. Communication Skills by Leena Sen, Prentice-Hall of India, 2005.
4. Academic Writing- A Practical guide for students by Stephen Bailey, Rontledge Falmer, London & New York, 2004.
5. English Language Communication : A Reader cum Lab Manual Dr A Ramakrishna Rao, Dr G Natanam & Prof SA Sankaranarayanan, Anuradha Publications, Chennai
6. Body Language- Your Success Mantra by Dr. Shalini Verma, S. Chand, 2006.
7. DELTA’s key to the Next Generation TOEFL Test: Advanced Skill Practice, New Age International (P) Ltd., Publishers, New Delhi.
8. Books on TOEFL/GRE/GMAT/CAT by Barron’s/cup
9. IELTS series with CDs by Cambridge University Press.
10. Technical Report Writing Today by Daniel G. Riordan & Steven E. Pauley, Biztantra Publishers, 2005.
11. Basic Communication Skills for Technology by Andra J. Rutherford, 2nd Edition, Pearson Education, 2007.
12. Communication Skills for Engineers by Sunita Mishra & C. Muralikrishna, Pearson Education, 2007.
13. Objective English by Edgar Thorpe & Showick Thorpe, 2nd edition, Pearson Education, 2007.
14. Cambridge Preparation for the TOEFL Test by Jolene Gear & Robert Gear, 4th Edition.
15. Technical Communication by Meenakshi Raman & Sangeeta Sharma, Oxford University Press.

DISTRIBUTION AND WEIGHTAGE OF MARKS:
Advanced Communication Skills Lab Practicals:
1. The practical examinations for the English Language Laboratory practice shall be conducted as per the University norms prescribed for the core engineering practical sessions.
2. For the English Language lab sessions, there shall be a continuous evaluation during the year for 25 sessional marks and 50 End Examination marks. Of the 25 marks, 15 marks shall be awarded for day-to-day work and 10 marks to be awarded by conducting Internal Lab Test(s). The End Examination shall be conducted by the teacher concerned with the help of another member of the staff of the same department of the same institution.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT I-Sem T P C
0 3 2
MICROPROCESSORS AND INTERFACING LAB
I. Microprocessor 8086 :
1. Introduction to MASM/TASM.
2. Arithmetic operation – Multi byte Addition and Subtraction, Multiplication and Division – Signed and unsigned Arithmetic operation, ASCII – arithmetic operation.
3. Logic operations – Shift and rotate – Converting packed BCD to unpacked BCD, BCD to ASCII conversion.
4. By using string operation and Instruction prefix: Move Block, Reverse string, Sorting, Inserting, Deleting, Length of the string, String comparison.
5. DOS/BIOS programming: Reading keyboard (Buffered with and without echo) – Display characters, Strings.

II. Interfacing :
1. 8259 – Interrupt Controller : Generate an interrupt using 8259 timer.
2. 8279 – Keyboard Display : Write a small program to display a string of characters.
3. 8255 – PPI : Write ALP to generate sinusoidal wave using PPI.
4. 8251 – USART : Write a program in ALP to establish Communication between two processors.

III. Microcontroller 8051
1. Reading and Writing on a parallel port.
2. Timer in different modes.
3. Serial communication implementation.

and
Equipment required for Laboratories:
1. 8086 µP Kits
2. 8051 Micro Controller kits
3. Interfaces/peripheral subsystems
i) 8259 PIC
ii) 8279-KB/Display
iii) 8255 PPI
iv) 8251 USART

4. ADC Interface
5. DAC Interface
6. Traffic Controller Interface
7. Elevator Interface

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT II-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:

1. Programming world wide web-Sebesta,Pearson
2. Core SERVLETS ANDJAVASERVER PAGES VOLUME 1: CORE TECHNOLOGIES By Marty Hall and Larry Brown Pearson
3. Internet and World Wide Web – How to program by Dietel and Nieto PHI/Pearson Education Asia.
4. Jakarta Struts Cookbook , Bill Siggelkow, S P D O’Reilly for chap 8.
5. Murach’s beginning JAVA JDK 5, Murach, SPD
6. An Introduction to web Design and Programming –Wang-Thomson
7. Web Applications Technologies Concepts-Knuckles,John Wiley
8. Programming world wide web-Sebesta,Pearson
9. Web Warrior Guide to Web Programmming-Bai/Ekedaw-Thomas
10. Beginning Web Programming-Jon Duckett WROX.
11. Java Server Pages, Pekowsky, Pearson.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT II-Sem T P C
4+1* 0 4
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 : A LOHA, 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

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT II-Sem T P C
4+1* 0 4
E – COMMERCE
UNIT - I
Electronic Commerce-Frame work, anatomy of E-Commerce applications, E-Commerce Consumer applications, E-Commerce organization applications.

UNIT - II
Consumer Oriented Electronic commerce - Mercantile Process models.

UNIT - III
Electronic payment systems - Digital Token-Based, Smart Cards, Credit Cards, Risks in Electronic Payment systems.

UNIT-IV
Inter Organizational Commerce - EDI, EDI Implementation, Value added networks.

UNIT - V
Intra Organizational Commerce - work Flow, Automation Customization and internal Commerce, Supply chain Management.

UNIT - VI
Corporate Digital Library - Document Library, digital Document types, corporate Data Warehouses. Advertising and Marketing - Information based marketing, Advertising on Internet, on-line marketing process, market research.

UNIT - VII
Consumer Search and Resource Discovery - Information search and Retrieval, Commerce Catalogues, Information Filtering.

UNIT - VIII
Multimedia - key multimedia concepts, Digital Video and electronic Commerce, Desktop video processings, Desktop video conferencing.

TEXT BOOK :
1. Frontiers of electronic commerce – Kalakata, Whinston, Pearson.

REFERENCES :
1. E-Commerce fundamentals and applications Hendry Chan, Raymond Lee, Tharam Dillon, Ellizabeth Chang, John Wiley.
2. E-Commerce, S.Jaiswal – Galgotia.
3. E-Commerce, Efrain Turbon, Jae Lee, David King, H.Michael Chang.
4. Electronic Commerce – Gary P.Schneider – Thomson.
5. E-Commerce – Business, Technology, Society, Kenneth C.Taudon, Carol Guyerico Traver.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT II-Sem T P C
4+1* 0 4
MIDDLEWARE TECHNOLOGIES
UNIT-I
Introduction to client server computing: Evolution of corporate computing models from centralized to distributed computing, client server models. Benefits of client server computing, pitfalls of client server programming.

UNIT-II
CORBA with Java: Review of Java concept like RMI, RMI API, JDBC. Client/Server CORBA-style, The object web: CORBA with Java.

UNIT III
Introducing C# and the .NET Platform; Understanding .NET Assemblies; Object –Oriented Programming with C#; Callback Interfaces, Delegates, and Events.

UNIT IV
Building c# applications: Type Reflection, Late Binding, and Attribute-Based Programming; Object Serialization and the .NET Remoting Layer; Data Access with ADO.NET; XML Web Services.

UNIT-V
Core CORBA / Java: Two types of Client/ Server invocations-static, dynamic. The static CORBA, first CORBA program, ORBlets with Applets, Dynamic CORBA-The portable count, the dynamic count multi
count.

UNIT-VI
Existential CORBA : CORBA initialization protocol, CORBa activation services, CORBAIDL mapping CORBA java- to- IDL mapping, The introspective CORBA/Java object.

UNIT-VII
Java Bean Component Model : Events, properties, persistency, Intrespection of beans, CORBA Beans.

UNIT-VIII
EJBs and CORBA: Object transaction monitors CORBA OTM’s, EJB and CORBA OTM’s, EJB container frame work, Session and Entity Beans, The EJB client/server development Process The EJB container protocol, support for transaction EJB packaging EJB design Guidelines.

TEXT BOOKS :
1. Client/Server programming with Java and CORBA Robert Orfali and Dan
Harkey, John Wiley & Sons ,SPD 2nd Edition
2. Java programming with CORBA 3rd Edition, G.Brose, A Vogel and K.Duddy,
Wiley-dreamtech, India John wiley and sons

REFERENCES :
1. Distributed Computing, Principles and applications, M.L.Liu, Pearson
Education
2. Client/Server Survival Guide 3rd edition Robert Orfali Dan Harkey & Jeri
Edwards, John Wiley & Sons
3. Client/Server Computing D T Dewire, TMH.
4. IBM Webspere Starter Kit Ron Ben Natan Ori Sasson, TMh, New Delhi
5. Programming C#, Jesse Liberty, SPD-O’Reilly.
6. C# Preciesely Peter Sestoft and Henrik I. Hansen, Prentice Hall of India
7. Intoduction to C# Using .NET Pearson Education
8. C# How to program, Pearson Education
9. C# and the .NET Platform Andrew Troelsen, Apress Wiley-dreamtech, India
Pvt Ltd

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT II-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 :
1. 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.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT II-Sem T P C
4+1* 0 4
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.

REFERENCES:
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. Craig Larman Appling UML and Patterns: An introduction to Object – Oriented Analysis and Design and Unified Process, Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT II-Sem T P C
0 3 2
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.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
III Year B.Tech. IT II-Sem T P C
0 3 2
WEB TECHNOLOGIES LAB
Objective :
To create a fully functional website with mvc architecture. To Develop an online Book store using we can sell books (Ex amazon .com).
Hardware and Software required :
1. A working computer system with either Windows or Linux
2. A web browser either IE or firefox
3. Tomcat web server and Apache web server
4. XML editor like Altova Xml-spy [www.Altova.com/XMLSpy – free ] , Stylusstudio , etc.,
5. A database either Mysql or Oracle
6. JVM(Java virtual machine) must be installed on your system
7. BDK(Bean development kit) must be also be installed

Week-1:

Design the following static web pages required for an online book store web site.
1) HOME PAGE:
The static home page must contain three frames.

Top frame : Logo and the college name and links to Home page, Login page, Registration page,
Catalogue page and Cart page (the description of these pages will be given below).

Left frame : At least four links for navigation, which will display the catalogue of respective links.
For e.g.: When you click the link “CSE” the catalogue for CSE Books should be displayed in the Right frame.

Right frame: The pages to the links in the left frame must be loaded here. Initially this page contains
description of the web site.

Logo Web Site Name

Home Login Registration Catalogue Cart

CSE
ECE
EEE
CIVIL

Description of the Web Site

Fig 1.1

2) LOGIN PAGE:

This page looks like below:

Logo Web Site Name

Home Login Registration Catalogue Cart

CSE
ECE
EEE
CIVIL

Login :
Password:

3) CATOLOGUE PAGE:
The catalogue page should contain the details of all the books available in the web site in a table.
The details should contain the following:

1. Snap shot of Cover Page.
2. Author Name.
3. Publisher.
4. Price.
5. Add to cart button.

Logo Web Site Name

Home Login Registration Catalogue Cart

CSE

ECE

EEE

CIVIL

Book : XML Bible
Author : Winston
Publication : Wiely

$ 40.5

Book : AI
Author : S.Russel
Publication : Princeton hall
$ 63

Book : Java 2
Author : Watson
Publication : BPB publications
$ 35.5

Book : HTML in 24 hours
Author : Sam Peter
Publication : Sam publication
$ 50

Note: Week 2 contains the remaining pages and their description.

Week-2:
4) CART PAGE:

The cart page contains the details about the books which are added to the cart.
The cart page should look like this:

Logo Web Site Name

Home Login Registration Catalogue Cart

CSE
ECE
EEE
CIVIL

Book name Price Quantity Amount

Java 2 $35.5 2 $70
XML bible $40.5 1 $40.5

Total amount - $130.5

5) REGISTRATION PAGE:

Create a “registration form “with the following fields

1) Name (Text field)
2) Password (password field)
3) E-mail id (text field)
4) Phone number (text field)
5) Sex (radio button)
6) Date of birth (3 select boxes)
7) Languages known (check boxes – English, Telugu, Hindi, Tamil)
8) Address (text area)

WEEK 3:

VALIDATION:

Write JavaScript to validate the following fields of the above registration page.

1. Name (Name should contains alphabets and the length should not be less than 6 characters).
2. Password (Password should not be less than 6 characters length).
3. E-mail id (should not contain any invalid and must follow the standard pattern
name@domain.com)
4. Phone number (Phone number should contain 10 digits only).

Note : You can also validate the login page with these parameters.

Week-4:

Design a web page using CSS (Cascading Style Sheets) which includes the following:

1) Use different font, styles:
In the style definition you define how each selector should work (font, color etc.).
Then, in the body of your pages, you refer to these selectors to activate the styles.

For example:

This is normal bold

Selector {cursor:value}

For example:

CROSS LINK

HELP LINK

This is headline style bold

2) Set a background image for both the page and single elements on the page.
You can define the background image for the page like this:

BODY {background-image:url(myimage.gif);}

3) Control the repetition of the image with the background-repeat property.
As background-repeat: repeat
Tiles the image until the entire page is filled, just like an ordinary background image in plain HTML.
4) Define styles for links as
A:link
A:visited
A:active
A:hover
Example:

5) Work with layers:
For example:
LAYER 1 ON TOP:

LAYER 1

LAYER 2

LAYER 2 ON TOP:

LAYER 1

LAYER 2

6) Add a customized cursor:
Selector {cursor:value}
For example:

CROSS LINK

HELP LINK

Week-5:

Write an XML file which will display the Book information which includes the following:
1) Title of the book
2) Author Name
3) ISBN number
4) Publisher name
5) Edition
6) Price
Write a Document Type Definition (DTD) to validate the above XML file.
Display the XML file as follows.
The contents should be displayed in a table. The header of the table should be in color GREY. And the Author names column should be displayed in one color and should be capitalized and in bold. Use your own colors for remaining columns.
Use XML schemas XSL and CSS for the above purpose.
Note: Give at least for 4 books. It should be valid syntactically.
Hint: You can use some xml editors like XML-spy

Week-6:
VISUAL BEANS:
Create a simple visual bean with a area filled with a color.
The shape of the area depends on the property shape. If it is set to true then the shape of the area is Square and it is Circle, if it is false.
The color of the area should be changed dynamically for every mouse click. The color should also be changed if we change the color in the “property window “.

Week-7:

1) Install TOMCAT web server and APACHE.
While installation assign port number 4040 to TOMCAT and 8080 to APACHE. Make sure that these ports are available i.e., no other process is using this port.
2) Access the above developed static web pages for books web site, using these servers by putting the web pages developed in week-1 and week-2 in the document root.
Access the pages by using the urls : http://localhost:4040/rama/books.html (for tomcat)
http://localhost:8080/books.html (for Apache)
Week-8:
User Authentication :
Assume four users user1,user2,user3 and user4 having the passwords pwd1,pwd2,pwd3 and pwd4 respectively. Write a servelet for doing the following.
1. Create a Cookie and add these four user id’s and passwords to this Cookie.
2. Read the user id and passwords entered in the Login form (week1) and authenticate with the values (user id and passwords ) available in the cookies.
If he is a valid user(i.e., user-name and password match) you should welcome him by name(user-name) else you should display “ You are not an authenticated user “.
Use init-parameters to do this. Store the user-names and passwords in the webinf.xml and access them in the servlet by using the getInitParameters() method.

Week-9:
Install a database(Mysql or Oracle).
Create a table which should contain at least the following fields: name, password, email-id, phone number(these should hold the data from the registration form).
Practice 'JDBC' connectivity.
Write a java program/servlet/JSP to connect to that database and extract data from the tables and display them. Experiment with various SQL queries.
Insert the details of the users who register with the web site, whenever a new user clicks the submit button in the registration page (week2).

Week-10:

Write a JSP which does the following job:
Insert the details of the 3 or 4 users who register with the web site (week9) by using registration
form. Authenticate the user when he submits the login form using the user name and password
from the database ( similar to week8 instead of cookies).

Week-11:
Create tables in the database which contain the details of items (books in our case like Book name , Price, Quantity, Amount )) of each category. Modify your catalogue page (week 2)in such a way that you should connect to the database and extract data from the tables and display them in the catalogue page using JDBC.

Week-12:
HTTP is a stateless protocol. Session is required to maintain the state.
The user may add some items to cart from the catalog page. He can check the cart page for the
selected items. He may visit the catalogue again and select some more items. Here our interest is the selected items should be added to the old cart rather than a new cart. Multiple users can do the same thing at a time(i.e., from different systems in the LAN using the ip-address instead of localhost). This can be achieved through the use of sessions. Every user will have his own session which will be created after his successful login to the website. When the user logs out his session should get invalidated (by using the method session.invalidate() ).

Modify your catalogue and cart JSP pages to achieve the above mentioned functionality using sessions.

JAWAHAR LAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
MULTIMEDIA AND APPLICATION DEVELOPMENT
UNIT-I
Fundamental concepts in Text and Image: Multimedia and hypermedia, world wide web, overview of multimedia software tools. Graphics and image data representation graphics/image data types, file formats, Color in image and video: color science, color models in images, color models in video.

UNIT-II
Fundamental concepts in video and digital audio: Types of video signals, analog video, digital video, digitization of sound, MIDI, quantization and transmission of audio.

UNIT-III
Action Script I : ActionScript Features, Object-Oriented ActionScript, Datatypes and Type Checking, Classes, Authoring an ActionScript Class

UNIT-IV
Action Script II : Inheritance, Authoring an ActionScript 2.0 Subclass, Interfaces, Packages, Exceptions.

UNIT-V
Application Development : An OOP Application Frame work, Using Components with ActionScript MovieClip Subclasses.

UNIT VI
Multimedia data compression: Lossless compression algorithm: Run-Length Coding, Variable Length Coding, Dictionary Based Coding, Arithmetic Coding, Lossless Image Compression, Lossy compression algorithm: Quantization, Transform Coding, Wavelet-Based Coding, Embedded Zerotree of Wavelet Coefficients Set Partitioning in Hierarchical Trees (SPIHT).

UNIT VII
Basic Video Compression Techniques: Introduction to video compression, video compression based on motion compensation, search for motion vectors, MPEG, Basic Audio Compression Techniques.

UNIT-VIII
Multimedia Networks: Basics of Multimedia Networks, Multimedia Network Communications and Applications : Quality of Multimedia Data Transmission, Multimedia over IP, Multimedia over ATM Networks, Transport of MPEG-4, Media-on-Demand(MOD).

TEXT BOOKS:
1. Fudamentals of Multimedia by Ze-Nian Li and Mark S. Drew PHI/Pearson
Education.
2. Essentials ActionScript 2.0, Colin Moock, SPD O,REILLY.

REFERENCE BOOKS:
1. Digital Multimedia, Nigel chapman and jenny chapman, Wiley-Dreamtech
2. Macromedia Flash MX Professional 2004 Unleashed, Pearson.
3. Multimedia and communications Technology, Steve Heath, Elsevier(Focal
Press).
4. Multimedia Applications, Steinmetz, Nahrstedt, Springer.
5. Multimedia Basics by Weixel Thomson.
6. Multimedia Technology and Applications, David Hilman , Galgotia.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
EMBEDDED SYSTEMS
Unit - I
Embedded Computing : Introduction, Complex Systems and Microprocessor, The Embedded System Design Process, Formalisms for System Design, Design Examples. (Chapter I from Text Book 1, Wolf).

Unit - II
The 8051 Architecture : Introduction, 8051 Micro controller Hardware, Input/Output Ports and Circuits, External Memory, Counter and Timers, Serial data Input/Output, Interrupts. (Chapter 3 from Text Book 2, Ayala).

Unit - III
Basic Assembly Language Programming Concepts : The Assembly Language Programming Process, Programming Tools and Techniques, Programming the 8051. Data Transfer and Logical Instructions.
(Chapters 4,5 and 6 from Text Book 2, Ayala).

Unit - IV
Arithmetic Operations, Decimal Arithmetic. Jump and Call Instructions, Further Details on Interrupts.
(Chapter 7and 8 from Text Book 2, Ayala)

Unit - V
Applications : Interfacing with Keyboards, Displays, D/A and A/D Conversions, Multiple Interrupts, Serial Data Communication. (Chapter 10 and 11 from Text Book 2, Ayala).

Unit - VI
Introduction to Real – Time Operating Systems : Tasks and Task States, Tasks and Data, Semaphores, and Shared Data; Message Queues, Mailboxes and Pipes, Timer Functions, Events, Memory Management, Interrupt Routines in an RTOS Environment.
(Chapter 6 and 7 from Text Book 3, Simon).

Unit - VII
Basic Design Using a Real-Time Operating System : Principles, Semaphores and Queues, HardReal-Time Scheduling Considerations, Saving Memory and Power, An example RTOS like uC-OS (Open Source); Embedded Software Development Tools: Host and Target machines, Linker/Locators for Embedded
Software, Getting Embedded Software into the Target System; Debugging Techniques: Testing on Host Machine, Using Laboratory Tools, An Example System. (Chapter 8,9,10 & 11 from Text Book 3, Simon).
Unit - VIII
Introduction to advanced architectures : ARM and SHARC, Processor and memory organization and Instruction level parallelism; Networked embedded systems: Bus protocols, I2C bus and CAN bus; Internet-Enabled Systems, Design Example-Elevator Controller.
(Chapter 8 from Text Book 1, Wolf).

TEXT BOOKS :
1. Computers and Components, Wayne Wolf, Elseveir.
2. The 8051 Microcontroller, Third Edition, Kenneth J.Ayala, Thomson.

REFERENCES :
1. Embedding system building blocks, Labrosse, via CMP publishers.
2. Embedded Systems, Raj Kamal, TMH.
3. Micro Controllers, Ajay V Deshmukhi, TMH.
4. Embedded System Design, Frank Vahid, Tony Givargis, John Wiley.
5. Microcontrollers, Raj kamal, Pearson Education.
6. An Embedded Software Primer, David E. Simon, Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT 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 Book:
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.

REFERNCES:

1. UNIX SYSTEMS PROGRAMMING USING C++ T CHAN, PHI.
2. UNIX for programmers and Users, 3RD Edition, GRAHAM GLASS, KING ABLES, Pearson Education.
3. Advanced UNIX programming, 2nd edition, M J Rochkind pearson education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
MOBILE COMPUTING
UNIT - I
Introduction to Mobile Communications and Computing : Mobile Computing (MC) : Introduction to MC, novel applications, limitations, and architecture.
GSM : Mobile services, System architecture, Radio interface, Protocols, Localization and calling, Handover, Security, and New data services.

UNIT - II
(Wireless) Medium Access Control : Motivation for a specialized MAC (Hidden and exposed terminals, Near and far terminals), SDMA, FDMA, TDMA, CDMA.

UNIT - III
Mobile Network Layer : Mobile IP (Goals, assumptions, entities and terminology, IP packet delivery, agent advertisement and discovery, registration, tunneling and encapsulation, optimizations), Dynamic Host Configuration Protocol (DHCP).

UNIT - IV
Mobile Transport Layer : Traditional TCP, Indirect TCP, Snooping TCP, Mobile TCP, Fast retransmit/ fast recovery, Transmission /time-out freezing, Selective retransmission, Transaction oriented TCP.

UNIT - V
Database Issues : Hoarding techniques, caching invalidation mechanisms, client server computing with adaptation, power-aware and context-aware computing, transactional models, query processing, recovery, and quality of service issues.

UNIT - VI
Data Dissemination: Communications asymmetry, classification of new data delivery mechanisms, push-based mechanisms, pull-based mechanisms, hybrid mechanisms, selective tuning (indexing) techniques.

UNIT - VII
Mobile Ad hoc Networks (MANETs): Overview, Properties of a MANET, spectrum of MANET applications, routing and various routing algorithms, security in MANETs.

UNIT - VIII
Protocols and Tools : Wireless Application Protocol-WAP. (Introduction, protocol architecture, and treatment of protocols of all layers), Bluetooth (User scenarios, physical layer, MAC layer, networking, security, link management) and J2ME.

TEXT BOOKS :
1. Jochen Schiller,“Mobile Communications”,Addison-Wesley. (Chapters
4,7,9,10,11),second edition, 2004.
2. Stojmenovic and Cacute, “Handbook of Wireless Networks and Mobile
Computing”, Wiley, 2002,
ISBN 0471419028. (Chapters 11, 15, 17, 26 and 27)

REFERENCES :
1. Reza Behravanfar, “Mobile Computing Principles: Designing and Developing
Mobile Applications with UML and XML”, ISBN: 0521817331, Cambridge
University Press, October 2004,
2. Adelstein, Frank, Gupta, Sandeep KS, Richard III, Golden , Schwiebert, Loren,
“Fundamentals of Mobile and Pervasive Computing”, ISBN: 0071412379,
McGraw-Hill Professional, 2005.
3. Hansmann, Merk, Nicklous, Stober, “Principles of Mobile Computing”,
Springer, second edition, 2003.
4. Martyn Mallick, “Mobile and Wireless Design Essentials”, Wiley DreamTech,
2003.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
INFORMATION RETRIEVAL SYSTEMS
(ELECTIVE - I)

UNIT-I
Introduction: Definition, Objectives, Functional Overview, Relationship to DBMS, Digital libraries and Data Warehouses.

UNIT-II
Information Retrieval System Capabilities: Search, Browse, Miscellaneous

UNIT-III
Cataloging and Indexing: Objectives, Indexing Process, Automatic Indexing, Information Extraction.

UNIT-IV
Data Structures: Introduction, Stemming Algorithms, Inverted file structures, N-gram data structure, PAT data structure, Signature file structure, Hypertext data structure.

UNIT-V
Automatic Indexing: Classes of automatic indexing, Statistical indexing, Natural language, Concept indexing, Hypertext linkages

UNIT-VI
Document and Term Clustering: Introduction, Thesaurus generation, Item clustering, Hierarchy of clusters.

UNIT-VII
User Search Techniques: Search statements and binding, Similarity measures and ranking, Relevance feedback, Selective dissemination of information search, Weighted searches of Boolean systems, Searching the Internet and hypertext.
Information Visualization: Introduction, Cognition and perception, Information visualization technologies.

UNIT-VIII
Text Search Algorithms: Introduction, Software text search algorithms, Hardware text search systems.
Information System Evaluation: Introduction, Measures used in system evaluation, Measurement example – TREC results.

TEXTBOOK :
1. Kowalski, Gerald, Mark T Maybury: Information Retrieval Systems: Theory and
Implementation, Kluwer Academic Press, 1997.

REFERENCES :
1. Frakes, W.B., Ricardo Baeza-Yates: Information Retrieval Data Structures and
Algorithms, Prentice Hall, 1992.
2. Modern Information Retrival By Yates Pearson Education.
3. Information Storage & Retieval By Robert Korfhage – John Wiley & Sons.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
INFORMATION SECURITY
(ELECTIVE - I)

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.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
VIRTUAL REALITY
(ELECTIVE - I)

UNIT-I
Introduction : The three I’s of virtual reality, commercial VR technology and the five classic components of a VR system. (1.1, 1.3 and 1.5 of Text Book (1))

UNIT - II
Input Devices : (Trackers, Navigation, and Gesture Interfaces): Three-dimensional position trackers, navigation and manipulation, interfaces and gesture interfaces. (2.1, 2.2 and 2.3 of Text Book (1)).

UNIT - III
Output Devices: Graphics displays, sound displays & haptic feedback. (3.1,3.2 & 3.3 of Text Book (1))

UNIT - IV
Modeling : Geometric modeling, kinematics modeling, physical modeling, behaviour modeling, model management. (5.1, 5.2 and 5.3, 5.4 and 5.5 of Text Book (1)).

UNIT - V
Human Factors: Methodology and terminology, user performance studies, VR health and safety issues. (7.1, 7.2 and 7.3 of Text Book (1)).

UNIT - VI
Applications: Medical applications, military applications, robotics applications.
(8.1, 8.3 and 9.2 of Text Book (1)).

UNIT - VII
VR Programming-I : Introducing Java 3D, loading and manipulating external models, using a lathe to make shapes.
(Chapters 14, 16 and 17 of Text Book (2))

UNIT - VIII
VR Programming-II : 3D Sprites, animated 3D sprites, particle systems. (Chapters 18, 19 and 21 of Text Book (2))

TEXT BOOKS :
1. Virtual Reality Technology, Second Edition, Gregory C. Burdea & Philippe Coiffet, John Wiley & Sons, Inc.,
2. Killer Game Programming in Java, Andrew Davison, Oreilly-SPD, 2005.

REFERENCES :
1. Understanding Virtual Reality, interface, Application and Design, William
R.Sherman, Alan Craig, Elsevier(Morgan Kaufmann).
2. 3D Modeling and surfacing, Bill Fleming, Elsevier(Morgan Kauffman).
3. 3D Game Engine Design, David H.Eberly, Elsevier.
4. Virtual Reality Systems, John Vince, Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
HUMAN COMPUTER INTERACTION
(ELECTIVE - I)

UNIT - I
Introduction : Importance of user Interface – definition, importance of good design. Benefits of good design. A brief history of Screen design.

UNIT - II
The graphical user interface – popularity of graphics, the concept of direct manipulation, graphical system, Characteristics, Web user – Interface popularity, characteristics- Principles of user interface.

UNIT - III
Design process – Human interaction with computers, importance of human characteristics human consideration, Human interaction speeds, understanding business junctions.

UNIT - IV
Screen Designing : Design goals – Screen planning and purpose, organizing screen elements, ordering of screen data and content – screen navigation and flow – Visually pleasing composition – amount of information – focus and emphasis – presentation information simply and meaningfully – information
retrieval on web – statistical graphics – Technological consideration in interface design.

UNIT - V
Windows – New and Navigation schemes selection of window, selection of devices based and screen based controls.

UNIT - VI
Components – text and messages, Icons and increases – Multimedia, colors, uses problems, choosing colors.

UNIT - VII
Software tools – Specification methods, interface – Building Tools.

UNIT - VIII
Interaction Devices – Keyboard and function keys – pointing devices – speech recognition digitization and generation – image and video displays – drivers.

TEXT BOOKS :
1. The essential guide to user interface design, Wilbert O Galitz, Wiley DreamaTech.
2. Designing the user interface. 3rd Edition Ben Shneidermann , Pearson Education Asia.

REFERENCES :
1. Human – Computer Interaction. ALAN DIX, JANET FINCAY, GRE GORYD, ABOWD, RUSSELL BEALG, PEARSON.
2. Interaction Design PRECE, ROGERS, SHARPS. Wiley Dreamtech,
3. User Interface Design, Soren Lauesen , Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
SOFTWARE PROJECT MANAGEMENT
(ELECTIVE II)
UNIT - I
Conventional Software Management : The waterfall model, conventional software Management performance.
Evolution of Software Economics : Software Economics, pragmatic software cost estimation.

UNIT - II
Improving Software Economics : Reducing Software product size, improving software processes, improving team effectiveness, improving automation, Achieving required quality, peer inspections.
The old way and the new : The principles of conventional software Engineering, principles of modern software management, transitioning to an iterative process.

UNIT - III
Life cycle phases : Engineering and production stages, inception, Elaboration, construction, transition phases.
Artifacts of the process : The artifact sets, Management artifacts, Engineering artifacts, programmatic artifacts.

UNIT - IV
Model based software architectures : A Management perspective and technical perspective.
Work Flows of the process : Software process workflows, Iteration workflows,

UNIT - V
Checkpoints of the process : Major mile stones, Minor Milestones, Periodic status assessments.
Iterative Process Planning : Work breakdown structures, planning guidelines, cost and schedule estimating, Iteration planning process, Pragmatic planning.

UNIT - VI
Project Organizations and Responsibilities : Line-of-Business Organizations, Project Organizations, evolution of Organizations.
Process Automation : Automation Building blocks, The Project Environment.

UNIT - VII
Project Control and Process instrumentation : The seven core Metrics, Management indicators, quality indicators, life cycle expectations, pragmatic Software Metrics, Metrics automation.
Tailoring the Process : Process discriminants.

UNIT - VIII
Future Software Project Management : Modern Project Profiles, Next generation Software economics, modern process transitions.
Case Study: The command Center Processing and Display system- Replacement (CCPDS-R)

TEXT BOOK :
1. Software Project Management, Walker Royce: Pearson Education, 2005.

REFERENCES :
1. Software Project Management, Bob Hughes and Mike Cotterell: Tata McGraw-
Hill Edition.
2. Software Project Management, Joel Henry, Pearson Education.
3. Software Project Management in practice, Pankaj Jalote, Pearson
Education.2005.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
ADVANCED COMPUTING CONCEPTS
(ELECTIVE - II)

UNIT I
Grid Computing : Data & Computational Grids, Grid Architectures and its relations to various Distributed Technologies

UNIT II
Autonomic Computing, Examples of the Grid Computing Efforts (IBM).

UNIT III
Cluster setup & its Advantages, Performance Models & Simulations; Networking Protocols & I/O, Messaging systems.

UNIT IV
Process scheduling, Load sharing and Balancing; Distributed shared memory, parallel I/O .

UNIT - V
Example cluster System - Beowlf; Cluster Operating systems: COMPaS and NanOS

UNIT - VI
Pervasive Computing concepts & Scenarios; Hardware & Software; Human - machine interface.

UNIT - VII
Device connectivity; Java for Pervasive devices; Application examples

UNIT - VIII
Classical Vs Quantum logic gates ;One ,two & three QUbit Quantum gates; Fredkin & Toffoli gates ; Quantum circuits; Quantum algorithms.

TEXT BOOK :
1. J. Joseph & C. Fellenstein:’ Grid Computing ‘, Pearson Education.
2. J.Burkhardt et .al :’Pervasive computing’ Pearson Education
3. Marivesar:’Approaching quantum computing ‘, Pearson Education.

REFERENCES :
1. Raj Kumar Buyya:’High performance cluster computing’, Pearson Education.
2. Neilsen & Chung L:’Quantum computing and Quantum Information’, Cambridge University Press.
3. A networking approach to Grid Computing , Minoli, Wiley.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
4+1* 0 4
IMAGE PROCESSING
(ELECTIVE - II)
UNIT - I
Introduction : Examples of fields that use digital image processing, fundamental steps in digital image processing,components of image processing system. Digital Image Fundamentals: A simple image formation model, image sampling and quantization, basic relationships between pixels (p.nos. 15-17, 21- 44, 50-69).

UNIT - II
Image enhancement in the spatial domain : Basic gray-level transformation, histogram processing, enhancement using arithmetic and logic operators, basic spatial filtering, smoothing and sharpening spatial filters, combining the spatial enhancement methods ( p.nos 76-141).

UNIT - III
Image restoration : A model of the image degradation/restoration process, noise models, restoration in the presence of noise–only spatial filtering, Weiner filtering, constrained least squares filtering, geometric transforms; Introduction to the Fourier transform and the frequency domain, estimating the degradation
function (p.nos 147-167, 220-243, 256-276).

UNIT - IV
Color Image Processing : Color fundamentals, color models, pseudo color image processing, basics of full–color image processing, color transforms, smoothing and sharpening, color segmentation (p.nos: 282- 339).

UNIT - V
Image Compression : Fundamentals, image compression models, error-free compression, lossypredictive coding, image compression standards (p.nos: 409-467,492-510).

UNIT - VI
Morphological Image Processing : Preliminaries, dilation, erosion, open and closing, hit or miss transformation, basic morphologic algorithms (p.nos:519-550).

UNIT - VII
Image Segmentation : Detection of discontinuous, edge linking and boundary detection, thresholding, region–based segmentation (p.nos: 567-617).

UNIT - VIII
Object Recognition : Patterns and patterns classes, recognition based on decision–theoretic methods, matching, optimum statistical classifiers, neural networks, structural methods – matching shape numbers, string matching (p.nos: 693-735).

TEXT BOOK :
1. Digital Image Processing, Rafeal C.Gonzalez, Richard E.Woods, Second
Edition, Pearson Education/PHI.

REFERENCES :
1. Image Processing, Analysis, and Machine Vision, Milan Sonka, Vaclav Hlavac
and Roger Boyle, Second Edition, Thomson Learning.
2. Introduction to Digital Image Processing with Matlab, Alasdair McAndrew,
Thomson Course Technology
3. Digital Image Processing and Analysis, B. Chanda, D. Datta Majumder,
Prentice Hall of India, 2003.
4. Computer Vision and Image Processing, Adrian Low, Second Edition,
B.S.Publications
5. Digital Image Processing using Matlab, Rafeal C.Gonzalez, Richard E.Woods,
Steven L. Eddins, Pearson Education.
6. Digital Image Processing, William K. Prat, Wily Third Edition
7. Digital Image Processing, Jahne, Springer.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
0 3 2
NETWORK PROGRAMMING LAB
Objectives:
• To teach students various forms of IPC through Unix and socket Programming

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 LAN Connected
• Any flavour of Unix / Linux

Week1.
Implement the following forms of IPC.
a)Pipes
b)FIFO

Week2.
Implement file transfer using Message Queue form of IPC

Week3.
Write a programme to create an integer variable using shared memory concept and increment the variable simultaneously by two processes. Use senphores to avoid race conditions

Week4.
Design TCP iterative Client and server application to reverse the given input sentence

Week5.
Design TCP iterative Client and server application to reverse the given input sentence

Week6.
Design TCP client and server application to transfer file

Week7.
Design a TCP concurrent server to convert a given text into upper case using multiplexing system call “select”

Week8.
Design a TCP concurrent server to echo given set of sentences using poll functions

Week9.
Design UDP Client and server application to reverse the given input sentence

Week10
Design UDP Client server to transfer a file

Week11
Design using poll client server application to multiplex TCP and UDP requests for converting a given text into upper case.

Week12
Design a RPC application to add and subtract a given pair of integers

Reference Book:
1.Advance Unix Programming Richard Stevens, Second Edition Pearson Education
2. Advance Unix Programming, N.B. Venkateswarlu, BS Publication.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT I-Sem T P C
0 3 2
MULTIMEDIA AND APPLICATION DEVELOPMENT LAB

1. Assigning Actions to an Object, and a Button
2. Creating Loops
3. Generation Random Numbers
4. Creating a Function, Calling a Function
5. Detecting the Player Version
6. Detecting the Operating System
7. Checking the System language
8. Detecting Display Settings
9. Tinting a Movie Clip’s Color
10. Controlling a Movie Clip’s Color with Sliders
11. Drawing a Circle
12. Drawing a Rectangle
13. Filling a Shape with a Gradient
14. Scripting Masks
15. Converting Angle Measurements
16. Calculating the Distance Between the Two Points
17. Formatting Currency Amount
18. Converting Between Units of Measurement
19. Determining Points Along a Circle
20. Sorting or Reversing an Array
21. Implementing a Custom Sort
22. Creating a Text Field
23. Making a Password Inputfield
All the above programs are to be done in Flash MX 2004.

REFERENCES :
1. Action Script Cookbook, Joey Lott, SPD-Oreilly.
2. Flash MX Action Script for designers, Doug Sahlin, Dreamtech Wiley.
3. Flash MX Professional 2004 Unleashed, David Vogeleer and Matthew Pizzi,
Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT II-Sem T P C
4+1* 0 4
MANAGEMENT SCIENCE

Unit - I
Introduction to Management: Concepts of Management and organization- nature, importance and Functions of Management, Taylor’s Scientific Management Theory, Fayol’s Principles of Management, Mayo’s Hawthorne Experiments, Maslow’s Theory of Human Needs, Douglas McGregor’s Theory X and Theory Y, Herzberg’s Two-Factor Theory of Motivation, Systems Approach to Management, Leadership Styles, Social responsibilities of Management.

Unit - II
Designing Organisational Structures : Basic concepts related to Organisation - Departmentation and Decentralisation, Types of mechanistic and organic structures of organisation (Line organization, Line and staff organization, functional organization, Committee organization, matrix organization, Virtual Organisation, Cellular Organisation, team structure, boundaryless organization, inverted pyramid structure, lean and flat
organization structure) and their merits, demerits and suitability.

Unit - III
Operations Management : Principles and Types of Plant Layout-Methods of production (Job, batch and Mass Production), Work Study -Basic procedure involved in Method Study and Work Measurement- Statistical Quality Control: chart, R chart, c chart, p chart, (simple Problems), Acceptance Sampling,
Deming’s contribution to quality.

Unit -IV
a) Materials Management: Objectives, Need for Inventory control, EOQ, ABC Analysis, Purchase Procedure, Stores Management and Stores Records.
b) Marketing: Functions of Marketing, Marketing Mix, Marketing Strategies based on Product Life Cycle, Channels of distribution

Unit - V
Human Resources Management (HRM) : Concepts of HRM, HRD and Personnel Management and Industrial Relations (PMIR), HRM vs.PMIR, Basic functions of HR Manager: Manpower planning, Recruitment, Selection, Training and Development, Placement, Wage and Salary Administration,
Promotion, Transfer, Separation, Performance Appraisal, Grievance Handling and Welfare Administration, Job Evaluation and Merit Rating.

Unit - VI
Project Management (PERT/CPM) : Network Analysis, Programme Evaluation and Review Technique (PERT), Critical Path Method (CPM), Identifying critical path, Probability of Completing the project within
given time, Project Cost Analysis, Project Crashing. (simple problems)

Unit - VII
Strategic Management : Mission, Goals, Objectives, Policy, Strategy, Programmes, Elements of Corporate Planning Process, Environmental Scanning, Value Chain Analysis, SWOT Analysis, Steps in Strategy Formulation and Implementation, Generic Strategy alternatives.

Unit - VIII
Contemporary Management Practices : Basic concepts of MIS, End User Computing, Materials Requirement Planning (MRP), Just-In-Time (JIT) System, Total Quality Management (TQM), Six sigma and Capability Maturity Model (CMM) Levels, Supply Chain Management, Enterprise Resource Planning (ERP), Performance Management, Business Process outsourcing (BPO), Business Process Re-engineering and Bench Marking, Balanced Score Card.

TEXT BOOKS :
1. Aryasri : Management Science, TMH, 2004.
2. Stoner, Freeman, Gilbert, Management, 6th Ed, Pearson Education, New Delhi, 2004.

REFERENCES :
1. Kotler Philip & Keller Kevin Lane: Marketing Mangement 12/e, PHI, 2005
2. Koontz & Weihrich: Essentials of Management, 6/e, TMH, 2005
3. Thomas N.Duening & John M.Ivancevich Management — Principles and Guidelines, Biztantra,2003.
4. Kanishka Bedi, Production and Operations Management, Oxford University Press, 2004.
5. Memoria & S.V.Gauker, Personnel Management, Himalaya, 25/e, 2005
6. Samuel C.Certo: Modern Management, 9/e, PHI, 2005
7. Schermerhorn, Capling, Poole & Wiesner: Management, Wiley, 2002.
8. Parnell: Strategic Management, Biztantra,2003.
9. Lawrence R Jauch, R.Gupta &William F.Glueck:Business Policy and Strategic Management, Frank Bros.2005.
10. L.S.Srinath: PERT/CPM,Affiliated East-West Press, 2005.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT II-Sem T P C
4+1* 0 4
MULTIMEDIA DATABASES
(ELECTIVE - III)

UNIT-I
Introduction : An introduction to Object-oriented Databases; Multidimensional Data Structures: k-d Trees, Point Quadtrees, The MX-Quadtree, R-Trees, comparison of Different Data Structures

UNIT-II
Image Databases : Raw Images, Compressed Image Representations, Image Processing: Segmentation, Similarity-Based Retrieval, Alternative Image DB Paradigms, Representing Image DBs with Relations, Representing Image DBs with R-Trees, Retrieving Images By Spatial Layout, Implementations

UNIT-III
Text/Document Databases : Precision and Recall, Stop Lists, Word Stems, and Frequency Tables, Latent Semantic Indexing, TV-Trees, Other Retrieval Techniques

UNIT-IV
Video Databases : Organizing Content of a Single Video, Querying Content of Video Libraries, Video Segmentation, video Standards
Audio Databases : A General Model of Audio Data, Capturing Audio Content through Discrete Transformation, Indexing Audio Data

UNIT-V
Multimedia Databases : Design and Architecture of a Multimedia Database, Organizing Multimedia Data Based on The Principle of Uniformity, Media Abstractions, Query Languages for Retrieving Multimedia Data, Indexing SMDSs with Enhanced Inverted Indices, Query Relaxation/Expansion

Unit-VI
Creating Distributed Multimedia Presentations : Objects in Multimedia Presentations, Specifying Multimedia Documents with Temporal Constraints, Efficient Solution of Temporal Presentation Constraints, Spatial Constraints.

Unit-VII
Spatial Concepts and Data Models: Models of spatial information, Design extending the ER model with spatial concepts, Extending the ER model pictograms, Object oriented data model with UML.

Unit-VIII
Spatial Query Languages: Extending the SQL for spatial data, Examples of queries that emphasis spatial data, Object relational schema examples querries.

TEXT BOOKS :
1. Principles of Multimedia Database Systems, V.S. Subrahmanian,
Elseveir(Morgan Kauffman).
2. Spatial Databases, Shashi Shekhar, Sanjiv Chawla, Pearson Education.

REFERENCES :
1. Multimedia Databases: An object relational approach, Lynne Dunckley,
Pearson Education.
2. Multimedia Database Systems, Prabhakaram, Springer.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT II-Sem T P C
4+1* 0 4
NETWORK MANAGEMENT SYSTEMS
(ELECTIVE - III)

UNIT-I
Data communications and Network Management Overview : Analogy of Telephone Network Management, Communications protocols and Standards, Case Histories of Networking and Management, Challenges of Information Technology Managers, Network Management: Goals, Organization, and Functions, Network and System Management, Network Management System Platform, Current Status and future of Network Management.

UNIT-II
SNMPV1 Network Management : Organization and Information and Information Models.
Managed network: Case Histories and Examples, The History of SNMP Management, The SNMP Model, The Organization Model, System Overview, The Information Model.

UNIT-III
SNMPv1 Network Management : Communication and Functional Models.
The SNMP Communication Model, Functional model

UNIT-IV
SNMP Management: SNMPv2 : Major Changes in SNMPv2, SNMPv2 System Architecture, SNMPv2 Structure of Management Information, The SNMPv2 Management Information Base, SNMPv2 Protocol, Compatibility With SNMPv1

UNIT-V
SNMP Management: RMON : What is Remote Monitoring? , RMON SMI and MIB, RMON1, RMON2, ATM Remote Monitoring, A Case Study of Internet Traffic Using RMON

UNIT-VI
Telecommunications Management Network : Why TMN?, Operations Systems, TMN Conceptual Model, TMN Standards, TMN Architecture, TMN Management Service Architecture, An Integrated View of TMN, Implementation Issues.

UNIT-VII
Network Management Tools and Systems : Network Management Tools, Network Statistics Measurement Systems, History of Enterprise Management, Network Management systems, Commercial
Network management Systems, System Management, Enterprise Management Solutions.

UNIT-VIII
Web-Based Management : NMS with Web Interface and Web-Based Management, Web Interface to SNMP Management, Embedded Web-Based Management, Desktop management Interface, Web-Based Enterprise Management, WBEM: Windows Management Instrumentation, Java management Extensions, Management of a Storage Area Network: , Future Directions

TEXT BOOK :
1. Network Management, Principles and Practice, Mani Subrahmanian, Pearson
Education.

REFERENCES :
1. Network management, Morris, Pearson Education.
2. Principles of Network System Administration, Mark Burges, Wiley Dreamtech.
3. Distributed Network Management, Paul, John Wiley.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT II-Sem T P C
4+1* 0 4
BIOMETRICS
(ELECTIVE - III)

UNIT I
Introduction – Benefits of biometric security – Verification and identification – Basic working of biometric matching – Accuracy – False match rate – False non-match rate – Failure to enroll rate – Derived metrics – Layered biometric solutions.

UNIT II
Finger scan – Features – Components – Operation (Steps) – Competing finger Scan technologies – Strength and weakness. Types of algorithms used for interpretation.

UNIT III
Facial Scan - Features – Components – Operation (Steps) – Competing facial Scan technologies – Strength and weakness.

UNIT IV
Iris Scan - Features – Components – Operation (Steps) – Competing iris Scan technologies – Strength and weakness.

UNIT V
Voice Scan - Features – Components – Operation (Steps) – Competing voice Scan (facial) technologies – Strength and weakness.

UNIT VI
Other physiological biometrics – Hand scan – Retina scan – AFIS (Automatic Finger Print Identification Systems) – Behavioral Biometrics – Signature scan- keystroke scan.

UNIT VII
Biometrics Application – Biometric Solution Matrix – Bio privacy – Comparison of privacy factor in different biometrics technologies – Designing privacy sympathetic biometric systems. Biometric standards – (BioAPI , BAPI) – Biometric middleware

UNIT VIII
Biometrics for Network Security. Statistical measures of Biometrics. Biometric Transactions.

TEXT BOOKS :
1. Biometrics – Identity Verification in a Networked World – Samir Nanavati,
Michael Thieme, Raj Nanavati, WILEY- Dream Tech
2. Biometrics for Network Security- Paul Reid, Pearson Education.

REFERENCE:
1. Biometrics- The Ultimate Reference- John D. Woodward, Jr. Wiley Dreamtech.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT II-Sem T P C
4+1* 0 4
BIOINFORMATICS
(ELECTIVE-IV)

UNIT-I
Introduction to Bioinformatics: Scope of Bioinformatics, Elementary commands and protocols, ftp, telnet, http. Primer on information theory.

UNIT-II
Introduction to Homology : Introduction to Homology (with special mention to Charles Darwin, Sir Richard Owen, Willie Henning, Alfred Russel Wallace).

UNIT-III
Special Topics In Bioinformatics : DNA mapping and sequencing, Map alignment, Large scale sequencing methods Shotgun and Sanger method.

UNIT-IV
Sequencing Alignment and Dynamic Programming : Heuristic Alignment algorithms. Global sequence alignments-Neddleman-Wunsch Algorithm Smith-Waterman Algorithm-Local sequence alignments (Amino acid substitution Matrices (PAM, BLOSUM).

UNIT-V
Primary Database and their Use : Introduction to Biological databases, Organization and management of databases. Searching and retrieval of information from the World Wide Web. Structure databases-PDB (Protein Data Bank), Molecular Modeling Databases (MMDB). Primary Databases NCBL,EMBL, DDBJ.

UNIT-VI
Secondary Databases : Introduction to Secondary Databases Organization and management of databases Swissprot, PIR,KEGG

UNIT-VII
Bio Chemical Data Bases : Introduction to BioChemical databases-organization and Management of databases. KEGG, EXGESCY, BRENDA, WIT.

UNIT-VIII
Evolutionary Trees and Phylogeny : Multiple sequence alignment and phylogenetic analysis.

TEXT BOOKS :
1. Bioinformatics Basics. Applications in Biological Science and Medicine by
Hooman H. Rashidi and Lukas K.Buehler CAC Press 2000.
2. Algorithms on Strings Trees and Sequences Dan Gusfiled. Cambridge
University Press 1997.

REFERENCES :
1. Bioinformatics: A Machine Learning Approach P. Baldi. S. Brunak, MIT Press
1988.
2. Bioinformatics. David Mount, 2000. CSH Publications
3. Developing Bioinformatics Skills. Cynthia Gibbas & Per Jamberk
4. Genomics and Proteomics-Functional and Computational aspects. Springer
Publications. Editior-Sandor Suhai.
5. Bioinformatics- Methods and Protocols-Human Press. Stephen Misener,
Stephen A. Krawetz.
6. Computational Biochemistry – C.Stan ,TSAI WILEY Publications.
7. Bioinformatics – A Practical guide to the Analysis of Genes and Proteins –
ANDREAS D.BAXEVANIS, B.F. FRANCIS OUELLETTE.
8. Bioinformatics – Principles and Applications – Harshawardhan P.Bal TATA
MEGRAW HILL.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT II-Sem T P C
4+1* 0 4
DESIGN PATTERNS
(ELECTIVE-IV)

UNIT –I
Introduction : What Is a Design Pattern?, Design Patterns in Smalltalk MVC, Describing Design Patterns, The Catalog of Design Patterns, Organizing the Catalog, How Design Patterns Solve Design Problems, How to Select a Design Pattern, How to Use a Design Pattern.

UNIT-II
A Case Study : Designing a Document Editor : Design Problems, Document Structure, Formatting, Embellishing the User Interface, Supporting Multiple Look-and-Feel Standards, Supporting Multiple Window Systems, User Operations Spelling Checking and Hyphenation, Summary .

UNIT-III
Creational Patterns : Abstract Factory, Builder, Factory Method, Prototype, Singleton, Discussion of Creational Patterns.

UNIT-IV
Structural Pattern Part-I : Adapter, Bridge, Composite.

UNIT-V
Structural Pattern Part-II : Decorator, açade, Flyweight, Proxy.

UNIT-VI
Behavioral Patterns Part-I : Chain of Responsibility, Command, Interpreter, Iterator.

UNIT-VII
Behavioral Patterns Part-II : Mediator, Memento, Observer, State, Strategy, Template Method ,Visitor, Discussion of Behavioral Patterns.

UNIT-VIII
What to Expect from Design Patterns, A Brief History, The Pattern Community An Invitation, A Parting Thought.

TEXT BOOK :
1. Design Patterns By Erich Gamma, Pearson Education

REFERENCES :
1. Pattern’s in JAVA Vol-I By Mark Grand ,Wiley DreamTech.
2. Pattern’s in JAVA Vol-II By Mark Grand ,Wiley DreamTech.
3. JAVA Enterprise Design Patterns Vol-III By Mark Grand ,Wiley DreamTech.
4. Head First Design Patterns By Eric Freeman-Oreilly-spd
5. Design Patterns Explained By Alan Shalloway,Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY
HYDERABAD
IV Year B.Tech. IT II-Sem T P C
4+1* 0 4
PATTERN RECOGNITION
(ELECTIVE - IV)

UNIT - I
Introduction : Machine perception, pattern recognition example, pattern recognition systems, the design cycle, learning and adaptation (Text book-1, p.nos: 1-17).

UNIT - II
Bayesian Decision Theory : Introduction, continuous features – two categories classifications, minimum error-rate classification- zero–one loss function, classifiers, discriminant functions, and decision surfaces (Text book-1, p.nos: 20-27, 29-31).

UNIT-III
Normal density : Univariate and multivariate density, discriminant functions for the normal densitydifferent cases, Bayes decision theory – discrete features, compound Bayesian decision theory and context (Text book-1, p.nos: 31-45,51-54,62-63).

UNIT-IV
Maximum likelihood and Bayesian parameter estimation : Introduction, maximum likelihood estimation, Bayesian estimation, Bayesian parameter estimation–Gaussian case (Text book-1, p.nos: 84-97).

UNIT-V
Un-supervised learning and clustering : Introduction, mixture densities and identifiability, maximum likelihood estimates, application to normal mixtures, K-means clustering. Date description and clustering – similarity measures, criteria function for clustering (Text book-1, p.nos: 517 – 526, 537 – 546).

UNIT-VI
Component analyses : Principal component analysis, non-linear component analysis; Low dimensional representations and multi dimensional scaling (Text book-1, p.nos: 568-570,573 – 576,580-581).

UNIT-VII
Discrete Hidden Morkov Models : Introduction, Discrete–time markov process, extensions to hidden Markov models, three basic problems for HMMs. (Text book -2, p.nos: 321 – 344)

UNIT-VIII
Continuous hidden Markov models : Observation densities, training and testing with continuous HMMs, types of HMMs. (Text book-2, p.nos: 348 – 352)

TEXT BOOKS :
1. Pattern classifications, Richard O. Duda, Peter E. Hart, David G. Stroke. Wiley
student edition, Second Edition.
2. Fundamentals of speech Recognition, Lawerence Rabiner, Biing – Hwang
Juang Pearson education.

REFERENCE :
1. Pattern Recognition and Image Analysis – Earl Gose, Richard John baugh, Steve Jost PHI 2004

DMDW FAQS with solutions for JNTU BTECH and MCA students unit vii

2009-05-07T02:48:00.000-07:00

1.Explain Cluster analysis?
Cluster analysis or clustering is the assignment of objects into groups (called clusters) so that objects from the same cluster are more similar to each other than objects from different clusters. Often similarity is assessed according to a distance measure. Clustering is a common technique for statistical data analysis, which is used in many fields, including machine learning, data mining, pattern recognition, image analysis and bioinformatics. Besides the term data clustering (or just clustering), there are a number of terms with similar meanings, including cluster analysis, automatic classification, numerical taxonomy, botryology and typological analysis.
2.Discuss different types of clustering techniques?
Data clustering algorithms can be hierarchical. Hierarchical algorithms find successive clusters using previously established clusters. Hierarchical algorithms can be agglomerative ("bottom-up") or divisive ("top-down"). Agglomerative algorithms begin with each element as a separate cluster and merge them into successively larger clusters. Divisive algorithms begin with the whole set and proceed to divide it into successively smaller clusters. Partitional algorithms typically determine all clusters at once, but can also be used as divisive algorithms in the hierarchical clustering. Density-based clustering algorithms are devised to discover arbitrary-shaped clusters. In this approach, a cluster is regarded as a region in which the density of data objects exceeds a threshold. DBSCAN and OPTICS are two typical algorithms of this kind.
Two-way clustering, co-clustering or biclustering are clustering methods where not only the objects are clustered but also the features of the objects, i.e., if the data is represented in a data matrix, the rows and columns are clustered simultaneously.
Another important distinction is whether the clustering uses symmetric or asymmetric distances. A property of Euclidean space is that distances are symmetric (the distance from object A to B is the same as the distance from B to A). In other applications (e.g., sequence-alignment methods, see Prinzie & Van den Poel (2006)), this is not the case.
Many clustering algorithms require specification of the number of clusters to produce in the input data set, prior to execution of the algorithm. Barring knowledge of the proper value beforehand, the appropriate value must be determined, a problem for which a number of techniques have been developed.
3. Explain Partitioning Around Medoids (Pam) algorithm.
Compared to the well - known kmeans algorithm, .Pam has the following features:
It operates on the dissimilarity matrix of the given data set or when it is presented with an n ´ p data matrix, the algorithm first computes a dissimilarity matrix.
It is more robust, because it minimizes a sum of dissimilarities instead of a sum of squared Euclidean distances.
It provides a novel graphical display, the silhouette plot, which allows the user to select the optimal number of clusters.
In many clustering problems, one is interested in the characterization of the clusters by means of typical objects, which represent the various structural features of objects under investigation. The algorithm Pam first computes k representative objects, called medoids. A medoid can be defined as that object of a cluster, whose average dissimilarity to all the objects in the cluster is minimal. In the classification literature, such representative objects are called centrotypes. After finding the set of medoids, each object of the data set is assigned to the nearest medoid. That is, object i is put into cluster vi, when medoid mvi is nearer than any other medoid mw.
d(i, mvi ) £ d (i,m w ) for all w = 1,..., k.
The k representative objects should minimize the objective function, which is the sum of the dissimilarities of all objects to their nearest medoid:
Objective function = S d(i, mvI)
The algorithm proceeds in two steps:
BUILD-step: This step sequentially selects k "centrally located" objects, to be used as initial medoids
SWAP-step: If the objective function can be reduced by interchanging (swapping) a selected object with an unselected object, then the swap is carried out. This is continued till the objective function can no longer be decreased.
Isolated clusters : The program considers two types of isolated clusters. L-clusters and L* clusters. Cluster C is an L-cluster, if for each object i belonging to C:
max dij < min dih, j C h C
Cluster C is an L* - cluster, if
max dij < min dlh, ij C, l C,h C
It is clear that L* - clusters are also L-clusters. It should be noted that the property of being isolated depends on the internal structure of a cluster as well as on its position relative to other clusters.
Diameter of a cluster
The diameter of Cluster C is defined as the largest dissimilarity between objects belonging to the Cluster C.
DiameterC = max dij, i,j C
Separation of a cluster
The separation of Cluster C is defined as the smallest dissimilarity between two objects; one of which belong to Cluster C and the other does not.
SeparationC = min dlh, l C, h C
Average distance to a medoid
If j is the medoid of Cluster C, the average distance of all objects of C to j is calculated as follows:
Average distancej =
where N is the number of object minus other than j.
Maximum distance to medoid
If object j is the medoid of cluster C, the maximum distance of objects of C to j is calculated as follows:
Maximum distancej = max dij , i C
Graphical display
Two of the most difficult tasks in cluster analysis are: How to decide the appropriate number of clusters and how to distinguish a bad cluster from a good one. The module Clusfind computes a set of values called silhouettes that provide key information about these tasks. First, we will explain how these are calculated and then we will show how they are used
Each cluster is represented by one silhouette, showing which objects lie within the cluster and which objects merely hold an intermediate position. The entire clustering is displayed by plotting all silhouettes into a single diagram, from which the quality of the clusters can be compared.
Silhouettes are constructed in the following way. Consider any object i of the data set, and let A denote the cluster to which it is assigned, and then calculate
a ( i ) = average dissimilarity of i to all other objects of A
Now consider any cluster C different from A and define
d ( i, C ) = average dissimilarity of i to all objects of C
Compute d ( i, C ) for all clusters C A, and then select the smallest of those
b = min d ( i,C ) , C A
Let B denote the cluster which attains the minimum i.e., d ( i,B ) = b ( i ) is called the neighbour of object i. The value s ( i ) can now be defined as:
s(i) =
Outlier Analysis:
l Working definition
– An outlier xk is an element of a data sequence S that is inconsistent with out expectations, based on the majority of other elements of S.
l Sources of outliers
– Measurement errors
– Other uninteresting anomalous data
l valid data observations made under anomalous conditions
– Surprising observations that may be important
Identifying Outliers
The 3s - edit rule
– If x ~ N(m, s2), then P(x-m>3s) » 0.003
– estimate mean x
– estimate standard deviation s’
– compute zk = (xk - x)/s’
– if zk > t, then xk is an outlier
4. Explain outlier analysis with illustration.
Rare, unusual, or just plain infrequent events are of interest in data mining in many contexts including fraud in income tax, insurance, and online banking, as well as for marketing. We classify analyses that focus on the discovery of such data items as outlier analysis. () captures the concept of an outlier as:
an observation that deviates so much from other observations as to arouse suspicion that it was generated by a different mechanism.
Outlier detection algorithms often fall into one of the categories of distance-based methods, density-based methods, projection-based methods, and distribution-based methods.
A general approach to identifying outliers is to assume a known distribution for the data and to examine the deviation of individuals from the distribution. Such approaches are common in statistics (, ) but such approaches do not scale well.
Distance based methods are common in data mining where the measure of an entities outliedness is based on its distance to nearby entities. The number of nearby entities and the minimum distance are two parameters. (see knorr and ng 1998 vldb24)
Density based approaches from breuning kriegel ng and sander 2000 sigmod LOF: local outlier factor. See also jin tung and han kdd2001.
The early work on outliers was carried out from a statistical view point where outliers are data points that deviate significantly from the identified underlying distribution of the data. () is a good textbook on outliers. () is another overview of statistical outliers.
Distance based approaches have been developed by (), () and (). Such approaches usually explore some neighbourhood and do not rely on underlying distributions.
() identify outliers by counting the number of neighbours within a specified radius of a data point. The radius and the threshold number of points are the only two parameters of the approach. The approach is simple but is inadequate for data that is distributed with uneven density where and might need to vary to cope with the changes. () have a similar approach whereby data points are ranked by the sum of their distance to their nearest neighbours.
() and then () introduce a density based approach to score data points with a local outlier factor (LOF). () introduce a heuristic to more efficiently identify the top outliers using the LOF.
() build mixture models as data becomes available and identifies outliers as those data items causing the most perturbation to the model.
() explore the issue of outliers in high dimensional space where data tends to be sparse and consequently all data points tend to be equidistant to other points (, ) and suggest an algorithm where the high dimensional space is projected to a lower dimensional space having unusually low density. An evolutionary algorithm is proposed to generate candidate subspaces in which outliers are to be searched for.
5.Explain K-Means and K-Medoids clustering algorithms?
The most common algorithm uses an iterative refinement technique. Due to its ubiquity it is often called the k-means algorithm; it is also referred to as Lloyd's algorithm, particularly in the computer science community.
Given an initial set of k means m1(1),…,mk(1), which may be specified randomly or by some heuristic, the algorithm proceeds by alternating between two steps:
Assignment step: Assign each observation to the cluster with the closest mean (i.e. partition the observations according to the Voronoi diagram generated by the means).

Si = {xj xj – mi(t) <= xj – mi(t) for all i* = 1, ….., k}

Update step: Calculate the new means to be the centroid of the observations in the cluster.

Mi (t+1) = i/ si(t)
The algorithm is deemed to have converged when the assignments no longer change.
The k-medoids algorithm is a clustering algorithm related to the k-means algorithm and the medoidshift algorithm. Both the k-means and k-medoids algorithms are partitional (breaking the dataset up into groups) and both attempt to minimize squared error, the distance between points labeled to be in a cluster and a point designated as the center of that cluster. In contrast to the k-means algorithm k-medoids chooses datapoints as centers (medoids or exemplars).
k-medoid is a classical partitioning technique of clustering that clusters the data set of n objects into k clusters known a priori. A useful tool for determining k is the silhouette.
It is more robust to noise and outliers as compared to k-means.
A medoid can be defined as that object of a cluster, whose average dissimilarity to all the objects in the cluster is minimal i.e. it is a most centrally located point in the given data set.
The most common realization of k-medoid clustering is the Partitioning Around Medoids (PAM) algorithm and is as follows:
The algorithm begins with arbitrary selection of the k objects as medoid points out of n data points (n>k)
After selection of the k medoid points, associate each data object in the given data set to most similar medoid. The similarity here is defined using distance measure that can be Euclidean distance, Manhattan distance or Minkowski distance
Randomly select nonmedoid object O′
compute total cost S of swapping initial medoid object to O′
If S<0, then swap initial medoid with the new one (if S<0 then there will be new set of medoids)
repeat steps 2 to 5 until there is no change in the medoid.

6.Explain Grid – based methods.
Grid based method consist of a gird structure formed by quantifying the object space into a finite number of cells. It is an approach of representing data object using a multi-resolution grid data structure on which all of clustering operations are performed. The benefit of grid-based methods is that it processed operations quickly without taking much time, as it depends only on the number of cells in each dimensions in the quantized space and does not rely on the number of data objects.
Grid – based approach are,
a) wave cluster : a wavelet transform is used to cluster object
b) STING : the grid cells contain statistical information which is reviewed by STING
c) CLIQUE : it is used for clustering in high-dimensional data region.
7.Discuss model based clustering methods.
Model based methods build a cluster on the basis of a model that receives the best data among others. A density function is built by model based algorithms to locate clusters. The density function defines the spatial distribution of the data points. On the basis of statistics which include noise or outliers model based algorithms can automatically find the number of clusters, which powerful clustering methods. We select clustering algorithms on the basis of The particular purpose of the application Data available.
Model based clustering are:
a) COBWEB
b) Expectation maximization (EM)
c) SOM
8.Discuss briefly Agglomerative and Divisive analysis
Agglomerative Clustering : Initially it starts with every object forming a separate group and then successively combining the objects or groups that are near to one another or until end condition is satisfied. This method is also referred as ‘bottom-up’ approach.
Divisive Clustering
Initially it starts with entire objects in a single cluster and then on successive iterations a cluster is broken down into smaller clusters until each cluster has single object or until end condition is satisfied. This method is also referred as ‘top-down’ approach.
9.Explain Partitional Methods
k-means clustering
The k-means algorithm assigns each point to the cluster whose center (also called centroid) is nearest. The center is the average of all the points in the cluster — that is, its coordinates are the arithmetic mean for each dimension separately over all the points in the cluster.
Example: The data set has three dimensions and the cluster has two points: X = (x1, x2, x3) and Y = (y1, y2, y3). Then the centroid Z becomes Z = (z1, z2, z3), where z1 = (x1 + y1)/2 and z2 = (x2 + y2)/2 and z3 = (x3 + y3)/2.
The algorithm steps are:
Choose the number of clusters, k.
Randomly generate k clusters and determine the cluster centers, or directly generate k random points as cluster centers.
Assign each point to the nearest cluster center.
Recompute the new cluster centers.
Repeat the two previous steps until some convergence criterion is met (usually that the assignment hasn't changed).
The main advantages of this algorithm are its simplicity and speed which allows it to run on large datasets. Its disadvantage is that it does not yield the same result with each run, since the resulting clusters depend on the initial random assignments. It minimizes intra-cluster variance, but does not ensure that the result has a global minimum of variance. Another disadvantage is the requirement for the concept of a mean to be definable which is not always the case. For such datasets the k-medoids variant is appropriate.
Fuzzy c-means clustering
In fuzzy clustering, each point has a degree of belonging to clusters, as in fuzzy logic, rather than belonging completely to just one cluster. Thus, points on the edge of a cluster, may be in the cluster to a lesser degree than points in the center of cluster. For each point x we have a coefficient giving the degree of being in the kth cluster uk(x). Usually, the sum of those coefficients for any given x is defined to be 1:
With fuzzy c-means, the centroid of a cluster is the mean of all points, weighted by their degree of belonging to the cluster:
The degree of belonging is related to the inverse of the distance to the cluster center:
then the coefficients are normalized and fuzzyfied with a real parameter m > 1 so that their sum is 1. So
For m equal to 2, this is equivalent to normalising the coefficient linearly to make their sum 1. When m is close to 1, then cluster center closest to the point is given much more weight than the others, and the algorithm is similar to k-means.
The fuzzy c-means algorithm is very similar to the k-means algorithm:
Choose a number of clusters.
Assign randomly to each point coefficients for being in the clusters.
Repeat until the algorithm has converged (that is, the coefficients' change between two iterations is no more than ε, the given sensitivity threshold) :
Compute the centroid for each cluster, using the formula above.
For each point, compute its coefficients of being in the clusters, using the formula above.
The algorithm minimizes intra-cluster variance as well, but has the same problems as k-means, the minimum is a local minimum, and the results depend on the initial choice of weights. The Expectation-maximization algorithm is a more statistically formalized method which includes some of these ideas: partial membership in classes. It has better convergence properties and is in general preferred to fuzzy-c-means.
QT clustering algorithm
QT (quality threshold) clustering (Heyer, Kruglyak, Yooseph, 1999) is an alternative method of partitioning data, invented for gene clustering. It requires more computing power than k-means, but does not require specifying the number of clusters a priori, and always returns the same result when run several times.
The algorithm is:
The user chooses a maximum diameter for clusters.
Build a candidate cluster for each point by including the closest point, the next closest, and so on, until the diameter of the cluster surpasses the threshold.
Save the candidate cluster with the most points as the first true cluster, and remove all points in the cluster from further consideration. Must clarify what happens if more than 1 cluster has the maximum number of points ?
Recurse with the reduced set of points.
The distance between a point and a group of points is computed using complete linkage, i.e. as the maximum distance from the point to any member of the group (see the "Agglomerative hierarchical clustering" section about distance between clusters).
Locality-sensitive hashing
Locality-sensitive hashing can be used for clustering. Feature space vectors are sets, and the metric used is the Jaccard distance. The feature space can be considered high-dimensional. The min-wise independent permutations LSH scheme (sometimes MinHash) is then used to put similar items into buckets. With just one set of hashing methods, there are only clusters of very similar elements. By seeding the hash functions several times (eg 20), it is possible to get bigger clusters.
Graph-theoretic methods
Formal concept analysis is a technique for generating clusters of objects and attributes, given a bipartite graph representing the relations between the objects and attributes. Other methods for generating overlapping clusters (a cover rather than a partition) are discussed by Jardine and Sibson (1968) and Cole and Wishart (1970).
Spectral clustering
Given a set of data points A, the similarity matrix may be defined as a matrix S where Sij represents a measure of the similarity between points . Spectral clustering techniques make use of the spectrum of the similarity matrix of the data to perform dimensionality reduction for clustering in fewer dimensions.
One such technique is the Shi-Malik algorithm, commonly used for image segmentation. It partitions points into two sets (S1,S2) based on the eigenvector v corresponding to the second-smallest eigenvalue of the Laplacian matrix
L = I − D − 1 / 2SD − 1 / 2
of S, where D is the diagonal matrix

This partitioning may be done in various ways, such as by taking the median m of the components in v, and placing all points whose component in v is greater than m in S1, and the rest in S2. The algorithm can be used for hierarchical clustering by repeatedly partitioning the subsets in this fashion.
A related algorithm is the Meila-Shi algorith, which takes the eigenvectors corresponding to the k largest eigenvalues of the matrix P = SD − 1 for some k, and then invokes another (e.g. k-means) to cluster points by their respective k components in these eigenvectors.

Agglomerative hierarchical clustering
This method builds the hierarchy from the individual elements by progressively merging clusters. In our example, we have six elements {a} {b} {c} {d} {e} and {f}. The first step is to determine which elements to merge in a cluster. Usually, we want to take the two closest elements, according to the chosen distance.
Optionally, one can also construct a distance matrix at this stage, where the number in the i-th row j-th column is the distance between the i-th and j-th elements. Then, as clustering progresses, rows and columns are merged as the clusters are merged and the distances updated. This is a common way to implement this type of clustering, and has the benefit of caching distances between clusters. A simple agglomerative clustering algorithm is described in the single-linkage clustering page; it can easily be adapted to different types of linkage (see below).
Suppose we have merged the two closest elements b and c, we now have the following clusters {a}, {b, c}, {d}, {e} and {f}, and want to merge them further. To do that, we need to take the distance between {a} and {b c}, and therefore define the distance between two clusters. Usually the distance between two clusters A and B is one of the following:
The maximum distance between elements of each cluster (also called complete linkage clustering):
Max{d(x,y): x € A, y € B}
The minimum distance between elements of each cluster (also called single-linkage clustering):
Min {d (x, y): x € A, y € B}
The mean distance between elements of each cluster (also called average linkage clustering, used e.g. in UPGMA):
The sum of all intra-cluster variance.
The increase in variance for the cluster being merged (Ward's criterion).
The probability that candidate clusters spawn from the same distribution function (V-linkage).
Each agglomeration occurs at a greater distance between clusters than the previous agglomeration, and one can decide to stop clustering either when the clusters are too far apart to be merged (distance criterion) or when there is a sufficiently small number of clusters (number criterion).