Deepa PhD CS

  ANALYSIS & DESIGN OF ALGORITHMS (2 3PCSC01) Unit-wise Multiple Choice Questions(MCQ) https://deepanotes.blogspot.com/2022/05/c-program-binary-tree-traversal.html   Unit:1 - INTRODUCTION   Introduction: - Algorithm Definition and Specification – Space complexity-Time Complexity [1] Asymptotic Notations - Elementary Data Structure: Stacks and Queues – Binary Tree - Binary Search Tree - Heap – Heapsort- Graph. https://deepanotes.blogspot.com/2024/11/define-algorithm-time-and-space.html   Unit:2 - TRAVERSAL AND SEARCH TECHNIQUES   Basic Traversal And Search Techniques: Techniques for Binary Trees-Techniques for Graphs - Divide and Conquer: - General Method – Binary Search – Merge Sort – Quick Sort. https://deepanotes.blogspot.com/2024/11/divide-and-conquer-technique.html   Unit:3 - GREEDY METHOD   The Greedy Method: - General Method – Knapsack Problem – Minimum Cost Spanning Tree – Single Source Shortest Path.  ...

  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 ...