Deepa PhD CS

  DEFINE: ALGORITHM An algorithm is a set of well-defined, step-by-step instructions or procedures designed to perform a specific task or solve a particular problem. Characteristics of Algorithms: 1. Finite - An algorithm must complete in a limited number of steps. 2. Well-Defined - Each step should be clear and unambiguous. 3. Effective - Each operation is feasible and can be carried out within a practical timeframe. 4. Input - It should accept zero or more inputs to work with. 5. Output - It should produce at least one output (result). Types of Algorithms: Sorting Algorithms: Organize data in a certain order (e.g., quicksort, mergesort, bubblesort). Search Algorithms: Locate specific data within a structure (e.g., binary search, linear search). Graph Algorithms: Solve problems related to graphs, like finding the shortest path (e.g., Dijkstra’s algorithm, BFS, DFS). Dynamic Programming Algorithms: Solve problems by breaking them down into overlapping sub-problems (e.g., Fibonacci ...

  Dynamic Programming Dynamic Programming (DP) is a technique used to solve problems by breaking them down into smaller, simpler subproblems. It's especially useful for optimization problems where the same subproblems are solved repeatedly. Key Ideas: Overlapping Subproblems : The problem can be divided into smaller subproblems, and the same subproblems are solved multiple times. Optimal Substructure : The solution to the overall problem can be constructed from the solutions to these smaller subproblems. How It Works: Memoization : This is a top-down approach where you solve the problem recursively, but you store (or "memoize") the results of subproblems to avoid recomputing them. Tabulation : This is a bottom-up approach where you solve the problem iteratively, starting with the simplest subproblems and building up to the final solution. In Short: Dynamic programming helps you solve problems efficiently by sol...

  UNIT II - DIVIDE AND CONQUER TECHNIQUE General Method – Binary Search – Merge Sort – Quick Sort.  GENERAL METHOD The divide and conquer technique is a problem-solving approach that works in three main steps: 1.       Divide : Break down a large problem into smaller, simpler sub-problems. 2.       Conquer : Solve each of the sub-problems individually. This can often be done recursively if the sub-problems are still large. 3.     Combine : Combine the solutions of the sub-problems to get the solution to the original, larger problem. This approach is commonly used in algorithms like binary search, merge sort and quick sort, where breaking down a problem makes it easier and faster to solve.   BINARY SEARCH Binary search is an efficient algorithm for finding a target value within a sorted list. Here’s how it works: Start in the Middle : Look at the middle element of the list. Compare : ...

UNIT - V : BACKTRACKING General Method – 8-Queens Problem – Sum Of Subsets – Graph Coloring –  Hamiltonian Cycles General Method Backtracking is a problem-solving technique used in algorithms to find solutions by exploring all possible options. In backtracking, a state-space tree is a tree-like structure that represents all possible states (solutions or non-solutions) of a problem. Backtracking algorithms explore this tree using a depth-first search approach, systematically checking each path until a solution is found or all possibilities have been exhausted.  Here’s how it works, step-by-step: Start with a choice : Make a decision and move forward. Check feasibility : If this choice leads to a solution or partial solution, continue. If not, stop exploring this path. Go back and try a different path : If you reach a dead end, go back to the last point where you made a choice. Try a different path from there. Repeat until you find a solution ...

  Data Structures   1. Which of the following is/are the levels of implementation of data structure? a) abstract level     b) application level      c) implementation level               d) all of the above   2. The best data structure to check whether an arithmetic expression has balanced parentheses a) Queue                                b) Stack                 c) Tree                    d) List   3. Stack data structure is needed to convert a) infix to postfix notation            ...