This week was fun, we got to spend time learning about different kinds of algorithms, brute force string matching, and what exactly is a best case or worse case for a brute force approach. We looked at how to traverse a graph, using a depth first search algorithm, where (in putting it in my own terms) attempt to get the farthest down you possibility can in the graph until hitting a dead end, then when you do, back up til you reach a node that has a new node you haven't visited yet. We also discussed bread first search algorithm, which to me, is when you explore/discover all possible nodes connected to the current node you're on and note them in a queue. Then move on to the next node in the queue (in alphabetical or numerical order), and discover all possible new nodes there, adding them to the queue. Do this until ever node has been visited. We also covered the divide and conquer algorithm, which to me is a general technique that can be applied to multiple problem times, and programmatically it works well with recursive programming.
Tuesday, January 28, 2025
Wednesday, January 22, 2025
Design & Analysis ofAlgorithms - Week 2
This week we started to get into more "meat" of the course. We started to discuss different algorithms (recursive and non-recursive), and how to analyze them. How we can use Big O notation to denote how efficient an algorithm is, how the running time of an algorithm scales as the input size grows. This week also contained one of my favorite puzzles, the 4 gallons of water from a 3 gallon and 5 gallon container. Definitely not all ages appropriate, but seeing that puzzle in the movie Die Hard with a Vengeance cemented it in my mind. As in lots of aspects of life, being able to think clearly and calmly in a chaotic situation is a very important skill.
Wednesday, January 15, 2025
Design & Analysis ofAlgorithms - Week 1
The first week of a new class is always exciting (and can be a bit nerve-racking). There's the excitement of starting the journey of learning something new, coming to terms with what the coursework is going to be like, and generally just getting settled. I enjoyed the Puzzles and hope they continue.
This week, we got an introduction into the general idea of what an algorithm is. We looked at some known example algorithms like Euclid’s Algorithm for the greatest common denominator. We looked at how a problem can have multiple algorithms that solve it, each with different advantages or disadvantages.
We started looking at how algorithms are used in computer science, for things like sorting, searching, string processing, graph problems, and more.
Speaking of graphs, we delivered deeper into looking at graphs, graph representations, paths, and how they represent data. Akin to graphs, we looked at trees.
And finally, we talked about how to measure an algorithm. Analyzing an algorithm's efficiency, which could be both or either time complexity or space complexity.
This weeks homework was coming up with an algorithm that would detect whether a string is a palindrome or not. There's lots of different approaches one can take to solve the problem, and some are programming languages specific. So it was fun to take some time to thing what might be the most efficient way to determine this.