Posts

Showing posts from May, 2022

GREEDY METHOD

  UNIT :3 - THE GREEDY METHOD Knapsack Problem, Minimum Cost Spanning Tree, Single Source Shortest Path THE GENERAL METHOD The Greedy Method is a problem-solving approach used in designing algorithms. It works by making a series of choices, each of which is the best choice at the moment, with the hope that these local choices will lead to the global optimal solution.   Key Steps in the Greedy Method: 1. Initialization: Start with an empty or initial solution. 2. Selection: At each step, choose the option that looks best. 3. Feasibility Check: Ensure that the choice is valid and keeps the solution feasible. 4. Repeat: Continue until the problem is solved or all choices are exhausted.   When does the Greedy Method work? The greedy method works if the problem satisfies the Greedy-Choice Property (local optimal choices lead to a global optimum) and Optimal Substructure (optimal solutions to subproblems combine to form an optimal solution to the whole problem).   KNAPSACK...

UNIT – III - Finite Automata - Part 1

Image
UNIT – III - Finite Automata Syllabus: Finite Automata · DFA · NDFA · DFA vs NDFA · NFA to DFA Conversion · Minimization of DFA · Regular Expressions · Pumping Lemma · Myhill–Nerode Theorem   TOPIC 1   Introduction to Finite Automata   A Finite Automaton (FA) is an abstract mathematical machine that recognizes patterns in strings of symbols. It reads the input one symbol at a time and decides whether the string belongs to a particular language. It has a finite number of states and transitions between those states. Example: A machine that checks whether a binary number ends with 1 can be designed as a finite automaton. Important Terminology Term Definition Example State A condition or configuration of the machine q 0 , q 1 Input alphabet (Σ) A finite set of input symbols Σ = {0, 1} String A finite sequence of symbols from Σ ...