CST370 - Week 3

In this week's module, we covered brute force & exhaustive search, breadth-first search, depth-first search, and the master theorem. Brute force is a simple method of solving problems by just trying every possible outcome. For example, when considering the traveling salesman problem, just attempt all the possible paths and compare them to find which is the least cost. Breadth-first searches consider all the nodes at one level of a graph, before moving onto the next while depth-first searches involve following a path to its deepest point before coming back and checking other routes. Luckily, these were problems I'd practiced often in the path so I felt a little more confident with the material this week.

For the first part of the homework, we were to output a mark array after simulating a depth-first search. This part wasn't so bad to implement once I drew out the logic. The second part was a little more tricky to figure out. We needed to use permutations to solve the traveling salesman problem. I managed to pass all the available tests, but I feel the way that I stored the data and compared routes was a little.. messy.. to say the least. Hopefully, I will have time to review my code with the professor or the TA once it has been graded.

CST370 - Week 2

 This week we covered time efficiency and asymptotic notations. There are three main types of notations when it comes to time efficiency (or time complexity): Big-O, Big-Theta, and Big-Omega, with Big-Omega being less commonly used. Big-O notation considers the upper bound -- Meaning all functions with lower or same order of growth as f(n). Big-Theta is more precise -- All functions with the same order of growth as f(n). While, Big-Omega is the lower bound -- meaning all functions with same or higher order of growth as f(n). To figure out the order of growth, you must consider the number of executions of the basic operation of the algorithm. To represent the order of growth in Big-O notation, you must find the dominant factor and eliminate coefficients. For example, if the number of executions can be represented by 0.5n³ + 500n², the dominant order is n³ and we eliminate the coefficient, so the order is O(n³).  Big-Theta is used to represent the average time, but cannot be used if the best and worst case efficiencies are different.

The most difficult part of this week for me was considering the mathematical part of analysis. Using backward substitution and establishing base conditions and recurrence relations is definitely something I need to review.

CST370 - Week 1

 For this week we were introduced to the basics of algorithms and their usefulness in computer science. After going through the lecture material, I realized that I'm decent at implementing algorithms practically, but I don't have a good understanding of what makes an algorithm a good one and how to determine operations vs basic operations, etc. This will definitely be something that I take time to review further as the class progresses. Another opportunity for me will be slowing down to review pseudocode. I noticed that I tend to assume I know what's going on and glance over the code too quickly when I should be taking the code line by line to make sure I'm fully understanding. One thing I am excited for is the mathematical side of this class. My math has gotten a little rusty over the years, but it used to be my favorite part of computer science, so I'm hoping to find that connection with it again.

CST311 - Week 8

 For this week, we briefly read over firewalls and how they are used in regards to network security. However, most of my time this week was spent working on PA4. For this assignment I worked mainly on part 3, which had to do with generating the certificate. I learned how to save IP addresses from the Mininet network to file and how to generate the certificate without user interaction in order to match the demo video. Learning about how to use the subprocess module was interesting and I imagine it will be very beneficial moving forward to be able to send instructions to the command line in that way. 

CST 311 - Week 7

 For week 7, most of my time was spent studying for the final exam. I spent some more time tracing through Djikstra's algorithm and practicing my understanding of IP addresses and subnet masks. When it comes to new content, we read over Chapter 6, which covers The Link Layer and LANs. As opposed to the network layer that covers end-to-end communication across a series of links, this chapter focused on how information traverses the individual links. 

Basics

There are two link-layer channels -- broadcast channels, which connect multiple hosts in wireless networks, and point-to-point communication links, for example, two routers connected by a long-distance link. The basic service of the link layer is to transfer a datagram from one node to an adjacent one, but we read about the potentially varying details of a link-layer protocol, like framing, link access, reliable delivery, and error detection and correction. We learned that the link layer is usually implemented on a chip called the network adapter, which implements these services. The layer's functionality is mostly controlled by the hardware with only higher-level functionality being software-controlled. Because of this, you can think of the link layer as the place in the stack where hardware meets software. 

Error Checking

One of the main sections that stuck out to me was the section on error-checking. There are three techniques for detecting errors -- parity checks, checksumming methods, and cyclic redundancy checks. 

Parity checks are the simplest form of error-checking, where for information D with d bits in an even parity scheme, the sender includes an additional bit with value such that the total number of 1s in the d + 1 bits is even. In an odd scheme, the number of 1s will be odd. With a two-dimensional parity scheme, a receiver can detect the error and also where it occurred.

A checksum is based on the idea that bytes of data are treated as 16-bit integers and summed. The 1s complement of this forms the checksum. When received, 1s complement of the checksum is performed and if any resulting bits are 1, an error will be detected.

A widely used technique is one based on cyclic redundancy check codes. First, the sender and receiver agree on an r + 1 bit pattern called a generator (G). The idea is that for data D, the sender chooses r additional bits, R, and append them to D so that d + r bit pattern is exactly divisible by G. If the remainder of (d + r)/G does not equal zero, there has been an error.

CST 311 - Week 6

 This week we went covered chapter 5 of the textbook, which dealt with the control plane within the network layer. The control-plane is the network-wide logic that controls how a datagram is routed and also how the network-layer components and services are configured and managed. Later in the chapter we talked about two main routing protocols: OSPF, which exists within a single network and BGP, which interconnects all of the networks that make up the internet. Finally we covered some ways of managing an IP network -- ICMP, the Internet Control Message Protocol, and SNMP, the Simple Network Management Protocol. The thing that stood out the most to me this week was the review of shortest-path algorithms. While I've learned about Djikstra's algorithm in previous courses, I definitely needed to review how to trace it through the nodes. The worksheet for practicing this proved to be extremely useful and I looked up a few other videos to help me feel more comfortable with the content as well.

CST 311 - Week 5

 This week we took a dive into the network layer, which is widely considered to be the most complex layer of the protocol stack. The main role of the network layer is to move packets from a sender to a receiver. Because of this, two functions in particular are very important -- forwarding and routing. Forwarding refers to the router-local action of transferring a packet from an input link interface to the appropriate output link interface. Routing on the other hand refers to the network-wide process that determines end-to-end paths that packets take from source to destination. We also looked over different types of packet scheduling -- FIFO, Priority Queuing, Round Robin, and Weighted Fair Queuing. Next we took some time to learn about IP address and how to convert between binary and dotted-decimal notation. We also covered DHCP, or the Dynamic Host Configuration Protocol, which is a client-server protocol that allows a host to obtain an IP address automatically.

 Overall this week contained a wealth of information and I'm not sure I've wrapped my head around it. I'm about halfway through the optional worksheets and I intend to finish going over those in order to get a better grasp on the concepts before the final exam next week.