Demo: Algorithm Classification
Duration: 15 min
This video lesson is available to enrolled students.
Inside: a video lesson and guided study material.
Module outline
- Database Management System: Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Decomposition Properties & 4NF, File Organization & Indexing, Relational Algebra, SQL, Relational Calculus, Transaction Management, Concurrency Control
- Discrete Mathematics: Set Theory, Relations, Functions, Graph Theory, Group Theory, Propositional and Predicate Logic
- Digital Electronics: Digital Systems & Boolean Basics, Logic Gates & Hardware, Boolean Expression, Boolean Minimization, Combinational Circuit, Sequential Circuits, Number System, Number Representation, Registers and Counters, Boolean Algebra and Logic Gates, Microprocessors and Microcontrollers, Logic Families and CMOS Logic, Microprocessors, Logic Gates and Boolean Algebra, Number Systems and Codes, Minimization of Boolean Functions, Timing, Hazards and Testing, Logic Families, Combinational Logic Design, Arithmetic Circuits, Semiconductor Memories and Programmable Logic Devices, Combinational Logic Circuits, Sequential Circuits and State Machines, Latches and Flip-Flops, Finite State Machines, Minimization of Boolean Functions, Arithmetic Circuits, Registers and Counters, Latches and Flip-Flops, Number Systems and Codes
- Computer Architecture: Basics of COA, Floating Point Rep, Cache Memory Organization, Input Output Organisation, Pipelining, Instr Formats & Modes, Control Unit Design, Semiconductor Memories and Programmable Logic, Processor Organization and Instructions, Memory Hierarchy and Input/Output
- Operating System: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Deadlock, Virtual Memory, Disc Scheduling, File Management, Memory Management, Threads & Process Creation
- Computer Networks: Introduction to CN, DLL: Access Control, DLL: Flow Control, DLL: Error Control, DLL: Framing, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Net Layer:Routing Protocol, Transport Layer Services, TL: Congestion & UDP, Application Layer, Network Security, Hardware Basics
- Data Structures: Introduction to DS, Array, Stack, Queue, Linked List, Tree, Graphs, Hashing
- Algorithms: Algorithm Analysis, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Minimum Spanning Trees, Shortest Path Algos, Time Complexity Analysis
- Theory Of Computation: Introduction to TOC, Deterministic FA (DFA), Non-Deterministic FA, Regular Expressions, Grammar, Regular Language Properties, Moore & Mealy Machines, Pushdown Automata & CFG, Turing Machines, Complexity Theory
- Compiler Design: Intro to Compilers, Lexical Analysis, Grammar & CFG, Syntax Analysis: Top-Down, Syntax Analysis: Bottom-Up, Semantic Analysis & SDT, Intermediate Code Gen, Code Optimization
- C language: C Fundamentals, Control Flow, Functions, Arrays & Pointers, Storage Classes, Structures & Enums
- Software Engineering: Fundamentals of Software Engineering, Software Requirements and Quality Assurance, Software Design, Estimation and Metrics, Software Testing, Software Maintenance and Configuration Management
- Emerging Trends & AI: Emerging Tech Trends, Artificial Intelligence, Cloud Computing, Internet of Things
- Computer Graphics: Basics of Computer Graphics, 2-D Geometrical Transforms and Viewing
- Aptitude: Percentage, Ratio and Proportion (Ratios), Logarithm, HCF LCM, Average, Sequence and Series (Series), Number System, Powers and Exponents (Surds and Indices), Algebra, Permutation and Combination, Probability, Profit and Loss, Simple Interest and Compound Interest, Pipe and Cistern, Speed Time and Distance, Mixture and Alligation, Mensuration and Geometry, Mental Ability, Age Problems, Partnership, Statistics, Data Interpretation, Arithmetic, Linear Algebra, Trigonometry, Percentages, Simplification and Approximation, Number System, Ratio and Proportion, Averages, Mixtures and Alligation, Permutations and Combinations, Profit, Loss and Discount, Sequences and Series, Vocabulary, Subject-Verb Agreement, Sentence Completion, Geometry, Reading Comprehension, Powers, Surds and Logarithms, Mathematical Operations, Alphabet and Word Tests, Transformation of Shapes, Signal Space and Optimum Detection, Constraint Puzzles, Mensuration, Patterns in Two-Dimensional Figures, Measurement and Quantity Take-Off, Three-Dimensional Patterns and Visualization, Numerical Reasoning, Sentence Structure and Correction, Critical Reasoning, Syllogisms and Venn Diagrams, Coding and Decoding, Series Completion, Order, Ranking and Sequence, Data Sufficiency, Differential Calculus, Wireless, Satellite and Optical Communication Systems, Complex Analysis, Vector Analysis, Trigonometry, Probability, Statistics, Differential Calculus, Algebra, Time and Work, Speed, Time and Distance, Data Interpretation, Combinatorics
- Reasoning: Non Verbal Reasoning (Spatial Aptitude) (Spatial Reasoning) (Visual Reasoning), Series (Number and Letter Series) (Numerical Relations and Reasoning), Coding Decoding, Data Sufficiency, Syllogisms, Deductive and Inductive Reasoning (Logical Deduction and Induction) (Prepositional Reasoning), Seating Arrangements, Blood Relations, Directions (Direction Test), Analytical Reasoning (Counting Figures Reasoning), Puzzle Solving (Puzzles), Calendar, Clock, Cubes & Dices, Selection Decision Table (Decision Making), Logical Sequence Of Words, Venn Diagram, Data Arrangement, Inequality, Analogy, Ranking, Order and Sequence, TCS NQT Advanced Reasoning Ability, Assembling and Grouping of Shapes, Cubes and Dice, Analogy and Classification, Direction Sense, Algebra, Logical Deduction and Induction, Speed, Time and Distance, Narrative Sequencing, Project Monitoring, Resources and Safety, Traverse Surveying, Time and Work, Clocks and Calendars, Data Interpretation, Blood Relations, Data Sufficiency
- English (Verbal Ability): Vocabulary, Noun, Pronoun, Adjectives, Preposition, Articles, Direct and Indirect Speech, Tenses, Conjunction, Subject Verb Agreement (Verb Noun Agreement), Modals, Sentence Re-arrangements (Para Jumbles) (Narrative Sequencing), Sentence Correction (Error Correction), Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions), Cloze Test (Cloze Passage), Verbal Analogy (Word Based Analogy), Adverb, Verb, Prepositions and Conjunctions, Idioms and Phrases, Verb Forms and Verb Patterns, Sentence Basics, Nouns and Pronouns, Adjectives and Adverbs, Articles and Determiners, Voice and Reported Speech, Modals, Conditionals and Subjunctive, Blood Relations, Tenses, Vocabulary
- Engineering Mathematics: Calculus, Vectors
- GATE Live Class Recordings 2026: GATE 2026 Live Class
AI summary & chapters
AI Summary
An AI-generated summary of this video lecture.
This lecture segment introduces the fundamental classification of algorithms into deterministic and non-deterministic categories. The instructor begins by defining a Deterministic Algorithm as one that always produces the same output for a given input and follows a predictable sequence of steps. This definition is emphasized through underlining key phrases on the slide titled 'Algorithm Classification: - Deterministic vs Non-Deterministic'. To illustrate this concept, the instructor presents a C-style code snippet named `Deterministic_Search(int A[], int n, int key)`. The implementation utilizes a standard linear search loop: `for(int i = 1; i <= n; i++)`, checking if `A[i] == key` to print 'Found' and return, or printing 'Not Found' if the loop completes. The instructor then populates an array A with specific integer values, such as [20, 15, 37, 83, 5, 10], and sets a search key (e.g., 15 or 5) to demonstrate the algorithm's execution. The visual trace shows the loop variable `i` incrementing sequentially from 1 to n, comparing each element against the target key. This step-by-step progression highlights the predictable nature of deterministic algorithms, where every iteration is known in advance. The segment transitions to Non-Deterministic Algorithms, defined as those that may produce different outputs for the same input due to inherent randomness. A new function `NonDeterministic_Search` is introduced, featuring the line `i = random(1, n); // randomly choose any index`. The instructor demonstrates this by simulating two executions on the same array with key=5. In one run, a random index might select 83 (resulting in 'Not Found'), while another run could randomly select the index containing 5 (resulting in 'Found'). This contrast effectively illustrates how non-deterministic algorithms lack the fixed, predictable path of their deterministic counterparts.
Chapters
0:00 – 2:00 00:00-02:00
The video opens with the definition of a Deterministic Algorithm, emphasizing that it 'Always produces the same output for a given input and follows a predictable sequence of steps'. The instructor underlines these key phrases on the slide 'Algorithm Classification: - Deterministic vs Non-Deterministic'. A C-style code snippet `Deterministic_Search(int A[], int n, int key)` is displayed to provide a concrete example. The code shows a linear search loop `for(int i = 1; i <= n; i++)` that iterates through an array. The instructor initializes the array A with values [20, 15, 37, 83, 5, 10] and sets the search key to 15. This setup establishes the baseline for understanding how deterministic algorithms operate systematically.
2:00 – 5:00 02:00-05:00
The instructor traces the execution of the deterministic search algorithm on the array [30, 15, 37, 83, 5, 10] with a search key of 5. The visual notes track the loop condition `i <= n` (where n=6) and the comparison logic. For iteration i=1, A[1]=20 is compared to key 5 (Mismatch). For i=2, A[2]=15 is compared (Mismatch). The trace continues through indices 3 and 4, showing A[3]=37 and A[4]=83 failing the check. The instructor highlights that the algorithm proceeds sequentially, incrementing `i` by 1 each time until the condition is met or the array ends. This detailed walkthrough reinforces the concept of a 'predictable sequence of steps' where every action is determined by the previous state.
5:00 – 10:00 05:00-10:00
The lecture transitions to Non-Deterministic Algorithms, defined on-screen as those that 'May produce different output for the Same input due to inherit randomness'. The instructor introduces a function `NonDeterministic_Search(int A[], int n, int key)` containing the line `i = random(1, n); // randomly choose any index`. Unlike the deterministic version, this algorithm does not iterate sequentially. Instead, it selects a random index immediately. The instructor demonstrates this by simulating an execution where the random selection picks index 4 (value 83), which does not match key=5, resulting in 'Not Found'. This example contrasts sharply with the deterministic trace shown previously.
10:00 – 14:55 10:00-14:55
The instructor completes the non-deterministic demonstration by showing a second execution path where the random index selection picks 5 directly, resulting in 'Found'. This variability for the same input (key=5) underscores the definition of non-determinism. The final segment revisits the Deterministic Algorithm to reinforce the contrast, showing the full loop `for(int i = 1; i <= n; i++)` again. The instructor walks through the iterations until A[5] matches key=5, printing 'Found' and returning. The slide text explicitly contrasts the two approaches: deterministic algorithms follow a fixed path, while non-deterministic ones rely on randomness. The video concludes by summarizing these classifications through the lens of algorithmic predictability and output consistency.
The lecture effectively distinguishes between deterministic and non-deterministic algorithms using linear search as a primary example. The core distinction lies in predictability: deterministic algorithms follow a fixed, sequential path (e.g., `for(int i = 1; i <= n; i++)`), ensuring the same output for identical inputs. In contrast, non-deterministic algorithms introduce randomness (e.g., `i = random(1, n)`), leading to variable outcomes even with the same input data. The instructor uses visual traces of array indices and loop conditions to make these abstract concepts concrete. Key takeaways include the definition of determinism as 'always producing the same output' and the mechanism of non-determinism via random index selection. The use of specific array values like [30, 15, 37, 83, 5, 10] and search keys like 5 allows students to follow the logic step-by-step. This foundational classification is crucial for understanding algorithm behavior in computer science.

