Data Structures and Algorithmic Design

How does one apply algorithmic design and data structure techniques in developing structured programs anyway?

      Let’s start off here with a definition, “Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language” (n.d.).  With that being said there are a few steps or categories to follow here while working on an algorithm design.  First there is search, sort, insert, update and delete.  In search we are “searching” for a particular item within the data structure.  Sort is when we want to sort items in a particular way, insert is simply inserting an item in that data structure, update is when we update an item within that data structure and obviously delete is when we remove an existing item(s) within the same data structure. 

     Once we work through all of that we then have certain characteristics of an algorithm.  Those characteristics are the following: Unambiguous, input, output, finiteness, feasibility and independence.  The algorithm should first be clear and unambiguous, the input is when it should have zero or more input types, the output is when it should have one or more well defined outputs and at least one should match.  Finiteness refers to an algorithm terminating after a finite number, feasibility is where they should be feasible with all available resources and independence referring to step by step directions and should be independent of any other programming code.   

     Now that we are clear on an algorithm let's look at the data structures side, “In the most general sense, a data structure is any data representation and its associated operations. Even an integer or floating-point number stored on the computer can be viewed as a simple data structure. More commonly, people use the term “data structure” to mean an organization or structuring for a collection of data items. A sorted list of integers stored in an array is an example of such a structuring” (Shaffer, 2013).  There are a few simple steps you can follow here as well.

1. Analyze the problem to determine the basic operations 2.  Quantify the resource constraints for each operation 
   3.  Select the data structure that best meets these requirements  

Are some algorithms and data structure designs better than others? 

      No I don’t think that some algorithms and data structure designs are better than others really because I would say that it depends on your use case.  Right because if you need to work on a binary tree than you might also utilize an algorithm as well.  I would really say here that it depends on the project that you are doing and that no algorithm is any better to use than any other and the same goes for the data structures as well. 

  

Discuss in the post how you would apply algorithmic design and data structure techniques in developing structured programs. 

     Applying algorithmic design and data structure techniques would be that we could first start with the algorithmic design as far as the techniques we can look at in three ways: Implementation method, design method as well as some other Classifications.  Implementation, “Recursion or Iteration: A recursive algorithm is an algorithm which calls itself again and again until a base condition is achieved whereas iterative algorithms use loops and/or data structures like stacks, queues to solve any problem. Every recursive solution can be implemented as an iterative solution and vice versa” (2020).  Serial or parallel or distributed algorithms and exact or appropriateness.  Classifications are the greedy method, divide and conquer and dynamic programming.  Lastly the others are randomizers and classification by complexities.   

  

     Data structures can be defined as, “Data Structures are a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently” (Mallawaarachchi, 2020).  Some of the common data structures are arrays, linked lists, stacks, the queue, hash tables, trees, heaps and finally graphs.  With that being said I’ve also included a few videos as well. 

References 

(2020, April 14). Algorithms Design Techniques. Retrieved July 21, 2020, from https://www.geeksforgeeks.org/algorithms-design-techniques/ 

Data Structures - Algorithms Basics. (n.d.). Retrieved July 21, 2020, from https://www.tutorialspoint.com/data_structures_algorithms/algorithms_basics.htm 

Mallawaarachchi, V. (2020, May 07). 8 Common Data Structures every Programmer must know. Retrieved July 21, 2020, from https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42 

Shaffer, C. A. (2013). Data structures and algorithm analysis (Links to an external site.) (3.2 ed.). Retrieved from http://people.cs.vt.edu/~shaffer/Book/JAVA3elatest.pdf

How to Install Java and Object-Oriented Design Principles

Greeting fellow coders.  Today we will be starting to learn Java by first installing Eclipse and then the required JDK (Java Development Kit) in order for you to start coding.  Below you will find a list of both links and helpful video tutorials that will get you started with learning to code in Java.  I will try to include tutorials in both Windows and Mac just in case.  Have fun and if there are other links or videos that I missed feel free to mention that in the comments.  Good luck.

https://www.tutorialspoint.com/java/java_quick_guide.htm
https://www.java.com/en/download/help/windows_manual_download.xml
https://www.java.com/en/download/help/mac_install.xml
https://docs.oracle.com/javase/10/install/installation-jdk-and-jre-macos.htm#JSJIG-GUID-2FE451B0-9572-4E38-A1A5-568B77B146DE

Some of the features of the object-oriented design principles can be found at: https://www.javaguides.net/2018/08/object-oriented-design-principles-in-java.html 
Another good site to define these principles is: https://medium.com/@halilozel1903/object-oriented-design-principles-9fbbb4f0f4da

Summary Blog Post for the Final Operating Systems Project

OS Theory Concept Map Final Summary Blog Post

Section 1: Categorize, describe, and give examples of the major functions of operating systems.

     Let's start here with, “The main task an operating system carries out is the allocation of resources and services, such as allocation of: memory, devices, processors and information. The operating system also includes programs to manage these resources, such as a traffic controller, a scheduler, memory management module, I/O programs, and a file system” (2020).  On top of that the operating system is also responsible for a great deal of things of the inner workings of the computer.  Here’s what an OS does on a regular basis: 

1.  Information and resource protection: The OS is responsible for all resources and information in the most protected way possible 
2. Accounting: Tracks the account of all the functionalities that take place and this is where all of the errors are stored after they occur 
3. Resource allocation: Ensures the proper usage of all the computers resources 
4. Error detection and handling: The OS detects any errors or bugs that occur during tasks and then decides on a countermeasure 
5. Manipulation of file systems: The OS makes a decision on the type of storage that is being used and then decides how the data should be manipulated 
6. Handling input/output operations: The inputs/outputs come from the many peripherals that we use like the keyboard or the mouse 
7. Program execution: The OS is responsible for the execution of all programs that take place within whether they are from the user or the system itself 
8. File management: These are organized into many directories for efficiencies sake, the ease of navigation through files and the usage as well 
9. Device management: Manages each device communication and their respective drivers as well 
10. Processor management: This decides the order in which processes have access to the processor and how much time each process will take and it also keeps track of the status as well 
11. Memory management: Manages primary memory and main memory 
12. Coordination between other software and users: Coordinates and assigns things like the compilers, assemblers, interpreters and other software to various users 
13. Security: Password protection 
14. Control of systems performance: Monitors the systems overall health to try to improve its performance 
15. Job accounting: Keeps track of time and resources used by various tasks and users 
16. Error detecting aids: Monitors the system for errors to avoid malfunctions 

Section 2:  Describe process, process state, and process control block, compare single- and multi-threaded motivations and models and describe the critical-section problem and explain a software solution that resolves this problem.

     First of all process is a program in execution and that program must execute in sequential order.  Process state is that as a program executes it changes states.  It goes from new to running to waiting to ready and finally to terminate.  The process control block is that information associated with each process.  This includes the process state, the programs counter, the CPU registers and scheduling information, memory management, accounting information, and finally the I/O status information.  

     Before we can compare threading, we should define what single threading and multi-threading motivations and models mean.  “Multithreading is a type of execution model that allows multiple threads to exist within the context of a process such that they execute independently but share their process resources. A thread maintains a list of information relevant to its execution including the priority schedule, exception handlers, a set of CPU registers, and stack state in the address space of its hosting process” (2017).  Multi-threading can also be quite complicated.  Whereas single threading means that the process contains a single set of execution instructions in one sequence.  It’s literally one command process at a time.  The identification of errors in the CPU is way easier in a single threaded processor than a multi-threaded processor.    

     Finally, the critical section problem is basically this, “The critical section is a code segment where the shared variables can be accessed. An atomic action is required in a critical section i.e. only one process can execute in its critical section at a time. All the other processes have to wait to execute in their critical sections” (Barnes, 2018).  The critical section software solution to resolve the problem could be a simple scheduler that would allow certain tasks to go in a sequence one right after another.  There are many types of schedulers so I guess it depends on your need: First in & First out, Priority scheduling, Round-robin, and Fixed priority preemptive scheduling just to name a few kinds that you could utilize here. 

Section 3: Outline the objectives and functions of memory management in operating systems and compare and contrast the physical address space with the virtual address space as they relate to different memory mapping techniques in operating systems.

     First of all let's start with a definition, “Memory management is the functionality of an operating system which handles or manages primary memory and moves processes back and forth between main memory and disk during execution. Memory management keeps track of each and every memory location, regardless of either it is allocated to some process or it is free. It checks how much memory is to be allocated to processes. It decides which process will get memory at what time. It tracks whenever some memory gets freed or unallocated and correspondingly it updates the status” (n.d.).  There are three types of addresses used in a program before and after memory is allocated: relative address, symbolic address and the physical address.  Symbolic address here means that it’s simply used in the source code, relative address means that the compiler turns symbolic address into relative address, and physical address means that the loader generates this at a time when the program is loaded into the main memory.  

     Logical address or virtual address space is generated by the CPU while the program is running.  The physical address space is actually a physical location of required data in memory.  The difference between logical (virtual) and physical address is that, “The basic difference between Logical and physical address is that Logical address is generated by CPU in perspective of a program whereas the physical address is a location that exists in the memory unit.  Logical Address Space is the set of all logical addresses generated by CPU for a program whereas the set of all physical address mapped to corresponding logical addresses is called Physical Address Space” (2019).  The logical address also doesn’t exist physically in the memory whereas despite it’s name the physical address is simply a location in the memory that can be accessed physically.  The user can view the logical address whereas they can’t view the physical address.  “The run-time mapping is from virtual to physical address is done by a hardware device called the memory-management unit (MMU) The memory-mapping hardware converts logical address into physical address” (Silberschatz, 2014, p. 330).
 

 

Section 4: Outline the objectives and functions of file systems management and the supported operations, including their reliability and performance, contrast different directory structures and describe different types of input/output devices, distinguishing between the hardware and software layers and summarizing the integration across I/O and memory components.  

     A file system has five major tasks that it needs to achieve in order to be successful. Those objectives are: Confirming the validity of a file's data, providing support for I/O in relation to the storage device, provide I/O support to users (single or multiple depending on the use and access permissions of the file), meet the requirements for users in terms of the operations with the data and optimizing performance of the file. It is important to note that the performance optimization is based on times for throughput and response.  File systems are responsible for naming files and put restrictions on the names of files. It may set limits such as length of the file name or allowed characters. A file system will also hold metadata about a file, which may include: date the file was created, the size of the file, date that the file was last accessed, access permissions for the file, and last backup/modification dates for the file. Though it is worth noting that in many instances the metadata may be stored separately from the file. Reliability and performance are heavily dependent on the type of files system.  

     Major file systems include: FAT, GFS, HFS, NTFS and UDF. FAT or the File Allocation Table is the file system used by the Windows Operating Systems. Originally designed in 1977, it is very reliable, but has issues with performance (speed). It is also subject to issues with scalability of more modern systems and servers. NTFS has been used for versions of Windows after the NT 3.1 OS version, and it made significant gains in terms of speed over the old FAT system. The GFT, or Global File System is used by favors of the Linux operating system. It is generally considered to be very nimble (high performance) as it allows direct access. In some flavors however the implementation has been left wanting in reliability, though this is not true of all versions of Linux and many are also reliable.  HFS, or the Hierarchical File System is most heavily associated with the Mac/Apple operating systems. HFS is generally regarded as a fair balance between reliability and speed. UDF is a platform neutral option that is used primarily by the makers of optical drives and DVD players. They are very fast but have not always been highly reliable and can lead to "skips" if the disk is damaged or the reader head encounters issues.

     A directory structure is, “A single directory may or may not contain multiple files. It can also have sub-directories inside the main directory. Information about files is maintained by Directories. In Windows OS, it is called folders” (n.d.).  The directory structures are as follows: Single-level directory, Two-level directory, Tree-structured directory, Acyclic-graph directory, and General graph directory.  Each directory structure does the same thing.  First it starts out by searching for a file, creating a file, deleting a file, listing a directory, renaming a file, and then finally traversing the file system.  A single directory is basically when all the files are contained in the same directory.  Therefore, each and every file within the directory needs its own unique name.  “In the two-level directory structure, each user has his own user file directory (UFD).  The UFD’s have similar structures, but each lists only the files of a single user.  When a user job starts or a user logs in, the systems master file directory (MFD) is searched.  The MFD is indexed by user name or account number, and each entry points to the UFD for that user” (Silberschatz, et al., 2014, pg. 493).
 
     In the tree-structured directory and the tree has a root directory and every file has its own unique name.  Along with each directory having a sub-directory and they have their own special system calls that are used to delete and create directories from there.  Acyclic-graph directory allows directories to share sub-directories and files and these could be in two different directories.  Sharing here means that if I were to delete something that my coworker worked on then that file would be deleted.  Whereas if we were to just copy that file and just my copy would be deleted, and my coworker would still have their copy.  Lastly is the general graph directory.  “In general graph directory structure, cycles are allowed within a directory structure where multiple directories can be derived from more than one parent directory.  The main problem with this kind of directory structure is to calculate total size or space that has been taken by the files and directories” (Ashish, 2019).    

     Different types of I/O devices for the computer are: keyboard, mouse, monitor, printer, and external speakers/headphones.  “The concept of input and output devices is much simpler than it sounds. These devices—most commonly associated with computers—are the basic peripheral hardware you use on a daily basis. Input hardware serves to send data into the computer's CPU, while output devices send data outwards to the user” (Johnson, 2020).

Section 5: Outline the goals and principles of domain- and language-based protection in a modern computer system and describe how an access matrix is used to protect specific resources a process can access and describe how security is used to protect programs, systems, and networks from threats.

     The goals of domain and language-based protection would be to first and foremost prevent malicious misuse of the system by users or programs.  To ensure that each shared resource is used only in accordance with the systems policies and to ensure that any errant programs cause the minimal amount of damage possible.  The principles of said protections would be primarily the principle of least privilege which will only allow enough privileges enough to perform a specific task.  There should be an Admin account and especially if you are sharing one computer every person gets their own account with one person being designated as the admin.  Lastly, we need to ensure that any and all failures of the system do the least amount of harm possible.   

     The access matrix, “Access Matrix is a security model of protection state in computer system. It is represented as a matrix. Access matrix is used to define the rights of each process executing in the domain with respect to each object. The rows of matrix represent domains and columns represent objects. Each cell of matrix represents set of access rights which are given to the processes of domain means each entry(i, j) defines the set of operations that a process executing in domain Di can invoke on object Oj” (2019).  Silberschatz, Galvin, & Gagne (2014) also add that, “The access matrix provides an appropriate mechanism for defining and implementing strict control for both static and dynamic association between processes and domains. When we switch a process from one domain to another, we are executing an operation (switch) on an object (the domain).  We can control domain switching by including domains among the objects of the access matrix” (p.609).

     Security is used in four levels: Human, Operating System, Network and Physical.  Let’s take a look at network security first since I was close to getting a certificate in this part.  “Network security is any activity designed to protect the usability and integrity of your network and data.  It includes both hardware and software technologies.  It targets a variety of threats.  It stops them from entering or spreading on your network.  Effective network security manages access to the network” (2020). With that being said there are many types of network security here: Firewalls, email security, antivirus and anti-malware software, network segmentation, access control, application security, data loss prevention, intrusion prevention systems, VPN’s (virtual private networks), web security, wireless security and mobile device security.   

     The human part we are talking about here are things like Phishing, dumpster diving, keylogging, Ransomware or botnets.  The operating system is the denial of service attacks and the physical part of this would be more like password locking your workstations or putting an actual physical lock and key on the machine rooms.  These can be your home security systems as well like ADT, NEST, SimpliSafe or Brinks home security.  

Summary 

     Operating systems enable processes to share and exchange information by, "A process is basically a program in execution. The execution of a process must progress in a sequential fashion. To put it in simple terms, we write our computer programs in a text file, and when we execute this program, it becomes a process which performs all the tasks mentioned in the program.  When a program is loaded into the memory and it becomes a process, it can be divided into four sections ─ stack, heap, text, and data" (Le, 2020).  When it executes it passes through different states and stages: Start, ready, running, waiting and terminate.  There's also something called an access control block which is basically a data structure that is supposed to keep track of the following processes: Processes state, process privileges, process ID, pointer, program counter, CPU registers, CPU scheduling information, memory management information, accounting information, and IO status information.  

     Main memory and virtual memory can solve memory management issues by, "Main memory, also called RAM, is the physical memory unit in the computer. Virtual memory also serves as computer memory, but is actually hard drive space acting as temporary storage for computer processes.  When the computer runs out of physical RAM, it uses virtual memory space set aside on the hard drive.  Main memory speeds up a computer, while virtual memory tends to transfer data at speeds much slower than physical RAM. Thus, you should only use virtual memory when absolutely necessary" (Huebsch, 2020).  

     The mechanisms necessary to control the access of programs or users to the resources defined by a computer system are outlined by the five types of access control.  There's mandatory access control (MAC), discretionary access control (DAC), role based access control (RBAC), rule based access control and attribute based access control.  The purpose would be, "The goal of access control is to minimize the risk of unauthorized access to physical and logical systems. Access control is a fundamental component of security compliance programs that ensures security technology and access control policies are in place to protect confidential information, such as customer data. Most organizations have infrastructure and procedures that limit access to networks, computer systems, applications, files and sensitive data, such as personally identifiable information and intellectual property" (Rouse, 2018).

     Finally I would use these concepts learned from this course more for my future courses here at Ashford rather than in my job because if I know how operating systems work I can have a better understand of the inner workings of the computer.  Especially as I move into the next few courses as I am taking data structures, database systems and computer networking.  Unfortunately I will never have a reason to use this at my job as I make sandwiches and put away orders but I am hoping to put this degree to good use and find a better job in the IT field after graduation. 

References 

(2019, August 14). Logical and Physical Address in Operating System. Retrieved from               https://www.geeksforgeeks.org/logical-and-physical-address-in-operating-system/ (Links to an external site.)

(2019, August 29). Access matrix in Operating System. Retrieved from https://www.geeksforgeeks.org/access-matrix-in-operating-system/
 
Ashish, V. (2019, December 5). Structures of Directory in Operating System. Retrieved from https://www.geeksforgeeks.org/structures-of-directory-in-operating-system/ 


Barnes, R. (2018). Critical Section Problem.  Retrieved from https://www.tutorialspoint.com/critical-section-problem

File Systems in Operating System: Structure, Attributes, Type. (n.d.). Retrieved from https://www.guru99.com/file-systems-operating-system.html (Links to an external site.)

Huebsch, R. (2020). Difference Between Virtual Memory & Main Memory. Retrieved June 22, 2020, from https://www.techwalla.com/articles/difference-between-virtual-memory-main-memory

  
Johnson, S. (2020).  Input & Output Devices. Retrieved from https://www.techwalla.com/articles/input-output-devices

Le, J. (2020, June 09). How Operating Systems Work: 10 Concepts you Should Know as a

Developer. Retrieved June 22, 2020, from https://medium.com/cracking-the-data-science-interview/how-operating-systems-work-10-concepts-you-should-know-as-a-developer-8d63bb38331f

 
Operating System - Memory Management. (n.d.). Retrieved from https://www.tutorialspoint.com/operating_system/os_memory_management.htm

Rouse, M. (2018, September 05). What is access control? - Definition from WhatIs.com. Retrieved June 22, 2020, from https://searchsecurity.techtarget.com/definition/access-control

 
Silberschatz, A., Galvin, P. B., & Gagne, G. (2014). Operating system concepts essentials (2nd ed.). Retrieved from https://redshelf.com/ (Links to an external site.) 

Singh, A.  (2020, February 4). Functions of Operating System. Retrieved from https://www.geeksforgeeks.org/functions-of-operating-system/ (Links to an external site.)

What is Multithreading? - Definition from Techopedia. (2017). Retrieved from                                      https://www.techopedia.com/definition/24297/multithreading-computer-architecture

What Is Network Security? (2020, May 4). Retrieved from https://www.cisco.com/c/en/us/products/security/what-is-network-security.html#~types