JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Prerequisites:

• 1. A course on “Computer Programming & Data Structures”.
• 2. A course on “Advanced Data Structures & Algorithms”.

Course Objectives:

• Introduces the recurrence relations for analyzing the algorithms.
• Introduces the graphs and their traversals.
• Describes major algorithmic techniques (divide-and-conquer, greedy, dynamic programming, Brute Force, Transform and Conquer approaches) and mention problems for which each technique is appropriate.
• Describes how to evaluate and compare different algorithms using worst-case, average-case and best-case analysis.
• Introduces string matching algorithms.
• Introduces linear programming.

Course Outcomes:

• Ability to analyze the performance of algorithms.
• Ability to choose appropriate data structures and algorithm design methods for a specified application.
• Ability to understand how the choice of data structures and the algorithm design methods impact the performance of programs.

UNIT - I

Introduction: Role of Algorithms in computing, Order Notation, Recurrences, Probabilistic Analysis and Randomized Algorithms. Sorting and Order Statistics: Heap sort, Quick sort and Sorting in Linear Time. Advanced Design and Analysis Techniques: Dynamic Programming- Matrix chain Multiplication, Longest common Subsequence and optimal binary Search trees.

UNIT - II

Greedy Algorithms - Huffman Codes, Activity Selection Problem. Amortized Analysis. Graph Algorithms: Topological Sorting, Minimum Spanning trees, Single Source Shortest Paths, Maximum Flow algorithms.

UNIT - III

Sorting Networks: Comparison Networks, Zero-one principle, bitonic Sorting Networks, Merging Network, Sorting Network.

R16 B.TECH CSE.

Matrix Operations- Strassen's Matrix Multiplication, inverting matrices, Solving system of linear Equations

UNIT - IV

String Matching: Naive String Matching, Rabin-Karp algorithm, matching with finite Automata, Knuth- Morris - Pratt algorithm.

UNIT - V

NP-Completeness and Approximation Algorithms: Polynomial time, polynomial time verification, NP-Completeness and reducibility, NP-Complete problems. Approximation Algorithms- Vertex cover Problem, Travelling Sales person problem

TEXT BOOK:

• 1. Introduction to Algorithms,'' T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, Third Edition, PHI.

REFERENCES:

• 1. Fundamentals of Computer Algorithms, Ellis Horowitz, Satraj Sahni and Rajasekharam, Galgotia publications pvt. Ltd.
• 2. Design and Analysis Algorithms - Parag Himanshu Dave, Himanshu Bhalchandra Dave Publisher: Pearson
• 3. Algorithm Design: Foundations, Analysis and Internet examples, M.T. Goodrich and R. Tomassia, John Wiley and sons.
• 4. Data structures and Algorithm Analysis in C++, Allen Weiss, Second edition, Pearson education. R16 B.TECH CSE. WEB SERVICES AND SERVICE ORIENTED ARCHITECTURE (PROFESSIONAL ELECTIVE – VI) B.Tech. IV Year II Sem. L T P C Course Code: CS862PE 3 0 0 3

Course Objectives:

• To Understand Web Services and implementation model for SOA
• To Understand the SOA, its Principles and Benefits
• To Understand XML concepts
• To Understand paradigms needed for testing Web Services
• To explore different Test Strategies for SOA-based applications
• To implement functional testing, compliance testing and load testing of Web Services
• To Identify bug-finding ideas in testing Web Services

UNIT - I

Evolution and Emergence of Web Services - Evolution of distributed computing, Core distributed computing technologies – client/server, CORBA, JAVA RMI, Microsoft DCOM, MOM, Challenges in Distributed Computing, role of J2EE and XML in distributed computing, emergence of Web Services and Service Oriented Architecture (SOA). Introduction to Web Services – The definition of web services, basic operational model of web services, tools and technologies enabling web services, benefits and challenges of using web services.

UNIT - II

Web Services Architecture – Web services Architecture and its characteristics, core building blocks of web services, standards and technologies available for implementing web services, web services communication, basic steps of implementing web services. Describing Web Services – WSDL introduction, nonfunctional service description, WSDL1.1 Vs WSDL 2.0, WSDL document, WSDL elements, WSDL binding, WSDL tools, WSDL port type, limitations of WSDL.

UNIT - III

Brief Over View of XML – XML Document structure, XML namespaces, Defining structure in XML documents, Reuse of XML schemes, Document navigation and transformation. SOAP: Simple Object Access Protocol, Inter-application communication and wire protocols, SOAP as a messaging protocol, Structure of a SOAP message, SOAP envelope, Encoding, Service Oriented Architectures, SOA revisited, Service roles in a SOA, Reliable messaging, The enterprise Service Bus, SOA Development Lifecycle, SOAP HTTP binding, SOAP communication model, Error handling in SOAP.

UNIT - IV

Registering and Discovering Services: The role of service registries, Service discovery, Universal Description, Discovery, and Integration, UDDI Architecture, UDDI Data Model,

R16 B.TECH CSE.

Interfaces, UDDI Implementation, UDDI with WSDL, UDDI specification, Service Addressing and Notification, Referencing and addressing Web Services, Web Services Notification.

UNIT - V

SOA and web services security considerations, Network-level security mechanisms, Application-level security topologies, XML security standards, Semantics and Web Services, The semantic interoperability problem, The role of metadata, Service metadata, Overview of .NET and J2EE, SOA and Web Service Management, Managing Distributed System, Enterprise management Framework, Standard distributed management frameworks, Web service management, Richer schema languages, WS-Metadata Exchange.

TEXT BOOKS:

• 1. Web Services & SOA Principles and Technology, Second Edition, Michael P. Papazoglou.
• 2. Developing Java Web Services, R. Nagappan, R. Skoczylas, R.P. Sriganesh, Wiley India.
• 3. Developing Enterprise Web Services, S. Chatterjee, J. Webber, Pearson Education.

REFERENCE BOOKS:

• 1. XML, Web Services, and the Data Revolution, F.P. Coyle, Pearson Education.
• 2. Building web Services with Java, 2nd Edition, S. Graham and others, Pearson Education.
• 3. Java Web Services, D.A. Chappell & T. Jewell, O’Reilly, SPD.
• 4. McGovern, et al., “Java web Services Architecture”, Morgan Kaufmann Publishers, 2005.
• 5. J2EE Web Services, Richard Monson-Haefel, Pearson Education. R16 B.TECH CSE.