This article explains the concept of recursion in programming, where a function calls itself to solve smaller instances of a problem, and its applications in tasks like tree traversal and divide-and-conquer algorithms. It also discusses the benefits of recursion for simplifying complex problems and improving code readability, while highlighting potential issues like stack overflow. Alexander S. Ricciardi September 12th, 2024 In computer science, recursion is an algorithmic technique in which a function calls itself to solve smaller instances of the same problem. In programming, recursion is an amazing technique with the help of which we can reduce the length of our code and make it easier to read and write” (GeeksforGeeks, 2024, p1). Recursion is used in programming to solve complex problems involving repetition and hierarchical structures such as tree traversals, graph algorithms, and divide-and-conquer problems like sorting and searching. The basic components found in recursive functions are base cases and recursive cases.A base case is a condition that, when met, ends the recursion process (Ricciardi, 2024). A recursive case is a set of code lines that are executed until a base condition is met. A classic example where recursion is well suited is in computing the factorial of a number. A factorial can be defined as a non-negative integer 𝑛, denoted 𝑛!, the product of all positive integers less than or equal to 𝑛: 𝑛! = 𝑛×(𝑛−1)! In Java: public class Factorial { public static int factorial(int n) { // --- Base case: factorial of 0 is 1 ---- if (n == 0) { return 1; // --- Recursive case --- } else { return n * factorial(n - 1); } } Note that the factorial() method calls itself until it reaches the base case where 𝑛 = 0 There are various benefits to using recursion. One of the biggest benefits of using recursion is that it allows programmers to easily break down complex problems into simpler, more manageable subproblems. This approach is often referred to as the divide-and-conquer approach, it is implemented in algorithms like mergesort, where recursion divides a complex sort problem into smaller problems leading to a more efficient sort solution than the linear sort iterating solution.Additionally, recursion helps with code readability by simplifying and shortening code lines. When using recursion, programmers can write problems involving repetition or hierarchical structures (trees) without the need to implement complex loops.Recursion also simplifies, and it is efficient at handling dynamic and random data structures such as linked lists and tree structures. For instance, when traversing a binary tree, using recursion simplifies the implementation of the process without the need to implement a stack. Although recursion has various advantages, in some scenarios using a stack is preferable over recursion. For example, recursion can generate a stack overflow error, ‘ StackOverflowError  ’, if the recursive depth (number of recursion calls) becomes too large. This can happen in cases like deep tree traversals or depth-first search algorithms, where the number of recursion calls may exceed the system's call stack capacity. In Java, the limit of the call stack varies depending on the platform used and the Java Virtual Machine implemented.  Java stack size can be configured using the JVM argument ‘ -Xss ’, for example ‘ java -Xss1M MyProgram ‘ where 1M is the size of the call back for MyProgram (Goodrich, Tamassia, & Goldwasser, 2023). It is best practice to use a stack or tail recursion, if possible, in this scenario. “A recursion is a tail recursion if any recursive call that is made from one context is the very last operation in that context, with the return value of the recursive call (if any) immediately returned by the enclosing recursion” (Goodrich, Tamassia, & Goldwasser, 2023, 5.5 Eliminating tail recursion). Note that while some programming languages optimize tail-recursive functions, Java does not. Thus, in Java, an optimized tail-recursive function needs to be implemented implicitly. Below are examples of implementing a depth-first search (DFS) traversal of a tree, using recursion with a possibility of ‘ StackOverflowError ’and a stack (Dequee) eliminating the possibility of a ‘ StackOverflowError ’: Using recursion possibility of ‘ StackOverflowError ’: public class DFS { // Node class static class Node { int value; Node left, right; // Constructor Node(int value) { this.value = value; left = right = null; // Left and right children are null initially } } // Recursive Depth-First Search (DFS) method public static void depthFirstSearchRecursive(Node node) { // --- Base case --- if (node == null) { return; } // Process the current node (visit) System.out.println(node.value); // Recursively traverse the left subtree depthFirstSearchRecursive(node.left); //--- Recursive case --- depthFirstSearchRecursive(node.right); /* Potential stack overflow issue: Each recursive call adds a new frame to the call stack. If the tree is too deep (e.g., with many levels), the recursion depth can exceed the system's maximum stack size, causing a StackOverflowError. */ } public static void main(String[] args) { // Create a binary tree Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); System.out.println("DFS Traversal using Recursion:"); depthFirstSearchRecursive(root); } } Using the stack approach eliminating the possibility of a  ‘ StackOverflowError ’: import java.util.ArrayDeque; import java.util.Deque; public class DFS { // Single node in the binary tree static class Node { int value; Node left, right; // Node Constructor Node(int value) { this.value = value; left = right = null; // Left and right children are null initially } } // Depth-First Search (DFS) traversal method public static void depthFirstSearch(Node root) { Deque stack = new ArrayDeque<>(); stack.push(root); // traverse the stack until is empty while (!stack.isEmpty()) { // Pop the top node from the stack Node current = stack.pop(); System.out.println(current.value); if (current.right != null) { stack.push(current.right); // Add right child to stack } if (current.left != null) { stack.push(current.left); // Add left child to stack } } } public static void main(String[] args) { // Create a binary tree Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); System.out.println("DFS Traversal using Deque:"); depthFirstSearch(root); } } Output: DFS Traversal using Deque: 1 2 4 5 3 To summarize, recursion is a technique in which a function calls itself to solve smaller instances of the same problem, it is often used in problems like tree traversal, graph algorithms, and divide-and-conquer strategies. While recursion simplifies complex problems and code readability, excessive recursive calls can lead to stack overflow errors, particularly in deeply nested structures such as trees, making iterative approaches using explicit stacks preferable in certain cases. References: Arslan, Ş. (2023, February 25). A Comprehensive tree traversal guide in Javascript - General and binary tree traversals. Shinar Arslan Blog. https://www.sahinarslan.tech/posts/a-comprehensive-tree-traversal-guide-in-javascript-general-and-binary-tree-traversals GeeksforGeeks (2024, August 18). Introduction to recursion . GeeksforGeeks. https://www.geeksforgeeks.org/introduction-to-recursion-2/ Goodrich T, M., Tamassia, R., & Goldwasser H. M. (2023, June). Chapter 5: Algorithms recursion. Data structures and algorithms . zyBook ISBN: 979-8-203-40813-6.

This article provides a detailed explanation of RAID (Redundant Array of Independent Disks), a storage technology that merges multiple disk drives into a single unit to enhance data redundancy and performance. It covers various RAID levels, from RAID 0 to RAID 10, explaining their unique configurations, advantages, and ideal use cases based on speed, capacity, cost, and fault tolerance. Alexander S. Ricciardi July 18th, 2023 Redundant Array of Independent Disk or Random Array of Inexpensive Disks (RAID) is a storage technology that combines multiple physical disk drives into a single logical unit recognized by the operating system (Stallings, 2018). Raid storage can also be defined as a storage technology that creates a data loss fail-safe by merging two or more hard disk drives (HDDs) or solid-state drives (SSDs) into one cohesive storage unit, or array (Daniel, 2023). The main use or goal of RAID storage is to protect against the total loss of a disk drive’s data by repeating or recreating that data and storing it on the additional drive or drives, a process also known as data redundancy. Furthermore, by distributing the data across multiple drives, the RAID strategy, the data can be simultaneously accessed from multiple drives, therefore improving I/O performance. The data is distributed across the drive by striping. Striping is the process of dividing data into blocks and spreading the data blocks across multiple devices. Strips may be physical blocks, sectors, or some other unit. The RAID system is organized into various levels, which can be defined as RAID 0, RAID 1, RAID 2, RAID 3, RAID 4, RAID 5, RAID 6, and RAID 10. Note: all RAID levels provide redundancy, except for RAID 0. NOTE . From Stallings, 2018, Figure 11.8 RAID level 0 In RAID 0, the data is striped across multiple drives. As a result, it provides high read/write performances. Additionally, it does not incorporate redundancy. Not providing redundancy, i.e., not providing protection against total data lost, RAID level 0 is not commonly used. RAID level 1 In RAID 1, the data is striped and duplicated into two separate drives. In other words, every drive in the array (of drives) has a mirror drive that contains the same data. This provides redundancy and increases read speeds. But on the other hand, compared to RAID 0, it lowers writing speeds. This technique is referred to as mirroring. RAID level 2 RAID 2 uses parity. The data is striped, but the strips are very small, bite-size. Furthermore, instead of striping the blocks across the drives, the bits are stored in parallel across all the drives (Natarajan, 2016). Furthermore, two groups of the drive are used, one to write/read the data and another one to write/read the error correction codes (redundancy group). In other words, the bits of the code are stored in the corresponding bit positions on multiple parity drives, and on a single read, all disks are simultaneously accessed. Additionally, RAID 2 usually uses Hamming error correction code (ECC) and stores this information in the redundancy drives. If an error occurs, it uses the correction code to rebuild the data. Finally, it requires fewer drives than RAID 1, but it is costly. The number of redundant drives is proportional to the log of the number of data drives. RAID 2 can be beneficial in an environment in which many disk errors occur. However, due to the high reliability of modern drives, “RAID 2 is overkill and is not implemented” (Stallings, 2018, p. 502). RAID level 3 As RAID 2, it uses parity, the difference is that RAID 3 requires only a single redundant drive. Therefore, it is less costly than RAID 2. RAID 3 allows very high data transfer rates, but only one I/O request can be executed at a time. RAID level 4 RAID 4 also uses parity, the difference is that it utilizes an independent access technique, where the strips are relatively large, and drives operate independently allowing several I/O requests to be accessed in parallel. However, “every write operation must involve the parity disk, which therefore can become a bottleneck” (Stallings, 2018, p. 504). RAID Level 5 RAID 5 scheme is similar to RAID 4, the difference is that it implements striping with parity. It implements strips of parity across the drives, this avoids the potential I/O bottleneck of the single parity disk found in RAID 4. It is the most common RAID configuration, and when compared to RAID 0 and RAID 1 which require a minimum of two drives, it requires a minimum of three drives to function. Like RAID 0, RAID 5 read speeds fast but its write speed is lower due to the redundant creation of parity strips. Furthermore, the loss of an entire drive will not result in any data loss. RAID Level 6 RAID 6 scheme is similar to RAID 5, the difference is that instead of implementing one strips of parity across the drives, it implements two different strips of parity across the drives, see Figure 1. This “provides extremely high data availability. Three disks would have to fail within the MTTR (mean time to repair) interval to cause data to be lost” (Stallings, 2018, p. 504), but on the other hand, it severally affects write performance. RAID Level 10 RAID 10 combines both data striping (RAID 0) and disk mirroring (RAID 1). This achieves redundancy by duplicating the data and performance by striping. A minimum of four drives is necessary to implement it. In other words, RAID 10 is the best of both RAID 0 and RAID 1, with fast read and write speeds and fault tolerance (Natarajan, 2016). In conclusion, the best RAID configuration depends on the application's requirements, which may be based on speed, capacity, cost, data redundancy, or a combination of these. For example, a supercomputer application may prefer RAID 0 where performance, capacity, and low-cost are more important than reliability. In comparison, applications where data integrity is crucial, such as healthcare, banking, and defense, may prefer RAID 6. While it may come at a higher cost and offer less performance, particularly when writing data, than RAID 0. Nonetheless, RAID 6 still provides high data access and protects against data loss even in the event of two drives failing simultaneously. References: Daniel, B. (2023, March 7). RAID levels 0, 1, 5, 6 and 10 & raid types (software vs. hardware). Trusted Computing Innovator. https://www.trentonsystems.com/blog/raid-levels-0-1-5-6-10-raid-types#:~:text=The%20best%20RAID%20configuration%20for,RAID%206%20and%20RAID%2010 Natarajan, R. (2016, March 25). RAID 2, RAID 3, RAID 4, raid 6 explained with diagram. The Geek Stuff. https://www.thegeekstuff.com/2011/11/raid2-raid3-raid4-raid6/ Stallings, W. (2018). Operating Systems: Internals and design principles. Pearson

This article discusses the widespread presence of computers in critical infrastructures and the importance of implementing cybersecurity measures to safeguard systems from malware. It highlights various types of malware and outlines key countermeasures, such as antivirus software, firewalls, and encryption, to prevent security breaches and protect sensitive data. Alexander S. Ricciardi July 24th, 2023 Computers are everywhere, in our cars, phones, appliances, our grocery stores, airplanes, banks, and more… they are part of every critical infrastructure that our daily lives depend on. Thus, it is crucial to understand and implement cybersecurity measures. That is, measures that safeguard the functionality of our computer systems and the information stored in those systems. In the context of operating systems, the key to safeguarding a computer system's functionality and the integrity of the information stored in it, is to prevent “malicious software (malware) from gaining unauthorized privileges on the system and, in particular, from gaining root access” (Stallings, 2018. P. 631). Different types of malware exist, and each can affect a system in uniquely destructive ways. From viruses that replicate themselves and ransomware that encrypts crucial data to spyware that monitors and steals sensitive information. Figure 1 depicts a list of 12 types of malware that you are most likely to come across. For each type, a small description and real-world examples are given. Figure 1 Malware List Note . From 12 types of malware + examples that you should know, by Baker, 2023, ( https://www.crowdstrike.com/cybersecurity-101/malware/types-of-malware/ ). Copyright 2023 by crowdstrike.com . Therefore, it is essential to implement countermeasures or security controls to prevent security incidents. That is to prevent malware from accessing a computer system's functionality and data. The Federal Information Processing Standard (FIPS) defines security controls as “the management, operational, and technical controls (i.e., safeguards or, countermeasures) prescribed for an information system to protect the confidentiality, integrity, and availability of the system and its information” (FIPS 199, n.d.). Below is a list of countermeasures that can be implemented: Antivirus/Antimalware Software detects and neutralizes threats like viruses, worms, and spyware. They work by comparing files on a computer to a database of known threats and behaviors. Firewalls are a barrier between a trusted network and an untrusted network. They can prevent unauthorized access to a network and can often detect and block many types of attacks. Intrusion Detection System (IDS) is a system that monitors network traffic and system activities for malicious activities or policy violations and generates an alert when such activity occurs (Lutkevich, 2021). Intrusion Prevention System (IPS) is an IDS that detects potential threats but also takes actions to prevent them from causing harm. Patch Management is the action to manage software or systems patches. It is important to regularly update and patch systems, it can help prevent security incidents.  Penetration Testing and Vulnerability Assessments . A vulnerability assessment identifies and measures security weaknesses in a system. A penetration test is a simulated cyber attack designed to identify vulnerabilities in an organization's security system (Escobar, 2021). Security Awareness Training : Educating users about the signs of a security incident can prevent many attacks. Users should be trained to recognize and report phishing attempts, suspicious behavior, and potential malware. Access Controls and User Permissions , it is important to implement controls on which users can access what data and to ensure that users have the appropriate amount of access to perform their duties. Encryption , which involves encoding sensitive data. This data can only be decrypted by authorized applications and users who have access to the data. Systems Event Management (SIEM) is a security solution that helps organizations recognize and address potential security threats and vulnerabilities before they have a chance to disrupt business operations (IBM, n.d.). In conclusion, computer systems are in every critical infrasture, making it essential to safeguard them from malware is essential for the security and stability of the critical infrastructures that underpin our daily lives. By implementing effective countermeasures, such as antivirus software, firewalls, and security training, we can significantly reduce the risk of cyber threats and ensure the continued protection of critical systems and infrastructures. References: Baker, B. (2023, July 19). 12 types of malware + examples that you should know[Figure 1]. crowdstrike.com . https://www.crowdstrike.com/cybersecurity-101/malware/types-of-malware/ Escobar, E. (2021, August 19). Vulnerability assessments versus penetration tests. Secureworks . https://www.secureworks.com/blog/vulnerability-assessments-versus-penetration-tests Lutkevich, B. (2021, October 7). What is an intrusion detection system (IDS)? Techtarget.com . https://www.techtarget.com/searchsecurity/definition/intrusion-detection-system?Offer=abt_pubpro_AI-Insider IBM (n.d.). What is Security Information and Event Management (SIEM)? Ibm.com . https://www.ibm.com/topics/siem FIPS 199, standards for security categorization of federal ... - NIST. (n.d.). National Institute of Standards and Technology. Retrieve from: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.199.pdf Stallings, W. (2018).  Operating Systems: Internals and design principles . Pearson

This article explains the importance of the Filesystem Hierarchy Standard (FHS) in Linux and other UNIX-like systems, focusing on its role in organizing files, ensuring cross-distribution compatibility, and supporting system stability. It highlights how understanding FHS is crucial for effective system navigation, troubleshooting, and security management. Alexander S. Ricciardi July 18th, 2023 In computer science, file structure is usually a tree-like hierarchical organization representation of files stored in secondary memory. “It is also a collection of operations for accessing the data. It enables applications to read, write, and modify data. File structures may also help to find the data that matches certain criteria” (Sari, 2023). Linux distributions and other UNIX-like operating systems implement Filesystem Hierarchy Standard (FHS) as a file structure system. FHS is a standard that defines the directory structure and directory contents. This standard consists of a set of requirements and guidelines for file and directory placement. “The guidelines are intended to support interoperability of applications, system administration tools, development tools, and scripts as well as greater uniformity of documentation for these systems” (LSB Workgroup, 2015, Abstract section). In this post, I discuss the importance of understanding file structure, specifically FHS in Linux systems. Understanding FHS is crucial to effectively navigate and managing a Linux system, ensuring cross-distribution compatibility, maintaining system stability, conducting efficient troubleshooting, and implementing appropriate security measures. Navigating and Managing The role of a file structure system is to allow software and user to manage files in secondary memory (create, delete, read, write, and modify files). Additionally, FHS is responsible for retrieving the root filesystem, which is used to boot, restore, and/or repair the system (LSB Workgroup, 2015). In the context of Linux, it is crucial to understand the FHS directory structure and directory contents to navigate and manage files. Figure 1 illustrates the Linux directory FHS structure. Figure 1 Linux Directory FHS Structure Note. From Linux Directory Structure (File System Hierarchy) Explained with Examples, by M. Maruthamuthu, 2019, ( https://www.2daygeek.com/linux-directory-structure-file-system-hierarchy/ ). Copyrights 2023 2daygeek.com Cross-Distribution Compatibility Understanding how FHS differed from other file system structure systems is crucial for applications development and user utilization. FHS’ main quality is that it can support cross-distribution compatibility. In Linux terms, a distribution is an operating system developed by various open-source projects and programmers. “Each distribution includes the Linux kernel (the foundation of the operating system), the GNU shell utilities (the terminal interface and commands)” (“What is a Linux distribution?”, n.d.). In other words, different Linux distributions can have different approaches to file and directory placement and still ensures a level of consistency across distributions. Furthermore, this level of consistency across distributions facilitates the creation of applications compatible across various Linux distributions.  System Stability and Troubleshooting Maintaining system stability is another key advantage of understanding the FHS. Linux separates user data from system data, static files from dynamic files, and local files from network files. This separation prevents the unintentional alteration or deletion of critical system files, ensuring a stable and secure system. Effective troubleshooting is an integral part of managing any system. In Linux systems, when problems arise, knowing the FHS will allow you to pinpoint potential sources of issues. For example, if a system service isn't starting as expected, checking files in /var/log might provide useful error messages. Security Knowing which directories contain sensitive data or system-critical files helps when setting permissions or installing a security-enhancing software package. FHS allows users to quickly identify important directories, such as /etc for system configuration files, /var for logs and spool files, and /home for user data, amongst others. This makes it easier to configure and enforce security policies across the system. In conclusion, the file structure is usually a tree-like hierarchical organization representation of files stored in secondary memory, which allows data access and enables applications and users to create, delete, read, write, and modify files. In this post, I discussed Filesystem Hierarchy Standard (FHS) as a file structure system. FHS is a standard that defines the directory structure and directory contents in Linux distributions and other UNIX-like operating systems. Finally, having a good understanding of FHS is essential to effectively navigate and manage files, develop cross-distribution applications, preserve system stability, conduct efficient troubleshooting, and put into place suitable security measures in Linux distributions and other UNIX-like operating systems. References: LSB Workgroup (2015, March 19). Filesystem hierarchy standard [PDF]. The Linux Foundation. Retrieve from: https://refspecs.linuxfoundation.org/FHS_3.0/fhs-3.0.pdf Sari, S. (2023, May 30). File structures. Baeldung on Computer Science. https://www.baeldung.com/cs/file-structures#:~:text=A%20file%20structure%20is%20a,data%20that%20matches%20certain%20criteria Stallings, W. (2018).  Operating Systems: Internals and design principles . Pearson What is a Linux distribution?: Answer from SUSE defines. SUSE Defines. (n.d.). https://www.suse.com/suse-defines/definition/linux-distribution/

This article explains process synchronization in Operating Systems (OS) and challenges like the Bounded-Buffer, Readers-Writers, and Dining-Philosophers problems. It discusses solutions using semaphores, message passing, and monitors to avoid issues like race conditions, deadlock, and starvation. Alexander S. Ricciardi September 27th, 2024 In the context of an operating system (OS), process synchronization can be defined as a set of methods and techniques used to coordinate the concurrent execution of multiple processes or threads. In a multi-process environment, which can also be referred to as "multiprocessing" or "parallel computing", process synchronization plays a crucial role in ensuring that shared data is accessed and modified correctly by addressing several problems that may arise in multi-process environments. Classic problems of process synchronization are the Bounded-Buffer, Readers–Writers, and Dining-Philosophers problems. Solutions to these problems can be developed using tools such as semaphores, binary semaphores,  Message passing, and monitors (Silberschatz et al., 2018, p. 314). the Bounded-Buffer Problem: The Bounded-Buffer Problem is a classic synchronization problem that involves coordinating the operations of producers and consumers accessing a fixed-size buffer. A Bounded-Buffer can lead to Race Condition.  A Race Condition is “a situation in which multiple threads or processes read and write a shared data item, and the final result depends on the relative timing of their execution” (Stallings, 2018, Chapter 5). Mutual exclusion must be enforced to ensure that only one process can access the shared buffer at a given time. The following is a Bounded-Buffer producer and consumer pseudocode. // producer while (true) { // produce item v while ((in + 1) % n == out) { // do nothing } b[in] = v; in = (in + 1) % n; } // consumer while (true) { while (in == out) { // do nothing } w = b[out]; out = (out + 1) % n; // consume item w } (Stallings, 2018, Chapter 5.4) The problem Description: The fixed-size buffer can hold a limited number of items. Multiple producers may add items to the buffer concurrently. Multiple consumers may remove items from the buffer concurrently. Producers must wait if the buffer is full. Consumers must wait if the buffer is empty. A solution to the Bounded-Buffer Problem is the implementation of semaphore, which is a mutual exclusion method. A semaphore (also called a counting semaphore or a general semaphore) is an integer value used for signaling among processes, and can only be accessed through two standard atomic operations: semWait() and semSignal(). The letter 's' is generally used to denote a semaphore, below is an example of semaphore pseudocode. struct semaphore { int count; queueType queue; }; void semWait(semaphore s) { s.count--; if (s.count < 0) { /* place this process in s.queue */ /* block this process */ } } void semSignal(semaphore s) { s.count++; if (s.count <= 0) { /* remove a process P from s.queue */ /* place process P on ready list */ } } (Stallings, 2018, Figure 5.6) Note that only three operations may be performed on a semaphore, all of which are atomic: initialize, decrement, and increment. The decrement operation may result in the blocking of a process, and the increment operation may result in the unblocking of a process. Furthermore, a binary semaphore is a semaphore that takes on only the values 0 and 1, and a mutex is “similar to a binary semaphore. A key difference between the two is that the process that locks the mutex (sets the value to 0) must be the one to unlock it (sets the value to 1)" (Stallings, 2018, Chapter 5.4). Below is an example of binary semaphore pseudocode: struct semaphore { int count; queueType queue; }; void semWait(semaphore s) { s.count--; if (s.count < 0) { /* place this process in s.queue */ /* block this process */ } } void semSignal(semaphore s) { s.count++; if (s.count <= 0) { /* remove a process P from s.queue */ /* place process P on ready list */ } } Stallings, 2018, Figure 5.7) Note that: A binary semaphore may be initialized to zero or one. The semWaitB(semaphore s) function checks if the value is zero, then the process executing the semWaitB() is blocked. If the value is one, then the value is changed to zero and the process continues execution. The semSignalB(semaphore s)  function checks if the queue is empty (s is equal to zero) on the semaphore, if so, the semaphore is set to one, else a process blocked by a semWaitB() is unblocked (removed from the queue) and placed on the ready list. The following pseudocode shows a possible solution to the Bounded-Buffer Problem using semaphores: /* program boundedbuffer */ const int sizeofbuffer = /* buffer size */; semaphore s = 1, n = 0, e = sizeofbuffer; void producer() { while (true) { produce(); // produce item semWait(e); semWait(s); append(); // add item to "the end of the list" semSignal(s); semSignal(n); } } void consumer() { while (true) { semWait(n); semWait(s); take(); // take item from "the list" semSignal(s); semSignal(e); consume(); // consume item } } void main() { parbegin(producer, consumer); } (Stallings, 2018, Figure 5.13) 2- Readers–Writers Problem The Readers–Writers Problem can be described as multiple readers and writers concurrently assessing a resource (e.g., a file or database) and potentially affecting the data integrity. The condition that needs to be met to ensure data integrity are: Any number of readers may simultaneously read the file. Only one writer at a time may write to the file. If a writer is writing to the file, no reader may read it. Note that readers are processes that are not required to exclude one another, and writers are processes that are required to exclude all other processes, readers and writers alike. (Stallings, 2018, Chapter 5.7) A solution to the Readers–Writers Problem is the implementation of semaphore or message passing. Message passing is a mechanism to allow processes or threads to communicate and synchronize their actions. In message passing, communication occurs by explicitly sending a message from a sender to a receiver. The sender encapsulates the data or information to be transmitted into a message and sends it to the receiver. The receiver then receives the message and extracts the information or data from it. 3- Dining-Philosophers problem The dining-Philosophers problem describes a scenario where, for example, five philosophers share a meal at a round table. Every philosopher has a plate and one fork to their right and one fork to their left. They need to use two forks to eat, and it is a total of five forks on the table. The problem arises when all the philosophers decide to eat at the same time. The Dining-Philosophers Problem is a classic synchronization problem, it is a metaphor for the problems of deadlock and starvation, which can occur when multiple processes attempt to access multiple resources simultaneously. Starvation is the situation in which a process or thread waits indefinitely within a semaphore. (Silberschatz et al., 2018, p. G-32) Deadlock is the state in which two processes or threads are stuck waiting for an event that can only be caused by one of the processes or threads. (Silberschatz et al., 2018, p. G-9). Two main methods exist to prevent or avoid deadlocks. The first one is the deadlock avoidance approach, which grants access to a resource if it cannot result in a deadlock. The second one is the deadlock prevention approach which involves changing the rules so that processes will not make requests that could result in deadlock. Note that for a deadlock to occur, each of the four conditions listed below must hold: Mutual Exclusion: Only one process at a time can use a resource. Hold and Wait: A process that holds at least one resource and is waiting to acquire additional resources held by other processes. No Preemption: A resource can be released only voluntarily by the process holding it after that process has completed its task. Circular Wait: A set of waiting processes. In other words, a deadlock will not occur by ensuring that at least one of the conditions does not exist. Deadlock prevention prevents at least one of the four conditions of deadlock. On the other hand, deadlock avoidance allows the four conditions, but it allows only three of the four conditions to exist concurrently. Finally, one of the solutions for Dining-Philosophers Problem is using a monitor-based solution. A monitor is a programming language construct that allows to put a lock on objects, The main characteristics of a monitor are the following: The local data variables are accessible only by the monitor’s procedures and not by any external procedure. A process enters the monitor by invoking one of its procedures. Only one process may be executing in the monitor at a time; any other processes that have invoked the monitor are blocked, waiting for the monitor to become available. (Stallings, 2018, Chapter 5.5). In conclusion, process synchronization is a complex subject and it is essential in operating systems to coordinate the concurrent execution of multiple processes or threads. It addresses various problems such as the Bounded-Buffer Problem, Readers-Writers Problem, and Dining-Philosophers Problem. These problems highlight the challenges of managing shared resources, ensuring mutual exclusion, avoiding race condition and deadlock, and preventing starvation. References: Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating system concepts [PDF]. Wiley. Retrieved from: https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdfLinks to an external site. Stallings, W. (2018).  Operating Systems: Internals and design principles . Pearson

This article showcases asymptotic analyses evaluating algorithms' time complexity using Big-Oh notation through a series of Java-based programming problems. Alexander S. Ricciardi September 1st , 2024 This documentation is part of the Critical Thinking 3 Assignment from CSC400: Data Structures and Algorithms at Colorado State University Global. It consists of a series of exercises designed to demonstrate the principles of asymptotic analysis. Asymptotic analysis uses the Big-Oh notation. “In computer science, the Big-Oh notation is used to describe the time complexity or space complexity of algorithms (Geeks for Geeks, 2024). Mathematically, it defines the upper bound of an algorithm’s growth rate, known as the asymptotic upper bound, and is denoted as 𝑓(𝑛) is 𝑂(𝑔(𝑛)) or 𝑓(𝑛) ∈ 𝑂(𝑔(𝑛)), pronounced 𝑓(𝑛) is Big-Oh of 𝑔(𝑛). The term "asymptotic" refers to the behavior of the function as its input size 𝑛 approaches infinity. In the context of computer science, it describes the worst-case scenario for time complexity or space complexity. For example, an algorithm with 𝑂(𝑛²) time complexity will grow much faster than one with 𝑂(𝑛) as the input size increases, with n representing the number of primitive operations. Primitive operations are low-level instructions with a constant execution time.” (Ricciardi, 2024. Post)  Definition of Big-Oh: Let f(n) and g(n) be functions mapping positive integers to positive real numbers. We say that f(n) ∈ O(g(n)) if there is a real constant c > 0 and an integer constant n0 ≥ 1 such that f(n) ≤ c⋅g(n) , for n ≥ n0 (Carrano & Henry, 2018) The Assignment Direction: Complete the following exercises. For each exercise, show your work and all the steps taken to determine the Big-Oh for each problem. Partial points cannot be awarded without showing work. Exercise 1 What is the Big-Oh of the following computation?  int sum = 0; for (int counter = n; counter > 0; counter = counter - 2) sum = sum + counter; Exercise 2 Suppose your implementation of a particular algorithm appears in Java as follows:  for (int pass = 1; pass <= n; pass++) { for(int index = 0; index < n; index++) { for(int count = 1; count < 10; count++) { . . . } //end for } // end for } //end for The algorithm involves an array of "n" items. The previous code shows only the repetition in the algorithm, but it does not show the computations that occur within the loops.Those computations, however, are independent of "n." What is the order of the algorithm?       Exercise 3 Consider two programs, A and B. Program A requires 1000 x n^2 operations and Program B requires 2n operations. For which values of n will Program A execute faster than Program B?   Exercise 4 Consider an array of length "n" containing unique integers in random order and in the range 1 to n + 1. For example, an array of length 5 would contain 5 unique integers selected randomly from the integers 1 through 6. Thus the array might contain 3 6 5 1 4. Of the integers 1 through 6, notice that 2 was not selected and is not in the array. Write Java code that finds the integer that does not appear in such an array. Explain the Big-Oh in your code. My notes: - Each exercise starts on a new page. - 𝑔(𝑛) is the number of primitive operations. - The summation properties of a constant Exercise 1 What is the Big-Oh of the following computation?  int sum = 0; for (int counter = n; counter > 0; counter = counter - 2) sum = sum + counter; In this exercise 𝑔(𝑛) is the number of primitive operations. Step 1: Understanding the code - The ‘sum’ variable initializes to ‘0’. - The ‘counter’ loop iterates from ‘n’ to ‘1’ inclusive. Note that all the variables andconstants in the loop are integers. o The ‘counter’ variable initializes to ‘n’. o The ‘counter’ variable is compared to ‘0’, the loop iterates as long as ‘counter’ is greater than ‘0’. o The ‘counter’ variable is post-decremented by ‘2’, this means that the ‘counter’ is compared to ‘0’ before being decremented. o The ‘sum’ variable is incremented by the value of the ‘counter’ variable in eachiteration of the for-loop until the ‘counter’ is less than or equal to ‘0’. If ‘n = 10’ - 1st iteration ‘counter = 10’ and ‘sum = 0 + 10 = 10’ - 2nd iteration ‘counter = 8’ and ‘sum = 10 + 8 = 18’ - 3rd iteration ‘counter = 6’ and ‘sum = 18 + 6 = 24’ - 4th iteration ‘counter = 4’ and ‘sum = 24 + 4 = 28’ - 5th iteration ‘counter = 2’ and ‘sum = 28 + 2 = 30’ The number of iterations is 𝑛/2 If ‘n = 11’ - 1st iteration ‘counter = 11’ and ‘sum = 0 + 11 = 11’ - 2nd iteration ‘counter = 9’ and ‘sum = 11 + 9 = 20’ - 3rd iteration ‘counter = 7’ and ‘sum = 20 + 7 = 27’ - 4th iteration ‘counter = 5’ and ‘sum = 27 + 5 = 32’ - 5th iteration ‘counter = 3’ and ‘sum = 32 + 3 = 35’ - 6th iteration ‘counter = 1’ and ‘sum = 32 + 1 = 36’ The number of iterations is (𝑛+1)/2 Step 2: Counting the number of iterations The for-loop will iterate as long as the ‘counter > 0’, the ‘counter is initialized to ‘n’, and it is decremented by ‘2’. If 𝑘 is the number of iterations, then the last iteration would occur when 𝑛 - 2𝑘 ≤ 0. Solving for 𝑘, 𝑘 ≥ 𝑛/2 . Using the examples above of ‘n = 10’ and ‘n = 11’, we can say that 𝑘 = 𝑛/2 when 𝑛 is even and k = (𝑛+1)/2 when 𝑛 is odd.  Justification: An odd number is an integer of the form 𝑛 = 2𝑐 + 1, where 𝑐 is an integer. Then 𝑘 = (2𝑐+1+1)/2 = (2/2) 𝑐 + (2/2) = 𝑐 + 1. An even number is an integer of the form 𝑛 = 2𝑐, where 𝑐 is an integer. Then 𝑘 = (2𝑐)/2 = (2/2) 𝑐 = 𝑐 If 𝑐 = 5 Then 𝑛_𝑒𝑣𝑒𝑛 = 2∗5 = 10 and 𝑘_𝑒𝑣𝑒𝑛 = 𝑛_𝑒𝑣𝑒𝑛/2 = 5 = 𝑐 And 𝑛_𝑜𝑑𝑑 = 2∗5+1 = 11 𝑎𝑛𝑑 𝑘_𝑜𝑑𝑑 = (11+1)/2 = 12/2 = 6 = 𝑐+1  Step 3: Number of primitive operations 𝑔(𝑛) per instruction - The ‘sum’ variable initializes to 0, it is executed only once, 𝑔₁(𝑛) = 1. - The ‘counter’ variable initializes to n by the for-loop statement this is executed only once, 𝑔₂(𝑛) = 1. - The ‘counter’ variable is compared to ‘0’, this is executed in each iteration of the loop, and the number of iterations is 𝑘_𝑒𝑣𝑒𝑛 = 𝑛_𝑒𝑣𝑒𝑛/2 , then 𝑔₃(𝑛_𝑒𝑣𝑒𝑛) = 𝑛_𝑒𝑣𝑒𝑛/2; and 𝑘_𝑜𝑑𝑑 = (𝑛_𝑜𝑑𝑑+1)/2, then 𝑔₃(𝑛_𝑜𝑑𝑑) = (𝑛_𝑜𝑑𝑑+1)/2 - The ‘counter’ is post-decremented by ‘2’, this is done after each iteration of the loop and the comparison of ‘counter’ to ‘0’returns true, the number of iterations is 𝑘_𝑒𝑣𝑒𝑛 = 𝑛_𝑒𝑣𝑒𝑛/2, then 𝑔₄(𝑛𝑒𝑣𝑒𝑛) = 𝑛_𝑒𝑣𝑒𝑛/2 ; and 𝑘_𝑜𝑑𝑑 = (𝑛_𝑜𝑑𝑑+1)/2, then 𝑔₄(𝑛_𝑜𝑑𝑑) = (𝑛_𝑜𝑑𝑑+1)/2 - The ‘sum’ variable is incremented by the value of the ‘counter’ variable in each iteration of the for-loop until the ‘counter’ is less than or equal to ‘0’, then the number of times this instruction will be executed is the number of iterations 𝑘_𝑒𝑣𝑒𝑛 = 𝑛_𝑒𝑣𝑒𝑛/2, then 𝑔₅(𝑛_𝑒𝑣𝑒𝑛) = 𝑛_𝑒𝑣𝑒𝑛/2 ; and 𝑘_𝑜𝑑𝑑 = (𝑛_𝑜𝑑𝑑+1)/2, then 𝑔₅(𝑛_𝑜𝑑𝑑) = (𝑛_𝑜𝑑𝑑+1)/2  Step 4: The total of primitive operations If 𝒏 is even, 𝒌 = 𝒏/𝟐 - 𝑔(𝑛) = 𝑔₁(𝑛) + 𝑔₂(𝑛) + 𝑔₃(𝑛) + 𝑔₄(𝑛) +𝑔₅(𝑛) - 𝑔(𝑛) = 1 + 1 + 𝑘 + 𝑘 + 𝑘 = 1 + 1 + 𝑛/2 + 𝑛/2 + 𝑛/2 - 𝑔(𝑛) = 2 + (3/2)𝑛 If 𝒏 is odd, 𝒌 = (𝒏-𝟏)/𝟐 - 𝑔(𝑛) = 𝑔₁(𝑛) + 𝑔₂(𝑛) + 𝑔₃(𝑛) + 𝑔₄(𝑛) +𝑔₅(𝑛) - 𝑔(𝑛) = 1 + 1 + 𝑘 + 𝑘 + 𝑘 = 1 + 1 + (𝑛+1)/2 + (𝑛+1)/2 + (𝑛+1)/2 = 2/2 + 2/2 + 1/2 + 1/2 + 1/2 + 𝑛/2 + 𝑛/2 + 𝑛/2 - 𝑔(𝑛) = 7/2 + (3/2)𝑛 Step 5: The Big-Oh notation By the definition of the Big-Oh notation, 𝑂(𝑔(𝑛)). If 𝑛 is even, with 𝑔(𝑛) = 2 + (3/2)𝑛 then the asymptotic complexity is 𝑂(𝑛) Justification: 2 + (3/2)𝑛 ≤ 𝑐𝑛, for 𝑐 = 4/2 + 3/2 = 7/2 , when 𝑛 ≥ 𝑛₀ = 2 and 𝑛 is even. If 𝑛 is odd, with 𝑔(𝑛) = 7/2 + (3/2)/𝑛 then the asymptotic complexity is 𝑂(𝑛) justification: 2 + (3/2)𝑛 ≤ 𝑐𝑛, for 𝑐 = 4/2 + 3/2 = 7/2 , when 𝑛 ≥ 𝑛₀ = 1 and 𝑛 is odd. When 𝑛 is even Big-Oh is 𝑂(𝑛) and when 𝑛 is even Big-Oh 𝑂(𝑛), thus: The Big-Oh of the computation is 𝑂(𝑛) In conclusion, the asymptotic analysis shows that the complexity of the algorithm is directly proportional to the size of the input n, indicating a linear growth rate. O(n) represents a linear type of complexity.  Exercise 2 Suppose your implementation of a particular algorithm appears in Java as follows: for (int pass = 1; pass <= n; pass++) { for(int index = 0; index < n; index++) { for(int count = 1; count < 10; count++) { . . . } //end for } // end for } //end for The algorithm involves an array of "n" items. The previous code shows only the repetition in the algorithm, but it does not show the computations that occur within the loops. Those computations, however, are independent of "n." What is the order of the algorithm?    Note that the order of an algorithm refers to its "time complexity" or Big-Oh notation. Below is the time complexity analysis of the code above.   Step 1: Understanding the code -  The outer loop (‘pass’) itenerates from ‘1’ to ‘n’ inclusive. Note that all the variables and constants in the loop are integers. o   The ‘pass’ variable initializes to ‘1’. o   The ‘pass’ variable is compared to ‘n’, the loop iterates as long as ‘pass’ is less than or equal to ‘n’. o   The ‘pass’ variable is post-incremented by ‘1’, this means that the ‘pass' variable is compared to ‘n’ before being incremented. -   The middle loop (‘index’) itenerates from ‘0’ to ‘n’ exclusive. Note that all the variables and constants in the loop are integers. o   The ‘index’ variable initializes to ‘0’. o   The ‘index’ variable is compared to ‘n’, the loop iterates as long as ‘index’ is less than ‘n’. o   The ‘index’ variable is post-incremented by ‘1’, this means that the ‘pass' variable is compared to ‘n’ before being incremented. -  The inner loop (‘count’) itenerates from ‘1’ to ‘10’ exclusive. Note that all the variables and constants in the loop are integers. o   The ‘count’ variable initializes to ‘1’. o   The ‘count’ variable is compared to ‘10’, the loop iterates as long as ‘count’ is less than ‘10’. o   The ‘count’ variable is post-incremented by ‘1’, this means that the ‘count' variable is compared to ‘10’ before being incremented.   Step 2:  Counting the number of iterations -  The outer loop will iterate as long as  ‘pass’ is less than or equal to ‘n’, and it is post-incremented by ‘1’, starting at ‘pass = 1’.If  is the number of iterations: Thus, the loop iterates 𝒏 times  -  The outer middle will iterate as long as the ‘index’ is strictly less than ‘n’. and it is post-incremented by ‘1’, starting at ‘index = 0’. If  is the number of iterations: Thus, the loop iterates 𝑛 times. However, since the loop is nested within the outer loop, it iterates a total of 𝑛 ∙ 𝑛 = 𝒏² times. - The inner loop will iterate as long as ‘count’ is strictly less than ‘10’, and it is post-incremented by ‘1’, starting at ‘pass = 1’. If 𝑘 is the number of iterations:  Thus, the loop iterates 9 times. However, since the loop is nested within the middle loop, it iterates a total of 9 ∙ 𝑛 ² = 𝟗𝒏² times.   Step 3: Number of primitive operations 𝑔(𝑛) per instruction - The number of primitive operations for the outer loop is: o The ‘pass’ variable initializes to ‘1’ by the for-loop statement this is executedonly once, then 𝑔₁(𝑛) = 1. o The ‘pass’ variable is compared to ‘n’, this is executed in each iteration of the loop, and the number of iterations is 𝑘 = 𝑛, then 𝑔₂(𝑛) = 𝑛. o The ‘pass’ is post-incremented by ‘1’, this is done after each iteration of the loop and the comparison of ‘pass’ to ‘n’ returns true, the number of iterations is 𝑘 = 𝑛, then 𝑔₃(𝑛) = 𝑛. The total of primitive operations for the outer loop is: 𝑔_𝑜𝑢𝑡𝑒𝑟𝑙𝑜𝑜𝑝(𝑛) = 𝑔₁(𝑛) + 𝑔₂(𝑛) + 𝑔₃(𝑛) = 1 + 𝑛 + 𝑛 = 1 + 2𝑛 𝑔_𝑜𝑢𝑡𝑒𝑟𝑙𝑜𝑜𝑝(𝑛) = 1 + 2𝑛  - The number of primitive operations for the middle loop is: o The ‘index’ variable initializes to ‘0’ by the for-loop statement this is executed only once. However, since the middle loop is nested within the outer loop, the index’ variable is initialized 𝑛 times, then 𝑔₁(𝑛) = 1 ∙ 𝑛 = 𝑛. o The ‘index’ variable is compared to ‘n’, this is executed in each iteration of the loop, and the number of iterations is 𝑘 = 𝑛², then 𝑔₂(𝑛) = 𝑛². o The ‘index’ is post-incremented by ‘1’, this is done after each iteration of the loop and the comparison of ‘index’ to ‘n’ returns true, and the number of iterations is 𝑘 = 𝑛², then 𝑔₃(𝑛) = 𝑛². The total of primitive operations for the outer loop is: 𝑔_𝑚𝑖𝑑𝑑𝑙𝑒𝑙𝑜𝑜𝑝 (𝑛) = 𝑔₁(𝑛) + 𝑔₂(𝑛) + 𝑔₃(𝑛) = + 𝑛 + 𝑛² + 𝑛² = 𝑛 + 2𝑛² 𝑔_𝑚𝑖𝑑𝑑𝑙𝑒𝑙𝑜𝑜𝑝 (𝑛) = 𝑛 + 2𝑛² - The number of primitive operations for the inner loop is: o The ‘count’ variable initializes to ‘1’ by the for-loop statement this is executed only once. However, since the inner loop is nested within the middle loop, the ‘count’ variable is initialized 𝑛2 times, then 𝑔₁(𝑛) = 1 ∙ 𝑛² = 𝑛² . o The ‘index’ variable is compared to ‘10’, this is executed in each iteration of the loop, and the number of iterations is 𝑘 = 9𝑛² , then 𝑔3(𝑛) = 9𝑛² o The ‘index’ is post-incremented by ‘1’, this is done after each iteration of the loop and the comparison of ‘index’ to ‘10’ returns true, and the number of iterations is 𝑘 = 9𝑛² , then 𝑔3(𝑛) = 9𝑛² . The total of primitive operations for the outer loop is: 𝑔_𝑖𝑛𝑛𝑒𝑟𝑙𝑜𝑜𝑝(𝑛) = 𝑔₁(𝑛) + 𝑔₂(𝑛) + 𝑔₃(𝑛) = 𝑛² + 9𝑛² + 9𝑛² = 19𝑛² 𝑔_𝑖𝑛𝑛𝑒𝑟𝑙𝑜𝑜𝑝(𝑛) = 19𝑛²   Step 4: The total of primitive operations done by the loops - 𝑔_𝑙𝑜𝑜𝑝𝑠(𝑛) = 𝑔_𝑜𝑢𝑡𝑒𝑟𝑙𝑜𝑜𝑝 (𝑛) + 𝑔_𝑚𝑖𝑑𝑑𝑙𝑒𝑙𝑜𝑜𝑝 (𝑛) + 𝑔_𝑖𝑛𝑛𝑒𝑟𝑙𝑜𝑜𝑝 (𝑛) - 𝑔_𝑙𝑜𝑜𝑝𝑠(𝑛) = 1 + 2𝑛 + 𝑛 + 2𝑛² + 19𝑛² - 𝑔_𝑙𝑜𝑜𝑝𝑠(𝑛) = 21𝑛² + 3𝑛 + 1 Step 5: The Big-Oh notation Since the array computation in the inner loop, the only place where computations are done can be considered a constant said we called ‘c’, then the number of times that computation will be is executed is 𝑔_𝑖𝑛𝑛𝑒𝑟𝑐𝑜𝑚𝑝 = 9𝑐𝑛². With 𝑔_𝑖𝑛𝑛𝑒𝑟𝑐𝑜𝑚𝑝(𝑛) = 9𝑐𝑛² then the asymptotic complexity is 𝑂_𝑖𝑛𝑛𝑒𝑟𝑐𝑜𝑚𝑝(𝑛²). Justification: 9𝑐𝑛² with c being a constant ≤ (9𝑐)𝑛² = 𝑐𝑛². By the definition of the Big-Oh notation, 𝑂_𝑖𝑛𝑛𝑒𝑟𝑐𝑜𝑚𝑝(𝑛²). In other words, we can ignore the array computations in terms of time complexity analysis because the computations within the inner loop are independent of “n”, meaning that the computations in the inner loop, in the context of the time complexity, are constant and are ignored by the Big-Oh nation. The time complexity of the loops is 𝑂_𝑙𝑜𝑜𝑝𝑠(𝑛²): with 𝑔_𝑙𝑜𝑜𝑝𝑠(𝑛) = 21𝑛² + 3𝑛 + 1 then the asymptotic complexity is 𝑂_𝑙𝑜𝑜𝑝𝑠(𝑛²) Justification: 21𝑛² + 3𝑛 + 1 ≤ (21+3+1)𝑛² = 𝑐𝑛², for 𝑐 = 25, when when 𝑛 ≥ 𝑛₀ = 1. By the definition of the Big-Oh notation. The overall complexity of the algorithm is 𝑂(𝑛²) Justification: With 𝑂_𝑙𝑜𝑜𝑝s(𝑛²), 𝑔_𝑙𝑜𝑜𝑝s(𝑛) = 𝑛² and 𝑂_𝑖𝑛𝑛𝑒𝑟𝑐𝑜𝑚𝑝(𝑛²), 𝑔_𝑖𝑛𝑛𝑒𝑟𝑐𝑜𝑚𝑝(𝑛) = 𝑛² then 𝑛² + 𝑛² = 2𝑛² = 𝑐𝑛², for c=2. By the definition of the Big-Oh notation, the overall complexity of the algorithm is 𝑂(𝑛²) . Therefore The order of the algorithm is 𝑂(𝑛²) In conclusion, the computations within the inner loop are independent of the input ‘n’, meaning that the computation in inner loop, in the context of the time complexity is constant. Since this is the only place where the actual computations occur, we can ignore it in terms of time complexity analysis. The order of the algorithm is 𝑂(𝑛²) indicating that time complexity is quadratic. 𝑂(𝑛²) is a quadric type time complexity.  Exercise 3 Consider two programs, A and B. Program A requires 1000 x 𝑛² operations and Program B requires 2n operations. For which values of n will Program A execute faster than Program B? The number of operations for program A is 𝑔_𝐴(𝑛) = 1000𝑛² where 𝑛 is the number of inputs. The number of operations for program B is 𝑔_𝐵(𝑛) = 2𝑛 where 𝑛 is the number of inputs. When comparing algorithms a primitive operation corresponds to 1 unit of time, 𝑔𝐴(𝑛) and 𝑔𝐵(𝑛) can be defined as a growth rate where the out is the duration and the input is the number of operations ‘n’. Therefore to find the ‘n’ values where Program A executes faster than Program B, we need to identify where 𝑔_𝐴(𝑛) < 𝑔_𝐵(𝑛). 𝑔_𝐴(𝑛) < 𝑔_𝐵(𝑛) 1000𝑛² < 2𝑛 𝑛²/𝑛 < 2/1000 𝑛 < 0.002 The values of ‘n’ where Program A executes faster than Program B are between -∞ and 0.002 excluded, (-∞,0.002). However, operations can be defined only as whole numbers or integers, ‘n’ the number of operations can be a decimal, it can be defined only as an integer Therefore, Therefore, Program A will never run faster than Program B. Another method that provides a more accurate representation of the relationship is to use the time complexity of the algorithms to compare the algorithms. The time complexity of Program A is 𝑂_𝐴(𝑛²) Justification: 1000𝑛² ≤ (1000)𝑛² = 𝑐𝑛², for 𝑐 = 1000, when 𝑛 ≥ 𝑛₀ = 1 The time complexity of Program B is 𝑂_𝐴(𝑛) Justification: 2𝑛 ≤ (2)𝑛 = 𝑐𝑛, for 𝑐 = 2, when 𝑛 ≥ 𝑛₀ = 1 To find the value of ‘n’ where Program A executes faster than Program B, we need to identify where 𝑂_𝐴(𝑛²) < 𝑂_𝐵(𝑛). 𝑛² < 𝑛 => 𝑛² 𝑛 < 1 => 𝑛 < 1 this is not possible when ‘n’ is an integer and 𝑛 ≥ 𝑛₀ = 1 No values of ‘n’ exist where Program A executes faster than Program B.  Exercise 4 Consider an array of length "n" containing unique integers in random order and in the range 1 to n + 1. For example, an array of length 5 would contain 5 unique integers selected randomly from the integers 1 through 6. Thus the array might contain 3 6 5 1 4. Of the integers 1 through 6, notice that 2 was not selected and is not in the array. Write Java code that finds the integer that does not appear in such an array. Explain the Big-Oh in your code. Note that the expected sum of integers in array length from 1 to 𝑛 + 1 is:  The Java code:  /** * Finds the missing number * * @param array The array of unique integers with one integer missing. * @param n The length of the array * @return The missing integer */ public static int missingNum(int[] array, int n) { // The expected sum of integers from 1 to n+1 int expectedSum = (n + 1) * (n + 2) / 2; int actualSum = 0; // The actual sum of the numbers in the array for (int i = 0; i < n; i++) { actualSum += array[i]; } return expectedSum - actualSum; } Step 1: Understanding the code -   The ‘expectedSum’ variable initializes to ‘(n + 1) * (n + 2) / 2’. -   The ‘actualSum’ variable initializes to ‘0’. -   The ‘array’ loop iterates through from the ‘0’ to the ‘n’ exclusive. Note that all the variables and constants in the loop are integers. o   The ‘i’ variable initializes to ‘0’. o   The ‘i’ variable is compared to ‘n’, the loop iterates as long as  ‘i’ is lesse than ‘n’. o    The ‘i’ variable is incremented by ‘1’, this means that the ‘i’ is compared to ‘n’ before being incremented. o   The ‘atualSum’ variable is incremented by the value of the ‘arrau[i]’ variable in each iteration of the for-loop until the ‘i’ is equal to or more than ‘n’. -   The function returns  ‘expectedSum – actualSum’ Step 2:  Counting the number of iterations in the array loop -    The array loop will iterate as long as  ‘i’ is less ‘n’, and it is post-incremented by ‘1’, starting at ‘i = 0’. If  is the number of iterations: Thus, the loop iterates 𝑛 times. Step 3: Number of primitive operations 𝑔(𝑛) per instruction - The ‘expectedSum’ variable initializes to ‘0’, it is executed only once, 𝑔₁(𝑛) = 1. - The ‘actualSum’ variable initializes to ‘‘(n + 1) * (n + 2) / 2’, it is executed only once, 𝑔₂(𝑛) = 1. - The number of primitive operations for the array loop is: o The ‘i’ variable initializes to ‘0’ by the for-loop statement this is executed only once, 𝑔₃(𝑛) = 1. o The ‘i’ variable is compared to ‘n’, this is executed in each iteration of the loop, and the number of iterations is 𝑘 = 𝑛, then 𝑔₄(𝑛) = 𝑛. o The ‘i’ is post-incremented by ‘1’, this is done after each iteration of the loop and the comparison of ‘pass’ to ‘n’ returns true, the number of iterations is 𝑘 = 𝑛, then 𝑔₅(𝑛) = 𝑛. o The ‘actualSum’ is incremented with the value of ‘array[i]’ variable in each iteration of the for-loop until the ‘i' is equal to or more than ‘n’. The number of times this instruction will be executed is the number of iterations k = n, then 𝑔₆(𝑛) = 𝑛 The total of primitive operations for the outer loop is: 𝑔_𝑙𝑜𝑜𝑝(𝑛) = 𝑔₃(𝑛) + 𝑔₄(𝑛) +𝑔₅(𝑛) + 𝑔₆(𝑛) = 1 + 𝑛 + 𝑛 + 𝑛 = 1 + 3𝑛 𝑔_𝑙𝑜𝑜𝑝(𝑛) = 1 + 3𝑛 - The function returns ‘expectedSum – actualSum’, this instruction is performed only once, the 𝑔₇(𝑛) = 1 Step 4: The total of primitive operations  𝑔(𝑛) = 𝑔₁(𝑛) + 𝑔₂(𝑛) + 𝑔_𝑙𝑜𝑜𝑝(𝑛) + 𝑔₇(𝑛) 𝑔(𝑛) = 1 + 1 + 1 + 3𝑛 + 1 = 4 + 3𝑛  𝑔(𝑛) = 4 + 3𝑛  Step 5: The Big-Oh notation The Big-Oh notation is O(n). Justification: 4 + 3𝑛 ≤ (4 + 3)𝑛 = 𝑐𝑛, for 𝑐 = 7, when 𝑛 ≥ 𝑛0 = 1. By the definition of the Big-Oh notation, the overall complexity of the code is 𝑂(𝑛) . The Big-Oh notation of my code is 𝑂(𝑛). The Big-Oh notation 𝑂(𝑛) in my code indicates that the complexity of the code grows in a 1-to-1 proportional relationship with the size of the input, ‘n’, which is the size of the ‘actualArray’ array. In other words, the complexity of the code grows linearly with the size of the array ‘n’, this is known as linear complexity. For example, in terms of time complexity, as the size of the array gets larger, the time it takes to run the code also increases proportionally in 1-to-1 relationship. This is because the duration that it takes to iterate through each element in the loop is the most time-consuming part of the code and all other primitive operations are ignored by the Big-Oh notation, due to their minimal impact on the overall complexity of the code.

This article explains the fundamental concept of the Stack Abstract Data Type (ADT), its Last-In-First-Out (LIFO) principle, real-life applications such as browser history navigation and expression evaluation, and provides a basic Java implementation of a custom Stack. Alexander S. Ricciardi September 8th, 2024 In computer science, a Stack is a fundamental Abstract Data Type (ADT) that follows the Last-In-First-Out (LIFO) principle, which means that the last item added to the Stack is the first to be removed. The term stack comes from the analogy of a stack of plates in a spring-loaded dispenser, commonly found in cafeterias (Carrano & Henry, 2018). Where plates are pushed onto the top of the stack and popped off from the top, making the push and pop operations fundamental to the Stack ADT's functionality. The operation usually implemented in a Stack ADT are: Push (e): Adds a new element to the top of the stack. Pop (e): Removes and returns the top element of the Stack. Peek (e): Returns the top element without removing it. IsEmpty (): Checks if the Stack is empty. Clear (): Removes all elements from the Stack​ A real-life scenario where the Stack ADT is used is in web browser history navigation. For example, each time a user leaves a web page, the browser pushes the page URL onto the URL history Stack. When the browser’s "Back" button is clicked, the previous page's URL is popped from the top of the history Stack, and the current page’s URL is pushed onto another Stack, let's call it the URL forward Stack. Conversely, when the user clicks the "Forward" button, the current page’s URL is pushed onto the URL history stack, and the URL at the top of the URL forward stack is popped and displayed. A real-life scenario where Stack ADT is a mandatory choice is in algebraic expression evaluation, particularly when converting an infix algebraic expression to a postfix algebraic expression. In infix expressions, operators are placed between operands (e.g., A + B); this is the common way used by humans rather than by machine computing but it requires parentheses and precedence rules. On the other hand, in postfix expression, operators come after operands (e.g., A B +); there is no need for parentheses, and is easier for computers to evaluate using a Stack, it is solely based on the order of the operands and operators. In this scenario, the Stack ADT is perfectly suited to manage the order of operations. A stack is used to temporarily hold operators until their precedence and associativity are determined ensuring that the algebraic expression is evaluated in the correct order. This makes the Stack an efficient and essential ADT in such algorithms. Another mandatory application of a Stack ADT is in managing function calls in programming, particularly in environments that support recursion, such as the Java Virtual Machine (JVM) or C++ runtime environments. When a function is called, the function's local variables and return addresses are pushed onto the call Stack. This allows JVM, for example, to keep track of where to return in the program execution after the function execution is completed, particularly during recursive and nested function calls. Below is a simple Java program that mimics the basic functionality of the Java Stack memory. import java.util.EmptyStackException; // Custom Stack class public class MyLinkedStack { private Node top; private int size; // Node class to represent each element in the stack private static class Node { private T data; private Node next; public Node(T data) { this.data = data; } } public MyStack() { this.top = null; this.size = 0; } public void push(T data) { Node newNode = new Node<>(data); newNode.next = top; // set the next reference to the current top top = newNode; // make the new node the top of the stack size++; } public T pop() { if (isEmpty()) { throw new EmptyStackException(); } T poppedData = top.data; top = top.next; // remove the top node size--; return poppedData; } public T peek() { if (isEmpty()) { throw new EmptyStackException(); } return top.data; } public boolean isEmpty() { return top == null; } public int size() { return size; } } // Class with main method to test the stack class Main { public static void MimicJavaStackMemory(String[] args) { MyLinkedStack stack = new MyStack<>(); stack.push(10); stack.push(20); stack.push(30); System.out.println("Top element: " + stack.peek()); System.out.println("Stack size: " + stack.size()); System.out.println("Popped element: " + stack.pop()); System.out.println("Popped element: " + stack.pop()); System.out.println("Top element after popping: " + stack.peek()); System.out.println("Stack size after popping: " + stack.size()); } } Ouputs Top element: 30 Stack size: 3 Popped element: 30 Popped element: 20 Top element after popping: 10 Stack size after popping: 1 To summarize, a Stack is a fundamental Abstract Data Type (ADT) that follows the Last-In-First-Out (LIFO) principle, making it ideal for applications like browser history navigation and algebraic expression evaluation. It is also essential in managing function calls in programming, particularly in environments that support recursion. References: Carrano, F. M., & Henry, T. M. (2018, January 31). 6.1 Stacks. Data structures and abstractions with Java (5th Edition). Pearson.

This article explores the fundamental concepts of vectors, their mathematical properties, and their applications in computer graphics, particularly in transformations such as translation, scaling, and rotation within multidimensional Euclidean spaces. Alexander S. Ricciardi September 8th, 2024 Vectors are a fundamental component in geometry, and they are a crucial concept in Computer Science for science for performing operations in multidimensional spaces, they are used in fields like computer graphics, machine learning, and scientific computing to represent directions, implement transformations, optimize algorithms, and process data. In this post, I will define what a vector is and discuss its applications in graphic visualization. Mathematically a vector is characterized by magnitude and direction. In physics and mathematics, the vector is used to define a quantity with direction and magnitude. In a vector space, a mathematical structure formed by a collection of vectors, a vector is an object that can be added to other vectors and multiplied by scalars (real or complex numbers). Some characteristics of vector space are: v , u , and w are vectors α and β are scalars: Commutativity: u + v = v + u Associativity: ( u + v) + w = u + (v + w) Zero vector: There exists a zero vector 0 such that v + 0 = v Inverse elements of addition: For each vector v there exists a vector -v   such that v + (-v) = 0 Distributivity of scalar multiplication: a(u + v)=αu + αv   Distributivity of scalar multiplication: (α + β)v =αv + βv(a + b) Associativity of scalar multiplication: α(βv) = (αβ)v In affine space, a vector space with points, a vector can be defined as a directed line segment between any two points from one point to the other (Angle & Shreiner, 2020). They can be represented by a point-point notation in the form of v = P - Q , where v is the vector, P and Q are the points. The direction of the vector is from P to Q and its magnitude is the length between the two points.  Some characteristics of affine space are: α and β are scalars No origin: Affine spaces do not have a fixed point of origin. Point-Vector Operations: You can add a vector to a point to get another point, and subtract one point from another to get a vector. Affine Combinations: An affine combination of points is a weighted sum, a sum where the weights (a coefficient similar to a scalar) add up to 1. For example, the point P = αP ₁ + βP ₂  where α + β =1 , is an affine combination of points P ₁ and P ₂ .  In Euclidean space, a type of affine space, distances between points can be measured, angles between vectors can be also measured using the vectors’ dot product, and cartesian coordinates are used. Some characteristics of Euclidean space are: Distance: The distance between two points is determined by the Euclidean distance formula,. Angles: Angles between vectors are measured using the dot product. Cartesian Coordinates: Points in Euclidean space are represented using Cartesian coordinates. Orthogonality: Vectors are orthogonal (perpendicular) if their dot product is equal to 90 degrees. Dot Product: The dot product of two vectors measures the angle between them. Norm or Magnitude: The length (magnitude) of a vector is computed as the square root of the sum of the squares of its components. Transformation Operations: Computation of linear transformations such as translation, rotation, scaling, and reflection. A common example of an Euclidean space is R ⁿ ­. The 2D plane R² and 3D space R³ are often visualized using Euclidean space operations, making them ideal for applications in computer graphics, where vectors are used in modeling and rendering, they are used to determine object position, camera movements, and lightning calculation. One of the most useful applications of vectors is in transformations, where they are utilized for the following types of transformations : Translation: Moving objects in space by adding a translation vector to their coordinates. P' = P + T Where: P and P' are position vectors. T is a translation. Scaling: Resizing objects by multiplying their coordinates by scaling factors. P' = S ⋅ P Where: P and P' are position vectors. S is a scaling matrix, not a vector. Rotation: Rotating objects around an axis using rotation matrices derived from vectors. P′ = R ⋅ P Where: P and P' are position vectors. R is a rotation matrix, not a vector. Shearing and Reflection : are complex transformations that modify the shape and orientation of an object using various vector operations. Let's visit the concept of rotation about the y-axis. To perform this transformation we will need to use the following matrix (counterclockwise rotation): Where: Θ is the rotation angle (dictates the length of the rotation) Applying the rotation to point P (technically the point does not rotate it changes position following a circular path, this is because points are one-dimensional, they represent a location in a system). Where: 1 is the homogeneous coordinate, used for matrix transformations in 3D space. It converts the point 3D vector into a matrix that can be easily used for matrix calculation, particularly for translation transformation. The following video explains why it is used in graphic visualization Quick Understanding of Homogeneous Coordinates for Computer Graphics . Computing the rotation using the dot product: Where: P' is the location of the new point after applying the rotation about the y-axis, notice that the value of y did not change only the x and z values did. Below is the representation of a 2D made of two independent components, the “I” shaped object and the circles, the object is the logo for my Blog website and GitHub page. Note that the 'I' shape and the circles rotate about the z-axis in 3D (if the object was a 3D object) and about a fixed point, the center of the object, in 2D in opposite directions. Once both components complete a 360° rotation, they reverse direction, switching from counterclockwise to clockwise and vice versa. The animation runs on an infinite loop. In summary, vectors are fundamental geometric concepts that are essential in computer science for operations in multidimensional spaces. They have applications in fields like computer graphics, machine learning, and scientific computing. In this post, I explored their applications in graphic visualization, including their role in transformations such as translation, scaling, and rotation within Euclidean space. References: Angel, E., & Shreiner, D. (2020). Chapter 4  Geometric object and transformation.  Interactive computer graphics. 8th edition . Pearson Education, Inc. ISBN: 9780135258262 Miolith (2023, December 3). Quick understanding of homogeneous coordinates for computer graphics [Video]. YouTube. https://www.youtube.com/watch?v=o-xwmTODTUI&t=134s

This article explains the differences between physical and logical memory, addresses, and various memory allocation methods, including fixed partitioning, dynamic partitioning, and the buddy system, in operating systems. Alexander S. Ricciardi July 5th, 20243 In Operating Systems (OS), physical and logical memory  refer to distinct concepts related to the actual storage and management of data, while physical and logical addresses  relates to how the system locates and accesses that data. In simple terms, a memory is a physical place where the data is stored, and an address is the memory-address of the data stored in a register. Registers are commonly referred to as a type of computer memory built directly into the processor or Central Processing Unit (CPU) that is used to store and manipulate data during the execution of instructions (Hopkins, 2023). Memory is an essential component of a computer system's functionality. "Computer memory is organized into at least two levels, referred to as main memory and secondary memory" (Stallings, 2018, p. 315). Main memory is also called system memory or Random-Access Memory (RAM). RAM is volatile, meaning that it does not provide permanent storage, i.e., if your turn a computer off, the data stored in the computer RAM will be lost. Moreover, the CPU utilizes the RAM to store and quickly access data necessary to execute processes. Secondary memory , on the other hand, is slower than the RAM and it is mostly utilized as data long-term storage. However, second memory can also be utilized to store and access data necessary to execute processes, this concept is called virtual mememory (virtual RAM). To link the different concepts: Physical memory refers to the actual memory hardware, that is, the RAM. While it can also refer to secondary memory, for the purpose of this post, I will define it as the RAM. The logical memory, in the context of this post, can be defined as the CPU address register, which is where data logical addresses are stored. logical and physical addresses are sets of finite bits pointing to data stored in the RAM. The logical address, also called virtual address (not to be confused with virtual memory) is generated by the CPU during program execution. The set of all logical addresses generated for a program is referred to as the logical address space of the program. The physical address, on the other hand, points to a location in the RAM, and it is computed by the Memory Management Unit (MMU), which is a hardware component responsible for translating a logical address to a physical address. through the MMU. This safeguards or protects the physical memory from being directly accessed by a program. In other words, programs cannot directly access the data stored on the RAM, they access it indirectly. The set of all physical addresses corresponding to logical addresses is referred to as the physical address space. The figures below depict the relationship between the logical address, physical addresses, CPU, and MMU. (Silberschatz et al., 2018, Figure 9.5, Figure 9.2, Figure 9.1) Additionally, different mapping schemes exist to map the logical address space to the physical address space. The example above illustrates a simple MMU scheme that is a generalization of the base register scheme. The base register or relocation register stores a base value that is used to compute the physical address from the logical address. For example, in the first figure: The CPU generated a logical address value of 346. MMU generated a base address (Relocation Register) value of 14000 corresponding to the base value of the physical address space. The MMU translates the logical address into the physical address utilizing the base address, here 346 + 14000 = 14346. In summary, the CPU generates logical addresses and the MMU translates them into physical addresses to access the data stored in the physical memory. How is the RAM partitioned to store data? Operating Systems use different methods of allocating memory contiguously. Methods such as fixed partitioning, dynamic partitioning, and the buddy system. These methods allocated memory (RAM), this is done contiguously, meaning that each computing process is assigned a single block of memory that is adjacent to other process blocks. This ensures efficient utilization of memory and reduces fragmentation (Contiguous Memory Allocation, n.d.). (Images from Stallings, 2018, p. 321) Not contiguous blocks are also referred to as fragmented blocks. Fixed partitioning characteristics: The size of the block is equal for all processes. The size is determined when the system is started up and remains the same until the system is shut down. Each process that is loaded into memory is assigned to a partition. If a process is larger than a single partition, it must be divided into smaller pieces that fit into separate partitions. One downside to fixed partitioning is the potential for memory waste, known as internal fragmentation. This happens when any program, no matter how small, occupies an entire partition. This can cause internal fragmentation. Since the number of partitions is fixed, the number of processes that can be loaded into memory at the same time is limited by the number of partitions. Dynamic partitioning characteristics: The size of the partition isn't fixed. When a process needs to be loaded into memory, a partition just large enough to hold the process is allocated. Often results in more efficient use of memory because it minimizes internal fragmentation. Since each partition is just large enough to hold its process, there's less unused space within each partition. Despite reducing internal fragmentation, dynamic partitioning can lead to a problem called external fragmentation. This occurs when free memory is broken into small, non-contiguous blocks over time. Even if there is enough total free memory to accommodate a process, it may not be able to be allocated if the free memory isn't contiguous. To deal with external fragmentation, a process called compaction may be used. This involves shifting the processes in memory to make all the free memory contiguous. However, compaction can be a resource-intensive task. It requires efficient algorithms to allocate and de-allocate memory. The most common of these are the "first-fit" and "next-fit" algorithms, which each have their own trade-offs in terms of memory utilization and allocation speed. The buddy system Characteristics: It is a mix of the fixed and dynamic partitioning methods Memory is divided into partitions of different sizes, but each size is a power of 2. For example, starting with a block of size 1024KB, it can be divided into smaller "buddy" blocks of sizes 512KB, 256KB, 128KB, 64KB, 32KB, 16KB, 8KB, 4KB, 2KB, and 1KB. When a process requests memory, the system checks for a free partition of the exact size requested. If a partition of the exact size doesn't exist, the system splits a larger partition in half (and continues splitting if necessary) until it has a partition of the correct size. When memory is freed, the system checks if the "buddy" of the freed partition (the adjacent partition of the same size) is also free. If it is, the system combines the two partitions into a larger partition of the next power of 2 size. This combining (or coalescing) continues until the system can't combine the freed partition with its buddy. The Buddy System offers a good compromise between efficient use of memory and reduction of fragmentation. It's more efficient than fixed partitioning because it can handle processes of different sizes more flexibly. And it reduces the external fragmentation that can be a problem with dynamic partitioning by merging free memory blocks. The buddy system, however, has its drawbacks. One of these is overheads is involved splitting and combining blocks of memory. In conclusion, physical and logical memory - physical and logical addresses play essential roles in how an OSs manages data storage and access. Physical memory refers to the actual hardware (RAM). On the other hand, logical memory is an abstraction for process execution. The Memory Management Unit (MMU) translates logical addresses into physical addresses. Additionally, memory allocation methods like fixed partitioning, dynamic partitioning, and the buddy system help utilize to manage RAM usage and minimize fragmentation. References: Afteracademy (2020, March 30). What is the difference between logical and Physical Address WRT operating system? AfterAcademy . https://afteracademy.com/blog/what-is-the-difference-between-logical-and-physical-address-wrt-operating-system/ Contiguous Memory Allocation (n.d.).   Online Courses and eBooks Library . https://www.tutorialspoint.com/contiguous-memory-allocation#:~:text=Contiguous%20memory%20allocation%20is%20a,or%20adjacent%20to%20each%20other . Hopkins, J. (2023, May 24). What is a register in a CPU and how does it work? Total Phase Blog . https://www.totalphase.com/blog/2023/05/what-is-register-in-cpu-how-does-it-work/ Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts [PDF]. Wiley. Retrieved from: https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdf   Stallings, W. (2018). Operating Systems: Internals and design principles . Pearson.

This article discusses the importance of establishing ethical guidelines that both promote the advancement of AI technologies and ensure their safe and responsible implementation, highlighting the need for integrating ethical principles directly into AI systems and fostering a development culture that prioritizes safety and societal well-being. Alexander S. Ricciardi March 25th, 2024 Since the release of the chatbot ChatGPT, Artificial Intelligence (AI) technologies have been a feature of the news, suddenly bringing awareness to the technologies’ potential to revolutionize how people live and work. Additionally, the rapid exponential advancements and growth of these technologies have also sparked fears of misuse, loss of control, the risk of human extinction, and an intense debate about the need for guidelines to ensure their safe and ethical development and implementation. There are also concerns about the feasibility of establishing guidelines that simultaneously promote advancements in AI technology and safeguard society's safety and well-being, with some advocating for severe restrictions on these technologies. However, rather than implementing a fallacy of draconian restrictions or pauses, it is both feasible and critically important to establish guidelines that promote AI technological advances and development while ensuring their implementation is not harmful to individuals, communities, and society. This is possible by advocating for the integration of ethical principles directly into AI systems through approaches like Constitutional AI (CAI) and AI Ethical Reasoning (AIER), by establishing an AI developers' culture that prioritizes safety and ethics, and by establishing a governmental agency that aims to guide the society through the economic and social changes that AI advancements are inevitably bringing. The Question Is it feasible to establish AI guidelines that promote advancement in AI technologies, while ensuring that their implementation is not harmful to society? It is possible by advocating for the integration of ethical guidelines directly into the AI systems themselves, rather than imposing limitations on AI advancements. For instance, Arbelaez Ossa et al. (2024) in their quantitative study “Integrating Ethics in AI Development: A Qualitative Study” explore the best ethical approach to aligning AI development with healthcare needs. They interviewed 41 AI experts and analyzed the data using reflective thematic analysis. A thematic analysis is qualitative research used to identify, analyze, and report patterns (themes) within data. Their findings indicated that when developing an AI, especially for healthcare, AI developers need to consider the ethics, goals, stakeholders, and the specific situations where AI will be used, rather than the technology itself. This approach promotes AI advancements and ensures that ethical guidelines are aligned with the needs and requirements of different healthcare systems. Table 1 GPQA Benchmark Note : Benchmark evaluation results for GPQA. From Constitutional AI: Harmlessness from AI Feedback, by Bai et al., 2022, Table 8. Additionally, a new concept is emerging in AI development that promotes advancement in AI technologies with the integration of ethical guidelines directly into the AI systems. The article "Constitutional AI: Harmlessness from AI Feedback" (Bai et al., 2022) from Anthropic introduces a new approach called Constitutional AI or CAI for training AI systems to be helpful, honest, and harmless using a combination of supervised learning and reinforcement learning techniques. In other words, the CAI approach integrates ethical guidelines directly into the AI systems training. Anthropic is an American AI startup company, founded by former members of OpenAI. Anthropic’s last state-of-the-art model Claude-3, which was trained with the CAI approach, surpasses ChatGPT-4 and Google Gemini models in all reasoning, math, coding, reading comprehension, and question-answering benchmarks as well as in Graduate-Level Google-Proof Q&A benchmark (GPQA), as illustrated in Table 1. GPQA is a dataset designed to evaluate the capabilities of Large Language Models (LLMs) as well as the effectiveness of oversight mechanism frameworks, which are processes that ensure AI systems operate safely, ethically, and according to guidelines and societal norms. Furthermore, AI systems can be trained to reason more efficiently, consequently avoiding the generation of potentially biased or harmful content. Zelikman et al. (2024) argue that their generalized Self-Taught Reasoner (STaR) algorithm can train language models (LMs) to reason more efficiently by using a single thought training process. They describe this approach as “applying STaR ‘quietly’, training the model to think before it speaks” (Zelikman et al. 2024, p2) or Quiet-STaR. Figure 1 visualizes this Quiet-STaR single thought training process. They apply Quiet-STaR to Mistral 7B LLM, improving considerably the reasoning abilities of the Mistral model. Nonetheless, it can be argued that integrating the Quiet-STaR technique with the Anthropic CAI approach could teach AI systems to reason more efficiently, consequently avoiding the generation of potentially biased or harmful content, this can be referred to as AI Ethical Reasoning or AIER. Therefore, integrating Arbelaez Ossa et al. quantitative study, the Anthropic CAI, and the Quiet-STaR approaches into the development of AI systems can significantly diminish the potential for the systems to generate biased or harmful content, making their implementation safer. This demonstrates that it is feasible to promote advancement in AI technologies while ensuring that their implementation is not harmful to society. However, many argue that it is not possible, believing that the risk posed by AI is so significant that it is crucial to establish guidelines that limit or even pause advancements in AI technologies. Figure 1 Quiet-STaR Note: Visualization of the Quiet-STaR algorithm as applied during training to a single thought. From Quiet-STaR: Language models can teach themselves to think before speaking, by Zelikman et al., 2024, Figure 1 The Counterargument The Future of Life Institute (2023) in its article “ Policy Making in the Pause ” argues for the implementation of robust third-party auditing and certification for specific AI systems and a pause on AI development until AI labs “have protocols in place to ensure that their systems are safe beyond a reasonable doubt, for individuals, communities, and society.” (Future of Life Institute, 2023, p4). The authors conclude by arguing that the dangers of unchecked AI advancements can result in substantial harm, in both the near and longer term, to individuals, communities, and society. On the other hand, robust third-party auditing and certification of AI research and development can achieve responsibly developed AI that benefits humanity. At first glance, this approach seems to be similar to one proposed by Arbelaez Ossa et al. and the Constitutional AI method, which is to ensure that AI development is responsible and beneficial to society. However, the Future of Life Institute's proposal advocates for a pause in AI development until safety protocols are in place, while the other approaches are more focused on integrating ethical guidelines directly into the AI systems themselves without necessarily limiting or pausing advancements in AI technologies. In other words, Future of Life Institute's approach does not promote AI advancements but instead advocates for limiting it. This approach is also shared by others, the author of the Time article “Exclusive: U.S. Must Move ‘Decisively’ to Avert ‘Extinction-Level’ Threat From AI, Government-Commissioned Report Says” (Perrigo, 2024) reports that Gladstone AI, an AI startup commission by the U.S. Government to conduct an AI risk assessment, warns that the advances in AI, more specifically in Artificial General Intelligence (AGI) pose urgent and growing risks to national security, potentially causing an extinction-level threat to the human species. Gladstone AI recommends making it illegal to train AI models above a certain computing power threshold, requiring government permission for AI companies to train and deploy new models, outlawing open-source AI models, and severely controlling AI chip manufacture and export. This approach goes further than the Future of Life Institute approach in limiting and controlling AI development by arguing for draconian government oversight over the AI industry. However, the Future of Life Institute and Gladstone AI proposal are a case of "shutting the stable door after the horse has bolted." Not only the approaches are impossible to implement worldwide but can also be extremely harmful to the future well-being of Western nations. The Fallacy “Shutting the stable door after the horse has bolted” is a fallacy that occurs when suggesting a solution for an issue that has already occurred or is currently occurring. In the context of AI development, arguing for strict regulations or a complete halt to AI research and development when advanced AI systems are already being developed and deployed by various organizations worldwide is an example of this fallacy. The current state of AI development is rapidly advancing, and ignoring this reality while arguing for potentially ineffective or late measures might not effectively address the risks posed by AI. For instance, on March 12, 2024, Cognition AI launched the first fully autonomous AI agent, Devin. Devin is an AI system autonomously capable of fully developing software, training other AI models, and editing its own codebase. (Vance, 2024) Moreover, implementing such restrictions poses potential risks for Western nations to miss the Artificial Superintelligence (ASI) ‘train,’ especially if other countries, like China and Russia, do not follow suit. Bostrom, a renowned philosopher at the University of Oxford and the director of the Future of Humanity Institute said in a Big Think interview, “I think there is a significant chance that we'll have an intelligence (AI) explosion. So that within a short period of time, we go from something that was only moderately affecting the world, to something that completely transforms the world.” (Big Think, 2023, 02:05). The illustration by Tim Urban, see Figure 2 “ANI-AGI-ASI Train,” (Urban, 2015) supports well Bostrom’s argument. Furthermore, the illustration acts as a metaphor for the rapid advancement of AI technologies and the possibility that if Western nations fail to keep pace with these advancements due to overly restrictive regulations will fall behind nations such as China and Russia. For instance, in a two-year study, the U.S. National Security Commission on Artificial Intelligence warned "China is already an AI peer, and it is more technically advanced in some applications. Within the next decade, China could surpass the US as the world's AI superpower." (Sevastopulo, 2021, p1). Therefore, the best approach for Western nations to remain competitive in the field of AI is to adopt and combine the Arbelaez Ossa et al. and Anthropic CAI approaches with AI reasoning techniques such as Quiet-STaR, which promote AI advancements while ensuring their implementation is not harmful to society by directly integrating ethics and ethical reasoning capabilities into the training and development of the AI models. Figure 2 The ANI-AGI-ASI Train Note: The illustration is a metaphor that depicts the rapid advancement of AI technology, progressing from Artificial Narrow Intelligence (ANI), which is less intelligent than human-level intelligence, to Artificial General Intelligence (AGI), which is equivalent to human-level intelligence, and to Artificial Super-Intelligence (ASI), which surpasses human intelligence. From The AI revolution: The road to superintelligence Part-2, by Urban, 2015.   The Solutions To establish ethical guidelines that promote the advancement of AI technologies while ensuring its implementation is not harmful to society, it is essential to build on Bai et al. (2022) concept of Constitutional AI by integrating ethical guidelines directly into the training of AI systems. Additionally, as suggested by Arbelaez Ossa et al. (2024), AI developers should prioritize ethics, goals, stakeholders, and the specific contexts in which AI will be deployed. To achieve this, several strategies are proposed. For instance, in a Senate subcommittee hearing, Altman, CEO of OpenAI, proposed creating an agency to issue licenses for developing large-scale AI models, establish safety regulations, and test AI models before public release, and Montgomery, IBM's chief privacy and trust officer, advocated for a precision regulation approach that focuses on specific AI uses rather than regulating the technology itself. (Kang, 2023) Ng renowned computer scientist in AI, founder of DeepLearning.AI , and adjunct professor at Stanford University (Stanford HAI, n.d.), in his lecture on July 26, 2023, at Stanford University dismisses concerns about AI posing an existential threat to humanity, arguing that AI development will be gradual and manageable (Stanford Online, 2023). In other words, Ng's approach to AI regulations is not to regulate AI technologies directly but to manage their implementation gradually. This approach is similar to the approach proposed by Webb, the founder of the Future Today Institute and professor of strategic foresight at the NYU Stern School of Business. During the 2024 South by Southwest Conference (SXSW), she suggested the establishment of a U.S. Department of Transition. (SXSW, 2024) The department would be tasked with assessing and forecasting how the advancements in AI technologies, connected devices, and biotechnology would affect different sectors of the economy. In other words, the department would assist the country's economy in adapting to the rapid technological advancements driven by the emergence of AI. All these strategies share the common goal of establishing ethical guidelines that promote the advancement of AI technologies while ensuring their implementation is not harmful to individuals, communities, and society. The only sensible solution to implementing the approach is adopting minimal AI technology development regulatory guidelines, with the government acting as both a facilitator in the advancement of AI technologies and as a gatekeeper ensuring that its implementations are not harmful to society. This approach is only possible by applying the principles of Constitutional AI in AI development, and by establishing an AI developers' culture that prioritizes efficient and safe AI reasoning capabilities in line with ethics or AIER, goals, stakeholders, and the specific context where each AI system would be deployed. Conclusion While the rapid advancement of AI technologies has raised concerns about the potential risks that it poses to society, it is not only possible but essential to establish guidelines that promote the development and advancement of AI technologies while ensuring their implementation is not harmful to individuals, communities, and society. This can be done by integrating ethical principles directly into AI systems through approaches like Constitutional AI and AI Ethical Reasoning by fostering an AI development culture that prioritizes ethics, stakeholder considerations, and context-specific deployment, rather than implementing severe restrictions or pauses on AI advancements. Furthermore, oversight and regulation of AI require a nuanced approach, especially for Western nations, to avoid missing out on the rapid advancements toward Artificial Superintelligence. This can be done by implementing gradually AI technologies and by establishing government agencies like the proposed U.S. Department of Transition with the main goal of guiding society through the economic and social changes that AI advancements are inevitably bringing. In this role, the government acts as both a facilitator of AI technology advancements and as a gatekeeper ensuring that their implementations are not harmful to society. Moreover, these measures must be put in place, now, as the rapid pace of AI advancement means that society cannot afford to wait, and substantial efforts should be made by the U.S. Government and AI developers to promote and support research on AI Ethical Reasoning. References Anthropic. (2024, March 4). The claude 3 model family: Opus, sonnet, haiku. Anthropic.  Retrieved from: https://www-cdn.anthropic.com/de8ba9b01c9ab7cbabf5c33b80b7bbc618857627/Model_Card_Claude_3.pdf Arbelaez Ossa, L., Lorenzini, G., Milford, S. R., Shaw, D., Elger, B. S., & Rost, M. (2024). Integrating ethics in AI development: a qualitative study.  BMC Medical Ethics ,  25 (1), NA.  https://link-gale-com.csuglobal.idm.oclc.org/apps/doc/A782196655/AONE?u=colstglobal&sid=bookmark-AONE&xid=e925a51dLinks to an external site. Bai, Y., Kadavath, S., Kundu, S., Askell, A., Kernion, J., Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKinnon, C., Chen, C., Olsson, C., Olah, C., Hernandez, D., Drain, D., Ganguli, D., Li, D. Tran-Johnson, E., Perez, E., … Kaplan, J. (2022, December 15). Constitutional AI: Harmlessness from AI feedback . ArXiv. https://doi.org/10.48550/arXiv.2212.08073 Big Think. (2023, April 9). Nick Bostrom on the birth of superintelligence [Video]. Big Think. https://bigthink.com/series/the-big-think  interview/superintelligence/?utm_source=youtube&utm_medium=video&utm_campaign=youtube_description Future of Life Institute. (2023, April 12). Policy making in the pause. Future of Live Institute . https://futureoflife.org/document/policymaking-in-the-pause Kang, C. (2023, May 16). OpenAI’s Sam Altman urges A.I. regulation in Senate hearing. The New York Times . https://www.nytimes.com/2023/05/16/technology/openai-altman-artificial-intelligence-regulation.html Perrigo, B. (2024, March 11). Exclusive: U.S. must move ‘decisively’ to avert ‘extinction-level’ threat from AI, government-commissioned report says. Time Magazine.   https://time.com/6898967/ai-extinction-national-security-risks-report/   Sevastopulo, D. (2021, March 3). China on track to surpass US as AI superpower, Congress told; Semiconductors. Financial Times , 4. https://link-gale-com.csuglobal.idm.oclc.org/apps/doc/A653575133/AONE?u=colstglobal&sid=bookmarkAONE&xid=042ad65a South by Southwest (SXSW). (2024, March 4). Amy Webb Launches 2024 Emerging Tech Trend Report | SXSW 2024 [Video]. SXWX. https://www.sxsw.com/news/2024/2024-sxsw-featured-session-amy-webb-launches-2024-emerging-tech-trend-report-video Stanford HAI. (n.d.). Andrew Ng . Stanford University. https://hai.stanford.edu/people/andrew-ng   Stanford Online. (2023, August 29). Andrew Ng: Opportunities in AI – 2023  [Video]. YouTube. https://www.youtube.com/watch?v=5p248yoa3oE Vance, A., (2024, March 12). Gold-medalist coders build an AI that can do their job for them. Bloomberg . https://www.bloomberg.com/news/articles/2024-03-12/cognition-ai-is-a-peter-thiel-backed-coding-assistant Urban, T. (2015, January 27). The AI revolution: The road to superintelligence Part-2.  Wait But Why . https://waitbutwhy.com/2015/01/artificial-intelligence-revolution-2.html Zelikman, E., Harik, G., Shao, Y., Jayasiri, V., Haber, N., & Goodman, N. (2024, March 14). Quiet-STaR: Language models can teach themselves to think before speaking . ArXiv. https://doi.org/10.48550/arXiv.2403.09629

This article explains double buffering in computer graphics, emphasizing its importance in preventing screen flickering and ensuring smooth, responsive application animations. Alexander S. Ricciardi August 25th, 2024 In computer graphic visualization, double buffering is a crucial technique that is used to address the issues of screen refresh rates and image rendering, particularly in applications where smooth animation and user interactions are essential. Within a graphics system, images are generated in the framebuffer, and the framebuffer's content—the image—is shown on an output device, usually a screen, which is managed by the window system or, in the case of WebGL, by the browser. Moreover, in single-buffer models, there is only one buffer—the color buffer in the framebuffer—for rendering and display (Angel & Shreiner, 2020). However, an output device like a screen has a fixed refresh rate that is independent of how frequently the graphics system updates the framebuffer. Thus, an issue may arise between the screen refresh rate and the graphics system updating the framebuffer, particularly when repeatedly clearing and redrawing an area of the screen, an operation often performed in animations. In other words, there is no synchronization between when new images are drawn into the framebuffer and when the framebuffer is redisplayed by the hardware. This may lead to situations where only part of the image is displayed, depending on the screen refresh rate. In most cases, this translates into an image flickering issue. Figure 1 Double Buffers Note: From Platform Integration Aspects: Framebuffer Concepts by Embedded Wizard (n.d.) Double buffering provides a solution to this problem by using two buffers. One buffer, called the front buffer, is used to display the current image, while the other, called the back buffer, is used to draw the next image. Once the image from the front buffer is displayed on the screen, the contents of the back buffer are transferred to the front buffer, and a new image is drawn in the back buffer, and so forth. This eliminates flickering and provides seamless animation. One application that heavily relies on double buffering is Virtual Reality. In VR applications, the user’s experience needs to be deeply immersive to be effective. In this scenario, double buffering is crucial as it helps maintain application responsiveness by preventing flickering and ensuring that the display is updated seamlessly (Lenovo, n.d.). This is especially important when users interact with the GUI, such as dragging windows or scrolling through content. The smooth updates provided by double buffering enhance the overall responsiveness and usability of the interface—another application where double buffering is video games. The user can also experience screen flickering and incomplete scene rendering. For instance, in a first-person shooter game without double buffering implemented, an incomplete scene can be displayed when the screen refreshes, revealing, for example, an enemy hiding behind a wall because the wall was not yet drawn (Nerd First, 2015). Double buffering prevents such issues, ensuring smooth and fully rendered images and enhancing the player experience. In conclusion, double buffering eliminates issues like flickering and incomplete scene rendering ensuring seamless animations. This technique is particularly vital in applications where user interaction is crucial, such as virtual reality and video games, where maintaining responsiveness and immersion is key to a successful interactive experience.  References: Angel, E., & Shreiner, D. (2020). Chapter 3 interaction and animation. Interactive computer graphics. 8th edition. Pearson Education, Inc. ISBN: 9780135258262 Embedded Wizard (n.d.). Platform integration aspects: Framebuffer concepts. Embedded Wizard. https://doc.embedded-wizard.de/framebuffer-concepts Lenovo (n.d). What is double buffering? Lenovo. https://www.lenovo.com/us/en/glossary/doublebuffering/?orgRef=https%253A%252F%252Fwww.perplexity.ai%252F Nerd First (April 23, 2015). Double buffering - Friday Minis 103 [Video]. Youtube. https://www.youtube.com/watch?v=f3tO_gyyLmk

This article describes the role of process states in Operating Systems, detailing how they manage resource allocation and processor time through transitions between Ready, Running, Waiting, and Terminated states. Alexander S. Ricciardi June 20th, 2023 Processes and their states are fundamental components of an Operating System playing a role in resource management. Moreover, process states have a crucial part in how processor time and processor resources are allocated and distributed. A process can be defined as:  “A program in execution. An instance of a program running on a computer. The entity that can be assigned to and executed on a processor. A unit of activity characterized by the execution of a sequence of instructions, a current state, and an associated set of system resources.” (Stallings, Chapter 3, 2018) In the context of the discussion, a process can be defined as a set of instructions that need to be executed by a processor. Secondly, a process state is the status of a process at a given time. They are four main processes in a Process Life Cycle: Ready to be assigned to a processor.  Running, a processor is executing the process. Waiting, the process is idle waiting for resources. Terminated, the process is removed from memory. The first state that I will discuss in this post is the Running state. A process is in the Running state when it is being executed by a processor, and the process will be executed until one of the following events happens: The process is completed. The process state will change from Running to Terminated.  The process is preempted by the OS due to a higher priority process coming into the ready state. The process state will change from Running to Ready. The process’s time slice has expired. The process state will change from Running to Ready. The process requested an I/O operation. The process state will change from Running to Waiting. The process is waiting for data from another process. The process state will change from Running to Waiting. A system call is requested. If the system call was requested by the process, the process state will change from Running to Waiting, If the system call was requested by another process (multiprogramming and/or multiprocessor environments) from Running to Ready. An exception happened, for example, the process is trying to open a nonexistent file. Depending on the exception the process state change from Running to Waiting or from Running to Terminated. The second state that I will discuss in this post is the Waiting state also called the Blocked state. A process is in a Waiting state when it is waiting for some event to occur (like user input or disk access), or it's waiting for a resource to become available. The process is idle and not being executed. The process will be in the Waiting state until one of the following events happens: Completion of an I/O request. The process state will change from Waiting to Ready. Receiving requested data (or signal) from another process. The process state will change from Waiting to Ready. A requested resource is available. The process state will change from Waiting to Ready. Furthermore, a process with a Waiting state status can only transition to a Ready state, in comparison a process in a Running state can transition to a Terminated, a Ready, or a Waiting state. The following chart flow depicts the transitions between the four main states Running, Terminated, Waiting, and Ready state and the New state. Figure 1 Process State Note: From Operating System Concepts by Silberschatz et al. (2018) In conclusion, processes and their state are fundamental components of an operating system used to manage resources, and process states play a crucial part in how processor time and processor resources are allocated and distributed. Additionally, there are four main states, which are Ready, Running, Waiting, and Terminated states. A process is in a Running state when is being run by a processor, and in a Waiting state when the process is waiting for resources or signals from another process. Furthermore, a process in a Waiting state can only transition to a Ready state, on the other hand, a process in a Running state can transition to a Terminated, a Ready, or a Waiting state.  References: Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts [PDF]. Wiley. Retrieved from: https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdf Stallings, W. (2018). Operating Systems: Internals and design principles. Pearson.