Greedy Algorithms
A greedy algorithm always makes the best choice at the moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution. Greedy algorithms work in stages. In each stage, a decision is made that is good at that point, without bothering about the future.
For example, you can greedily approach your life. You can always take the path that maximizes your happiness today. But that doesn’t mean you’ll be happier tomorrow.
In general, they are computationally cheaper than other families of algorithms like dynamic programming, or brute force. This is because they don’t explore the solution space too much. And, for the same reason, they don’t find the best solution to a lot of problems.
To solve a problem based on the greedy approach, there are two stages
- Scanning the list of items
- Optimization
How do you decide which choice is optimal?
Assume that you have a function that needs to be optimized (either maximized or minimized) at a given point. A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision.
Advantages of Greedy Algorithm
- The main advantage of the Greedy method is that it is straightforward, easy to understand and easy to code. In Greedy algorithms, once we make a decision, we do not have to spend time re- examining the already computed values.
- Analyzing the run time for greedy algorithms will generally be much easier than for other techniques (like Divide and conquer).
Disadvantages of Greedy Algorithm
- The main disadvantage of Greedy Algorithm is that there is no guarantee that making locally optimal improvements in a locally optimal solution gives the optimal global solution.
- It is not suitable for problems where a solution is required for every subproblem like sorting. In such problems, the greedy strategy can be wrong, in the worst case even lead to a non-optimal solution.
- Even with the correct algorithm, it is hard to prove why it is correct.
Problems best solved by Greedy Algorithm
- Travelling Salesman Problem
- Kruskal’s Minimal Spanning Tree Algorithm
- Dijkstra’s Minimal Spanning Tree Algorithm
- Knapsack Problem
- Job Scheduling Problem
Database
Java uses the JDBC library to connect and manupilate databases. JDBC works with Java on a variety of platforms, such as Windows, Mac OS, and the various versions of UNIX.
First, you need a connection. To create a connection, you need the username, password, and host for the database you want to connect to. Here I have a Enum to create a connection factory.
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.SQLException;
public enum DBConnection {
INSTANCE("java_jdbc");
private Connection connection = null;
private String database;
private DBConnection(String database) {
this.database = database;
String URL = "jdbc:mysql://localhost:3306/" + database + "?createDatabaseIfNotExist=true&useUnicode=true&characterEncoding=utf8&useSSL=false&serverTimezone=UTC";
String USER = "root";
String PASS = "";
try {
connection = DriverManager.getConnection(URL, USER, PASS);
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
}
}
public Connection getConnection() {
return connection;
}
public String getDatabase() {
return this.database;
}
}
Create a table
public static void createTable() {
System.out.println("creating " + TABLE_NAME + " table...");
DB_CONNECTION = DBConnection.INSTANCE.getConnection();
Statement stmt = null;
try {
stmt = DB_CONNECTION.createStatement();
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
}
System.out.println("Check if table " + TABLE_NAME + " already exists.");
// @formatter:off
String checkTableSQL = "SELECT COUNT(*) as tableCount " +
"FROM INFORMATION_SCHEMA.TABLES " +
"WHERE TABLE_SCHEMA = '"+DBConnection.INSTANCE.getDatabase()+"' "+
"AND TABLE_NAME = '"+TABLE_NAME+"'; ";
// @formatter:on
try {
System.out.println("SQL QUERY: " + checkTableSQL);
ResultSet resultSet = stmt.executeQuery(checkTableSQL);
resultSet.next();
int tableCount = resultSet.getInt("tableCount");
if (tableCount > 0) {
System.out.println("dropping " + TABLE_NAME + " table.");
System.out.println("SQL QUERY: " + "DROP TABLE " + TABLE_NAME + "; ");
boolean removedTable = stmt.execute("DROP TABLE " + TABLE_NAME + "; ");
System.out.println("table dropped " + removedTable);
}
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
}
System.out.println("creating " + TABLE_NAME + " table.");
// @formatter:off
String createTableSQL = "CREATE TABLE "+TABLE_NAME+" " +
"(id INTEGER NOT NULL AUTO_INCREMENT, " +
" first_name VARCHAR(255), " +
" last_name VARCHAR(255), " +
" age INTEGER, " +
" PRIMARY KEY ( id )); ";
// @formatter:on
try {
System.out.println("SQL QUERY: " + createTableSQL);
stmt.executeUpdate(createTableSQL);
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
}
System.out.println(TABLE_NAME + " table has been created!\n\n");
}
public static void insertDataToTable() {
System.out.println("inserting data into " + TABLE_NAME + " table...");
DB_CONNECTION = DBConnection.INSTANCE.getConnection();
try {
DB_CONNECTION.setAutoCommit(false);
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
}
// load users
try {
for (int i = 0; i < NUMBER_OF_USERS; i++) {
StringBuilder query = new StringBuilder();
query.append("INSERT INTO user (first_name, last_name, age) ");
query.append("VALUES (?, ?, ?); ");
System.out.println("SQL QUERY: " + query.toString());
/**
* Use prepareStatement to insert data into the query and avoid SQL injection
*/
PreparedStatement pStmnt = DB_CONNECTION.prepareStatement(query.toString(), Statement.RETURN_GENERATED_KEYS);
String firstName = ConstantUtils.getRandomFirstname();
String lastName = ConstantUtils.getRandomLastname();
int age = RandomGeneratorUtils.getIntegerWithin(1, 51);
pStmnt.setString(1, firstName);
pStmnt.setString(2, lastName);
pStmnt.setInt(3, age);
System.out.println("parameter 1: " + firstName);
System.out.println("parameter 2: " + lastName);
System.out.println("parameter 3: " + age);
int numOfRowsCreated = pStmnt.executeUpdate();
if (numOfRowsCreated > 0) {
int id = 0;
ResultSet rs = pStmnt.getGeneratedKeys();
if (rs.next()) {
id = rs.getInt(1);
}
System.out.println("new id: " + id);
}
}
DB_CONNECTION.commit();
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
try {
DB_CONNECTION.rollback();
} catch (SQLException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
} finally {
}
System.out.println(TABLE_NAME + " table has been populated with " + NUMBER_OF_USERS + " rows!\n\n");
}
public static void readDataFromTable(int selectedId) {
System.out.println("reading data from " + TABLE_NAME + " table...");
DB_CONNECTION = DBConnection.INSTANCE.getConnection();
try {
DB_CONNECTION.setAutoCommit(false);
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
}
ResultSet rs = null;
PreparedStatement pStmnt = null;
// Read user
try {
StringBuilder query = new StringBuilder();
query.append("SELECT id, first_name, last_name, age ");
query.append("FROM user ");
query.append("WHERE id = ? ");
System.out.println("SQL QUERY: " + query.toString());
pStmnt = DB_CONNECTION.prepareStatement(query.toString());
pStmnt.setInt(1, selectedId);
System.out.println("parameter 1: " + selectedId);
rs = pStmnt.executeQuery();
DB_CONNECTION.commit();
rs.next();
User user = User.generateUserFromResultset(rs);
System.out.println(user.toString());
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
} finally {
try {
if (rs != null) {
rs.close();
}
if (pStmnt != null) {
pStmnt.close();
}
} catch (SQLException e) {
System.out.println(e.getMessage());
}
}
System.out.println("Row with id=" + selectedId + " has been retrived from " + TABLE_NAME + ".\n\n");
}
public static void updateDataInTable(int selectedId) {
System.out.println("updating data in " + TABLE_NAME + " table...");
DB_CONNECTION = DBConnection.INSTANCE.getConnection();
try {
DB_CONNECTION.setAutoCommit(false);
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
}
// Update user
try {
StringBuilder query = new StringBuilder();
query.append("UPDATE user ");
query.append("SET first_name = ? ");
query.append(", age = ? ");
query.append("WHERE id = ? ");
System.out.println("SQL QUERY: " + query.toString());
PreparedStatement pStmnt = DB_CONNECTION.prepareStatement(query.toString());
int age = RandomGeneratorUtils.getIntegerWithin(1, 51);
String firstName = "Folau";
pStmnt.setString(1, firstName);
pStmnt.setInt(2, age);
pStmnt.setInt(3, selectedId);
System.out.println("parameter 1: " + firstName);
System.out.println("parameter 2: " + age);
System.out.println("parameter 3: " + selectedId);
pStmnt.executeUpdate();
DB_CONNECTION.commit();
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
try {
DB_CONNECTION.rollback();
} catch (SQLException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
}
System.out.println(TABLE_NAME + " table has been updated for row with id=" + selectedId + "!\n\n");
}
- Set autocommit to false
DB_CONNECTION.setAutoCommit(false);
- Commit changes when things are ok
DB_CONNECTION.commit();
- Roll back when things are not ok
DB_CONNECTION.rollback();
public static void updateDataInTable(int selectedId) {
System.out.println("updating data in " + TABLE_NAME + " table...");
DB_CONNECTION = DBConnection.INSTANCE.getConnection();
try {
DB_CONNECTION.setAutoCommit(false);
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
}
// Update user
try {
StringBuilder query = new StringBuilder();
query.append("UPDATE user ");
query.append("SET first_name = ? ");
query.append(", age = ? ");
query.append("WHERE id = ? ");
System.out.println("SQL QUERY: " + query.toString());
PreparedStatement pStmnt = DB_CONNECTION.prepareStatement(query.toString());
int age = RandomGeneratorUtils.getIntegerWithin(1, 51);
String firstName = "Folau";
pStmnt.setString(1, firstName);
pStmnt.setInt(2, age);
pStmnt.setInt(3, selectedId);
System.out.println("parameter 1: " + firstName);
System.out.println("parameter 2: " + age);
System.out.println("parameter 3: " + selectedId);
pStmnt.executeUpdate();
DB_CONNECTION.commit();
} catch (SQLException e) {
System.out.println("SQLException, msg=" + e.getLocalizedMessage());
e.printStackTrace();
try {
DB_CONNECTION.rollback();
} catch (SQLException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
}
System.out.println(TABLE_NAME + " table has been updated for row with id=" + selectedId + "!\n\n");
}
Dynamic Programming
Dynamic programming is similar to Divide and Conquer in in that a problem is broken down into smaller sub-problems. But unlike, Divide and Conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are stored and used for similar or overlapping sub-problems.
Note that the difference between Dynamic Programming and straightforward recursion is in memoization of recursive calls. If the sub problems are independent and there is no repetition then memoization does not help, so dynamic programming is not a solution for all problems.
Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution.
Dynamic programming takes the brute force approach. It Identifies repeated work, and eliminates repetition.
Dynamic Programming Strategy
- Divide – breaking the problem into smaller sub-problems.
- Conquer – solve the problem if it’s small enough(base case) or check cache to see if a simpler problem has been solved and use that answer. If the problem is still not small enough, divide it into smaller problems solve them.
- Combine – combine solutions from subproblems and generate a solution for the original problem.
Dynamic programming can be used in both bottom-up(Tabulation) and top-down(Memoization) manner. And of course, most of the times, referring to the previous solution output is cheaper than recomputing in terms of CPU cycles.
Bottom-up(Tabulation) Dynamic Programming
We evaluate the function starting with the smallest possible input argument value and then we step through possible values, slowly increasing the input argument value. While computing the values we store all computed values in a table (memory). As larger arguments are evaluated, pre-computed values for smaller arguments can be used.
Tabulation is the opposite of the top-down approach and avoids recursion. In this approach, we solve the problem “bottom-up” (i.e. by solving all the related sub-problems first). This is typically done by filling up an n-dimensional table. Based on the results in the table, the solution to the top/original problem is then computed.
Tabulation is the opposite of Memoization, as in Memoization we solve the problem and maintain a map of already solved sub-problems. In other words, in memoization, we do it top-down in the sense that we solve the top problem first (which typically recurses down to solve the sub-problems).
/**
* Dynamic Programming with Tabulation<br>
*/
public static int fibonacciWithTabulation(int num) {
if (num <= 0) {
return 0;
}
int storage[] = new int[num + 1];
/**
* first and second case are pre-computed
*/
/*
* first case
*/
storage[0] = 0;
/*
* second case
*/
storage[1] = 1;
for (int i = 2; i <= num; i++) {
storage[i] = storage[i - 1] + storage[i - 2];
System.out.println(storage[i - 1] + "+" + storage[i - 2] + " = " + storage[i]);
}
return storage[num];
}
Top-down(Memoization) Dynamic Programming
The problem is broken into sub problems, each of these sub problems is solved, and the solutions are remembered or stored in memory(Map). If this function is called twice with the same parameters, you simply look up the answer in the storage(Map). As the first action you check if pre-computed value exists in storage. if it does exist use in the storage, use or return that value, if it does not compute it or divide it again.
Here is an example.
/**
* Dynamic Programming with Memoization<br>
* storage can be a map, array, or list depending on your situation.
*/
private static int fibonacciWithCache(Map<Integer, Integer> storage, int num) {
if (num <= 1) {
return num;
}
if (storage.containsKey(num)) {
return storage.get(num);
}
int number1 = fibonacciWithCache(storage,num - 1);
int number2 = fibonacciWithCache(storage,num - 2);
int result = number1 + number2;
storage.put(num, result);
return result;
}
When do you use Divide and Conquer?
When we see problems like:
- shortest/longest
- minimized/maximized
- least/most,
- fewest/greatest
- biggest/smallest
These kinds of problems are optimisation problems.
How to solve a problem with Dynamic Programming
Imagine you have found a problem that’s an optimisation problem, but you are not sure if it can be solved with Dynamic Programming. First, identify what you are optimising for. Once you realize what you are optimising for, you have to decide how easy it is to perform that optimisation. Sometimes, the greedy approach is enough for an optimal solution.
Before we even start to plan the problem as a dynamic programming problem, think about what the brute force solution might look like. Are sub steps repeated in the brute-force solution? If so, we try to imagine the problem as a dynamic programming problem.
Mastering dynamic programming is all about understanding the problem. List all the inputs that can affect the answers. Once we’ve identified all the inputs and outputs, try to identify whether the problem can be broken into subproblems. If we can identify subproblems, we can probably use Dynamic Programming.
Then, figure out what the recurrence is and solve it. When we’re trying to figure out the recurrence, remember that whatever recurrence we write has to help us find the answer. Sometimes the answer will be the result of the recurrence, and sometimes we will have to get the result by looking at a few results from the recurrence.
Dynamic Programming can solve many problems, but that does not mean there isn’t a more efficient solution out there. Solving a problem with Dynamic Programming feels like magic, but remember that dynamic programming is merely a clever brute force. Sometimes it pays off well, and sometimes it helps only a little.
Where is Divide and Conquer being used?
- Many string algorithms including longest common subsequence, longest increasing subsequence, longest common substring, edit distance.
- Algorithms on graphs can be solved efficiently: Bellman-Ford algorithm for finding the shortest distance in a graph, Floyd’s All-Pairs shortest path algorithm, etc.
- Chain matrix multiplication
- Subset Sum
- 0/1 Knapsack
- Travelling salesman problem, and many more
MySQL Reset Root Password
Stop MySQL server
sudo systemctl stop mysql // OR /etc/init.d/mysql stop
Start MySQL server without loading grant table
The ampersand & at the end of the command above will cause the program to run in the background, so you can continue to use the shell.
When the --skip-grant-tables option is used, anyone can to connect to the database server without a password and with all privileges granted.
sudo mysqld_safe --skip-grant-tables &
Once safe mode has started up, log into MySQL and when prompted, use your standard root password.
mysql -u root mysql
Update user root password.
ALTER USER 'root'@'localhost' IDENTIFIED BY 'MY_NEW_PASSWORD';
If the above command does not work, try this.
UPDATE mysql.user SET authentication_string = PASSWORD('MY_NEW_PASSWORD') WHERE User = 'root' AND Host = 'localhost';
Be sure to reload everything.
FLUSH PRIVILEGES;
Now you have a new password “MY_NEW_PASSWORD”
Stop and restart the server normally
Stop server
mysqladmin -u root -p shutdown
Start server
sudo systemctl start mysql //OR /etc/init.d/mysql start
Verify your password change
mysql -u root -p
Enter your password. If you get in then you password has been successfully reset.
Recursion
Recursion is the technique of making a function call to itself. This technique provides a way to break complicated problems down into simple problems which are easier to solve.
Recursion Structure
- validation of input
- base case where it stops calling itself and returns a value
- recursive case, logical operation + call itself with reduced value(s)
When a invocation of the function makes a recursive call, that invocation is suspended until the recursive call completes, new storage locations for variables are allocated on the stack. As, each recursive call returns, the old variables and parameters are removed from the stack. Hence, recursion generally uses more memory and is generally slow. On the other hand, a recursive solution is much simpler and takes less time to write, debug and maintain. The execution starts from the top and goes to bottom, for example 6,5,4,3,1, then when it hits the base case, the calculation will start from bottom(base case) back to to.
Here are some examples of recursion:
- The factorial function (commonly denoted as n!) is a classic mathematical function that has a natural recursive definition.
- An English ruler has a recursive pattern that is a simple example of a fractal structure.
- Binary search is among the most important computer algorithms. It allows us to efficiently locate a desired value in a data set with upwards of billions of entries.
- The file system for a computer has a recursive structure in which directories can be nested arbitrarily deeply within other directories. Recursive algo- rithms are widely used to explore and manage these file systems.
Things like tree or graph data can be good candidates for recursion.
Every recursion or recursive function can be done with for loop or while loop.
Just as loops can run into the problem of infinite looping, recursive functions can run into the problem of infinite recursion. Infinite recursion is when the function never stops calling itself. Every recursive function should have a halting condition, which is the condition where the function stops calling itself. In the below examples, the halting condition is when the parameter num becomes 0 or 1.
Recursion may be a bit difficult to understand. The best way to figure out how it works is to experiment with it.
Sum with Recursion
private static int sum(int num) {
/**
* base case
*/
if (num <= 0) {
return 0;
}
/**
* recursive case
*/
return num + sum(num - 1);
}
private static int sumWithLoop(int num) {
int total = 0;
for (int i = 0; i <= num; i++) {
total += i;
}
return total;
}
10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
…
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
Factorial with Recursion
/**
* Recursion used for factorial<br>
* Start from the top and go to bottom, then calculation will start from bottom back to top
*/
private static int factorial(int num) {
/**
* validation
*/
if (num < 0) {
throw new IllegalArgumentException("num is invalid");
}
/**
* base case
*/
if (num == 0) {
return 1;
}
/**
* recursive case
*/
return num * factorial(num - 1);
}
private static int factorialWithLoop(int num) {
int fact = 0;
for (int i = 1; i <= num; i++) {
fact = fact * i;
}
return fact;
}
Fibonacci with Recursion
/**
* Recursion used for fibonacci<br>
* Start from the top and go to bottom, then calculation will start from bottom back to top
*/
private static int fibonacci(int num) {
if (num <= 1) {
return num;
}
int number1 = fibonacci(num - 1);
int number2 = fibonacci(num - 2);
return number1 + number2;
}
private static int fibonacciWithLoop(int num) {
int indexNumber = 0;
int number1 = 0;
int number2 = 1;
int sum = 0;
for (int i = 0; i < num; i++) {
sum = number1 + number2;
number1 = number2;
number2 = sum;
indexNumber = sum;
}
return indexNumber;
}
Fibonacci with Momeization
private static int fibonacci(int num, Map<Integer, Integer> map) {
if (num <= 1) {
return num;
}
if (map.containsKey(num)) {
return map.get(num);
}
int number1 = fibonacci(num - 1, map);
int number2 = fibonacci(num - 2, map);
int sum = number1 + number2;
map.put(num, sum);
return sum;
}
Map<Integer, Integer> map = new HashMap<>(); int total = fibonacci(9, map);