DSA REVIEWER.docx

**CP1: STAGES OF ADT** **Data** - Information collected to convey knowledge about a world or environment. **Abstract Data Types (ADT)** - A model or structure representing a type of data. - The data's attributes (e.g., size, values). - The functions that can be performed on the dat...

**CP1: STAGES OF ADT** **Data** - Information collected to convey knowledge about a world or environment. **Abstract Data Types (ADT)** - A model or structure representing a type of data. - The data's attributes (e.g., size, values). - The functions that can be performed on the data (e.g., add, remove, update). - ADTs can be implemented in many programming languages, commonly as ***classes***. **Stages of Abstract Data Types (ADT)** **1. Specification** - Define the components, properties, and relationships of the data. - Identify operations for the data *(what the data can do).* **2. Representation** - Plan how to store instances of the ADT. *(Data Structure)* **3. Implementation** - Define how each operation will be performed with the data. *(Algorithm)* **Modeling Data:** - **Static ADTs**: Rarely change or remain constant. - **Dynamic ADTs**: Frequently change. **Examples**: - **Stacks**: Follow Last-In-First-Out (LIFO). - **Queues**: Follow First-In-First-Out (FIFO). - **Trees**: Organize data hierarchically. - **Graphs**: Represent connections between nodes. **Data Structures** - Purpose: - Define relationships between data and support ADT operations. **Types of Data Structures:** - **Simple Data Structures (Primitive Data Types):** - Integer - Float - Boolean - Character **Composite Data Types** - **Arrays** - Store data of the same type in contiguous memory cells. - Allow *direct access* to each element by its index. - **Linked Lists** - Ordered collection of data where each element, or *node*, links to the next. - **Strings** - Sequence of characters with a specific *length*. - Used to store text data. - **Structs** - Group multiple data types into a single structure. - Allow the creation of *instances* that represent specific entities. - **Classes**: - Define both data (attributes) and operations (methods) as a unified type. - Instances of classes are called *objects*, which encapsulate both *state* and *behavior*. **Algorithms** - A sequence of finite instructions that define how to solve a specific problem. - Often initially written in **pseudocode**. - Data structures, together with algorithms, form programs. - Functions return values after processing. - Subroutines perform tasks with results as side effects. - **Components** - Input Values - Output Values - Problem Solved **Properties:** - **Finiteness**: Completes after a limited number of steps. - **Absence of Ambiguity**: Steps are clear and understandable. - **Sequence Definition**: Steps are in a logical order. - **Input/Output Definition**: Both input data and desired output are specified. - **Scope Definition**: Focus is on the specified problem area. - **Effectiveness**: Executes each step reliably within a finite time. - **Efficiency**: Optimizes resources like time and memory. **\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\--** **CP2: THE BASICS OF OOP** **Object-Oriented Programming (OOP)** - Models real-world characteristics and behaviors, allowing for the design of applications and software through a more intuitive structure. **Objects:** - basic entity of object-oriented programming language. - Represent entities with distinct characteristics (attributes) and behaviors (methods). **Classes:** - Serve as blueprints for creating objects. - An *instance* of a class is formed by specific objects based on that class\'s blueprint. **BASIC FEATURES OF OOP** - **Abstraction** - process of hiding complexities and presenting only the essential details of a system to the user. - **Encapsulation:** - binding of data and methods within a class, restricting access to protect the object\'s state. Abstraction solves the problem in the design side while, Encapsulation is the implementation. - **Inheritance:** - One class (child or subclass) acquires the properties (data members) and methods (functionalities) of another class (parent or superclass). - Once a method is defined in the parent class, it is automatically available to all child classes. - **Polymorphism:** - The ability of an operation to exhibit different behaviors based on the data passed to it. - *\"many forms.\"* - Purpose: Allows the same method to be implemented in various ways depending on the object type. **CREATING AN OBJECT** An object is created from a class using the \`new\` keyword in Java. *Steps to Create an Object:* - **Declaration**: Declare a variable with the object type. - **Instantiation**: Use the \`new\` keyword to create the object. - **Initialization**: Call a constructor to initialize the new object.  **Constructors:** - Initialize class instances, sharing the class name; a default one is provided if not defined. **Methods:** - Collections of code designed to perform specific tasks, written once but reusable multiple times during program execution. *Types of Methods* - **Predefined Methods**: Available in the standard library for immediate use (e.g., \`sqrt()\`, \`print()\`). - **User-Defined Methods**: Created by developers to perform specific tasks. **Making Method Call** - **Invocation:** - The program temporarily exits the current method to execute the called method, returning afterward. - **Passing Arguments:** - The calling method provides arguments (values from variables/constants) to the called method. - **Parameter Agreement**: - The number and type of arguments must match the parameters in the called method. **CLASSES IN JAVA** **Local Variables:** - Defined inside methods, constructors, or blocks. - Declared and initialized within the method. **Instance Variables:** - Declared within a class but outside any method. - Accessible from any method, constructor, or block within the class. **Class Variables:** - Declared within a class using the \`static\` keyword. - Shared across all instances of the class. **\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\--** **CP3: RECURSIVE ALGORITHM** "Recursion is a way of solving a big problem using the solution in its subproblems leading to a simpler and elegant solution." **Iterative Algorithm:** - An algorithm that repeatedly executes a block of code through loops until a specified condition is met. - Each cycle of the loop\'s execution is referred to as an iteration. **Recursive Algorithm:** - An algorithm is considered recursive if it involves a procedure that calls itself at least once. - **Recursive Call:** - The invocation of the \`recurse()\` method within itself. - **Stopping Condition:** - *A condition* that must be defined within the method to terminate recursive calls and prevent infinite loops. - ***A recursive method*** breaks down a task into smaller subtasks to solve the problem more efficiently. **Key Components of Recursion:** - **Base Case:** - The simplest version of the problem, which provides a straightforward solution. - **Recursive Step:** - uses smaller instances of the same problem to build toward the solution. **COMPUTING A PROBLEM** - Given a non-negative integer *n*, the factorial of *n* (denoted as *n*!) is the product of all positive integers less than or equal to *n*.  **Iterative Solution** Let n = 5 5! = 5 \* 4 \* 3 \* 2 \* 1 = 120 **Recursive Solution**  **Solutions to the Given Problem**  **\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\--** **CP4.1: LEARNING ARRAY DATA STRUCTURES PT. 1** **Arrays** - widely used data structure. - can hold multiple values of the same type under a single name. - Fixed Length: Arrays have a fixed length, meaning the size cannot be changed once defined. - Syntax: Arrays are declared using square brackets\[\]. **ARRAY DECLARATION**  **ARRAY INITIALIZATION** ***Subscript: 0,1,2,3,4... (starts at 0)*** ***Element: 1,2,3,4... (starts at 1)*** **Example:** **num at \[4\] = 75 subscript of 5^th^ element = \[4\]** **subscript of 63 = \[9\] what is the 6^th^ element = 80** **DIMENSIONS OF ARRAYS IN JAVA** **1D Array** - A single-dimensional array can be treated as either a row or a column. - It uses only one subscript for indexing. - Syntax: int x\[\] = new int\[10\]; - Example: String name\[\] = {\"Sam\", \"Manuel\", \"Jaimie\"}; **2D Array**  **what is \[1\]\[3\] = 9** **what is subscript of 15 = \[2\]\[4\]** **1D ARRAY REPRESENTATION**  **2D ARRAY REPRESENTATION** - **[ROW MAJOR REPRESENTATION]** ***FORMULA:* Start + k (\[(i-1)n\] + \[j-1\])**  ***Given the 3x2 array named M and each element of the array is two words long. Compute for the starting address of element M\[3\]\[2\].*** **m = 3 i = 3** **n = 2 j = 2** **k = 2** - ***COLUMN MAJOR REPRESENTATION*** ***FORMULA:* Start + k (\[(i-1)\] + \[j-1\]m)**  ***Given the 3x2 array named M and each element of the array is two words long. Compute for the starting address of element M\[3\]\[1\].*** **m = 3 i = 3** **n = 2 j = 1** **k = 2** **CP5: LEARNING LINKED LIST DATA STRUCTURE** **LINKED LIST** - An ordered collection of data elements where each element contains a reference (link) to the next element. **NODE** - Each element in a linked list. - Node Structure: - **Data**: Contains the value or information. - **Link**: Points to the next node in the sequence. **HEAD** - A pointer/reference to the first node in the linked list. **LAST NODE** - The last node in the linked list points to - **NULL**, indicating the end of the list. **[SINGLY-LINKED LIST]** - each node contains a pointer that identifies the next element in the list. - Structure: - Each node has *two fields*: - Data: Stores the value. - Next Pointer: Points to the next node in the list. - Characteristics: - Contains only *one link* to a single successor (the next node). - Traversal is typically done in one direction (from head to tail).  **[DOUBLY-LINKED LIST]** - each node has pointers to both its successor (next node) and predecessor (previous node). - Structure: - Each node contains *three fields*: - Data - Next Pointer - Previous Pointer - Characteristics: - Nodes can be navigated both forward and backward. - Allows more flexible traversal compared to singly-linked lists.  **[CIRCULARLY-LINKED LIST]** - all nodes are connected in such a way that the last node points back to the first node, forming a circular chain. - Types: - **Singly Circular Linked List**: Each node points to the next, with the last node linking back to the first. - **Doubly Circular Linked List**: Each node points to both its successor and predecessor, with the last linking to the first and the first linking to the last.