CST370 Design and Analysis of ALgorthms Week 3

 For week 3 of CST370 Design and Analysis of Algorithms we learn about Brute force string matching and exhaustive search.  With the string matching problem, we basically try to match the characters in a text and find a substring of the text that matches the pattern. Brute-Force matching basic idea is to compare the characters by character. If a mismatch occurs shift a character and restart the comparison. The best case for this is when immediate match occurs, a minimum number of comparisons will occur. It is often easy to think about the best case scenario but worst case is not. A worst case scenario may not be too obvious since it may require more comparisons. 

Exhaustive search is a brute force approach to solve combinatorial problems. The basic idea of this are to generate all potential solutions to the problem. Evaluate each case one by one and determine the solution among the possible cases. For example Traveling Salesman Problem (TSP) is to find the shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started. To solve this kind of problem one must fine all permutations of each city(nodes) and find the distance travel. One must then sum up all the travel distance between nodes. The efficiency depends on the number of permutations. If there are n nodes in the question we should identify all possible paths of the (n-1) node, except the starting node. The time efficiency of the problem requires at least (n-1)!.

 This week we also learn about Depth-First Search algorithm(DFS) and Breadth-First Search(BFS) Algorithm. Graph traversal has many graph problems require processing all vertices and edges of a graph in a systematic way. These two algorithms are popular graph traversal algorithms. For example DFS uses stack for its operation when trying to traverse a graph. Applications of DFS are checking connectivity, checking acyclicity of a graph and finding connected components. BFS on the other hand uses queue for its operation when traversing graphs. The application of BFS is the same as it is in DFS.Checking connectivity, checking acyclicty of a graph and finding connectivity components. We can also find paths from vertex to all other vertices with the smallest number of edges.

Lastly for this week we alearn about divide and conquer problem solving techniques. A problem is divided into several subproblems. Typically, it is divided into two subproblems. Subproblems are solved recursively. If its necessary the subproblems solutions are combine to get the solution of the original problem. The time efficiency of divide and conquer is base on apply master theorem. Case 1 is if a < b^d, then O(n^d). Case 2is if a = b^d then O(n^d * logn). And lastly Case 3 if a > b^d then O(nlogb^a).

Comments

Post a Comment

Popular posts from this blog

Week 4

  Part One: My Educational Goals My educational goal for  CS program is to have a strong foundation in computer science theory and practical skills. I should be able to design and develop software programs and computational solutions. Have a more effective problem-solving skills and be able to adapt easily in new and emerging technologies. Attaining my Bachelor Degree in Computer Science is also a goal of mine but I think it is enough. My the actual goal is to pass all the classes with clear understanding of what was taught and be able to retain it and apply some skills that I learn in the future. This goal of mine is a long term and far from being achieved. It will require discipline, consistency and patience. The short term goal that I have is to pass both CS 349 and CS 300. I believe we are halfway for this two courses and I should be able to achieve it soon as long as I keep doing my work and keep my grades up. Part Two: My Career Goal   My career goal as of right now...
Read more

Week 5

Image
 Week 5   Part One: Support and Comment on Teammates' Goals Comment 1: https://edlcsonline.blogspot.com/2025/09/week-4-learning-journal-education-goals.html      Comment 2: https://alexandercsumb.blogspot.com/2025/09/my-educational-goal-in-cs-program-my.html?sc=1759716690276#c3901700382400993030     Part Two: Possible Capstone Ideas (30 minutes) These lists are subject to change but this is roughly what I imagine doing as of now.   CAD software or 3D Design software:  I currently work on projects that develops software to design dental products. 3D design software has always been my passion but for my software it would focus more on general objects that can be printed. It will probably be similar as Blender. I will try to make it as user friendly as possible. This project can help me learn more about graphics and optimization. The only thing that is making me hesitate to do this for future capstone project is the time. But this is definitely ...
Read more

Week 2

Image
     Module 2 lectures focuses on the present condition of business and company. I learned a lot starting from the the state of software industry. Innovation itself moves fast in today's age, and in order to keep up with it, people has to learn to adapt quickly as well. I also learn about different methodologies that company uses for software development. I was already aware of the two present method which are  agile  and  devops  as my current company uses this method but I learned about the continuous method . Essentially there were methods that was used in the pass which are Waterfall, Capability Maturity Model, and Rational Unified Process . I also learn more about project management. I learn that project management is mainly about planning, organizing and managing resources to achieve the goals that the group is trying to attain. Different tools and techniques on project management such as managing constrains that hinders in project development su...
Read more