Week 1 - Palindromes and Problem Types
It's been a while since I have posted on the learning journal. The course that I am currently taking is CST 370 - Design and Analysis of Algorithms. So far from the looks of it the course will be very demanding so I will have to keep my focus and stay on top of all my assignments this semester. For this first week, it was quite straightforward as we reviewed what an algorithm is and looked at an example of a problem known as the GCD to identify the different ways that this problem can be approached. The lectures discuss the different methods such as using the Euclidean Algorithm which is taking two integers or inputs such as GCD(m, n) and applying GCD(n, m mod n) until the remainder or "m mod n" is equal to 0. We identified this algorithm using a normal structured description with step by step basis and also looked at it through pseudo-code. I think the biggest takeaway about this first section of the course was understanding the pseudo-code as I haven't been really paying attention to those since my last data structure course. The class provided a document that really helped me understand it clearly. After going over the euclidean algorithm we went over the two consecutive integer checking algorithm and middle school procedure by looking at their detailed structure and pseudo-code. Each method has their own case of when to use it such as with the consecutive integer checking where the algorithm would not work compared to Euclid's if one of the input numbers were zero, and middle school procedure is considered a legitimate algorithm because of prime factorization not defined unambiguously or perfectly clear or precise. Each algorithm can solve the problem but there are different case by case situations for them.
In addition to this week we reviewed the different problems that we will encounter such as sorting, searching, and graph problems, along with a small review of the data structures we may encounter in the future of the course. The sorting problem involves different sorting solutions for different situations such as some may work faster but are complex, some work better on the organization of inputs, and some work better with certain data structures. There were two key points that involved sorting which were if it was stable which means that if "it preserves the relative order of any two equal elements in its input" and in-place which is if it does not require extra memory. In addition the course looked at searching problems which involves searching a search key in large data sets and the role they play in storing and retrieving data. The biggest takeaway were the graph problems such as identifying the shortest path first, or TSP the traveling salesman problem which involves finding the shortest tour through each vertex or cities so that each is visited once. There is more to it but I wanted to talk about the other things such as reviewing the data structures and talking briefly about the analysis framework which will be looked at more next week.
As for data structures we reviewed arrays, linked-lists, double-linked lists, the stack, a queue, priority queue, and importantly graphs and trees. The graph section was the biggest focus within the lecture and the quiz. We reviewed what constitutes a graph by identifying the vertices and edges. Graphs can be undirected, directed, complete, dense, sparse, weighted or unweighted. There was a lot of information in this section. The biggest takeaway was the graph representation such as creating the adjacency matrix and adjacency lists. The last data structure we took a look at were trees and identifying what counts as a tree and the different types. The binary tree is a big focus in my previous data-structures class so I am assuming this will be the case in this course. Something I got from the book was identifying the left/right tree of the binary tree. The left child is less than the parent node while the right child is larger than the parent node, there shouldn't be any duplicates. Lastly I wanted to just talk briefly about the algorithm analysis framework and how memorizing the eight common time complexities will be very useful in future courses and outside of the school environment. The given document from the module was very helpful in identifying the basic operations of all pseudo-code within the first quiz. I definitely will need to keep practicing and identifying the patterns of these basic operations. There was a lot of information that I wanted to mention in this week's learning journal. I promise next week will be shorter, for some good reason I just had a lot on my mind for this week.
In addition to this week we reviewed the different problems that we will encounter such as sorting, searching, and graph problems, along with a small review of the data structures we may encounter in the future of the course. The sorting problem involves different sorting solutions for different situations such as some may work faster but are complex, some work better on the organization of inputs, and some work better with certain data structures. There were two key points that involved sorting which were if it was stable which means that if "it preserves the relative order of any two equal elements in its input" and in-place which is if it does not require extra memory. In addition the course looked at searching problems which involves searching a search key in large data sets and the role they play in storing and retrieving data. The biggest takeaway were the graph problems such as identifying the shortest path first, or TSP the traveling salesman problem which involves finding the shortest tour through each vertex or cities so that each is visited once. There is more to it but I wanted to talk about the other things such as reviewing the data structures and talking briefly about the analysis framework which will be looked at more next week.
As for data structures we reviewed arrays, linked-lists, double-linked lists, the stack, a queue, priority queue, and importantly graphs and trees. The graph section was the biggest focus within the lecture and the quiz. We reviewed what constitutes a graph by identifying the vertices and edges. Graphs can be undirected, directed, complete, dense, sparse, weighted or unweighted. There was a lot of information in this section. The biggest takeaway was the graph representation such as creating the adjacency matrix and adjacency lists. The last data structure we took a look at were trees and identifying what counts as a tree and the different types. The binary tree is a big focus in my previous data-structures class so I am assuming this will be the case in this course. Something I got from the book was identifying the left/right tree of the binary tree. The left child is less than the parent node while the right child is larger than the parent node, there shouldn't be any duplicates. Lastly I wanted to just talk briefly about the algorithm analysis framework and how memorizing the eight common time complexities will be very useful in future courses and outside of the school environment. The given document from the module was very helpful in identifying the basic operations of all pseudo-code within the first quiz. I definitely will need to keep practicing and identifying the patterns of these basic operations. There was a lot of information that I wanted to mention in this week's learning journal. I promise next week will be shorter, for some good reason I just had a lot on my mind for this week.
Comments
Post a Comment