CST-370 Week 3

    This week, I learned multiple algorithms that apply different techniques to solving problems. They include Brute force and Divide-and-Conquer.

Brute-force String Matching

Given a string of n characters, text, and a string of m characters called the pattern, find a substring of the text that matches the pattern.

Basic idea for solving string problems with Brute Force

  1. 1. Character by character comparison
  2. 2. If a mismatch occurs, shift a character and restart the comparison
Efficiency for best case: If there is an immediate match, minimum number of comparisons will occur. (m)
E.g.
- Text: CSUMBGO
- Pattern: CSU

Efficiency for worst case: If there is no matching pattern, may iterate through entire text.

Exhaustive Search and TSP

Exhaustive search: A brute-force approach to solving combinatorial problems.

Basic idea:
    1. Generate all potential solutions (or all possible cases) to the problems.
    2. Evaluate each case one by one
    3. Determine the solutions among the possible cases.

Traveling Salesman Problem (TSP): Used 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.

Time complexity of TSP:

    1. Efficiency depends on the number of permutations
    2. If there are n nodes in the question, we should identify all possible paths of the (n-1) node, except for the starting node.
    - The total possible paths are:
    (n-1)! = (n-1) * (n-2) * ... * 2 * 1
    - Therefore, the time efficiency of the problem requires at least (n-1)!

Exhaustive Seach - Knapsack

Knapsack problem: A classic optimization problem. Given n items (wights, values), find the most valuable subset of the items that fit into a knapsack with the capacity W. (Only 1 quantity per item. Can't take the same item twice)

Example:

Knapsack capacity: 10 (i.e. W = 10)

    - Item 1: w1 = 7, v1 = $42
    - Item 2: w2 = 3, v2 = $12
    - Item 3: w3 = 4, v3 = $40
    - Item 4: w4 = 5, v4 = $25

Basic idea:
    1. Consider all possible subsets.
    2. Compute weight and value of each subset
    3. Find the best subset which provides the maximum value

Best: {3, 4}

Time Efficiency: The number of possible subsets of a set with n items in 2^n, thus time complexity is at least 2^n

Comments

Post a Comment

Popular posts from this blog

Week 4

Part 1 Educational Goals. My main educational goal is to achieve my bachelor's degree in computer science in 2 years. Another educational goal of mine is to do well in my upper division classes so I can be prepared for a career in software development. I would also like to strengthen my collaboration skills through the use of group projects.  Part 2 Career Goals. One of my main career goals is to become a professional software developer after graduation. I hope to leverage my current internship as an Android developer to find a new internship next summer, so I can explore different fields in software development. Part 3 Guess ETS percentile. If I had to guess, I think I would be in the 70th percentile. I feel pretty comfortable with programming, but I think I would struggle more with the theory-based questions and would have to review my notes from discrete/data structures beforehand.  Part 4 Learning Journal.  Writing material:  For my Ethics essay, I will need to c...
Read more

CST-363 Week 1

  Relational database tables and spreadsheets look similar with both having rows and columns.  What are some important differences between the two? One of the biggest differences is that relational databases can be restored on failures. Relational databases also use SQL to retrieve and insert data. Installing and configuration a database and learning how to use it is more complicated that just reading and writing data to a file.  What are some important reasons that makes a database a useful investment of time?  Databases force data integrity and ensure it is consistent across programs. Databases can also restrict data to a program based on security rules. Databases can reduce redundancy and inconsistency.  What do you want to learn in this course that you think will be useful in your future career?  I think I would like to learn how to translate English into valid SQL queries/maybe accessing databases asynchronously as practically every company will have a...
Read more

Week 9

 Codingbat questions Did you plan it out or throw code at it?  I gave it a few seconds of thought before throwing code at it What worked? Java methods were pretty easy to understand coming from C++ and Kotlin. What DID NOT work? Some of the methods involving indexes through me off sometimes, as it is easier to visualize by writing down your steps to the solution than it is trying to do it in your head. (same with some of the problems involving edge cases) How many tries did it take?  Most only took 1-3 tries.
Read more