## Data Structures Thane-Free PDF

• Date:25 Sep 2020
• Views:4
• Pages:223
• Size:5.30 MB

Share Pdf : Data Structures Thane

Report CopyRight/DMCA Form For : Data Structures Thane

Transcription:

STRUCTURE OF THE COURSE CONTENT,BLOCK 1 PROBLEM SOLVING. Unit 1 Top down Design Implementation,Unit 2 Verification Efficiency. Unit 3 Analysis,Unit 4 Sample Algorithm,BLOCK 2 LISTS STACKS AND QUEUES. Unit 1 Abstract Data Type ADT,Unit 2 List ADT,Unit 3 Stack ADT. Unit 4 Queue ADT,BLOCK 3 TREES,Unit 1 Binary Trees.
Unit 2 AVL Trees,Unit 3 Tree Traversals and Hashing. Unit 4 Simple implementations of Tree,BLOCK 4 SORTING. Unit 1 Insertion Sort,Unit 2 Shell sort and Heap sort. Unit 3 Merge sort and Quick sort,Unit 4 External Sort. BLOCK 5 GRAPHS,Unit 1 Topological Sort,Unit 2 Path Algorithms.
Unit 3 Prim s Algorithm,Unit 4 Undirected Graphs Bi connectivity. 1 R G Dromey How to Solve it by Computer Chaps 1 2 Prentice Hall of. India 2002, 2 M A Weiss Data Structures and Algorithm Analysis in C 2nd ed Pearson. Education Asia 2002, 3 Y Langsam M J Augenstein and A M Tenenbaum Data Structures using. C Pearson Education Asia 2004, 4 Richard F Gilberg Behrouz A Forouzan Data Structures A Pseudocode. Approach with C Thomson Brooks COLE 1998, 5 Aho J E Hopcroft and J D Ullman Data Structures and Algorithms.
Pearson education Asia 1983,BLOCK I PROBLEM SOLVING. Computer problem solving can be summed up in one word it is demanding It is an intricate. process requiring much thought careful planning logical precision persistence and attention. to detail At the same time it can be challenging exciting and satisfying experience with. considerable room for personal creativity and expression It computer problem solving is. approached in this spirit then the chances of success are greatly amplified In the discussion. which follows in this introductory chapter we will attempt to lay the foundations for our. study of computer problem solving,This block consists of the following units. Unit 1 Top down Design Implementation,Unit 2 Verification Efficiency. Unit 3 Analysis,Unit 4 Sample Algorithm,TOP DOWN DESIGN IMPLEMENTATION. 1 0 Aims and objectives,1 1 Introduction,1 2 Top Down Design.
1 3 Advantages of Adopting a Top Down design,1 4 Implementation of Algorithms. 1 5 Let Us Sum Up,1 6 Keywords,1 7 Questions for Discussion. 1 8 Suggestion for Books Reading,1 0 AIMS AND OBJECTIVES. At the end of this lesson students should be able to demonstrate appropriate skills and show. an understanding of the following,Aims and objectives of Top down design. Introduction,Top down Design,Implementation,Advantages of this methodology.
1 3 INTRODUCTION, The primary goal in computer problem solving is an algorithm which is capable of being. implemented as a correct and efficient computer program In our discussion leading up to the. consideration of algorithm design we have been mostly concerned with the very broad. aspects of problem solving, We now need consider those aspects of problem solving We now need to consider those. aspects of problem solving and algorithm design which are closer to the algorithm. implementation Once we have defined the problem to be solved and we have at least a vague. idea of how to solve it we can begin to bring to bear powerful techniques for designing. algorithms The key to being able to successfully design algorithms lies in being able to. manage the inherent complexity of most problems that require computer solution People as. problem solvers are only able to focus on and comprehend at one time a very limited span. of logic or instructions A technique for algorithm design that tries to accommodate this. human limitation is known as top down design or stepwise refinement. 1 2 TOP DOWN DESIGN, Top down design is a strategy that we can apply to take the solution of a computer problem. from a vague outline to a precisely defined algorithm and program implementation Top. down design provides us with a way of handling the inherent logical complexity and detail. frequently encountered in computer algorithms It allows us to build our solutions to a. problem in a stepwise fashion In this way specific and complex details of the. implementation are encountered only at the stage when we have done sufficient ground work. on the overall structure and relationships among the various parts of the problem Solution. method where the problem is broken down into smaller sub problems which in turn are. broken down into smaller sub problems continuing until each sub problem can be solved in. few steps Problem solving technique in which the problem is divided into sub problems the. process is applied to each sub problem, Modules Self contained collection of steps that solve a problem or sub problem. Abstract Step An algorithmic step containing unspecified details. Concrete Step An algorithm step in which all details are specified. 1 2 1 Example,Main Module,Top Abstract,Main Program.
Figure An example of top down design, Process continues for as many levels as it takes to make every step concrete. Bottom Particular, Name of sub problem at one level becomes a module at next lower level. 1 2 2 Breaking a problem into sub problems, Before we can apply top down design to a problem we must first do the problem solving. ground work that gives us at least the broadest of outlines of our solution Sometimes this. might demand a lengthy and creative investigation into the problems while at the other times. the problem description may in itself provide the necessary starting point for top down. design The general outline may consist of single statement or a set of statements Top down. design suggests that we take the general statements that we have about the solution one at a. time and break them down into a set of more precisely defined subtasks These subtasks. should more accurately describe how the final goal is to be reached With each splitting of a. task into subtask it is essential that the way in which the subtasks need to interact with each. other be precisely defined Only in this way is it possible to preserve the overall structure of. the solution to the problem Preservation of the overall structure into the solution to a. problem is important both for making the algorithm comprehensible and also for making it. possible to prove the correctness of the solution The process of repeatedly breaking a task. down into subtasks and then each subtasks into still smaller subtasks must continue until the. eventually end up with subtasks that can be implemented as program statements For most. algorithms we only need to go down to two or three levels although obviously for large. software projects this is not true The larger and more complex the problem the more it will. need to be broken down to be made tractable The process of breaking down the solution to a. problem into subtasks in the manner described results in an implement able set of subtasks. that fit quiet naturally into block structured languages like Pascal and Algol There can. therefore be a smooth and natural interface between the stepwise refined algorithm and the. final program implementation a highly desirable situation for keeping the implementation. task as simple as possible,A General Example,Planning a large party. Figure Sub dividing the party planning, o Create an address list that includes each person s name address telephone number.
and e mail address, o This list should then be printed in alphabetical order. o The names to be included in the list are on scraps of paper and business cards. 1 2 3 Choice of suitable data structure, One of the most important decisions we have to make in formulating computer solutions to. problems is the choice of appropriate data structures. General Outline,Input Conditions Output Requirements. Body of Algorithm,Subtask 1 Subtask 2 Subtask 3,Subtask 1a Subtask 1b Subtask 2a Subtask 2b. Figure Schematic breakdown of a problem into subtasks as employed in top down. All programs operate on data and consequently the way the data is organized can have a. profound effect on every aspect of the final solution In particular an inappropriate choice of. data structure often leads to clumsy inefficient and difficult implementations On the other. hand an appropriate choice usually leads to a simple transparent and efficient. implementation,1 2 4 Construction of loops, In moving from general statements about the implementation towards sub tasks that can be.
realized as computations almost invariable we are led to a series of iterative constructs or. loops and structures that are conditionally executed. These structures together with input output statements computable expressions and. assignments make up the heart of the program implementations. 1 2 5 Establishing initial conditions for loops, To establish the initial conditions for a loop a usually effective strategy is to set the loop. variables to the values that would have to assume in order to solve the smallest problem. associated with the loop,s 0 Solution for n 0,1 2 6 Finding the iterative construct. Once we have the conditions for solving the smallest problem the next step is to try to extend. it to the next smallest problem in this case when i 1 That is we want to build on the. solution to the problem for i 0 to get the solution for i 1. The solution for n 1 is,s a 1 Solution for n 1,1 2 7 Termination of loops. There are a number of ways in which loops can be terminated In general the termination. conditions are dictated by the nature of the problem The simplest conditions for terminating. a loop occur when it is known in advance how much iteration need to be made In these. circumstances we can use directly the termination facilities built into programming. languages For example in Pascal the for loop can be used for such computations. For i 1to n do, this loop terminates unconditionally after n iterations. 1 3 THE ADVANTAGES OF ADOPTING A TOP DOWN DESIGN METHODOLOGY. Breaking the problem into parts helps us to clarify what needs to be done. At each step of refinement the new parts become less complicated and therefore. easier to figure out,Parts of the solution may turn out to be reusable.
Breaking the problem into parts allows more than one person to work on the solution. The possibility to perform system architectural exploration and a better overall system. optimization e g finding an architecture that consumes less power at a high level. before starting detailed circuit implementations, The elimination of problems that often cause overall design iterations like the. anticipation of problems related to interfacing different blocks. The possibility to do early test development in parallel to the actual block design etc. The ultimate advantage of top down design therefore is to catch problems early in the. design flow and as a result have a higher chance of first time success with fewer or no. overall design iterations hence shortening design time while at the same time. obtaining a better overall system design, The methodology however does not come for free and requires some investment from. the design team especially in terms of high level modeling and setting up a sufficient. model library for the targeted application domain Even then there remains the risk. that also at higher levels in the design hierarchy low level details e g matching. limitations circuit no idealities layout effects may be important to determine the. feasibility or optimality of an analog solution The high level models used therefore. must include such effects to the extent possible but it remains difficult in practice to. anticipate or model everything accurately at higher levels Besides the models. efficient simulation methods are also needed at the architectural level in order to. allow efficient interactive explorations,An Example of Top Down Design. We own a home improvement company,We do painting roofing and basement waterproofing. A section of town has recently flooded zip code 21222. We want to send out pamphlets to our customers in that area. 1 4 IMPLEMENTATION OF ALGORITMS, The implementation of an algorithm that has been properly designed in a top down fashion.
should be an almost mechanical process There are however a number of points that should. be remembered If an algorithm has been properly designed the path of execution should flow. in a straight line from top to bottom It is important that the program implementation adheres. to this top to bottom rule Programs and subprograms implemented in this way are usually. much easier to understand and debug They are also usually much easier to modify should the. need arise because the relationships between the various parts of the program are much more. Implementation phase, 1 Write code translate the algorithm into a programming language. 2 Test have the computer follow the steps execute the program. 3 Debug check the results and make corrections until the answers are correct. 4 Use the program,Use of Procedures to emphasize modularity. To assist with both the development of the implementation and the readability of the main. program it is usually helpful to modularize the program along the lines that follow naturally. from the top down design This practice allows as implementing the set of independent. procedures to perform specific and well defined tasks. For example if as part of an algorithm it is required to sort an array then a specific. independent procedure should be used for the sort In applying modularization in an. DATA STRUCTURES BCA I SEMESTER SUBJECT CODE BCA 04 SUBJECT TITLE DATA STRUCTURES 2 STRUCTURE OF THE COURSE CONTENT BLOCK 1 PROBLEM SOLVING Unit 1 Top down Design Implementation Unit 2 Verification Efficiency Unit 3 Analysis Unit 4 Sample Algorithm BLOCK 2 LISTS STACKS AND QUEUES Unit 1 Abstract Data Type ADT Unit 2 List ADT Unit 3 Stack ADT Unit 4 Queue ADT BLOCK 3 TREES