CST 370 Week 7 Learning Journal Entry

-

 Non-comparison Sorting, Dynamic programming, and the Greedy Technique

Non-Comparison Sorting

Non-comparison sorting is when sorting happens without comparing elements to each other. One method discussed this week is the counting sort. In counting sort, the frequency and distribution of elements are calculated for a set of inputs, and they are used to sort them in ascending or descending order. Below are the steps to complete a counting sort and an example of using a counting sort to place a set of integers in ascending order. 
  1. Create a table with a range of values and the frequency of each value. 
  2. Calculate the distribution of each element by adding up the frequency of the current element to the previous element.  
  3. Start with the last number in the original list of values and use the distribution to place an element in a specific position in an array
  4. Reduce the distribution for that element
  5. Repeat steps 3-4 for the next element in the list. 

Counting Sort

Dynamic Programming

Dynamic programming is a design technique that solves problems with overlapping subproblems. In order this design technique must have the following three steps: 
  1. Set up a recurrence relation that describes a solution to a problem with smaller sub-problems
  2. Solve the smaller sub-problems and record their solution in a table
  3. Use the table created in Step 2 to solve the original problem
Two algorithms discussed that are examples of dynamic programming are Warshall's algorithm and Floyd's algorithm. 

Warshall's algorithm consists of completing a transitive closure of a directed graph. A transitive closure is a table that describes vertices that one vertice can reach in a graph. To get the transitive closure, we need to create an adjacency matrix. Then, we need to use each row as an intermediate node (or connector) to determine if a path exists from one node to another. A '1' means that a path is present, and a '0' means a path is not present. If a path exists, the matrix will be updated. This is considered the recurrence part of the algorithm, and the computing matrix where each node is the intermediate node would be considered the smaller sub-problems. Once all nodes have been used as intermediate nodes, the end result will be the transitive closure matrix. An example of this can be seen below.
Warshall's Algorithm

Floyd's algorithm is very similar to Warshall's algorithm in terms of process, but instead of determining whether a path exists, it also takes into consideration the cost of the path. This algorithm is used to determine the shortest path between all pairs of vertices. In order to use this algorithm, we must have a weighted graph to create the adjacent matrix. In the matrix, we use 'infinity' symbols to represent that a path does not exist, and each node cannot go to itself as we are determining the shortest path between all pairs of vertices. We can complete the same process as mentioned in Warshall's algorithm, where each node is a determinate node, to develop a matrix that shows the shortest path between all vertices. An example of this process can be found below. 

Floyd's Algorithm

Greedy Technique

The Greedy technique is a technique different from dynamic programming. In this technique, we solve problems that have a sequence of choices where the choices are feasible, logically optimal, and irrevocable. This technique is used for optimal or fast approximation, such as finding the minimal spanning tree of a graph. When finding the minimal spanning tree of a weighted graph, we can use Prim's algorithm, which is a greedy technique. To apply the algorithm, we do the following: 
  1. Pick a starting vertex and list the remaining vertex in the form destination(starting, cost). If the destination has not been reached yet, we use destination(-, 'infinity'). 
  2. Add one vertex at a time to our tree vertices list based on which is the closest/shortest. 
  3. Nodes in the remaining tree list may need to be updated as we move down the list.
  4. stop when all vertices have been included. 
An example of the Prim's algorithm can be found below. 








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