# Tutor profile: Kumud I.

## Questions

### Subject: Chemistry

What Is Organic Chemistry? Where Is Organic Chemistry Used? Which Industries Hire Organic Chemists?

Organic chemistry is the study of the structure, properties, composition, reactions, and preparation of carbon-containing compounds, which include not only hydrocarbons but also compounds with any number of other elements, including hydrogen (most compounds contain at least one carbon–hydrogen bond), nitrogen, oxygen, halogens, phosphorus, silicon, and sulfur. This branch of chemistry was originally limited to compounds produced by living organisms but has been broadened to include human-made substances such as plastics. The range of application of organic compounds is enormous and also includes, but is not limited to, pharmaceuticals, petrochemicals, food, explosives, paints, and cosmetics. Organic chemistry is a highly creative science in which chemists create new molecules and explore the properties of existing compounds. It is the most popular field of study for ACS chemists and Ph.D. chemists. Organic compounds are all around us. They are central to the economic growth of the United States in the rubber, plastics, fuel, pharmaceutical, cosmetics, detergent, coatings, dyestuff, and agrichemical industries, to name a few. The very foundations of biochemistry, biotechnology, and medicine are built on organic compounds and their role in life processes. Many modern, high-tech materials are at least partially composed of organic compounds . Organic chemists spend much of their time creating new compounds and developing better ways of synthesizing previously known compounds. Organic chemists at all levels are generally employed by pharmaceutical, biotech, chemical, consumer product, and petroleum industries. Chemists in industry mainly work in development, while chemists in academia are involved in more basic research. The federal (e.g., Food and Drug Administration, Patent and Trademark Office) state, and local governments also hire organic chemists. Biotechnology Biotechnology (“biotech” for short) is a field of applied biology that involves using living organisms and bioprocesses to create or modify products for a specific use. The cultivation of plants has been viewed as the earliest example of biotechnology and the precursor to modern genetic engineering and cell and tissue culture technologies. Virtually all biotechnology products are the result of organic chemistry. Biotechnology is used in in health care, crop production and agriculture, nonfood uses of crops and other products (e.g., biodegradable plastics, vegetable oil, biofuels), and environmental applications. Biotechnology Companies: GenenTech, Monsanto, Dow AgroSciences, Cargill These companies make products such as seeds for crops that are resistant to certain diseases, seed coatings with specific properties, and plants that are drought resistant. Chemical The chemical industry is crucial to modern world economies and works to convert raw materials such as oil, natural gas, air, water, metals, and minerals into more than 70,000 different products. These base products are then used to make consumer products in addition to manufacturing, service, construction, agriculture, and other industries. Over three-fourths of the chemical industry’s output worldwide is polymers and plastics. Chemicals are used to make a wide variety of consumer goods, as well as thousands of products that are inputs to the agriculture, manufacturing, construction, and service industries. The chemical industry itself consumes about a quarter of its own output. Major industrial customers include rubber and plastic products, textiles, apparel, petroleum refining, pulp and paper, and primary metals. Chemical companies: BASF, Bayer, Braskem, Celanese, Dow, DuPont, Eastman Consumer Products Consumer products companies make consumer products for everyday use, such as soaps, detergents, cleaning products, plastic goods, and cosmetics. Consumer products companies: PPG Industries, DuPont, Mitsubishi Chemical, Johnson & Johnson Petroleum The petroleum industry includes the global processes of exploration, extraction, refining, transporting, and marketing petroleum products. The largest volume products of the industry are fuel oil and gasoline. Petroleum is also the raw material for many chemical products, including pharmaceuticals, solvents, fertilizers, pesticides, and plastics. The industry is usually divided into three major components: upstream (exploration and production), midstream (transportation), and downstream (refining crude oil, processing and purifying natural gas, creating petrochemicals). Petroleum companies: ExxonMobil, Shell Chemicals, Chevron Phillips Chemial Company, BP Pharmaceutical The pharmaceutical industry develops, produces, and markets drugs licensed for use as medications for humans or animals. Some pharmaceutical companies deal in brand-name (i.e., has a trade name and can be produced and sold only by the company holding the patent) and/or generic (i.e., chemically equivalent, lower-cost version of a brand-name drug) medications and medical devices (agents that act on diseases without chemical interaction with the body). Pharmaceuticals (brand name and generic) and medical devices are subject to a large number of country-specific laws and regulations regarding patenting, testing, safety assurance, efficacy, monitoring, and marketing. Pharmaceuticals companies: Pfizer, Novartis, Merck, Bayer, GlaxoSmithKline, Johnson & Johnson, Sanofi, Hoffman-LaRoche, AstraZeneca, and Abbott Laboratories.

### Subject: C++ Programming

Find minimum s-t cut in a flow network In a flow network, an s-t cut is a cut that requires the source ‘s’ and the sink ‘t’ to be in different subsets, and it consists of edges going from the source’s side to the sink’s side. The capacity of an s-t cut is defined by the sum of capacity of each edge in the cut-set. (Source: Wiki) The problem discussed here is to find minimum capacity s-t cut of the given network. Expected output is all edges of the minimum cut.

Minimum Cut and Maximum Flow Like Maximum Bipartite Matching, this is another problem which can solved using Ford-Fulkerson Algorithm. This is based on max-flow min-cut theorem. The max-flow min-cut theorem states that in a flow network, the amount of maximum flow is equal to capacity of the minimum cut. See CLRS book for proof of this theorem. From Ford-Fulkerson, we get capacity of minimum cut. How to print all edges that form the minimum cut? The idea is to use residual graph. Following are steps to print all edges of minimum cut. 1) Run Ford-Fulkerson algorithm and consider the final residual graph. 2) Find the set of vertices that are reachable from source in the residual graph. 3) All edges which are from a reachable vertex to non-reachable vertex are minimum cut edges. Print all such edges. Following is C++ implementation of the above approach. C++Java // C++ program for finding minimum cut using Ford-Fulkerson #include <iostream> #include <limits.h> #include <string.h> #include <queue> using namespace std; // Number of vertices in given graph #define V 6 /* Returns true if there is a path from source 's' to sink 't' in residual graph. Also fills parent[] to store the path */ int bfs(int rGraph[V][V], int s, int t, int parent[]) { // Create a visited array and mark all vertices as not visited bool visited[V]; memset(visited, 0, sizeof(visited)); // Create a queue, enqueue source vertex and mark source vertex // as visited queue <int> q; q.push(s); visited[s] = true; parent[s] = -1; // Standard BFS Loop while (!q.empty()) { int u = q.front(); q.pop(); for (int v=0; v<V; v++) { if (visited[v]==false && rGraph[u][v] > 0) { q.push(v); parent[v] = u; visited[v] = true; } } } // If we reached sink in BFS starting from source, then return // true, else false return (visited[t] == true); } // A DFS based function to find all reachable vertices from s. The function // marks visited[i] as true if i is reachable from s. The initial values in // visited[] must be false. We can also use BFS to find reachable vertices void dfs(int rGraph[V][V], int s, bool visited[]) { visited[s] = true; for (int i = 0; i < V; i++) if (rGraph[s][i] && !visited[i]) dfs(rGraph, i, visited); } // Prints the minimum s-t cut void minCut(int graph[V][V], int s, int t) { int u, v; // Create a residual graph and fill the residual graph with // given capacities in the original graph as residual capacities // in residual graph int rGraph[V][V]; // rGraph[i][j] indicates residual capacity of edge i-j for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph[u][v] = graph[u][v]; int parent[V]; // This array is filled by BFS and to store path // Augment the flow while tere is path from source to sink while (bfs(rGraph, s, t, parent)) { // Find minimum residual capacity of the edhes along the // path filled by BFS. Or we can say find the maximum flow // through the path found. int path_flow = INT_MAX; for (v=t; v!=s; v=parent[v]) { u = parent[v]; path_flow = min(path_flow, rGraph[u][v]); } // update residual capacities of the edges and reverse edges // along the path for (v=t; v != s; v=parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; } } // Flow is maximum now, find vertices reachable from s bool visited[V]; memset(visited, false, sizeof(visited)); dfs(rGraph, s, visited); // Print all edges that are from a reachable vertex to // non-reachable vertex in the original graph for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) if (visited[i] && !visited[j] && graph[i][j]) cout << i << " - " << j << endl; return; } // Driver program to test above functions int main() { // Let us create a graph shown in the above example int graph[V][V] = { {0, 16, 13, 0, 0, 0}, {0, 0, 10, 12, 0, 0}, {0, 4, 0, 0, 14, 0}, {0, 0, 9, 0, 0, 20}, {0, 0, 0, 7, 0, 4}, {0, 0, 0, 0, 0, 0} }; minCut(graph, 0, 5); return 0; }

### Subject: C Programming

Given a graph and a source vertex in graph, find shortest paths from source to all vertices in the given graph. Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has minimum distance from source. Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices in the given graph. Algorithm 1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty. 2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first. 3) While sptSet doesn’t include all vertices ….a) Pick a vertex u which is not there in sptSetand has minimum distance value. ….b) Include u to sptSet. ….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v. Let us understand with the following example: The set sptSetis initially empty and distances assigned to vertices are {0, INF, INF, INF, INF, INF, INF, INF} where INF indicates infinite. Now pick the vertex with minimum distance value. The vertex 0 is picked, include it in sptSet. So sptSet becomes {0}. After including 0 to sptSet, update distance values of its adjacent vertices. Adjacent vertices of 0 are 1 and 7. The distance values of 1 and 7 are updated as 4 and 8. Following subgraph shows vertices and their distance values, only the vertices with finite distance values are shown. The vertices included in SPT are shown in green color. Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). The vertex 1 is picked and added to sptSet. So sptSet now becomes {0, 1}. Update the distance values of adjacent vertices of 1. The distance value of vertex 2 becomes 12. Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). Vertex 7 is picked. So sptSet now becomes {0, 1, 7}. Update the distance values of adjacent vertices of 7. The distance value of vertex 6 and 8 becomes finite (15 and 9 respectively). Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). Vertex 6 is picked. So sptSet now becomes {0, 1, 7, 6}. Update the distance values of adjacent vertices of 6. The distance value of vertex 5 and 8 are updated. We repeat the above steps until sptSet doesn’t include all vertices of given graph. Finally, we get the following Shortest Path Tree (SPT). How to implement the above algorithm?

Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other vertices in the given graph. Algorithm 1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty. 2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first. 3) While sptSet doesn’t include all vertices ….a) Pick a vertex u which is not there in sptSetand has minimum distance value. ….b) Include u to sptSet. ….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v. Let us understand with the following example: The set sptSetis initially empty and distances assigned to vertices are {0, INF, INF, INF, INF, INF, INF, INF} where INF indicates infinite. Now pick the vertex with minimum distance value. The vertex 0 is picked, include it in sptSet. So sptSet becomes {0}. After including 0 to sptSet, update distance values of its adjacent vertices. Adjacent vertices of 0 are 1 and 7. The distance values of 1 and 7 are updated as 4 and 8. Following subgraph shows vertices and their distance values, only the vertices with finite distance values are shown. The vertices included in SPT are shown in green color. Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). The vertex 1 is picked and added to sptSet. So sptSet now becomes {0, 1}. Update the distance values of adjacent vertices of 1. The distance value of vertex 2 becomes 12. Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). Vertex 7 is picked. So sptSet now becomes {0, 1, 7}. Update the distance values of adjacent vertices of 7. The distance value of vertex 6 and 8 becomes finite (15 and 9 respectively). Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). Vertex 6 is picked. So sptSet now becomes {0, 1, 7, 6}. Update the distance values of adjacent vertices of 6. The distance value of vertex 5 and 8 are updated. We repeat the above steps until sptSet doesn’t include all vertices of given graph. Finally, we get the following Shortest Path Tree (SPT). How to implement the above algorithm? // A C / C++ program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph #include <stdio.h> #include <limits.h> // Number of vertices in the graph #define V 9 // A utility function to find the vertex with minimum distance value, from // the set of vertices not yet included in shortest path tree int minDistance(int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } // A utility function to print the constructed distance array int printSolution(int dist[], int n) { printf("Vertex Distance from Source\n"); for (int i = 0; i < V; i++) printf("%d \t\t %d\n", i, dist[i]); } // Funtion that implements Dijkstra's single source shortest path algorithm // for a graph represented using adjacency matrix representation void dijkstra(int graph[V][V], int src) { int dist[V]; // The output array. dist[i] will hold the shortest // distance from src to i bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest // path tree or shortest distance from src to i is finalized // Initialize all distances as INFINITE and stpSet[] as false for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; // Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (int count = 0; count < V-1; count++) { // Pick the minimum distance vertex from the set of vertices not // yet processed. u is always equal to src in first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent vertices of the picked vertex. for (int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, there is an edge from // u to v, and total weight of path from src to v through u is // smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]+graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } // print the constructed distance array printSolution(dist, V); } // driver program to test above function int main() { /* Let us create the example graph discussed above */ int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0}, {4, 0, 8, 0, 0, 0, 0, 11, 0}, {0, 8, 0, 7, 0, 4, 0, 0, 2}, {0, 0, 7, 0, 9, 14, 0, 0, 0}, {0, 0, 0, 9, 0, 10, 0, 0, 0}, {0, 0, 4, 14, 10, 0, 2, 0, 0}, {0, 0, 0, 0, 0, 2, 0, 1, 6}, {8, 11, 0, 0, 0, 0, 1, 0, 7}, {0, 0, 2, 0, 0, 0, 6, 7, 0} }; dijkstra(graph, 0); return 0; }

## Contact tutor

needs and Kumud will reply soon.