CST 370 Week 3 Learning Journal Entry

-

 Brute Force Design Techniques and Divide-and-Conquer 

This week, we learned about different exhaustive search algorithms that used a Brute-Force design technique. Exhaustive search algorithms consider every possible case before coming to a conclusion.  The first algorithm discussed was the sequential search and matching algorithm. This algorithm was presented in the form of searching a string to find a pattern, such as the one below. In this algorithm, every character in a string is checked for the pattern until the end of the pattern is reached. The efficiency of this algorithm is dependent on the text and pattern. In the example below, there are 16 characters in the text and 4 characters in the pattern that we are looking for. Since we are considering all comparisons and cases, we should have 13 shifts and 52 comparisons. 


Another exhaustive search was conducted for combinatorics problems. An exhaustive search can be used to solve problems such as the Traveling Salesman Problem, Knapsack Problem, and the Assignment Problem. In a video for the week, we were tasked to complete the work for the Assignment problem, which gave the number of hours each person could complete a job. Our task was to use the exhaustive method to find out what job was assigned to what person so that all jobs were completed within the minimum number of hours. 
Job Table

Work for Assignment Problem

In addition to applying exhaustive searches to combinatoric problems, we also applied exhaustive searches to graph problems. The two algorithms presented depth-first search and breadth-first search. The depth-first search uses a stack and a mark array to determine a graph traversal. The stack is used to determine if a node has been visited. It is pushed in the stack when it is first visited and popped out when it is visited again. The breadth-first search uses a queue and a mark array. In this algorithm, the vertex and its neighbors are added to the queues and popped off when it is visited. Both depth-first and breadth-first traversal need to be processed alphabetically/numerically. See below for a visual on the difference between breadth-first and depth-first searches.








Comments

Post a Comment

Popular posts from this blog

CST 334 Week 1 Journal Entry

-
Image
Week 1: Introduction to Operating Systems One of the main topics that I learned about this week in CST 334 was operating systems and the role they play in running programs. Operation Systems have two main tasks. One of the tasks is to provide an abstraction layer to the user. This layer shields hardware information from the user, as the user should not have access to it. In addition to the layer of abstraction, the operating system also acts as a resource manager. It optimizes the use of the resources in a computer while allocating them to each program in a fair and equitable manner.  Both of these tasks are completed with the help of two modes provided by the CPU: kernel mode and user mode. While in user mode, the information about the hardware is hidden, and the user is provided an address space to do the intended job. This mode provides the user with access to user, application, and system programs. While in kernel mode, the administor has access to hardware and can change the m...
Read more

CST 311 Week 8 Journal Entry

-
Image
Operational Security and Overall Class Reflection This week, we learned about operational security. Two types of operational security methods were discussed: firewalls and intrusion detection systems. Firewalls help filter out packets passing from the Internet to an internal network. They are designed to prevent denial of service attacks and illegal modifications of internal data and only allow authorized access to a network. This can help keep the untrusted packets out of an internal network and let the trusted packets in.  There are three types of firewalls. First, there is a firewall with stateless packet filtering. This firewall decides which packet to forward or drop based on information such as IP address, TCP/UDP port numbers, ICMP message types, and TCP SYN and ACK bits. The firewall can be set so that packets with given information can be evaluated based on rules, such as ACK =0, and can be blocked from entering the internal network.  Second, there is a firewall with ...
Read more

CST 311 Week 5 Journal Entry

-
Image
Network Layer: Data Plane This week, we had an introduction to the network layer and learned about the data plane. The network layer has the responsibility of routing data from host to host via segments or packets. When sending data, segments are encapsulated into datagrams that hold the data, and the network adds header information to help with the routing process. Routers use the header information to keep the datagrams in order and determine their next hop. Receiving data is sent from the network to the transport layer and then to the appropriate application. In this process, the network is responsible for forwarding packets from one router to another until it reaches its destination and determining the route that needs to be taken to get packets from one place to its intended destination.  In the network layer, there are two planes: the data plane and the control plane. The data plane is local and functions in each router. When datagrams arrive at a router, the next port is det...
Read more