CST370 - Week 7

This was our seventh week in CST 370 - Algorithms.

Counting Sort

Counting Sort is a sorting algorithm that doesn't directly compare elements to sort them.

First, we loop through the unsorted array once. During this loop we get the range of values in the array (for example, integers 10-15), we count how many times each number appears, then we calculate their distribution by adding the frequency of each number with the previous.

Then, we loop through the unsorted array again, starting from the end. For each number, we place it at the index listed in its distribution value, decrement the distribution value by 1, then continue to the next number.

 

 The time efficiency of Counting Sort is O(n + k), where k is the range of values in the input. Counting Sort is also stable, numbers with the same value in the appear in the same order in both the input and output.

Radix Sort

Radix Sort is another sorting algorithm that doesn't sort by directly comparing numbers. Instead, it runs Counting Sort on each digit of the input values, starting at the first digit, or Least Significant Digit.

 

This process is repeated until the last digit, or Most Significant Digit, at which point the array will be sorted. The time efficiency of Radix Sort is O(d * (n + k)), where d is the number of digits of the number in the input. This sorting algorithm runs in linear time, which means it can be very efficient.

Radix Sort Visualization

Dynamic Programming

Dynamic Programming is a general algorithm design technique for solving a problem with overlapping subproblems. It has the following steps:

  1. Set up a recurrence relation that describes a solution to a problem with smaller sub-problems.
  2. Solve the smaller sub-problems and record the solutions in a table.
  3. Solve the original problem using the table.

Fibonacci Numbers

A brute force approach to calculating Fibonacci numbers would be to use a recursive function.

  • f(0) = 0
  • f(1) = 1
  • f(n) = f(n - 1) + f(n - 2), where n >= 2

However, this approach is inefficient, as we need to call the function many times.

A dynamic approach would be to store the numbers generated in an array, and to reference the array when getting previous Fibonacci numbers. 

Coin-Collecting Problem

In the Coin-Collecting Problem, we have board of n rows and m columns. Each cell of the board can have 0 or 1 coins. We have a robot start at (1, 1) of the board. The robot can move one space to the right, or one space down. How should the robot move so that it reaches the bottom right cell of the board with as many coins as possible?

 

 We can solve this problem recursively:

 With the dynamic programming approach:

 

Then we start at the bottom-right cell and move backwards, always picking the cell with the higher value. We reverse the path we took back to the start, and that is our optimal value. 

Coin-Row Problem

In the Coin-Row problem we have a row of n coins whose values are some positive integers. The goal is to pick up the maximum amount of money, with the limitation that no two adjacent coins can be picked up.

Using recursion:

 

Using Dynamic Programming:

 

Then to find the optimal path we backtrack the calculations. 

Warshall's Algorithm (Transitive Closure)

Warshall's Algorithm computes the transitive closure of a directed graph. The Transitive Closure of a directed graph is an adjacency matrix that is updated to include indirect connections between two nodes (when one node can reach another by passing other nodes).

 

 

Floyd's Algorithm (All Pairs Shortest Paths)

Floyd's Algorithm calculates the shortest paths between all pairs in a weighted graph. The basic idea is similar to the Warshall's Algorithm.

  • It considers each vertext one by one and updates the matrix accordingly.
  • D(k) contains shortest distance of all pairs after considering vertices from 1 to k.
  • D(n) is the final solution of all pairs' shortest distance, as it considers all n vertices.

 

 

Greedy Technique

The Greedy Technique is used to solve problems with a sequence of choices (such as a sequence of coins with different values.

Each choice must be:

  • Feasible (satisfies the problem's constraints)
  • Locally Optimal (Greedy) (selects the best choice among all feasible choices available at that step)
  • Irrevocable (the choice cannot be changed later)

This technique is simple and useful for optimal or fast approximation. 

Prim's Algorithm

Prim's Algorithm is used to find the Minimum Spanning Tree of a weighted graph. A Spanning Tree is a tree that visits every node on the graph.

  1. Start with a tree T1 consisting of one vertex.
  2. Grow T1 by adding one vertex at a time, such as T2, T3, ... Tn.
  3. Construct Ti+1 from Ti by adding a vertex not in Ti that is closest to those already in Ti (This is a greedy step).
  4. Stop when all the vertices are included.

 

 

 

Comments

Post a Comment

Popular posts from this blog

Week 11

CST-338 Week 3  This week was the third week of CST-338. In this week we continued to learn more design and Java concepts. Black Box & White Box Testing This week we learned about two methodologies used for testing programs, black box and white box testing. Black box tests only focuses on the input, output, and functionality of a program, and not the internal code, logic, or structure of a program. One of the advantages of black box tests is that they are simple and easy to run. White box tests focus on the code, logic, and structure of a program. One of the advantages of white box tests is that can find logical errors, security vulnerabilities, or inefficiencies in code. Coupling & Cohesion This week we learned about coupling and cohesion in objects and methods. Coupling refers to how much different classes rely on each other. If two classes have tight coupling then they are more dependent, and changes in one are more likely to affect the other. If two classes have loose c...
Read more

Week 12

CST 338 - Week 4 This week was the fourth week is CST 338, also known as Software Engineering. In this week we began to learn about android development. Project 1 Review This week we finished a large project in CST 338. We have been asked to work with one or more classmates, and answer some questions about the project. With whom did you work? I worked with Nasser. What was your strategy for solving the assignments? My strategy was to read all of the method descriptions before I wrote any code. As I read them I created method stubs, and detailed TODO comments for each method. Afterwards, I started writing the methods from top to bottom in the assignment prompt. If a method called another method that I had not written yet, I would go ahead and write that method first so I better understood how they interacted. What was their strategy for solving the assignments? Their strategy was to follow the instructions closely as is, by following the UML diagrams and prompt as closely as possible. ...
Read more

Week 19

Image
 CST-363: Week 3 This is the third week of CST-363, also known as Intro. to Databases. Questions What is an SQL view.  How is it similar to a table? In what ways is it different? An SQL View stores a SELECT statement for later use, allowing the statement to be easily accessed in the future. A View functions similarly to a table, because SELECT statements return tables. However, the values that a View shows aren't being stored in the View, but the actual tables. This means that when one of those tables is updated, the View has to be as well. This also means that one needs to be very careful with updating or deleting rows using the View. Take a minute to think about how SQL compares to other programming languages like Java. What features are similar, and which are present in one language but not the other? The first and most clear difference is the syntax. SQL syntax is very different from that of Java and other programming languages. I think this makes basic SQL commands easy t...
Read more