Education4U

Design Algorithm & Analysis(DAA)

Lec-01: Introduction to Algorithm

Description

• An Algorithm is a sequence of steps to solve any problem.

• Design and Analysis of algorithms are more important for designing an algorithm to solve different series of problems in the branch of computer science and information technology.

• Basic concepts of Designing Strategies, Complexity analysis of Algorithms, followed by problems on Graph Theory and Sorting methods and Complexity theory.

Prerequisite

• The readers should have a basic or fundamental knowledge of programming and mathematics.

• The readers should know the data structure very well. Moreover, have a basic or fundamental understanding of Formal Language and Automata Theory.

Topics Covered

• Complexity • Notations • Divide & Conquer • BST & Spanning tree

• BFS & DFS • Shortest path & Greedy Methods • Dynamic Programming

• Backtracking

For whom

• For students pursuing a degree in any computer science, engineering, and/or information technology-related field.

Reference books

1. “Introduction to Algorithms (Eastern Economy Edition)” by Thomas H Cormen and Charles E Leiserson

2. “Design and Analysis of Computer Algorithms” by AHO

3. “Fundamentals of Computer Algorithms(second edition)” by Sahni Horowitz

4. “Introduction to the Design and Analysis of Algorithms” by Anany Levitin

Q & A
Exam Questions

Q1 . Define time complexity and space complexity. Write an algorithm for adding n natural numbers and find the space required by that algorithm
Q2 . List the steps to write an Algorithm
Q3 . Illustrate an algorithm for (1) Finding factorial of n number. (2). Sorting the Elements.
Q4 . Evaluate an algorithm for computing GCD (m, n) using Euclid’s algorithm.
Q5 . Design the equality GCD (m, n) = GCD (n, m mod n) for every pair of positive integers m and n.
Q6 . List out the steps that need to design an algorithm.
Q7 . Examine an algorithm to convert a binary number to a decimal number.
Q8 . Identify how you will measure the input size of algorithms.
Q9 . Explain how many algorithms you can write for solving find the prime numbers. Compare which is the simplest and the most efficient.
Q10 . Explain the various types of problems that can be solved using an algorithm.

Total time required for the program to complete its operation. Usually expressed in Big O notation.

The NP-Complete problem is a problem in NP, and it is as difficult as any other problem in this category because any other dispute in NP can be reduced in polynomial time.

Time efficiency is measured by estimating the number of executions of basic algorithm functions.
Space efficiency is measured by calculating the number of additional storage units consumed by the algorithm.

It is the standard document of the algorithm, which has been developed to represent the task, which limits the estimated time of the algorithm.
It is a way to define its efficiency. Usually called O mark.

It is a direct method of solving problems, usually directly based on the statement of the problem and the description of the concepts involved.

Input- Zero or more quantities are externally provided.
Output- At least one quantity is composed
Definiteness
- Each instruction is simple and unambiguous
Finiteness
- If we trace out the instructions of an algorithm, then for all step the algorithm complete after a finite number of steps
Effectiveness
- Every instruction must be elementary.

The name

It is a function of the dynamic programming process used to find the transitive closure of a directed graph.

A greedy technique for optimization problems will always add the currently best option for the current sub-solution.

1.Produces a feasible solution
2. Easy to solve the problem
3 Directly achieves the optimal solution

It is a function to find all pairs of shortest path problems & related to both directed and undirected weighted graphs, but they do not include cycles of negative length.

It is a greedy and efficient technique for finding the minimum spanning tree of a weighted link graph.

It depends on the data structure chosen for the chart.

It solves the single-source shortest path method, which can find the shortest path from a given vertex (source) to another vertex of a weighted graph or directed graph.
It implements the correct solution for graphs with non-negative weights.

It is a binary tree that reduces the weighted path length from root to leaf and includes a set of predefined weights. The basic application of the Hoffman tree is the Hoffman code.

It is an optimal prefix tree variable length coding technique, which assigns bit strings to characters according to the frequency of characters in a given text.

It is one of the essential file compression techniques.
1.It is easy
2.It is flexibility
3.It implements optimal and minimum length encoding

In this encoding, the encoding tree is updated every time a new character is read from the source text.
It is used to overcome the shortcomings of the simplest version.

Using the boundary method to generate depth-first nodes is called backtracking.
The advantage is that it can solve with far fewer than m trials.

Dynamic programming
1. Many numbers of decisions are generated.
2. It gives an optimal solution always
Greedy method
1. Only one sequence of decisions is generated.
2. It does not require to provide an optimal solution always.

The problem is to put n-queens on an n by n chessboard so that no two queens can charge each other in the same row or column or on the same diagonal.

A way of expressing function at the limit or unbounded behavior. Use the domain as the set of natural numbers N = {0, 1, and 2} to describe the symbol such notation facilitates the definition of the worst-case runtime function T (n). It can also be extended to the domain of real numbers.

The basic concept of merge sort divides the list into two smaller sub-lists of relatively equal size. This method is repeated recursively until only one item remains in the sub list. Thereafter, the various sorted child lists are merged to form a sorted parent list. This method will proceed recursively until the original sorted list is reached.

Considering the input problem, we restore a subset that reassures the constraints. Any subset that meets these constraints is called a feasible solution. The feasible solution that maximizes or minimizes a given goal method is called the best solution.

Encryption is the step of converting plain text into a password format called

No Reviews. Be the First Student to Review the course...

Review :

0 | 0 Reviews

Course Feature

Category Computer Science
Course Duration 9.5 Hrs
Language English
Price 59.00
Validity 1 Year
Q & A 25
Exam Questions 10
Full Course PDF View

Wishlist

Add to Cart

Computer Science

Design Algorithm & Analysis(DAA)

Lec-01: Introduction to Algorithm

Course Feature

Share

Data Communication

Distributed Systems

Adhoc & Sensor

Operating Systems(OS)

Useful Links

Download

Computer Science

1.Complexity

2.Notations

3.Divide & Conquer

4.BST & Spanning Trees

5.BFS & DFS

6.Shortest path & Greedy Methods

7.Dynamic Programming

8.Backtracking

Design Algorithm & Analysis(DAA)

Lec-01: Introduction to Algorithm

1.Complexity

2.Notations

3.Divide & Conquer

4.BST & Spanning Trees

5.BFS & DFS

6.Shortest path & Greedy Methods

7.Dynamic Programming

8.Backtracking

Q1 . What is the time complexity of the Algorithm?

Q2 . What is NP-Complete?

Q3 . Differentiate Time Efficiency and Space Efficiency?

Q4 . What is the Order of the Algorithm?

Q5 . What is the Brute Force?

Q6 . What are the various criteria used to improve the effectiveness of the algorithm?

Q7 . What is an Algorithm?

Q8 . What is WARSHALL’S Algorithm?

Q9 . What is a Greedy Algorithm?

Q10 . List the advantage of the greedy algorithm.

Q11 . What is Floyd's algorithm?

Q12 . What is prim's algorithm?

Q13 . How efficient is prim's algorithm?

Q14 . What is Dijkstra's Algorithm?

Q15 . What are the Huffman trees?

Q16 . What do you mean by Huffman code?

Q17 . List the advantage of Huffman's encoding?

Q18 . What is dynamic Huffman coding?

Q19 . What is backtracking?

Q20 . Write the difference between Dynamic programming and the Greedy method.

Q21 . What is meant by the n-queen Problem?

Q22 . What is Asymptotic Notation?

Q23 . Explain the algorithms for Merge sort and give a suitable example.

Q24 . What do you mean by the optimal solution?

Q25 . Explain how the encryption algorithm works?

Course Feature

Share

Related Courses

Data Communication

Distributed Systems

Adhoc & Sensor

Operating Systems(OS)

Useful Links

Download