Operating System Overview
54 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the role of an operating system?

An operating system acts as the translator between the user and the computer's hardware, managing essential tasks to enable smooth interaction.

Which of the following are common examples of operating systems? (Select all that apply)

  • ForgeOS
  • Windows (correct)
  • macOS (correct)
  • Android (correct)

    • Early operating systems had graphical user interfaces.

    False

    What are system calls?

    <p>Special instructions that programs use to communicate with the OS and request services.</p> Signup and view all the answers

    A distributed system consists of multiple independent computers, also known as __________.

    <p>nodes</p> Signup and view all the answers

    Which of the following is NOT a challenge faced in distributed systems?

    <p>Efficiency</p> Signup and view all the answers

    What is a Process Control Block (PCB)?

    <p>A data structure that stores information about a process, such as its state, memory location, and instructions completed.</p> Signup and view all the answers

    Threads allow a process to handle multiple tasks concurrently.

    <p>True</p> Signup and view all the answers

    What does the term 'deadlock' refer to?

    <p>A situation where two or more processes are waiting for resources held by each other, causing a standstill.</p> Signup and view all the answers

    Which memory management method divides memory into fixed-size blocks?

    <p>Paging</p> Signup and view all the answers

    What does SQL stand for?

    <p>Structured Query Language</p> Signup and view all the answers

    The ACID properties ensure transactions in a database are reliable.

    <p>True</p> Signup and view all the answers

    In Java, the bytecode is executed by the ________.

    <p>Java Virtual Machine (JVM)</p> Signup and view all the answers

    Match the following programming concepts to their descriptions:

    <p>OOP = Object-Oriented Programming JVM = Java Virtual Machine DDL = Data Definition Language SQL = Structured Query Language</p> Signup and view all the answers

    What is the worst-case time complexity of Quicksort?

    <p>O(n^2)</p> Signup and view all the answers

    What is the key idea behind Merge Sort?

    <p>Divide the list in half recursively and then merge the sorted sub-lists back together.</p> Signup and view all the answers

    Merge Sort is more efficient than Quicksort in worst-case scenarios.

    <p>True</p> Signup and view all the answers

    Which of these statements correctly describes deterministic algorithms?

    <p>They always produce the same output for the same input.</p> Signup and view all the answers

    What does NP-Hard signify in terms of computational problems?

    <p>NP-Hard problems are at least as hard as any problem in NP and likely have no efficient solutions.</p> Signup and view all the answers

    Which of the following is an example of an NP-Hard problem?

    <p>Traveling Salesman Problem</p> Signup and view all the answers

    What is PHP an acronym for?

    <p>Hypertext Preprocessor</p> Signup and view all the answers

    What is a benefit of using PHP?

    <p>Has a vast community for support.</p> Signup and view all the answers

    PHP is a client-side scripting language.

    <p>False</p> Signup and view all the answers

    In PHP, variables are declared using a ______ sign followed by a name.

    <p>$</p> Signup and view all the answers

    What is a drawback of using PHP?

    <p>Improper coding can lead to vulnerabilities.</p> Signup and view all the answers

    Which of the following are techniques for polygon filling?

    <p>All of the above</p> Signup and view all the answers

    What is translation in 2D transformations?

    <p>It moves an object from one location to another.</p> Signup and view all the answers

    The Z-Buffer Algorithm assigns a color value to each pixel.

    <p>False</p> Signup and view all the answers

    The RGB color model combines red, green, and ______ to create a wide range of colors.

    <p>blue</p> Signup and view all the answers

    Which of the following are basic transformations?

    <p>All of the above</p> Signup and view all the answers

    What does the term 'matrix formulation' refer to in transformations?

    <p>It refers to using matrices to represent transformations efficiently.</p> Signup and view all the answers

    What are the types of clipping techniques mentioned?

    <p>All of the above</p> Signup and view all the answers

    What is the primary purpose of the Cohen-Sutherland Line Clipping Algorithm?

    <p>To efficiently clip lines that intersect clip window boundaries.</p> Signup and view all the answers

    Dynamic Programming can be used to solve the Traveling Salesman Problem efficiently for large problems.

    <p>False</p> Signup and view all the answers

    Match the following algorithms with their application:

    <p>Binary Search = Searching for an element in a sorted list Prim's Algorithm = Finding minimum cost spanning trees Dijkstra's Algorithm = Finding shortest paths from a starting point Quicksort = Sorting a list efficiently</p> Signup and view all the answers

    What is the main purpose of animation techniques like tweening in computer graphics?

    <p>To automatically generate intermediate frames between keyframes</p> Signup and view all the answers

    What do data types define?

    <p>The kind of information a variable can hold, such as numbers or text.</p> Signup and view all the answers

    What is a variable?

    <p>A storage location in programming with a specific name and data type.</p> Signup and view all the answers

    Which of the following are types of control statements? (Select all that apply)

    <p>for loops</p> Signup and view all the answers

    Define an array.

    <p>A collection of similar data items accessed using an index.</p> Signup and view all the answers

    What is a class in programming?

    <p>A blueprint defining the properties and functionalities of objects.</p> Signup and view all the answers

    What does the super keyword refer to in Java?

    <p>It refers to the superclass's methods or variables.</p> Signup and view all the answers

    Abstract classes can be directly instantiated.

    <p>False</p> Signup and view all the answers

    What is the purpose of the try...catch block in Java?

    <p>To handle exceptions that may occur during program execution.</p> Signup and view all the answers

    What does multithreading allow in a Java application? (Select all that apply)

    <p>Execution of multiple parts concurrently</p> Signup and view all the answers

    What is the main difference between arrays and linked lists?

    <p>Arrays offer random access; linked lists require traversal.</p> Signup and view all the answers

    What does FIFO stand for in the context of queues?

    <p>First In, First Out.</p> Signup and view all the answers

    Describe a binary search tree (BST).

    <p>A special type of binary tree where each node is greater than all nodes in its left subtree and less than those in its right subtree.</p> Signup and view all the answers

    Which of the following are basic operations of trees? (Select all that apply)

    <p>Searching</p> Signup and view all the answers

    The smallest unit of color on a display screen is called a ______.

    <p>pixel</p> Signup and view all the answers

    What does the term 'resolution' refer to in computer graphics?

    <p>The number of pixels displayed horizontally and vertically.</p> Signup and view all the answers

    Liquid Crystal Display (LCD) technology uses liquid crystals to control light.

    <p>True</p> Signup and view all the answers

    What is the purpose of a video adapter?

    <p>To connect the computer to the display and process graphics data.</p> Signup and view all the answers

    Match the following types of sort algorithms with their characteristics:

    <p>Bubble Sort = Repeatedly compares adjacent elements and swaps them if they are in the wrong order Selection Sort = Finds the smallest element and moves it to the beginning Insertion Sort = Maintains a sorted sub-list and inserts each element at the correct position Binary Search = Divides the search area in half comparing the target to the middle element</p> Signup and view all the answers

    Study Notes

    Operating System Overview

    • An Operating System (OS) acts as a translator between the user and computer hardware, managing tasks behind the scenes.
    • Common examples of OS include Windows, macOS, Android, iOS, and Linux.

    Structure of Operating System

    • The OS can be imagined as a layered cake, with each layer having a specific job:
      • Kernel: The core layer, interacting with hardware and managing resources like memory, processors, and devices.
      • Device Drivers: Act as interpreters, translating commands from the OS into instructions specific to each hardware component.
      • System Utilities: Tools for performing essential tasks like file management, security, and maintenance.
      • User Interface: The graphical environment (desktop or touchscreen) used to interact with the computer.

    Evolution of Operating System

    • Early OSes were simple, text-based interfaces with limited functionality.
    • Over time, they evolved with features like:
      • Graphical User Interfaces (GUIs) for easier interaction.
      • Multitasking, allowing multiple programs to run simultaneously.
      • Increased security to protect user data.
      • Networking and internet capabilities for communication.

    Operating System Functions

    • The OS performs various tasks to keep the computer running smoothly:
      • Resource Management: Allocates and monitors memory, storage space, and processing power for different programs.
      • Process Management: Decides which programs get to run and for how long, ensuring efficient resource utilization.
      • File Management: Creates, organizes, stores, and retrieves files on storage devices.
      • Device Management: Controls how hardware components function (printers, keyboards, etc.).
      • Security: Protects the system from unauthorized access and harmful software.
      • User Interface: Provides the environment for users to interact with the computer and applications.

    System Calls

    • Programs use system calls to communicate with the OS and request services.
    • Imagine system calls as ways for programs to "ask permission" to do things on the computer, like accessing a file or displaying something on the screen.

    Distributed Systems

    • A distributed system consists of multiple independent computers (nodes) that communicate and cooperate to appear as a single, unified system to the user.
    • Trends in distributed systems include:
      • Cloud computing: Accessing computing resources (storage, processing power) over the internet.
      • Service-oriented architecture (SOA): Building applications by combining services from various distributed components.
      • Big data processing: Managing and analyzing massive amounts of data across multiple machines.

    Challenges in Distributed Systems

    • Complexity: Managing many interconnected computers requires careful design and coordination.
    • Reliability: Ensuring continued service even if some nodes fail.
    • Security: Protecting data and resources from unauthorized access across a network.

    Process Management

    • A process is like a running program on a computer, with instructions and data to complete a task.
    • Multiple processes can run at once, like cooking multiple dishes simultaneously.
    • Process state includes:
      • Running: Currently being executed by the CPU.
      • Waiting: Waiting for resources (like an oven).
      • Ready: Ready to run again.

    Process Control Block (PCB)

    • A PCB stores information about a process, including its state, memory location, and instructions completed.

    Threads

    • Threads are smaller pieces within a process, like sub-recipes for preparing ingredients.
    • Threads help a process handle multiple tasks concurrently.

    Process Scheduling

    • The OS decides which process gets the CPU's attention next, using scheduling algorithms like FIFO or SJF.

    Process Coordination

    • When multiple processes share resources, coordination ensures processes access them one at a time to avoid conflicts.
    • The critical section problem occurs when two or more processes need exclusive access to a shared resource.
    • Semaphores allow only one process to access a resource at a time, like a flag at a one-lane bridge.

    Inter-process Communication (IPC)

    • Processes need to talk to each other sometimes, like when one process finishes a task and another needs the result.
    • IPC allows processes to exchange information.

    Deadlock

    • Deadlock occurs when processes are waiting for resources held by each other, creating a standstill.
    • Conditions for deadlock include:
      • Mutual exclusion: Processes must have exclusive access to a resource.
      • Hold and wait: A process holds a resource and waits for another.
      • No preemption: A resource cannot be taken away from a process.
      • Circular wait: Processes form a circle, waiting for resources held by each other.
    • Strategies to deal with deadlocks include prevention, avoidance, detection, and recovery.

    Memory Management

    • RAM (Random Access Memory) is volatile memory that stores data and instructions for the CPU to access quickly.
    • ROM (Read-Only Memory) is non-volatile memory that stores permanent data (like the computer's startup instructions).
    • Secondary Storage (Hard Disk, SSD) holds larger amounts of data than RAM but is slower to access.
    • Address binding involves associating a logical address used in a program with a physical address in memory.

    Paging

    • Paging divides both logical and physical memory into fixed-size blocks called pages.
    • A page table translates logical addresses to physical addresses, enabling non-contiguous allocation.

    Segmentation

    • Segmentation divides logical memory into variable-sized segments based on logical units (code, data, stack).
    • Segmentation provides better memory protection and sharing than paging.

    Virtual Memory

    • Virtual memory creates the illusion of having more memory than physically available.
    • Demand paging loads required pages from secondary storage into RAM when needed by the program.

    Page Replacement

    • When the required page isn't in RAM and no free frames are available, an existing page needs to be evicted to make space.
    • Page replacement algorithms determine which page to evict.

    I/O Management

    • I/O devices enable communication between the computer and storage devices.
    • I/O management involves allocating and managing I/O devices for efficient data transfer.

    Storage Management

    • Storage management involves organizing and managing data on a storage device for efficiency and reliability.
    • Allocation methods decide how disk space is assigned to files when they are created.
    • Recovery techniques restore data in case of system crashes or disk failures.

    File Systems

    • A file system is a method of organizing files on a storage device.
    • File systems provide features like access control, file naming conventions, and directory structures.

    Database Management System (DBMS)

    • A DBMS is software that manages the database, providing features like data definition, data manipulation, and data querying.
    • Database design involves planning the structure of the database to optimize storage, retrieval, and maintain data integrity.

    Data Models

    • Data models are blueprints for organizing data within a database.
    • Common data models include:
      • Hierarchical
      • Network
      • Entity-Relationship (ER)
      • Object-Oriented
      • Relational### Entity-Relational Model (ER Model)
    • A way to conceptualize a database using entities, attributes, and relationships
    • Helps visualize the data structure before diving into the specifics of a relational database
    • Complex attributes: can hold multiple values for a single entity, usually broken down into separate entities or tables
    • Mapping cardinalities: describes the number of occurrences of one entity related to another in a relationship (e.g., one customer can place many orders)
    • Primary key: a unique identifier for each record in a table (like a social security number for a customer)
    • Removing redundant attributes: eliminates duplicated data by creating relationships between tables instead of storing the same information in multiple places
    • ER diagram to relational schema: transforming the ER diagram into tables with columns (attributes) and rows (records) based on the entities and relationships defined

    ER Diagram Design Issues

    • Identifying all relevant entities
    • Defining proper relationships and cardinalities
    • Avoiding data redundancy

    Relational Database Design

    • Features of good relational design:
      • Minimizes redundancy: reduces data duplication for efficiency and accuracy
      • Maximizes data integrity: ensures data consistency and reduces errors
      • Optimizes data retrieval: allows efficient querying and accessing specific information
    • Decomposition using functional dependencies: breaking down a table into smaller tables based on relationships between attributes to eliminate redundancy
    • Normal forms:
      • 1NF (First Normal Form): each attribute should have a single atomic value (no repeating groups)
      • 2NF (Second Normal Form): meets 1NF and all non-key attributes are fully dependent on the primary key
      • 3NF (Third Normal Form): meets 2NF and no non-key attribute is dependent on another non-key attribute
      • BCNF (Boyce-Codd Normal Form): meets 3NF and there are no determinant dependencies (a stricter version of 3NF)
      • 4NF (Fourth Normal Form): meets BCNF and eliminates multi-valued dependencies (less common)

    SQL

    • SQL (Structured Query Language): a special language used to talk to a database
    • SQL Data Definition (DDL): creates and modifies the structure of a database
      • Create databases and tables: defining the structure with columns (fields) to hold specific data types
      • Alter tables: modifying existing tables by adding, removing, or changing columns
      • Drop tables/databases: removing tables or entire databases when no longer needed
    • Basic structure of SQL queries:
      • SELECT: specifies what data to retrieve
      • FROM: tells the database which table(s) to look in
      • WHERE (optional): filters data based on specific conditions
      • ORDER BY (optional): sorts the retrieved data in a particular order
    • Additional basic operations:
      • INSERT: adding new data records to a table
      • UPDATE: modifying existing data in a table
      • DELETE: removing data records from a table
    • Set operations:
      • UNION: combines rows from two or more tables without duplicates
      • INTERSECT: finds rows that exist in both specified tables
      • EXCEPT: finds rows present in one table but not the other
    • Null values: represent missing or unknown data in a database field
    • Aggregate functions: perform calculations on entire sets of data
      • COUNT: counts the number of rows in a table or specific criteria
      • SUM: calculates the total of a numeric column
      • AVG: calculates the average of a numeric column
      • MIN/MAX: finds the minimum or maximum value in a column
    • Nested subqueries: use the result of one query as a condition in another
    • Modification of the database:
      • Data Manipulation Language (DML): statements like INSERT, UPDATE, and DELETE to modify data content
      • Data Control Language (DCL): statements to control access and permissions for users interacting with the database

    Intermediate SQL

    • Join expressions: combining data from multiple tables based on related columns
    • Views: creating virtual tables based on existing tables, offering different perspectives on the data
    • Integrity constraints: defining rules to ensure data accuracy and consistency (e.g., primary keys, foreign keys)
    • Authorization: setting permissions for users to control who can access and modify data

    Transactions in Databases

    • Transaction concept: a sequence of database operations treated as a single unit
    • Simple transaction model:
      • Start: the transaction begins
      • Read/Write: the transaction reads or writes data from the database
      • Commit: if everything goes well, the changes are permanently saved
      • Rollback: if something goes wrong, all changes are undone, leaving the database as it was before the transaction
    • ACID properties:
      • Atomicity: all or nothing, as mentioned above
      • Consistency: the database must move from one valid state to another
      • Isolation: concurrent transactions shouldn't interfere with each other's data
      • Durability: committed changes must persist even in case of system crashes
    • Serializability: ensures that concurrent transactions occur as if they were executed one after another
    • Concurrency control: manages concurrent transactions to avoid conflicts
      • Lock-based protocol: transactions "lock" the data they need to access, preventing others from modifying it until the lock is released
      • Timestamp-based protocols: transactions are assigned timestamps, and conflicts are resolved based on timestamps
      • Validation-based protocols: transactions are validated after execution to ensure they didn't violate any rules
    • Basic security issues:
      • Need for security: protecting data from unauthorized access, modification, or deletion
      • Physical & logical security: physical measures like access control and logical measures like user authentication and permissions
      • Design & maintenance issues: ensuring the database system itself is secure and kept up-to-date with security patches
      • Operating system issues: the operating system where the database runs also needs to be secure

    Java

    • Java: a powerful and popular programming language known for its simplicity and "write once, run anywhere" philosophy
    • Object-Oriented Programming (OOP) concepts:
      • Inheritance: creating new classes (subclasses) based on existing ones (superclasses)
      • Polymorphism: objects of different classes responding to the same method call
      • Abstraction: hiding implementation details and showing only essential features
      • Encapsulation: bundling data and methods that operate on that data into a single unit
    • Features of Java:
      • Object-oriented
      • Platform-independent
      • Secure
      • Robust
      • Simple
    • Java architecture:
      • Java source code
      • Java compiler
      • Java bytecode
      • Java Virtual Machine (JVM)

    Java OOP Concepts

    • Inheritance:
      • Subclasses inherit properties and behaviors from superclasses
      • Method overriding: subclasses redefine inherited methods to provide their own implementation
      • Super keyword: used in subclasses to refer to the superclass's methods or variables
      • Final keyword: a class or method declared as final cannot be inherited or overridden
    • Abstract classes:
      • Blueprints for objects that cannot be directly instantiated
      • Define the overall structure but leave some functionalities incomplete
    • Packages & interfaces:
      • Packages: organize related classes and interfaces into logical groups for better code management and to avoid naming conflicts
      • Import statement: allows using classes and interfaces from other packages in your code
      • Access modifiers: control the visibility of classes, methods, and variables within a package or throughout the project
    • IO packages:
      • Provide classes to interact with external sources like files, keyboards, and networks
      • Java Input Stream Classes: used to read data from various sources
      • Java Output Stream Classes: used to write data to various destinations

    Java Exception Handling & Multithreading

    • Exceptions:
      • Represent errors or abnormal conditions that occur during program execution
      • Can be caught and handled using try-catch blocks
    • Exception handling techniques:
      • try...catch block: includes code that might throw an exception and code to handle the exception
      • finally block: always executed, regardless of whether an exception is thrown or not
    • Creating your own exceptions: allows for custom exception handling and improves code readability and maintainability
    • Multithreading:
      • Creation of new threads: using the Thread class and its start() method
      • State of a thread: new, runnable, waiting, blocked, or terminated
      • Multitasking: allows multiple threads to run seemingly at once, improving responsiveness and performance
    • Thread communication: threads can communicate using techniques like wait/notify and locks
    • Thread priorities: can be assigned to influence which thread gets CPU resources first

    Java Applet vs. Applications & Beyond

    • Applets:
      • Small Java programs embedded within web pages, bringing some interactivity
      • Applet class: all applets inherit from the java.applet.Applet class
      • Applet structure: defined by methods like init(), start(), stop(), and paint() that handle initialization, starting, stopping, and drawing on the applet's window
    • Standalone GUI applications with AWT/Swing components:
      • AWT (Abstract Window Toolkit): the original GUI toolkit in Java, offering basic components like buttons, text fields, and windows
      • Swing: a more advanced GUI toolkit built on top of AWT, providing a richer set of components and a more modern look and feel
    • Event handling:
      • Event delegation model: separates event sources (components like buttons) from event listeners (code that reacts to events like clicks)
      • Events & listeners/adapters: different events have corresponding listener interfaces (e.g., MouseListener for### Data Structures
    • Linear Data Structures: Elements have a clear predecessor and successor, like a bookshelf. (e.g., Arrays, Linked Lists, Queues, Stacks)
    • Non-Linear Data Structures: Elements have a more complex relationship, not necessarily in a sequence. (e.g., Trees, Graphs)
    • Data Structure Operations:
      • Insertion: Adding new elements to the data structure.
      • Deletion: Removing elements from the data structure.
      • Searching: Finding specific elements within the data structure.
      • Traversal: Visiting each element in the data structure (usually in linear structures).
    • Time-Space Complexity of Algorithms:
      • Time Complexity: Measures how long an algorithm takes to execute (often expressed as Big O notation).
      • Space Complexity: Measures the amount of memory an algorithm uses (often also expressed as Big O notation).

    Arrays

    • Linear Array: A fixed-size collection of elements of the same data type, stored in contiguous memory locations (like a row of boxes on a shelf).
    • Memory Representation: Elements are stored sequentially in memory, accessed using an index (like a box number).
    • Insertion & Deletion: Can be inefficient, especially in the middle of the array, as elements might need to be shifted (like moving boxes on a shelf).
    • Multidimensional Arrays: Represent tables or grids, like a spreadsheet. (e.g., a 2D array for a chessboard).
    • Sparse Matrices: Matrices where most elements are zero. Special techniques are used to store only non-zero elements efficiently.

    Linked Lists

    • Definition: A collection of nodes, where each node contains data and a reference (pointer) to the next node in the list.
    • Memory Representation: Nodes can be scattered in memory, linked by references.
    • Single Linked List:
      • Elements can only be traversed in one direction (forward), like a one-way train track.
      • Operations:
        • Traversing: Starting from the head node and following references to visit each node.
        • Searching: Starting from the head node and comparing data with each node until the target is found or the end is reached.
        • Insertion: Can be efficient at the beginning or end of the list (like adding a car at the front or back of the train).
        • Deletion: Requires finding the node before the one to delete and adjusting references (like uncoupling a train car).
    • Circular Linked List: The last node points back to the head, forming a loop (like a train circling the track).
    • Doubly Linked List: Each node has references to both the previous and next node in the list (like a train car with couplers on both sides).

    Stacks and Queues

    • Stack:
      • Concept: Imagine a stack of plates. You can only add or remove plates from the top.
      • Operates in a LIFO (Last In, First Out) manner.
      • Representation:
        • Array: Elements are stored in an array, and a top pointer keeps track of the last element added.
        • Linked List: Elements are stored in nodes, with the top node referencing the element at the top.
      • Operations:
        • Push: Add an element to the top of the stack.
        • Pop: Remove and return the element from the top of the stack.
        • Peek: Return the element at the top of the stack without removing it.
        • IsEmpty: Check if the stack is empty.
        • IsFull: Check if the stack is full (applicable to array implementation with a fixed size).
    • Queue:
      • Concept: Imagine a queue at a store. People enter at the back and exit at the front.
      • Operates in a FIFO (First In, First Out) manner.
      • Representation:
        • Array: Elements are stored in an array with front and rear pointers.
        • Linked List: Elements are stored in nodes, with a front node referencing the first element and a rear node referencing the last element.
      • Operations:
        • Enqueue: Add an element to the back of the queue.
        • Dequeue: Remove and return the element from the front of the queue.
        • Peek: Return the element at the front of the queue without removing it.
        • IsEmpty: Check if the queue is empty.
        • IsFull: Check if the queue is full (applicable to array implementation with a fixed size).

    Trees and Graphs

    • Trees:
      • Imagine an upside-down tree with a single root node at the top and branches leading to child nodes.
      • Represent hierarchical structures where nodes have parent-child relationships.
      • Terminology:
        • Node: The basic building block of a tree, containing data and references to child nodes.
        • Root Node: The topmost node, with no parent.
        • Leaf Node: A node with no children.
        • Parent Node: A node that has one or more child nodes.
        • Sibling Nodes: Nodes that share the same parent.
        • Subtree: A portion of the tree rooted at a specific node.
    • Binary Tree:
      • A special type of tree where each node can have at most two children: a left child and a right child.
      • Representation:
        • Array Representation: Not ideal for most operations due to potential inefficiency in managing empty spaces.
        • Linked List Representation: Each node stores data and references to its left and right child nodes (if any).
    • Graphs:
      • Unlike trees, graphs represent relationships between entities (nodes) that are not necessarily hierarchical.
      • Terminology:
        • Node: An element or entity in the graph.
        • Edge: A connection between two nodes. Can be directed (one-way) or undirected (two-way).
        • Weighted Edge: An edge with an associated weight or cost.
        • Adjacent Nodes: Nodes connected by an edge.
        • Path: A sequence of connected edges leading from one node to another.

    Sorting and Searching Algorithms

    • Sorting:
      • Rearranges a collection of elements into a specific order (e.g., ascending, descending).
      • Algorithms:
        • Bubble Sort: Repeatedly compares adjacent elements. If they are in the wrong order, swap them.
        • Selection Sort: Finds the smallest (or largest) element and swaps it with the first (or last) element. Repeats for the remaining elements.
        • Insertion Sort: Maintains a sorted sub-list at the beginning. Iterates through the remaining elements, inserting each one at its correct position in the sorted sub-list.
    • Searching:
      • Finds a specific element within a collection of data.
      • Algorithms:
        • Sequential Searching (Linear Search): Compares the target element with each element in the collection, one by one, until a match is found or the entire collection is scanned.
        • Binary Search: Applicable to sorted collections only. Repeatedly divides the search area in half by comparing the target element with the middle element.

    Computer Graphics

    • Introduction:
      • Deals with creating and manipulating images using computers.
      • Applications: Entertainment, design, science & engineering, education & training.
    • Basic Building Blocks:
      • Pixel: The smallest unit of color on a display screen.
      • Resolution: The number of pixels displayed horizontally and vertically. Higher resolution means sharper images.
      • Aspect Ratio: The ratio of the width to the height of the display.
    • Behind the Scenes:
      • Frame Buffer: Memory that stores the color information for each pixel on the screen.
      • Raster Scan: A common display refresh method where an electron beam scans across the screen, line by line, to update the image.
      • Random Scan: Less common refresh method where the electron beam can jump to any point on the screen, but it's less efficient than raster scan.
    • Input Devices:
      • Keyboard: Used for typing text and issuing commands.
      • Mouse: Used for pointing and selecting objects on the screen.
      • Trackball: A stationary ball you rotate with your fingers to control a cursor.
      • Joystick: A handheld device with a stick that controls movement in games or simulations.
      • Dataglove: A glove equipped with sensors that track hand and finger movements for more immersive interaction.
      • Digitizers: Tablets or pads used for drawing or tracing images.
      • Image Scanners: Devices that capture physical images and convert them into digital data.
      • Touch Panels: Screens that detect touch input for interaction.
      • Voice Systems: Allow voice commands for interacting with computer graphics applications.
    • Display Devices:
      • Cathode Ray Tube (CRT): Traditional display technology using an electron beam to illuminate phosphors on the screen.
      • Liquid Crystal Display (LCD): Flat-panel displays that use liquid crystals to control light passing through them.
      • Light-Emitting Diode (LED): Displays that use LEDs to generate light directly.
      • Digital Video Standard Timing (DVST): A standard for video display refresh rates and resolutions.

    Output Primitives

    • Straight Line: The most fundamental primitive, defined by its endpoints.
    • DDA Algorithm (Digital Differential Analyzer): Calculates pixel positions for a line with a slope less than 1, iteratively updating x and y coordinates.
    • Bresenham's Line Algorithm: Another efficient line

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    interview.pdf

    Description

    Learn about the basics of operating systems, including their role in managing computer hardware and interactions. Explore examples like Windows, macOS, and Linux.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser