DFDFDD

--------------------------
Post Title 'DAA Assignment-1 Answers'
Post by user 'Adusumilli-Uday-Kumar'
Post encryped with secure 256-bit MD5 Encryption
Post accesable only VIA link
Post will Expire on '3-OCT-2017'
--------------------------



Q1.

Every algorithm needs a process in order to be created and utilized. Described below are the four stages of algorithm analysis and design:

Design....

The first stage is to identify the problem and thoroughly understand it. After you obtain the input, break out the problem into stages. All of this is elementary, but the same basic rules apply.
This is also the point where you are going to use flowcharts and/or use pseudo code to work out the specific problems of solving the flow of operations within the code.

Analysation and Validation....

Once you have the basic framework of the algorithm it’s time to start analyzing how efficient the code is in solving the problem. Professional programmers usually prefer to examine it prior to writing the code and analyze results based on their expectations from the design stage.
Either way, you're basically looking for the efficiency of the algorithm. Algorithms are measured in time and space for their efficiency. Look at the algorithm you’re designing and see how it works with different size data structures and what kind of time it takes to work through those structures.

Implementation....

Writing and coding the algorithm is the next step in the process. Write the code to execute quickly but can also handle the input data that it will receive.

Test ( Profiling and Debugging )....

Once the algorithm is designed and coded, go back and experiment with different variables in the algorithm. Experimentation in algorithmic design is really just another step of the analyzing of the algorithm. When you find flaws in what you have written or ways to write the code better, then go back to the design step and redesign the algorithm.

Circular Process of designing the algorithm....

The design and analysis of algorithms is a circular process. You may find yourself becoming involved in any one of the steps. An experiment on an existing algorithm might lead to a new design. Or a re-coding of an algorithm might lead to a more efficient execution. Wherever you find yourself, keep working towards the goal of efficiency of the algorithm.


Q2.
Bhavya, this is very basic and You're a smart girl. I'm sure You'll be able to write this yourself :)



Q3.
Bhavya, this is very basic and You're a smart girl. I'm sure You'll be able to write this yourself :)



Q4.

Dictionary :-

A dictionary is a set of items with a key attached to each item. Using the key, we can access, insert or delete the item quickly. Dictionary is a  major data structure. Dictionaries differ from lists in that you can access items in a dictionary by a key rather than a position. There are many ways to implement a dictionary. The thing that is most important to notice right now is that the get item and set item operations on a dictionary are O(1). Another important dictionary operation is the contains operation. Checking to see whether a key is in the dictionary or not is also O(1).

ADT :-

An abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.

Stable Algorithm :-

Sorting stability means that records with the same key retain their relative order before and after the sort.
So stability matters if, and only if, the problem you're solving requires retention of that relative order.
If you don't need stability, you can use a fast, memory-sipping algorithm from a library, like heapsort or quicksort, and forget about it.
If you need stability, it's more complicated. Stable algorithms have higher big-O CPU and/or memory usage than unstable algorithms.

First-Child-Next-Sibling Representation of Trees :-

Usually, tree data structures are organised in a way that each node contains pointers to all its children.
In a First-Child-Next-Sibling Representation of Trees that represents a multi-way tree T, each node corresponds to a node in T and has two pointers: one to the node's first child, and one to its next sibling in T. The children of a node thus form a singly-linked list.



Q5.

Some Important Problem Types Include...
• Sorting
Sorting algorithm is an algorithm that puts elements of a list in a certain order. Example - Bubble Sort, Selection Sort, etc.

• Searching
A search algorithm, broadly speaking, is an algorithm for finding an item with specified properties among a collection of items. Example - Binary search, Linear Search, etc.

• String processing
In text editors, we might want to search through a very large document
(say, a million characters) for the occurence of a given string (maybe dozens of characters).

• Graph problems
The set of problems for digraphs and undirected graphs are different. Graphs are made up of vertices and edges. Among classic algorithms/problems on digraphs we can note the following:
• Reachability. Can you get to B from A?
• Shortest path (min-cost path). Find the path from B to A with the minimum cost

Example...  Dijkstra's and Floyd's algorithms

• Combinatorial problems
Task to find a combinatorial object-such as a permutation or a combination.

• Geometric problems
Geometric algorithms deal with geometric objects such as points , lines, and polygons.

• Numerical problems
these involve mathematical objects of continuous nature: solving equations and system of equation, computing definite integrals, evaluating functions and so on.



Q6.

Bhavya, I'll look into this question when I get back to bangalore.



Q7.

Order of growth in algorithm means how the time for computation increases when you increase the input size. It really matters when your input size is very large.

Order of growth provide only a crude description of the behavior of a process. For example, a process requiring n^2 steps and a process requiring 1000n^2 steps and a process requiring 3n^2 10n 17 steps all have O(n^2) order of growth. Order of growth provides a useful indication of how we may expect the behavior of the process to change as we change the size of the problem. Depending on the algorithm, the behaviour changes. So, this is one of the most important things that we have to care when we design an algorithm for some given problem.

There are different notations to measure it and the most important one is Big O notation which gives you the worst case time complexity.



Q8.

Bhavya, I'll look into this question when I get back to bangalore.