-

 

Week 1 – CST370 – Design and Analysis of Algorithms

This week was a combination of week 0 and week 1. We were required to set up a GitHub account, if we did not have one already, to complete our homework assignments with GitHub Classroom. Homework 0 required us to write a program that reads two integer numbers from a user and displays the sum and difference of the two numbers. We also needed to make sure that the difference between the two numbers is always 0 or positive. The purpose of Homework 0 was to get familiar with GitHub Classroom, set up our IDE environment, and submitting to Canvas. The topics covered this week included Euclid’s Algorithm for GCD calculation, important problem types, fundamental data structures, and algorithm analysis framework.

Euclid’s Algorithm for GCD calculation is an algorithm that takes two numbers and finds the greatest common divisor by repeating the equality gcd(m, n) = gcd(n, m mod n) until m mod n is equal to zero. The last value of m will be the greatest common divisor of the two numbers.

Some of the important problem types covered this week included graph, sorting and searching. A graph is composed of nodes or vertices and lines or edges. Graphs can be used to model real life applications like transportation, communication networks, and project scheduling. We use sorting to arrange items in either ascending or descending order. Sorting has many applications, and it serves as the basis of many other algorithms. Searching problems involve finding a given value, called a search key, in a given set. There are different types of searching techniques like sequential search, binary search, and hashing. Sorting a data set will often make searching more efficient.

The material for this week also included a review of fundamental data structures such as linked lists, stacks, queues, graphs, and trees. Linked lists are a sequence of elements called nodes which contain data and a pointer that links to other nodes in the linked list. A stack is a list in which insertions and deletions can only be made at the end and it operates in a last-in-first-out (LIFO) fashion. A queue is a list where elements are added in the rear and deleted from the front in a first-in-first-out fashion. We covered more on graphs such as directed and undirected graphs as well as the Traveling Salesman Problem which finds the shortest possible route that visits each city exactly once and returns to the origin city. A tree is a special type of graph called a connected acyclic graph in which the number of edges is always equal to one less than the number of vertices. Binary search trees are represented as a node with a value for the vertex and pointers to its left and right child.

Lastly, we learned about algorithm analysis framework. We analyze algorithms to determine their efficiency by measuring the amount of resources necessary to execute the algorithm, which are typically time and memory. We will be focusing on time efficiency. We first need to identify the algorithm’s basic operation. This is the operation that is most frequently performed, and it is usually found in the algorithm’s innermost loop. The objective of algorithm analysis is to determine the order of growth. There are eight common time complexities for the order of growth constant time, logarithmic time, linear time, linearithmic time, quadratic time, cubic time, exponential time, and factorial time.

Comments

Post a Comment

Popular posts from this blog

-
Week 4 – CST – 300 Module 4 OLI – Module 4 and 5 This week’s OLI required us to meet with our team and discuss what we have learned from this unit. It was interesting to compare what I have learned to what the rest of my team learned from their experience with the unit. The assignment included an activity called “2 Truths, 1 Lie” which required each team member to share three strengths related to our group project. Of the three strengths, two were supposed to be truths and one a lie without disclosing which were truths and which was the lie. The rest of the team had to guess which of the three was the lie. For the most part, we were all able to pick out the lie from the strengths. That activity showed me that we are becoming familiar with our team members’ strengths which will help in assigning tasks during challenging projects. The last part of the assignment consisted of answering questions from what each of us shared. Everyone of our members agreed that it is a good idea to allo...
Read more
-
  Week 5 – CST – 300 Module 5 OLI – Module 6 and 7 The OLI for this week was interesting. It helped us recognize conflict and showed us how to deal with them using different conflict strategies. Module 6 showed us a video where Kurt and Freda had a conversation which quickly escalated into a conflict. Freda was questioning the level of a platform that had been checked already. Kurt told Freda that he didn’t trust her leveling phone app. After arguing for some time, Kurt noticed that the platform was not level because there was a piece of wood underneath it. I first noticed the conflict when Kurt told Freda that he did not trust her leveling app around the 15 second mark of the video. Module 7 was challenging, here we had to use the best conflict strategy to deal with conflict based on how important the relationship is and how much do we care about the problem. An example was in the scenario where you asked Taylor, a friend of a friend for a ride to get wood because your car...
Read more
-
Week 8 – CST – 300 Module 8 OLI – Post-Test This week we had to take the post-test which was a culmination of what we have learned throughout the course. It started off with opinion questions where you had to choose whether you agreed or disagreed with the statement. I compared my answers to the pre-test answers and, although they are not graded, I believe my answers improved. From the OLI modules, I learned that you must consider everyone’s opinions and to use conflict resolution techniques when there is difference of opinions. When someone is expressing their opinion, you must use active listening and let them know you understood by repeating to them what they told you in your own words. For dealing with conflicts, you must use active listening and then formulate an assertion message to deal with the conflict.   Part 1: Review Other Team’s Final Video Projects Gigabit Goon Squad Public Video – 1.       Is the topic well covered? Yes, I bel...
Read more