Notes, summaries, assignments, exams, and problems for Computer science

Database Query Processing: Steps and Cost Estimation

Query processing in a Database Management System (DBMS) involves several steps to transform a high-level query (such as an SQL query) into an efficient execution plan. Understanding these stages is crucial for database performance tuning.

Key Stages of Query Processing

The process typically follows these four major steps:

1. Parsing and Translation
2. Query Optimization
3. Evaluation/Execution Plan Generation
4. Query Execution

1. Parsing and Translation

Objective: Convert the SQL query into an internal representation, usually a parse tree or Abstract Syntax Tree (AST).

• The SQL query is checked for syntactic correctness.
• The SQL query is parsed into a parse tree.

Cost Estimation Techniques for Query Optimization

Cost...

Insertion Sort Algorithm

def insertion_sort(arr) :

for i in range(1, len(arr)):

key = arr[i]

j = i - 1

while j >= 0 and key < arr[j]:

arr[j + 1] = arr[j]

j -= 1

arr[j + 1] = key

# Example usage:

arr = [12, 11, 13, 5, 6]

insertion_sort(arr)

print("Sorted array is:", arr)

Binary Search Algorithm

def binary_search(arr, target):

left, right = 0, len(arr) - 1

while left <= right:

mid = (left + right) // 2

if arr[mid] == target:

return mid

elif arr[mid] < target:

left = mid + 1

else:

right = mid - 1

return -1

# Example usage:

arr = [2, 3, 4, 10, 40]

target = 10

result = binary_search(arr, target)

if result != -1:

print("Element

Space Complexity

• Analysis of the space complexity of an algorithm or program is the amount of memory it needs to run to completion.
• The space needed by a program consists of the following components:
• Fixed space requirements: Independent of the number and size of the program's input and output. It includes:

• Instruction Space (Space needed to store the code)
• Space for simple variables
• Space for constants

• Variable space requirements: This component consists of:

• Space needed by structured variables whose size depends on the particular instance I of the problem being solved
• Space required when a function uses recursion

Total Space Complexity

S(P) of a program is:

S(P) = C + S_p(I)

Here S_p(I) is the variable space requirements of program P working on an instance...

Types definition

#include <stdbool.h>

#include <stdlib.h>

Struct Definition

typedef int tItemL;
typedef struct tNode* tPosL; //Ptr to tNode
struct tNode {
tItemL data;
tPosL next;
tPosL prev;
};
typedef tPosL tList;

Prototypes

void createEmptyList(tList *L);
bool createNode(tPosL* p);
bool insertItem(tItemL d, tPosL p, tList *L);
void updateItem(tItemL d, tPosL p, tList* L);
tPosL findItem(tItemL d,tList L);
bool isEmptyList(tList L);
tItemL getItem(tPosL p, tList L);
tPosL first(tList L);
tPosL last(tList L);
tPosL previous(tPosL p, tList L);
tPosL next(tPosL p,tList L);
void deleteAtPosition(tPosL p , tList *L);
void deleteList(tList *L);

Function Definitions

#include "doubly_linked_list.h"
bool isEmptyList(tList L) { return (L == NULL); }
void...

E-Voting

Considerations

• Voter ID
• Candidate ID and Voter ID
• Representing information in text format
• Secure section for additional fields
• Providing a set number of options to reduce data input errors

Data Collection Methods

Questionnaires

Advantages: Less labor-intensive than interviews.

Disadvantages: Poorly designed questions (e.g., overuse or lack of closed questions) can lead to misunderstandings.

Interviews

Advantages: Provide more detailed information than questionnaires; allow for face-to-face interaction.

Disadvantages: Time-consuming; require skilled interviewers.

BYOD at Xingu Academy

Technical Aspects

• MAC address and IP address management
• Voice recognition software: Converts analog speech to digital sound, then to text using a sound database. Matches

Computing

Computing is the automatic processing of information with computers.

Input and Output

Input: Data entered into the computer.
CPU: Processes the information.
Output: The processed information is displayed.

Binary System

Computers use the binary system (0 and 1).
Bit (b): Smallest unit of information (0 or 1).
Byte (B): Group of 8 bits. Example: 1010 0001
Characters are usually expressed with 1 B (8 bits).

Character Encoding

ASCII (American Standard Code for Information Interchange): Represents characters using binary code.
ISO-8859-1: An extension of ASCII, uses 1 byte for characters. Example: A = 0100 0001 (65), = 0111 1110 (126)

Hardware

The physical components of a computer.

Internal Components

• Motherboard
• CPU

External Devices (Peripherals)

• Input:

Fresh leaks from the Chinese forum Saraba1st point to the imminent release of refreshed Clevo gaming laptops powered by the new Comet Lake-S desktop-grade CPUs, expected to launch this spring. User Liaojings1 obtained internal slides detailing the upcoming X170 laptops, which replace the aging P7xx-series, finally bringing Clevo's designs in line with competitors like Dell/Alienware and MSI.

Chassis and Design Improvements

To accommodate desktop-grade CPUs, the X170 features a redesigned chassis with larger rear exhaust grills. Additional upgrades include:

• Enhanced Audio: More powerful stereo speakers and a dedicated woofer.
• RGB Lighting: Integrated lighting on the rear and underneath the chassis.

Display and Visuals

Clevo is adopting slim-bezel...

What is a Process?

A process is essentially a program in execution.

Lightweight Processes in Linux

Lightweight Processes (LWPs) in Linux are processes that offer better support for multithreaded applications.

Multithreaded Applications in Linux

A multithreaded application is designed to perform multiple tasks concurrently within a single process. In Linux, a straightforward way to implement multithreaded applications is to associate a lightweight process with each thread.

This approach allows threads to access the same set of application data structures by simply sharing the same memory address space, the same set of open files, and so on. Simultaneously, each thread can be scheduled independently by the kernel, meaning one thread may sleep while...

C++ Code Examples: Data Filtering and Sorting

This document presents two fundamental C++ programming examples. The first demonstrates how to process user input to extract and display only unique integer values, effectively removing duplicates. The second illustrates the classic Bubble Sort algorithm for arranging elements in ascending order within a std::vector.

Filtering Duplicate Integers in C++

This C++ program prompts the user to enter 20 integers. It then processes these inputs to identify and store only the unique values, discarding any duplicates. Finally, it displays the list of non-duplicate integers.

Program Description: Unique Element Extraction

• Initializes an array a of size 20 to store unique elements, along with a subscript to track