Notes, summaries, assignments, exams, and problems for Computers

Listas Ligadas em C++: Adicionar, Excluir, Buscar e Imprimir

Implementação básica de uma lista simplesmente ligada em C++, cobrindo as operações essenciais de manipulação de dados.

Configuração Inicial em C++

#include <iostream>
using namespace std;

Classe Node (Nó)

Define a estrutura fundamental de cada elemento da lista.

class Node {
    public:
        int value; // Pode ser implementado qualquer tipo de dados aqui.
        Node *next;
        
        Node () {
            next = NULL; // Construtor Padrão
        }
        
        Node (int _value) { // Construtor com Atribuição de Valor
            value = _value;
            next = NULL;
        }
};

Classe List (Lista Ligada)

Gerencia a coleção de nós e as operações... Continue reading "Implementação de Listas Ligadas em C++ (CRUD)" »

Computer System Essentials

Core Operating System Components

Kernel: The OS's Foundation

The operating system's core, a platform that allows other software to execute.

Shell: User Interaction Interface

The operating system's interface for users to interact with all computer elements.

Thread: A Running Program or Task

Any program or task that is currently running.

File System: Data Storage & Retrieval Protocol

A protocol that defines how files are stored and retrieved on disk drives, or by threads and programs.

Disk Formatting: Setting a File System

The process of setting a disk's file system.

Major Operating Systems and Their Focus

• Microsoft Windows: Focuses its operating system on security.
• Linux: Emphasizes customizability.
• Chrome OS: Centered on web

1. CalculatorInterface.java

The following code defines the Remote Interface for the calculator application.

import java.rmi.*;

public interface CalculatorInterface extends Remote {
    public int add(int num1, int num2) throws RemoteException;
    public int subtract(int num1, int num2) throws RemoteException;
    public int multiply(int num1, int num2) throws RemoteException;
    public int divide(int num1, int num2) throws RemoteException;
}

2. ServerCalculator.java

This class implements the CalculatorInterface and extends UnicastRemoteObject to handle remote calls.

import java.rmi.*;
import java.rmi.server.*;

public class ServerCalculator extends UnicastRemoteObject implements CalculatorInterface {
    public ServerCalculator() throws RemoteException

Set Cover to Efficient Recruiting

Input: Set U of elements, collection S₁, ..., S_m of subsets of U, integer k ≥ 0

Construct an instance of the Efficient Recruitment Problem:

• Sports are represented by U.
• Applicants are represented by {1, ..., m}.
• For every s ∈ U and 1 ≤ i ≤ m, M[s, i] = 'qualified' if s ∈ S_i and 'not qualified' otherwise.

Steps:

1. Call the oracle for Efficient Recruiting with input M and k.
2. Return the result (yes or no) of the previous call.

Vertex Cover and Hitting Set

Graph: G = (V, E)

• U = V(G)
• S_i = {u, v}, where (u, v) is an edge of G.

Vertex Cover ⇒ Hitting Set:

If C is a vertex cover for G of size k, then by definition, for every edge (u, v) in G, either u ∈ C or v ∈ C. Therefore, C is a solution for Hitting Set because... Continue reading "Efficient Recruiting and Algorithm Design: Set Cover, Hamiltonian Path, and Longest Increasing Subsequence" »

Dynamic Host Configuration Protocol (DHCP) Servers

What is a DHCP Server?

A DHCP Server is a network server that automatically provides and assigns IP addresses, default gateways, and other network parameters to client devices. It relies on the standard protocol known as Dynamic Host Configuration Protocol (DHCP) to respond to broadcast queries by clients.

Benefits of DHCP

A DHCP server automatically sends the required network parameters for clients to properly communicate on the network. Without it, the network administrator has to manually set up every client that joins the network, which can be cumbersome, especially in large networks. DHCP servers usually assign each client with a unique dynamic IP address, which changes when the client’s... Continue reading "Network Fundamentals: DHCP, Subnetting, and Transport Protocols" »

1. Independent Set to Vertex Cover Reduction

Input

A graph G and an integer k.

Reduction Steps

1. Call the black-box for Vertex Cover with the input graph G.
2. Provide n-k as the target size, where n is the number of nodes in G.
3. Return the result ('yes' or 'no') from the black-box call.

2. SAT to Independent Set Reduction

Input

A CNF formula F.

Reduction Steps

1. Construct a graph G where the nodes of G are the literals occurring in F (with possible repetitions).
2. Add the following edges to G:
   • An edge joining every pair of complementary literals.
   • An edge joining any two literals that occur in the same clause.
3. Call the black-box for Independent Set with input graph G and an integer k, where k is the number of clauses in F.
4. Return the result ('yes' or 'no') from the

This section details the implementation of the Jacobi method in Fortran for solving a system of linear equations. The subroutine solucion_Jacobi takes a matrix A, a vector b, and an initial guess X as input, and returns the solution vector X.

Subroutine: solucion_Jacobi(A, b, X)

The subroutine begins with the following declarations and initializations:

• use normas
• integer, parameter :: Kx = 100
• real(8), parameter :: tolerancia = 1E-6
• real(8), allocatable :: X0(:), ERROR(:)
• real(8), intent(in) :: A(:,:), b(:)
• real(8), allocatable, intent(out) :: X(:)
• integer :: i, j, k, n
• real(8) :: sum, zero, ek

Where:

• Kx is the maximum number of iterations.
• tolerancia is the error tolerance.
• X0 is the previous iteration's solution vector.
• ERROR is the error vector.
• A is the

Binary Conversion

Single-Precision Floating-Point

Format: 1 sign bit, 8 exponent bits, 23 fraction bits

Bias: +127 (decimal to binary), -127 (binary to decimal)

Double-Precision Floating-Point

Format: 1 sign bit, 11 exponent bits, 52 fraction bits

Bias: +1023 (decimal to binary), -1023 (binary to decimal)

Example: -17.6875 (Single-Precision)

1. Sign Bit: + = 0, - = 1 (In this case, 1)
2. Integer Part to Binary: Repeatedly divide the integer part by 2 and record the remainders.
3. Fractional Part to Binary: Repeatedly multiply the fractional part by 2 and record the integer parts.
4. Combine and Normalize: Combine the binary integer and fractional parts. Normalize to the form 1.xxx * 2^exponent.
5. Calculate Exponent: Add the bias to the exponent.

Intra-AS Routing

RIP – Based on Distance-Vector (D-V), fewer messages, converges slower, smaller size.

OSPF – Based on Link-State (L-S), converges faster, more messages, larger networks.

Distance-Vector is distributed, and each router only knows the costs to its neighbors and their distance vectors.

Link state is global and requires that each router knows the network topology and link costs to all nodes.

OSPF: Used internally inside a network, an intra-network/domain protocol used in an AS.

BGP: An internetwork protocol used between two different ASs, used at the edge of your network to connect your network to the internet.

RIP: An intra-network protocol used in an AS, used for small networks (maximum number of hops is 16).

EBGP: Runs between two... Continue reading "Routing Protocols: RIP, OSPF, BGP, CSMA/CD, CSMA/CA" »

• Accuracy

  Tells us how correct a GPS measurement is.

• Array

  A group of disk drives that are connected and used as a single unit.

• Assembler

  A program that translates low-level programming language into machine code.

• Attachment

  A file sent as part of an email.

• Avatar

  An image in a computer game that represents a person.

• Barcode

  An arrangement of lines and spaces that represent data.

• Bit

  The smallest unit of computer data.

• Bitrate

  A measurement of the amount of data that is processed.

• Broadband

  A system that allows computers to transfer large amounts of information.

• Calibration

  The act of adjusting printers and scanners to display colors correctly.

• Capacity

  The amount of space an MP3 player has to store files.

• Catalog

  An inventory of books in a library.

• Cell phone

  A wireless