text:
# Experimental investigation of the fluid–structure interaction in an elastic 180° curved vessel at laminar oscillating flow

Experimental investigation of the fluid–structure interaction in an elastic 180° curved vessel... Fluid–structure interaction phenomena are extremely important when laminar flows through elastic vessels such as in biomedical flow problems are considered. In general, such elastic vessels are curved which is why an elastic 180° bend at a curvature ratio $$\delta = D/D_{\rm C} = 0.\bar{2}$$ δ = D / D C = 0 . 2 ¯ defines the reference geometry in this study. It is the purpose of this study to compare the results with the steady flow through a 180° rigid pipe bend and to quantify the impact of the fluid–structure interaction on the overall flow pattern and the vessel deformation at oscillating fully developed entrance flow. The findings comprise velocity, pressure, and structure deformation measurements. The vessel dilatation amplitude was varied between 3.75 % and 7 % of the vessel diameter at Dean De and Womersley number Wo ranges of $$327\,\le\,De\,\le\,350$$ 327 ≤ D e ≤ 350 and $$7\,\le\,Wo\,\le\,8.$$ 7 ≤ W o ≤ 8 . The flow is investigated by time-resolved stereoscopic particle-image velocimetry in five radial cross sections located in the elastic 180° bend and in the inlet pipes. The unsteady static vessel pressure is measured synchronously at these cross sections. The comparison of the steady with the unsteady flow field shows a strong change in the axial and secondary velocity distributions at periods of transition between the centrifugal forces and the unsteady inertia forces dominated regimes. These changes are characterized by asymmetric fluctuations of the centers of the counter-rotating vortex pair. The investigation of the impact of the structure deformation amplitude on these fluctuations reveals a significant attenuation at high deformation amplitudes. The spatial motion of the elastic vessel due to the forces applied by the flow exhibits amplitudes up to 15 % of the vessel diameter. Considering the fluid–structure interaction, an amplification of the volume flux amplitude by a factor of 2.1 at the vessel outlet and phase lags up to 30° occur. The static pressure distribution is characterized by a pronounced asymmetry between forward and backward flow with a 40 % higher peak magnitude at backward flow and phase lags of 35°. The results evidence that a strong distortion of the velocity distribution in the bend, which is caused by the oscillating nature of the flow, is reduced as a result of the fluid–structure interaction. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Experiments in Fluids Springer Journals

# Experimental investigation of the fluid–structure interaction in an elastic 180° curved vessel at laminar oscillating flow

, Volume 55 (10) – Sep 16, 2014
13 pages

/lp/springer_journal/experimental-investigation-of-the-fluid-structure-interaction-in-an-FnV8hrWRyp
Publisher
Springer Berlin Heidelberg
Subject
Engineering; Engineering Fluid Dynamics; Fluid- and Aerodynamics; Engineering Thermodynamics, Heat and Mass Transfer
ISSN
0723-4864
eISSN
1432-1114
D.O.I.
10.1007/s00348-014-1816-3
Publisher site
See Article on Publisher Site

### Abstract

Fluid–structure interaction phenomena are extremely important when laminar flows through elastic vessels such as in biomedical flow problems are considered. In general, such elastic vessels are curved which is why an elastic 180° bend at a curvature ratio $$\delta = D/D_{\rm C} = 0.\bar{2}$$ δ = D / D C = 0 . 2 ¯ defines the reference geometry in this study. It is the purpose of this study to compare the results with the steady flow through a 180° rigid pipe bend and to quantify the impact of the fluid–structure interaction on the overall flow pattern and the vessel deformation at oscillating fully developed entrance flow. The findings comprise velocity, pressure, and structure deformation measurements. The vessel dilatation amplitude was varied between 3.75 % and 7 % of the vessel diameter at Dean De and Womersley number Wo ranges of $$327\,\le\,De\,\le\,350$$ 327 ≤ D e ≤ 350 and $$7\,\le\,Wo\,\le\,8.$$ 7 ≤ W o ≤ 8 . The flow is investigated by time-resolved stereoscopic particle-image velocimetry in five radial cross sections located in the elastic 180° bend and in the inlet pipes. The unsteady static vessel pressure is measured synchronously at these cross sections. The comparison of the steady with the unsteady flow field shows a strong change in the axial and secondary velocity distributions at periods of transition between the centrifugal forces and the unsteady inertia forces dominated regimes. These changes are characterized by asymmetric fluctuations of the centers of the counter-rotating vortex pair. The investigation of the impact of the structure deformation amplitude on these fluctuations reveals a significant attenuation at high deformation amplitudes. The spatial motion of the elastic vessel due to the forces applied by the flow exhibits amplitudes up to 15 % of the vessel diameter. Considering the fluid–structure interaction, an amplification of the volume flux amplitude by a factor of 2.1 at the vessel outlet and phase lags up to 30° occur. The static pressure distribution is characterized by a pronounced asymmetry between forward and backward flow with a 40 % higher peak magnitude at backward flow and phase lags of 35°. The results evidence that a strong distortion of the velocity distribution in the bend, which is caused by the oscillating nature of the flow, is reduced as a result of the fluid–structure interaction.

### Journal

Experiments in FluidsSpringer Journals

Published: Sep 16, 2014

## You’re reading a free preview. Subscribe to read the entire article.

### DeepDyve is your personal research library

It’s your single place to instantly
that matters to you.

over 18 million articles from more than
15,000 peer-reviewed journals.

All for just $49/month ### Explore the DeepDyve Library ### Search Query the DeepDyve database, plus search all of PubMed and Google Scholar seamlessly ### Organize Save any article or search result from DeepDyve, PubMed, and Google Scholar... all in one place. ### Access Get unlimited, online access to over 18 million full-text articles from more than 15,000 scientific journals. ### Your journals are on DeepDyve Read from thousands of the leading scholarly journals from SpringerNature, Elsevier, Wiley-Blackwell, Oxford University Press and more. All the latest content is available, no embargo periods. DeepDyve ### Freelancer DeepDyve ### Pro Price FREE$49/month
\$360/year

Save searches from
PubMed

Create lists to

Export lists, citations


text:
# Keep Moving !!!!!

The potential energy of a particle of mass $$5kg$$ moving in the $$XY~plane$$ is given by $$U=(-7x+2y)J$$ where $$x$$ and $$y$$ are given in $$metres(m)$$ . If the particle starts from rest from the origin , then what is the velocity of the particle at time $$t=2s$$ ?????

Note : Give your answer in $$m/s$$ and avoid the units.....just write the answer as an integer !!!!!

×

format: plain


text:
T-Th 9:05
or
T-Th 11:15
in Olin 155

CS 1110: Introduction to Computing Using Python

Fall 2014

# Assignment 6:Clustering

Due to CMS by Thursday, November 20th at 11:59 pm.

Update 11/16/14: We forgot to include the precondition for the method run() in the class ClusterGroup. This is now included in the instructions below. In addition, the file a6.py has been updated.

Big Data is a major computer science topic these days. As computers become both ubiquitous and more powerful, many applications — from science to business to entertainment — are generating huge amounts of data. This data is too large to process by conventional means. That means we need new tools (such as new programming languages) and new algorithms to handle it all. The CS department has several upper level courses (such as CS 4780: Machine Learning) dedicated to this topic.

In this assignment you will work with one of the most popular (though not necessarily most efficient) tools for analyzing large amounts of data: k-means clustering. In k-means clustering, you organize the data into a small number (k) of clusters of similar values. For example, in the picture to the right, there are a lot of points in 3-dimensional space. These points are color-coded into five clusters, with all the points in a cluster being near to one another.

If you look at the wikipedia entry for k-means clustering, you can see that it has many, many applications. It has been used in market analysis, recommender systems (e.g., how Netflix recommends new movies to you), and computer vision, just to name a few. It is an essential tool to have if you are working with data. With the skills and knowledge you have been acquiring in CS 1110, you are now able to implement it yourself!

### Learning Objectives

This assignment has several important objectives.

• It gives you practice working with loops (both for-loops and while-loops).
• It gives you practice with writing your own classes.
• It illustrates the importance of class invariants.
• It gives you practice with using data encapsulation in classes.
• It gives you practice with both both 1-dimensional and 2-dimensional lists.
• It gives you experience with designing helper functions to structure your code properly.
• It demonstrates that you have the ability to implement a powerful data-analysis algorithm on real data.

Authors: W. White, D. Murphy, T. Westura, S. Marschner, L. Lee

Please review CS1110's academic integrity policies. If you talk to other students, please cite the collaboration in your source code. In addition, if you look at other sources online on K-means clustering, and use that to help with your code, please cite that as well. We have given this assignment before (though we have changed it up a bit to make it easier), so please do not look online for previous years solutions.

Depending on the amount of collaboration, we may or may not take off points. We generally reserve point deductions for sharing large amounts of code, and not just a few lines. However, we are not going to explain our deductions ahead of time. The only way to guarantee that you do not lose points is if you do not look at anyone else's code.

The bigger problem is if you do not cite your sources or collaborators at all. If we discover large similarities between two submissions, and neither of you cited the other, we will be forced to hold an Academic Integrity Hearing. Neither of us wants that.

### Collaboration Policy

You may do this assignment with one other person. If you are going to work together, then form your group on CMS as soon as possible. If you do this assignment with another person, you must work together. It is against the rules for one person to do some programming on this assignment without the other person sitting nearby and helping.

With the exception of your CMS-registered partner, is not a good idea to look at anyone else's code or show your code to anyone else, in any form what-so-ever. If you do see someone else's code, and it affects how you write your own, then you must cite the source in your submission.

## K-Means Clustering

In this section, we describe what cluster analysis is, and how we use k-means clustering to implement it. Cluster analysis is the act of grouping together similar points into groups. For example, one of the applications in this assignment is clustering for epidemiological analysis. You will get data with 2-dimensional longitude-latitude pairs of where birds carrying different strains of avian flu were found. You will cluster these into groups that give insight into different regions where the flu strain appeared.

When we say point, it could be a 2-dimensional point, a 3-dimensional point, a 4-dimensional point, and so on. In fact, we could have points of arbitrary dimension, particularly if the data is not spatial. For example, one of the data sets for this assignment is a fictional market analysis of candies. Each candy is a 4-dimensional point that represents how sweet, sour, nutty, and crunchy it is.

### Distances between Points

When we cluster points, we use the Euclidean Distance to measure the distance between them. You may already know how to compute the distance between two 2-dimensional points: $d(\mathbf{p},\mathbf{q}) = \sqrt{(p_x - q_x)^2 + (p_y - q_y)^2}$ or between 3-dimensional points: $d(\mathbf{p},\mathbf{q}) = \sqrt{(p_x - q_x)^2 + (p_y - q_y)^2 + (p_z - q_z)^2}.$ These are special cases of the general definition: given two $$n$$-dimensional points $$\textbf{p} = (p_1, p_2, \ldots, p_n)$$ and $$\textbf{q} = (q_1, q_2, \ldots, q_n)$$, the Euclidean distance between them is:

$d(\textbf{p},\textbf{q}) = \sqrt{(p_1-q_1)^2+(p_2-q_2)^2+\cdots+(p_n-q_n)^2}$

For example, suppose we have two points: $$\textbf{p} = (0.1,0.2,0.3,0.4)$$ and $$\textbf{q} = (0.0,0.2,0.3,0.2)$$. Then:

$d(\textbf{p},\textbf{q}) = \sqrt{(0.1-0.0)^2+(0.2-0.2)^2+(0.3-0.3)^2+(0.4-0.2)^2} = 0.7071\ldots$

### Cluster Centroids

Given a set of points, we can identify its centroid. The centroid is the “center of mass” of the cluster, which is to say, the average, or mean, of all of the points in the cluster. The centroid might happen to be one of the points in the cluster, but it does not have to be. For example, the picture to the right is an example of a 4-point cluster (black circles) with a centroid (red circle) that is not one of the points in the cluster.

To compute a centroid, we average. Remember that to average, you add up a collection of things and divide by the total. The same is true for points; we add up all the points, and then “divide” the result by the total number of points. Adding two points results in a new point that is the coordinate-wise addition of the two input points:

$\textbf{p}+\textbf{q} = (p_1+q_1, p_2+q_2, \ldots, p_n+q_n).$

When we divide a point by a number, the division is done coordinate-wise, as follows:

$\textbf{p}/a = (p_1/a, \>p_2/a,\> \ldots,\> p_n/a)$

### The Algorithm

The idea of k-means is quite simple: each point should belong to the cluster whose mean (centroid) it is closest to. But, the centroid of a cluster depends on which points you put into it. This creates a kind of chicken-and-egg problem, which is solved using an iterative approach: first assign points to clusters, then compute new centroids for these clusters, then re-assign points using the new centroids, and so on.

To make this general idea into a precise algorithm we can implement, we break down k-means clustering into several steps. Throughout, let $$n$$ be the dimension of the points.

#### 1. Pick $$k$$ Centroids

Our goal is to divide the points into $$k$$ adjacent groups. The first step is to guess $$k$$ centroids. Throughout these instructions, we will refer to the centroids as $$\textbf{m}_1,\textbf{m}_2,\ldots, \textbf{m}_k$$. (The letter m stands for “mean”, or centroid, which is where the algorithm's name comes from.)

Remember that the centroids are themselves $$n$$-dimensional points. Hence, for any mean $$\textbf{m}_j$$, where $$1 <= j <= k$$, we have

$\textbf{m}_j = (m_{j,1},m_{j,2},\ldots,m_{j,n})$

So each $$m_{j,i}$$ represents the ith coordinate of the jth centroid.

To pick $$k$$ centroids, all we do is choose $$k$$ points from our original dataset. We will choose these points at random, as if drawing cards from a deck. This is referred to as the Forgy Method, and it is one of the most popular ways to start k-means clustering.

#### 2. Partition the Dataset

Now that we have $$k$$ centroids, we assign every point in the data set to a centroid. We do this by matching each point to the nearest centroid $$\textbf{m}_j$$, and then have the points assigned to each centroid form a new cluster. This is known as partitioning because each point will belong to one and only one cluster.

If there happens to be a tie between which centroids are closest to a given point, we arbitrarily break the tie in favor of the $$\textbf{m}_j$$ with smallest $$j$$. If we put the centroids in a list, this would be the centroid that comes first in the list.

There will then be $$k$$ sets $$S_1, S_2, \ldots, S_k$$, where set $$S_j$$ is the cluster consisting of all the points associated with centroid $$\textbf{m}_j$$.

#### 3. Recompute the Means

Once we have the sets $$S_1, S_2, \ldots, S_k$$, we need to compute a new mean $$\textbf{m}_j$$ for each $$S_j$$. This new mean is just the average of all of the points in that set. Let

$S_j = \lbrace \textbf{q}_{1},\textbf{q}_{2},\ldots,\textbf{q}_{c_j}\rbrace$

be the set of points associated with centroid $$\textbf{m}_j$$, where $$c_j$$ is the number of points inside of $$S_j$$. Then the new mean is the $$n$$-dimensional point

$\textbf{m}_j = \frac{1}{c_j}(\textbf{q}_{1}+\textbf{q}_{2}+\cdots+\textbf{q}_{c_j}).$

The formula above uses the rules for adding points and dividing points by numbers that we discussed above. If you do not understand this formula, please talk to a staff member immediately.

Now, because we have recomputed the means, some points might be closer to the centroid for a cluster they are not currently in than to the centroid for the cluster they are in. To fix this, we repartition the dataset by going back to step 2 and proceeding as before.

#### 4. Repeat Steps 2 and 3 Until Convergence

The clustering algorithm continues this process: recompute the means and repartition the dataset. We want to keep doing this until the means stop changing. If all the means are unchanged after step 3, we know that partitioning again will produce the same clusters, which will have the same means, so there is no point in continuing. When this happens, we say that the algorithm has converged.

Sometimes it can take a very long time to converge — thousands of thousands of steps. Therefore, when we implement k-means clustering, we often add a “time-out factor”. This is a maximum number of times to repeat steps 2 and 3. If the algorithm does not converge before this maximum number of times, we stop anyway, and use the clusters that we do have.

### Classes Used in Our Implementation

Classes are ideal for representing complex mathematical objects. For example, we saw in class how to use classes to represent rectangles or times of day. There are several interesting mathematical objects in the description above (points, centroids, sets/clusters) and we could use classes to represent all of these.

Deciding which of these things to create classes for is the core of object-oriented software design. For this assignment we have made these decisions for you, since it is not always easy to hit the right balance of complexity against structure the first time, and we want you to spend your time implementing rather than redesigning.

For our implementation of k-means, we decided not to use classes to represent points and centroids, because Python's built-in lists serve well enough. In particular, you should not use the Point class in tuple3d. That class only supports 3-dimensional points, but we would like to support points in any dimension.

In the end, we decided to create classes for three important concepts in k-means. First there is the entire dataset, represented by an instance of the class Dataset. Second, there is a cluster of data, represented by an instance of the class Cluster. Finally, there is the set of clusters created by k-means, represented by an instance of the class ClusterGroup.

#### Points are Lists

Throughout this assignment, a point will be represented as a list of numbers; both ints and floats are allowed. This is true for centroids as well. For example, here is an example of a possible centroid if we were working with 4-dimensional points:

$\textbf{m}_j \mbox{ is represented as the list } [0.1, 0.5, 0.3, 0.7].$

In this example, if x stores the name of the list, then $$m_{j,2}$$ (using the notation from a previous section) is x[1], or 0.5, while $$m_{j,4}$$ is x[3], or 0.7. Note that our mathematical notation starts at 1, while list indices start at 0.

#### Class Dataset

The k-means algorithm starts with a dataset—a collection of points that will be grouped into clusters. This dataset is stored in an instance of the class Dataset. This class is very simple; it just holds the list of points, so its most important attribute is:

• _contents: A list of points inside this dataset

For example, if a dataset contains the points (0.1,0.5,0.3,0.7) and (0.2,0.0,0.2,0.1), then the attribute _contents is

[[0.1,0.5,0.3,0.7], [0.2,0.0,0.2,0.1]]

The points are all lists of numbers, and they all have to be the same length; remember that this length is the dimension of the data. We keep track of this dimension in a second attribute:

• _dimension: The dimension of all points in this dataset

The fact that all the points are supposed to have the right dimension is expressed by a class invariant: “The number of columns in _contents is equal to _dimension. That is, for every item _contents[i] in the list _contents, len(_contents[i]) == _dimension.”

You might argue that storing the dimension separately is redundant, since you could always look at the points in _contents to find it, but we would like the dimension to be defined even before we add any points to the dataset.

One of the things that you might notice about these attributes is that they all start with an underscore. As we mentioned in class, that is a coding convention to indicate that the attributes should not be accessed directly outside of the class Dataset. In particular, neither Cluster not ClusterGroup should access these attributes at all. When those two classes do need to access these attributes, they should do it through getters and setters. One of the things you will do in this assignment is implement these getters and setters.

#### Class Cluster

The next idea in the algorithm that we have defined a class for is a cluster $$S_j$$. To support this type, we defined the class Cluster. Objects of this class will actually hold two different values: the centroid $$\textbf{m}_j$$ and the set $$S_j$$. We do this because the centroid and cluster are associated with one another, so it makes sense to store them in a single object. We need two attributes corresponding to these ideas:

• _centroid: A list of numbers representing the point $$\textbf{m}_j$$
• _indices: A list of integers that are the indices where the points of this cluster can be found in the dataset.

Note that we are not storing the points belonging to a cluster; we are only storing the indices of the points in the dataset. This simplifies Cluster because it does not need to worry about maintaining lists of lists. Code that works with clusters does need to be able to get to the points, however, so one of its instance variables is a reference to the dataset:

• _dataset: The dataset of which this cluster is a subset.

Once again, these attributes start with an underscore, so we want getters and setters if we are going to access them in the class ClusterGroup (it is okay if a method in Cluster accesses one of its own attributes with an underscore in it). So again, you need getters, like getCentroid and setters like addIndex. There is also a special getter getContents that returns a copy of the points to be used by the visualizers.

In addition to the getters and setters, the class Cluster is the logical place to put code that does computations involving a single cluster. Reading the description of the k-means algorithm above, we find that the two core operations with clusters are computing the distance from a point to a cluster's centroid and finding a new centroid for the cluster. These operations are handled by the two most important methods of the Cluster class:

• A method to find the distance from a point to the cluster (distance)
• A method to compute a new centroid for a cluster (updateCentroid)

Finally, this class contains the special Python methods __str__ and __repr__. This methods are to help you with printing clusters more informative while debugging.

#### Class ClusterGroup

Since experimenting with the number of clusters is an important part of using the algorithm, we want to create several clusterings of the same data. For this reason, the final class represents a cluster group of the dataset; that is, a set of clusters that together cover the whole dataset. The data stored in this class is simple: a list of clusters, and as with Cluster, a reference back to the dataset.

• _dataset: The dataset we are clustering
• _clusters: The list of current clusters $$S_1, \ldots, S_k$$

Once again, we have getters and setters for these attributes. But the important methods of class ClusterGroup are the core of the k-means algorithm.

• A method to partition the dataset, implementing step 2 of the algorithm (_partition)
• A helper method for _partition to find the nearest cluster to a point (_nearest_cluster)
• A method to update all the cluster centroids, implementing step 3 (_update)

Finally there are the methods that orchestrate the whole process:

• A method that executes one step of the process, updating the centroids and re-partitioning the data (step)
• A method that computes a clustering, from start to finish (run)

So a user of the class who just wants to cluster a dataset into $$k$$ clusters would create a Dataset, add all the points to it, create a ClusterGroup with $$k$$ clusters, and then call run on that cluster group.

You will notice that some of the methods have names starting with an underscore. The meaning is the same as with attribues: these methods are meant to be used internally rather than called directly by code outside the ClusterGroup class.

## How to Work on the Assignment

This assignment involves implementing several things before you'll have the whole method working. As always, the key to finishing is to pace yourself and make effective use of all of the unit tests and the visualizers that we provide.

### Assignment Source Code

You should download the zip archive code.zip from this link. Unzip it and put the contents in a new directory. This time, you will see that this directory contains several things:

a6.py
This module contains the whole implementation of the clustering algorithm. It is the only file that you will need to modify and submit.
a6test.py
This file is a unit test to provide you with even more help with this assignment. Is not a 100% complete unit test, but you are not required to finish it. We describe this in more detail below.
plot3d.py
This is a GUI that will help you see what is going on, using an example with 3D points. We describe how it works below.
mapcluster
This is a folder with several files. It provides another GUI that will let you work with geographic data where the points are 2D and represent (longitude, latitude) pairs. We describe how it works below.
datasets
This is a folder with many sample data sets. They are useful for working with the two GUIs provided. We explain them in the discussion of the two GUIs below.

### Pacing Yourself

This assignment has a problem: there is an exam in the middle of the assignment. There is not much we can do about this. In alternating years, either this assignment or the color model assignment has a prelim in the middle. This year it is clustering.

To make matters worse, parts of this assignment will be covered by the exam. In particular, both the class Dataset (in its entirety) and Part A of Cluster are fair game. You should do everything that you can to finish these parts of the assignment before the due dates.

Once again, at the end of each part, we have a suggested completion date. While this is not enforced, we recommend that you try to hit these deadlines. If you cannot make these deadlines, it might be a sign that you are having difficulty and need some extra help. In that case, you should see a staff member as soon as possible.

### Using the Unit Test

We have provided a unit test module that runs the three classes in the kmeans module through their paces. It is split into several phases corresponding to implementation strategy below. If you follow our suggested strategy for implementing the assignment, then the unit test will help you check that one part is okay before moving on to the next step.

This unit test script is fairly long, but if you learn to read what this script is doing, you will understand exactly what is going on in this assignment and it will be easier to understand what is going wrong when there is a bug. You are encouraged to sit down with a staff member to talk about the unit test, to help you understand it better.

With that said, this unit test is not complete. It does not have full coverage of all the major cases, and it may miss some bugs in your code. In past semesters, we have seen many unusual errors that were not caught by this unit test. You may want to add additional tests as you debug, and that is fine. However, we do not want you to submit the file a6test.py when you are done, even if you made modifications to the file.

### Using the Visualizers

There are two visualizers provided with this code. They help you see what your implementation is doing. They will only work properly once you have completed the entire assignment. However, even if you have not completed the assignment, they are still useful and will show some information.

#### Visualizing K-Means on 3D-points

The visualizer plot3d.py is designed to be run as a script. To get it working, navigate to the assignment directory and type

python plot3d.py

When you start the visualizer for the first time, it will look like the window shown below. You will see a empty plot of 3-dimensional axis, as well as some buttons and menus to the right. If you click on the window with the plot, you can move the axes. You will find this useful when you are trying to look at three-dimensional data.

This GUI is not going to do anything until you start implementing the various parts of this assignment. Once you have most of the assignment completed (up to Part C of ClusterGroup), you can use the visualizer to perform a k-means clustering on a three-dimensional data set.

Once you have everything working, click on the button to select a file and load the file sample.csv. Your initialization step will pick three random centroids and partition the data. The result will look something like the following:

Note that each cluster is a different color. The points in the cluster are crosses, while the solid circle is the centroid.

You can use the pull-down menu to change the k-value. There is a limit on the number of k values you can choose because there are only so many different colors that we could think of. Whenever you change the k, it will reinitialize the centroids. It will also reinitialize the centroids when you hit the reset button.

Each time you hit the step button, it will perform step 3 of the k-means algorithm. You can watch the centroids change as you hit the button. When the algorithm converges, you will see the word "True" after Finished and the step button will no longer do anything. Below is a picture of a finished computation with final versions of the clusters.

This visualizer will work with any CSV file whose last three values on each line are numbers. For example, the data files candy.csv and small_candy.csv contain the 4-dimensional data (sweetness, sourness, nuttiness, and texture) that we described above. The file plot3d.py can visualize these as well, but only the last three values (sourness, nuttiness, and texture).

This visualizer will not work with the map data H3N8.avian.usa.csv and H4N6.avian.usa.csv. The files contain map data, and the rows only have two numbers.

#### Visualizing K-Means on Longitude and Latitude

The second visualizer is contained in a folder mapcluster. To get it working, you actually run the folder as a script. In other words, navigate to the assignment directory (not the folder mapcluster). Then type

python mapcluster

This will execute the script __main__.py inside of this folder, which in turn imports the other modules inside of the folder. We did this because we did not write all of the GUI ourselves. Some of the files in this folder were written by other people, so it was easier to organize the GUI as a folder than as a single file.

When you run this program it will look very similar to plot3d.py. The main difference is that it displays a map (which will be blank until a dataset is loaded) of the world.

To try it out, load either the data set H3N8.avian.usa.csv or H4N6.avian.usa.csv. These files contain data about influenza in birds. Each data point indicates a location where a bird was found that had a particular strain of avian influenza (bird flu). We might want to understand geographical differences in what regions these two strains tend to appear in.

These files contain repeated points for when multiple specimens were found in the same location. So the location of a cluster centroid may not be in what looks like the geographic center of its points, because you cannot see when multiple points are on top of each other.

These files were created from publicly available data accessible from the Animal Surveillance section of the Influenza Research Database. See Squires et al. (2012) Influenza research database: an integrated bioinformatics resource for influenza research and surveillance. Influenza and Other Respiratory Viruses, DOI: 10.1111/j.1750-2659.2011.00331.x.

### Asserting Preconditions

Once again, we want you to get into the habit of asserting preconditions. Unlike the last assignment, we are not making a distinction between enforced and normal preconditions. If it is a precondition, you should enforce it with an assert statement.

Some of the preconditions are quite complete this time. For example, method addPoint in Dataset requires that point is a list of numbers. There are two different things to check here:

• point is a list.
• Every element of point is a number (int or float)

The second part requires a for-loop (or equivalent) to check, and we do no know how to mix for-loops and asserts. The best way to handle this precondition is to write a helper function that returns True if these are both true, and False if not. We have provided this helper is_point for you in a6.py. To use it in the method addPoint, you simply write

assert is_point(point)

As with Assignment 4, we are not requiring any error messages with you assert statements. Note that this is not the only part of the precondition in addPoint to enforce, but it is hardest part.

As you work on this assignment, you may decide to write more helpers to enforce your preconditions. When you write your helpers, you need to remember to write a specification for each helper. The helpers should not have any preconditions. They should be prepared for any argument. It is not very useful to check preconditions with function or method that has its own preconditions.

## Recommended Implementation Strategy

In the file a6.py we have provided the definitions for the three classes discussed above. You have the class invariants and all method specifications, but almost all the method bodies are just stubs. Your task is to implement all the stubbed methods in these classes. We recommend starting with Dataset, since that is needed by the other classes. Then implement Cluster, and test that all its methods are working correctly. Finally implement and test ClusterGroup. When that is working correctly, your assignment is finished.

### The Dataset Class

This class has six methods: the initializer, four getters and a setter. The specifications of all of these methods are included in the file a6.py. The getters are the most straight-forward. Most of the time, you just need to return the attribute.

The only tricky getter is getPoint. Remember that when you return a list, you are returning the name of the folder. So, once we get a point from the Dataset, we could change its contents, potentially corrupting the dataset. getPoint always copies the point before it returns it, ensuring that we cannot accidentally corrupt the data set. The unit test a6test.py has a test to make sure that you did this correctly.

Similarly, when you implement the initializer, note that the specification says that the class is supposed to keep a copy of the parameter contents. In this context this means that you need to set the _contents attribute to a new list that contains copies of all the points in contents. Just writing contents[:] won't do it—that creates a new list that has references to the same points. A question to consider is, how do you copy all those individual lists? You may need a loop of one form or another.

Finally, when you implement addPoint, be sure that it also adds a copy of the provided point to the dataset.

#### Asserting Preconditions

As a last step, you should go back to every method with preconditions and assert those preconditions. This includes both the initializer and the setters. Recall that preconditions are how we preserve the invariants, so asserting the preconditions prevents the invariants from being violated.

As we explained above, you may want helper functions to assert the preconditions. For example, the initializer requires that contents is a 2D list of either ints or floats. There are a three things to check here:

• contents is a list.
• Every element of contents is a point (list of numbers).
• Every element of contents has the same length.

It would be best to write a helper function called is_point_list to check these three.

#### Testing it Out

Once you complete the Dataset class, you can run the unit test script. If you see output that says

class Dataset appears correct

You can also try your code in the visualizers. Run either visualizer and load a data file as described above. The points will only be displayed as black crosses, and the algorithm controls will not work, but you will be able to see the data.

If you click on the Reset button, you will see some error messages in the terminal saying FAILED VISUALIZATION. This is perfectly normal. These error messages are the visualizer letting us know that it was not able to form clusters yet and that it shifted down to testing just the Dataset part of your code only.

It is extremely important that you finish Dataset by Sunday, November 9. This guarantees that you have written a complete class before the exam, as this will be one of the questions on the exam.

### The Cluster Class

The class Cluster is a little more involved that Dataset, so we have broken it up into two parts: Part A and Part B. Each part has its own test procedure in a6test.py, so you can fully test one part before moving on to the next.

#### Part A: Getters and Setters

The specification for the Cluster class mentions the following instance attributes:

Instance Attributes:
_dataset [Dataset]: the dataset this cluster is a subset of
_indices [list of int]: the indices of this cluster's points
in the dataset
_centroid [list of numbers]: the centroid of this cluster
Extra Invariants:
len(_centroid) == _dataset.getDimension()
0 <= _indices[i] < _dataset.getSize(), for all 0 <= i < len(_indices)

Once again, these attributes begin with an underscore, which means that you will need to implement getters and setters. Once again these are straight-forward. The only unusual one if getContents. the return value is supposed to be a list containing (copies of) the points themselves, not the indices of the those points. You will need to loop over the indices, creating copies of the corresponding points from the database and collecting those copies in a newly created list.

You will also need to implement the initializer in this part of the assignment. When you are done, remember to assert all your preconditions.

#### Part B: distance and updateCentroid

The last two methods are more complex methods that are necessary for the k-means algorithm. To implement distance, refer to the definition of euclidean distance given earlier in this document.

The function updateCentroid is the most complex function in this class. You will need to first go through all the points, adding up their coordinates. You need the sum of the first coordinates of all the points in the cluster, the sum of all the second coordinates, and so on. After that, you will need to divide by the number of points in the cluster. Finally, you need to decide whether the centroid has changed. The function numpy.allclose is mentioned in the specification. This function takes two lists of numbers and tells you whether the corresponding numbers from the two lists are all very close in value.

When you are done, remember to assert all your preconditions.

#### Testing it Out

Once you complete each of these two parts, run the unit test. If everything is working, you will get the appropriate message.

Once you complete both parts, you will see that the visualizers have a lot more functionality. When you load up a data file and click the Reset button, you will see all points in the data set as blue markers in the plot window. In addition, you will see a blue circle with black border representing an initial centroid.

There will still be the error message FAILED VISUALIZATION printed out somewhere in the command shell. This is normal.

Ideally, you should try to finish Cluster by Tuesday, November 10. That means you will have completed two classes and can spend the rest of the week studying for the exam. At the very least, you should complete Part A before the exam, leaving only Part B for after the exam.

### The ClusterGroup Class

The last class to implement is the ClusterGroup class. As before, you need to implement the methods following their specifications. The methods in this class do a lot, but because of all the work you did in the lower-level classes, the code for these methods are reasonable.

Once again, we have broken this assignment up into several parts. Each part has its own test procedure in kmean_test.py.

#### Part A: The Initializer

The initializer has the job of setting up the clusters to their initial states so that the first iteration of the algorithm can proceed. Each cluster needs its centroid initialized, but will start with no data points in it until the first partitioning step. You will need to create a list of Cluster objects, and each one needs to be created using a point for its centroid. We draw these points at random from the dataset, but we do not want to select the same point twice, so simply selecting $$k$$ random indices into the dataset will not do it.

Fortunately, in the random package there is a function random.sample that selects a number of items from a list. The returned list has no duplicates in it. You should use this function to select which points from the dataset will become the seeds of clusters.

The specification for the initializer also supports the caller specifying exactly which points to use as cluster seeds. This is primarily for testing. Your code will have to do something a bit different depending on whether the seed_inds parameter is supplied. Once again, remember to assert all your preconditions.

There is only one getter to implement in Part A. Since ClusterGroup accesses other classes, but no classes access it, it does not need a lot of getters.

Now that the exam is over, try to finish Part A of ClusterGroup by Saturday, November 14. You should also have Part B of Cluster done by this point as well.

#### Part B: Partitioning

In the next step, you implement the two methods necessary to partition the data set among the different clusters. When implementing the _nearest_cluster method, you should use a loop over the list of clusters, since they are the possible candidates. During the execution of your loop, you may want to keep track of both the nearest cluster found so far and the distance to the nearest cluster found so far. An interesting question (with more than one good answer) is what you should initialize these values to.

The _partition method separates all the points into clusters. It can be very simple since the distance computation is already implemented in Cluster.

Try to finish Part B of ClusterGroup by Monday, November 16.

#### Part C: Update

The next two methods are used to perform a single step in the k-means algorithm. The _update method involves updating all the clusters, which is easy because the core operation is already implemented in Cluster. The only complication is keeping track of whether all the centroids remained unchanged. One approach is to do something similar to what you did for finding the nearest cluster: keep track of whether a changed centroid has been seen so far.

The step method is simple once you have _update and _partition. If you do it right, it is only two lines.

Try to finish Part C of ClusterGroup by Tuesday, November 19. Notice this is only one day after the previous part. By this point you have completed most of the hard work and the method implementations should actually be getting easier.

#### Part D: Run

The final method run involves calling step repeatedly. The only issue is that you have to know when to stop. This suggests a while-loop with a certain stopping condition.

This method takes an argument, so you should remember to assert your preconditions. Once you have implemented this method, you are done with the assignment. Update 11/16/14: We forgot to include the precondition for this method. The preconditions is maxstep is an int >= 0.

#### Testing it Out

Once you complete each part of ClusterGroup, run the unit test. If everything is working, you will get the appropriate message, just like with Cluster.

You can also test this part in the visualizer. When you load a data file, you should be able to run the entire clustering process. You can see the initial clusters once the Clustering initializer is working. Once part C is done, you can seeing the process of refining clusters step by step. You should be able to visually confirm the operation of the algorithm; after each iteration, each point should have the same color as the nearest centroid.

You might find it interesting to try different numbers of clusters for the avian flu datasets, or to run k-means clustering on them several times, and see how the means move around. Note that if you have “too few” clusters, points that seem far apart end up in the same cluster; but if you have “too many” clusters, you get clusters that seem to lie “too close” to each other. For example, with the H4N6 data, sometimes you get more than one cluster for the Alaska locations, which does not seem right; but sometimes you get the Alaska and California points all in the same cluster, which may also not seem right. Cluster analysis can be finicky. But you should often see the algorithm “discovering” clusters that correspond to identifiable geographic regions, which is kind of cool. Do you see any correlation with lakes and waterways?

## Finishing the Assignment

Once you have everything working you should go back and make sure that your program meets the class coding conventions. In particular, you should check that the following are all true:

• There are no tabs in the file, only spaces (in Komodo Edit tabs look like arrows if whitespace is visible)
• Functions are each separated by two blank lines.
• Lines are short enough (80 chars) that horizontal scrolling is not necessary.
• The specifications for all of the functions are complete and are docstrings.
• Specifications are immediately after the function header and indented.

At the top of a6.py you should have three single line comments with (1) the module name, (2) your name(s) and netid(s), as well as the identity of any other sources (documents or people) that contributed to your solution, and (3) the date you finished the assignment.

Upload the file a6.py to CMS by the due date: Thursday, November 20th at 11:59 pm. We do not want any other files, even if you added more tests to a6test.py.

Course Material Authors: D. Gries, L. Lee, S. Marschner, & W. White (over the years)


text:
# Mechanics: Displacement Vector

1. May 18, 2014

### teme92

1. The problem statement, all variables and given/known data

Consider the vector r(t)= (1-t)i + (3+2t)j + (t-4)k which depends on scalar parameter t. For which t0 is the length of r(t0) minimal?

2. Relevant equations

Equations of motion

3. The attempt at a solution

So I approached this question by saying the length would be minimal when the magnitude is minimal ie. |r|=0.

|r|=√[(1-t)2+(3+2t)2+(t-4)2]

Simplified down I got 3t2+t+13=0

I tried using the quadratic formula to solve this then but couldn't as the value under the square root was negative.

Am I approaching this question wrong then? Any help would be much appreciated.

2. May 18, 2014

### Ray Vickson

Why would you assume that the smallest value of |r| is zero? That would be the case only if the line passes through the origin. Draw a sketch of a similar situation in two dimensions, and look carefully at the picture.

3. May 18, 2014

### teme92

So if t is the x-axis and r(t) the y-axis when t=0 r(t) is at a minimum?

4. May 18, 2014

### teme92

Actually is it when the x-compenent is zero. So in this case 1-t=0 so t=1?

5. May 18, 2014

### vela

Staff Emeritus
$\vec{r}(t)$ describes a curve in three dimensions, and $t$ is a parameter telling you where you are on that curve. To sketch the curve, you need to do so in three dimensions. Ray is suggesting you try a simpler example where the curve lies in two dimensions so you can get an idea of how to analyze the problem correctly. For instance, you could try a curve like $\vec{r}(t) = (t-1)\hat{i} + (t+2)\hat{j}$.

Back to the original problem… You found the length $\| \vec{r}(t) \| = \sqrt{2(3t^2+t+13)}$ as a function of $t$. You want to find where this function attains a minimum. How do you do that?

6. May 18, 2014

### teme92

Differentiate and let it equal to zero. Then sub t values back into r(t)?

7. May 18, 2014

### vela

Staff Emeritus
Right. The problem is only asking for the value of $t$, so you don't need to plug the value back into $\vec{r}(t)$, though you might try it to see if the answer is reasonable.

8. May 18, 2014

### teme92

Ok vela thanks for the help. I got t=1/3 in the end. There was chain rule involved in differentiating so it would take a while to type it out. Thanks for the help again.

9. May 18, 2014

### vela

Staff Emeritus
You're off by a factor of 2.

10. May 18, 2014

### Ray Vickson

Even easier: $|r|$ is a minimum if and only if $r^2$ is a minimum (why?), so you might as well just minimize $r^2 = (1-t)^2 + (3+2t)^2 + (t-4)^2 = 6 t^2 + 2t + 26.$


text:
# Adaptive Regularization for Nonconvex Optimization sing Inexact Function Values and Randomly Perturbed Derivatives

Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, Philippe TOINT

Résultats de recherche: Papier de travailArticle de travail

2 Téléchargements (Pure)

## Résumé

A regularization algorithm allowing random noise in derivatives and inexact
function values is proposed for computing approximate local critical points
of any order for smooth unconstrained optimization problems. For an
objective function with Lipschitz continuous p-th derivative and given an
arbitrary optimality order q <= p, it is shown that this algorithm will, in
expectation, compute such a point in at most
O((min_{j=1,...,q}epsilon_j)^{-(p+1)/(p-q+1)})
inexact evaluations of f and its derivatives whenever q in {1,2}, where
\epsilon_j is the tolerance for j-th order accuracy.  This bound becomes at most
O((min_{j=1,...,q}epsilon_j)^{-(q(p+1))/(p)})
inexact evaluations if q>2 and all derivatives are Lipschitz
continuous. Moreover these bounds are sharp in the order of the accuracy
tolerances. An extension to convexly constrained problems is also outlined.
langue originale Anglais Arxiv 22 2005.04639 Publié - 13 mai 2020

## Empreinte digitale

Examiner les sujets de recherche de « Adaptive Regularization for Nonconvex Optimization sing Inexact Function Values and Randomly Perturbed Derivatives ». Ensemble, ils forment une empreinte digitale unique.
• ### Complexity in nonlinear optimization

TOINT, P., Gould, N. I. M. & Cartis, C.

1/11/08 → …

Projet: Recherche


text:
### - Art Gallery -

In mathematics, a P-matrix is a complex square matrix with every principal minor > 0. A closely related class is that of $$P_{0}$$-matrices, which are the closure of the class of P-matrices, with every principal minor $$\geq 0$$.

Spectra of P-matrices

By a theorem of Kellogg,[1][2] the eigenvalues of P- and $$P_{0}$$ - matrices are bounded away from a wedge about the negative real axis as follows:

If $$\{u_{1},...,u_{n}\}$$ are the eigenvalues of an n-dimensional P-matrix, where n>1, then

$${\displaystyle |\arg(u_{i})|<\pi -{\frac {\pi }{n}},\ i=1,...,n}$$

If $$\{u_{1},...,u_{n}\}$$, $$u_{i}\neq 0$$, i=1,...,n are the eigenvalues of an n-dimensional $$P_{0}$$-matrix, then

| $${\displaystyle |\arg(u_{i})|\leq \pi -{\frac {\pi }{n}},\ i=1,...,n}$$

Remarks

The class of nonsingular M-matrices is a subset of the class of P-matrices. More precisely, all matrices that are both P-matrices and Z-matrices are nonsingular M-matrices. The class of sufficient matrices is another generalization of P-matrices.[3]

The linear complementarity problem $${\displaystyle \mathrm {LCP} (M,q)}$$ has a unique solution for every vector q if and only if M is a P-matrix.[4] This implies that if M is a P-matrix, then M is a Q-matrix.

If the Jacobian of a function is a P-matrix, then the function is injective on any rectangular region of R n {\displaystyle \mathbb {R} ^{n}} \mathbb {R} ^{n}.[5]

A related class of interest, particularly with reference to stability, is that of P ( − ) {\displaystyle P^{(-)}} P^{{(-)}}-matrices, sometimes also referred to as N-P-matrices. A matrix A is a $$P^{{(-)}}$$ -matrix if and only if (-A) is a P-matrix (similarly for $$P_{0}$$ -matrices). Since $$\sigma (A)=-\sigma (-A)$$, the eigenvalues of these matrices are bounded away from the positive real axis.

Hurwitz matrix
Linear complementarity problem
M-matrix
Q-matrix
Z-matrix
Perron–Frobenius theorem

Notes

Kellogg, R. B. (April 1972). "On complex eigenvalues ofM andP matrices". Numerische Mathematik. 19 (2): 170–175. doi:10.1007/BF01402527.
Fang, Li (July 1989). "On the spectra of P- and P0-matrices". Linear Algebra and its Applications. 119: 1–25. doi:10.1016/0024-3795(89)90065-7.
Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (pdf). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. MR 2195759.
Murty, Katta G. (January 1972). "On the number of solutions to the complementarity problem and spanning properties of complementary cones" (PDF). Linear Algebra and its Applications. 5 (1): 65–108. doi:10.1016/0024-3795(72)90019-5.

Gale, David; Nikaido, Hukukane (10 December 2013). "The Jacobian matrix and global univalence of mappings". Mathematische Annalen. 159 (2): 81–93. doi:10.1007/BF01360282.

References

Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (pdf). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. MR 2195759.
David Gale and Hukukane Nikaido, The Jacobian matrix and global univalence of mappings, Math. Ann. 159:81-93 (1965) doi:10.1007/BF01360282
Li Fang, On the Spectra of P- and In mathematics, a P-matrix is a complex square matrix with every principal minor > 0. A closely related class is that of $$P_{0}$$-matrices, which are the closure of the class of P-matrices, with every principal minor $$\geq 0$$.

Spectra of P-matrices

By a theorem of Kellogg,[1][2] the eigenvalues of P- and $$P_{0}$$ - matrices are bounded away from a wedge about the negative real axis as follows:

If $$\{u_{1},...,u_{n}\}$$ are the eigenvalues of an n-dimensional P-matrix, where n>1, then

$${\displaystyle |\arg(u_{i})|<\pi -{\frac {\pi }{n}},\ i=1,...,n}$$

If $$\{u_{1},...,u_{n}\}$$, $$u_{i}\neq 0$$, i=1,...,n are the eigenvalues of an n-dimensional $$P_{0}$$-matrix, then

| $${\displaystyle |\arg(u_{i})|\leq \pi -{\frac {\pi }{n}},\ i=1,...,n}$$

Remarks

The class of nonsingular M-matrices is a subset of the class of P-matrices. More precisely, all matrices that are both P-matrices and Z-matrices are nonsingular M-matrices. The class of sufficient matrices is another generalization of P-matrices.[3]

The linear complementarity problem $${\displaystyle \mathrm {LCP} (M,q)}$$ has a unique solution for every vector q if and only if M is a P-matrix.[4] This implies that if M is a P-matrix, then M is a Q-matrix.

If the Jacobian of a function is a P-matrix, then the function is injective on any rectangular region of $$\mathbb {R} ^{n}$$.[5]

A related class of interest, particularly with reference to stability, is that of \ P^{{(-)}} \) -matrices, sometimes also referred to as N-P-matrices. A matrix A is a $$P^{{(-)}}$$ -matrix if and only if (-A) is a P-matrix (similarly for $$P_{0}$$ -matrices). Since $$\sigma (A)=-\sigma (-A)$$, the eigenvalues of these matrices are bounded away from the positive real axis.

Hurwitz matrix
Linear complementarity problem
M-matrix
Q-matrix
Z-matrix
Perron–Frobenius theorem

Notes

Kellogg, R. B. (April 1972). "On complex eigenvalues ofM andP matrices". Numerische Mathematik. 19 (2): 170–175. doi:10.1007/BF01402527.
Fang, Li (July 1989). "On the spectra of P- and P0-matrices". Linear Algebra and its Applications. 119: 1–25. doi:10.1016/0024-3795(89)90065-7.
Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (pdf). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. MR 2195759.
Murty, Katta G. (January 1972). "On the number of solutions to the complementarity problem and spanning properties of complementary cones" (PDF). Linear Algebra and its Applications. 5 (1): 65–108. doi:10.1016/0024-3795(72)90019-5.

Gale, David; Nikaido, Hukukane (10 December 2013). "The Jacobian matrix and global univalence of mappings". Mathematische Annalen. 159 (2): 81–93. doi:10.1007/BF01360282.

References

Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (pdf). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. MR 2195759.
David Gale and Hukukane Nikaido, The Jacobian matrix and global univalence of mappings, Math. Ann. 159:81-93 (1965) doi:10.1007/BF01360282
Li Fang, On the Spectra of P- and $$P_{0}$$}-Matrices, Linear Algebra and its Applications 119:1-25 (1989)
R. B. Kellogg, On complex eigenvalues of M and P matrices, Numer. Math. 19:170-175 (1972) $$P_{0}$$-Matrices, Linear Algebra and its Applications 119:1-25 (1989)
R. B. Kellogg, On complex eigenvalues of M and P matrices, Numer. Math. 19:170-175 (1972)

Mathematics Encyclopedia


text:
# Why does the second derivative of convex function exist almost everywhere?

Let $$f: I\to \mathbb{R}$$ be a convex function.

Why does the second derivative of $$f$$ exist almost everywhere?

By searching I knew that is Alexandrov theorem, but I didn't find the proof...

My try

For $$x_1 where function is defined , we have $$\frac{f(x)-f(x_1)}{x-x_1}\le\frac{f(x_2)-f(x_1)}{x_2-x_1}\le\frac{f(x_2)-f(x)}{x_2-x}$$ Considering $$x_1\to x^-$$ and $$x_2\to x^+$$, we can conclude that $$f_-'(x)$$ and $$f_+'(x)$$ exist and $$f_-'(x)\le f_+'(x)$$. (in this process we only need $$\frac{f(x)-f(x_1)}{x-x_1}\le\frac{f(x_2)-f(x)}{x_2-x}$$)

Considering $$x\to x_1$$ and $$x\to x_2$$, we can conclude that $$f_+'(x_1)\le \frac{f(x_2)-f(x_1)}{x_2-x_1} \le f_-'(x_2)$$

So we get that $$f_-(x)$$ and $$f_+(x)$$ exist and both are monotonically increasing.
In addition, $$f_-'(x)\le f_+'(x)$$.

Because monotone functions only have jump discontinuities and are continuous everywhere except countably many points, we can conclude that $$f'$$ exists everywhere except countably many points.

How to move on? Any hints? Thank you in advance!

• I believe you want to show that the closure of the set of points where $f$ is not differentiable is still countable. Then using the monotonicity of $f'$ you can probably show that $f''$ exists almost everywhere. – SmileyCraft Dec 24 '18 at 15:29
• @SmileyCraft Could you give me some hints about how to show $f''$ exists almost everywhere through using the monotonicity of $f'$? I got stuck on that... – Zero Dec 24 '18 at 15:50
• Have you tried to show already that the closure of the set of points where $f$ is not differentiable is countable? Because then I believe you can find a countable set of open intervals where $f$ is differentiable, such that the union has a countable complement. Using the monotonicity of $f'$ you can show that on every interval the set of points where $f'$ is not differentiable is countable. – SmileyCraft Dec 24 '18 at 15:55
• @SmileyCraft Thank you very much! I just realized that if $f$ is a monotonic function defined on an interval $I$ then $f$ is differentiable almost everywhere on $I$ , from which I can arrive at the conclusion – Zero Dec 24 '18 at 16:04
• This is not correct , convex functions can be nondifferentiable on a dense subset of $R$. – Red shoes Dec 25 '18 at 2:01


text:
# 147% Perfect

The sum of all the divisors of $$x$$, a positive integer, are summed, the result is $$\frac{3x-1}{2}$$

Find the sum of the $$7$$ smallest possible values of $$x$$.

×


text:
# Block Diagram in LaTeX: Step-by-Step TikZ Tutorial

• Today's tutorial is about drawing a block diagram in LaTeX using TikZ package. This step-by-step tutorial teaches you how to create nodes and customize them, position a node with respect to another one, connect nodes and draw line arrows

Block diagram drawn in LaTeX using TikZ package

• Drawing a block diagram in LaTeX using TikZ package can be achieved in 3 steps:
Step 1: Create nodes with different shapes (use relative positioning).
Step 2: Connect different nodes through their anchors.
Step 3: Define styles for the same shapes.

## Create nodes in TikZ

In our example, we distinguish two types of shapes: a circle and 3 rectangles. These shapes can be created using \node command. Here is an example:

\documentclass[border=0.2cm]{standalone}

% More defined colors
\usepackage[dvipsnames]{xcolor}

% Required package
\usepackage{tikz}
\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}

\node[draw,
circle,
minimum size=0.6cm,
fill=Rhodamine!50
] (sum) at (0,0){};

\end{tikzpicture}

\end{document}

The above code creates a node with name (sum) at the point with coordinates (0,0). To draw the node, we have to add the option draw to it and with circle option, we get a circle shape. By default, a node corresponds to a rectangle.

We provided also the minimum size of the node which is equal to 0.6cm. It should be noted that adding details to a node (text, image or even a tikz code) increases its size.

The node is filled with the color Rhodamine!50 which is one of the dvipsnames provided by xcolor package. For a full list, check the post: Predefined LaTeX colors: dvipsnames.

• You may wonder: why we don't use draw command to draw a circle following the syntax: \draw (0,0) circle(0.6cm); Indeed, this is doable using draw command but a node has an interesting feature which corresponds to anchors, it represents the coordinates of the node border.

## Anchors of a node in TikZ

Each node has anchors which corresponds to points coordinates of the node border. A feature that is not provided by draw command with circle shape. Different anchors are shown in the next illustration where we use the name of the node and an angle or we use predefined anchors such as (north, south, east, west, etc)

Now, we can draw easily the sum shape of the block diagram by connecting the point (sum.north east) with the point (sum.south west) through a straight line using draw command. The same for the points with coordinates (sum.south east) and (sum.north west). Here is the code:

\documentclass[border=0.2cm]{standalone}

% More defined colors
\usepackage[dvipsnames]{xcolor}

% Required package
\usepackage{tikz}
\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}

% Sum shape
\node[draw,
circle,
minimum size=0.6cm,
fill=Rhodamine!50
] (sum) at (0,0){};

\draw (sum.north east) -- (sum.south west)
(sum.north west) -- (sum.south east);

\end{tikzpicture}

\end{document}

which yields the following illustration:

Now, it remains to add the positive and negative signs. We can place them as nodes relative to the center of the sum node. Here is the corresponding piece of code:

\node[left=-1pt] at (sum.center){\tiny $+$};
\node[below] at (sum.center){\tiny $-$};

Adding these two lines to the previous code, we get the following result:

We added the option left=<value> to put the node at the left of the provided coordinates (sum.center) with an offset equals to the provided value. The same for the negative sign which is located below the center of the sum node.

## Relative positioning in TikZ

Now, we would like to create the controller block which corresponds to a rectangle filled with a golden color and has the label C(s). This can be achieved following the same steps as above where we will create a node with draw option and specify its size. To avoid positioning the at specific coordinates (x,y), we will use relative positioning with respect to the sum node. Check the following code:

\documentclass[border=0.2cm]{standalone}

% More defined colors
\usepackage[dvipsnames]{xcolor}

% Required package
\usepackage{tikz}
\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}

% Sum shape
\node[draw,
circle,
minimum size=0.6cm,
fill=Rhodamine!50
] (sum) at (0,0){};

\draw (sum.north east) -- (sum.south west)
(sum.north west) -- (sum.south east);

\draw (sum.north east) -- (sum.south west)
(sum.north west) -- (sum.south east);

\node[left=-1pt] at (sum.center){\tiny $+$};
\node[below] at (sum.center){\tiny $-$};

% Controller
\node [draw,
fill=Goldenrod,
minimum width=2cm,
minimum height=1.2cm,
right=1cm of sum
]  (controller) {$C(s)$};

\end{tikzpicture}

\end{document}

The above code creates a node with rectangular shape (default shape no need to specify it) which has a minimum width =2cm and minimum height=2cm. The node is located at the right of the sum node with 1cm distance. This is achieved using the option right=1cm of sum. We saved the rectangle node with the name (controller) which will be used for relative positioning of the system block H(s). Here is the obtained illustration:

Following the same steps as above, we can create the system and the sensor blocks. Here is the corresponding code:

\documentclass[border=0.2cm]{standalone}

% More defined colors
\usepackage[dvipsnames]{xcolor}

% Required package
\usepackage{tikz}
\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}

% Sum shape
\node[draw,
circle,
minimum size=0.6cm,
fill=Rhodamine!50
] (sum) at (0,0){};

\draw (sum.north east) -- (sum.south west)
(sum.north west) -- (sum.south east);

\draw (sum.north east) -- (sum.south west)
(sum.north west) -- (sum.south east);

\node[left=-1pt] at (sum.center){\tiny $+$};
\node[below] at (sum.center){\tiny $-$};

% Controller
\node [draw,
fill=Goldenrod,
minimum width=2cm,
minimum height=1.2cm,
right=1cm of sum
]  (controller) {$C(s)$};

% System H(s)
\node [draw,
fill=SpringGreen,
minimum width=2cm,
minimum height=1.2cm,
right=1.5cm of controller
] (system) {$H(s)$};

% Sensor block
\node [draw,
fill=SeaGreen,
minimum width=2cm,
minimum height=1.2cm,
below right= 1cm and -0.25cm of controller
]  (sensor) {$G(s)$};

\end{tikzpicture}

\end{document}

Compiling this code yields:

The sensor is positioned at the right and below of the controller node using the option: below right= 1cm and -0.25cm of controller.  It remains to connect these blocks with arrows.

## Draw an arrow with text label

This is the easiest part in drawing a block diagram in LaTeX. We need to connect anchors of different nodes. Let's start by drawing an arrow between the sum and the controller blocks:

\draw[-stealth] (sum.east) -- (controller.west)
node[midway,above]{$e$};

This line of code draws a line from (sum.east) to (controller.west). The line ends with an arrowhead of stealth type (For more arrow tips, check the post Exploring TikZ Arrows) . We added a label to the arrow using a node command, the label is positioned at the above the middle of the distance between two blocks. This has been achieved using midway option. The next table provides more details about positioning along a path:

We can do the same between the controller block and the system block:

\draw[-stealth] (controller.east) -- (system.west)
node[midway,above]{$u$};

For the output of the system, we will draw an arrow with 1.25cm length and we save the node at the middle of the arrow to use it for connecting the output with sensor block. Here is the corresponding code:

\draw[-stealth] (system.east) -- ++ (1.25,0)
node[midway](output){}
node[midway,above]{$y$};

The node is named (output) and we will draw a line from its center (output.center) to the (sensor.east) with a perpendicular lines. To achieve the later, we use |- (vertical then straight line) instead of --.

\draw[-stealth] (output.center) |- (sensor.east);
\draw[-stealth] (sensor.west) -| (sum.south)
node[near end,left]{$y_m$};

The west anchor of the sensor is connected with the south of the sum node using the path operation -| (straight then vertical line).

The input reference corresponds to a labeled arrow which can be drawn with the same manner as the output arrow.

Here is the Final code of the latex block diagram:

\documentclass[border=0.2cm]{standalone}

% More defined colors
\usepackage[dvipsnames]{xcolor}

% Required package
\usepackage{tikz}
\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}

% Sum shape
\node[draw,
circle,
minimum size=0.6cm,
fill=Rhodamine!50
] (sum) at (0,0){};

\draw (sum.north east) -- (sum.south west)
(sum.north west) -- (sum.south east);

\draw (sum.north east) -- (sum.south west)
(sum.north west) -- (sum.south east);

\node[left=-1pt] at (sum.center){\tiny $+$};
\node[below] at (sum.center){\tiny $-$};

% Controller
\node [draw,
fill=Goldenrod,
minimum width=2cm,
minimum height=1.2cm,
right=1cm of sum
]  (controller) {$C(s)$};

% System H(s)
\node [draw,
fill=SpringGreen,
minimum width=2cm,
minimum height=1.2cm,
right=1.5cm of controller
] (system) {$H(s)$};

% Sensor block
\node [draw,
fill=SeaGreen,
minimum width=2cm,
minimum height=1.2cm,
below right= 1cm and -0.25cm of controller
]  (sensor) {$G(s)$};

% Arrows with text label
\draw[-stealth] (sum.east) -- (controller.west)
node[midway,above]{$e$};

\draw[-stealth] (controller.east) -- (system.west)
node[midway,above]{$u$};

\draw[-stealth] (system.east) -- ++ (1.25,0)
node[midway](output){}node[midway,above]{$y$};

\draw[-stealth] (output.center) |- (sensor.east);

\draw[-stealth] (sensor.west) -| (sum.south)
node[near end,left]{$y_m$};

\draw (sum.west) -- ++(-1,0)
node[midway,above]{$y_{ref}$};

\end{tikzpicture}

\end{document}

## Optimize the code with tikzstyle command

You may remarked that all rectangular blocks have the same dimension characteristics and to avoid repeating these options: draw, minimum width=2cm, minimum height=1.2cm, we can create a style with these options using the \tikzstyle command as follows:

\tikzstyle{block} = [
draw,
minimum width=2cm,
minimum height=1.2cm
]

We named the style as block and we can use it as an option in all different node commands corresponding to the controller, system and sensor blocks.

• We've reached the end of this tutorialIf you have any questions or remarks, leave me a comment below or reach me via e-mail at admin@latexdraw.com, I will be happy to hear from you!


text:
### #3 Scaling law of locomotion-II

/*-----------Divider-----------*/
Today we are going to talk about the problem we left in the previous episode: how T. A. McMahon explained the scaling laws tride length M^(0.38), stride frequency M^(-0.14), and running speed M^(0.24). The key is the assumption of “elastic similarity.”

The Chinese version of this episode: 指數律_動物走路和跑步_下： https://goo.gl/OUJBlb
/*-----------Divider-----------*/
In the previous episode we suggested using the concept of inverted pendulum to derive the scaling law of stride length, stride frequency and running speed. Theoretically, you may have arrived at a result looks like stride length M^(1/3), stride frequency M^(-1/6), and running speed M^(1/6). These results came from the assumption of “geometric similarity,” which postulated that larger animals are the  isometric scaling of smaller animals.

If that were true, an elephant could have snapped its leg merely by its own weight. An axial load could cause the buckling of a beam. Based on an equation discovered by Euler in 1757, we could calculate the maximum axial load (, or the so called critical load) of a beam. We could also calculate how much the beam diameter has to adjust to stay within the critical load as the length of the beam doubles. Because during this scaling process, beams of various sizes share the same risk of buckling, such allometric scaling is termed as “elastic similarity.” T. A. McMahon discovered that the length of the beam should be proportional to its diameter to the power 2/3. The physics detail of the above would be discussed later.

Actually, McMahon compared 3 different hypothesis and found that the results based on elastic similarity matched the observed power best. He reproduced the scaling laws stride length M^(3/8), stride frequency M^(-1/8), and running speed M^(1/4), which matched the experimental ones perfectly. We encourage you to derive the scaling laws of body surface area, BMR and heart rate yourselves. What is your predicted scaling power? The answers could be found in the suggested reading.

/*-----And now let’s delve into the physics details-----*/
We have to briefly introduce some concepts of differential geometry and material mechanics. Let’s now look at Figure 1.

Figure 1. A parametric curve in 3D space.

Consider a curve in the 3D space. Each point along the curve could be described by a dimensionless parameter u as

Now consider a tiny segment with length Δs, as Δs approaches 0, we could write down that

We therefore arrive at a conclusion that

The tangential direction of the curve is defined as

And its magnitude is therefore

And we could also defined the unit tangential vector

The curve is not straight because there are changes in its tangent vectors. For each part of the curve, we could therefore draw its osculating circle. We try to find the changes in unit tangent vectors from position s to s+ds:

We then defined curvature κ to be the reciprocal of the radius of the osculating circle, i. e. κ=1/R. We could then derive that

And for a beam with lateral displacement h = h(x), we could easily know that

Figure 2. A beam curved into an arc.

Now let’s look at Figure 2 and consider a beam. Assumed that the beam is curved into an arc due to the axial load. From the figure above, it is obvious that some parts of the beam are compressed while other parts are extended. We could find an neutral axis, i. e. the axis along which the beam is neither compressed nor extended, somewhere in the beam. We then define origin to be the intersection point between the neutral axis and the lateral border at the left side. We could find the amount of compression or extension of the beam at z to be

We could then find strain, or the length change experienced by the material with unit length:
And from Hooke’s law, the stress, or the internal force per unit area experienced by the beam at z is

Where E is the Young’s modulus of the material. The larger the Young’s modulus, the harder the material is. Besides, we define moment (M) as the internal torque experienced by the cross-section of the material, mathematically the cross-product of its coordinate vector and internal force:

To find the total moment of a cross-section, it requires some integration:
In which I is called the area moment of inertia. Noticed that since κ=1/R, The moment M could also be expressed as M = EIκ.

Figure 3. A beam with axial load F and lateral displacement profile h(x).
Now let’s look at Figure 3. Consider a beam with axial load F. Assume that its lateral displacement at position x is h(x). From results derived above, we could write down the ODE and its boundary conditions:

The answer is simple, that is h(x)= Csin(nπx/L), n=0,1,2,3,….There is no lateral displacement if n=0, while n=1 means the beam is curved and could no longer support load. The critical load or the so called Euler buckling load could be calculated by inserting h(x)= Csin(πx/L) back to the ODE. And we will get
$-C\frac{\pi^2}{L^2}\sin(\frac{\pi&space;x}{L})=-\frac{F}{EI}C\sin(\frac{\pi&space;x}{L})$
$F&space;=&space;\frac{\pi^2EI}{L^2}$
This is the Euler's formula for the critical load of a beam.

In McMahon’s argument, he assumed F to be the weight of the beam itself. That is,

$F&space;=&space;\rho&space;L&space;(\frac{\pi}{4}D^2)$
And the area moment of inertia of a cylindrical beam reads
Insert all above into the Euler’s formula of critical load, we get
And therefore the length of beam should be proportional to its diameter to the power 2/3:
The coefficient (0.851) still depends on the inner structure of the beam, but the scaling law of 2/3 remains the same. And that's how McMahon reproduce the scaling laws stride length M^(0.38), stride frequency M^(-0.14), and running speed M^(0.24).

/*-----------Divider-----------*/


text:
{{ item.displayTitle }}
navigate_next
No history yet!
Progress & Statistics equalizer Progress expand_more
Student
navigate_next
Teacher
navigate_next
{{ filterOption.label }}
{{ item.displayTitle }}
{{ item.subject.displayTitle }}
arrow_forward
{{ searchError }}
search
{{ courseTrack.displayTitle }}
{{ printedBook.courseTrack.name }} {{ printedBook.name }}

## Solving Radical Equations 1.18 - Solution

Solving a radical equation usually involves three main steps.

1. Isolate the radical on one side of the equation.
2. Raise each side of the equation to a power equal to the index of the radical to eliminate the radical.
3. Solve the resulting equation.
4. Check the results for extraneous solutions.
Now we can analyze the given radical equation. $\begin{gathered} 8-\sqrt{x+12}=3 \end{gathered}$ First, let's isolate the radical, $\sqrt{x+12},$ on one side of the equation.
$8-\sqrt{x+12}=3$
$\text{-}\sqrt{x+12}=\text{-}5$
$\sqrt{x+12}=5$
We get an isolated radical with index equal to ${\color{#0000FF}{2}}.$ Then, we will raise each side of the equation to the power of ${\color{#0000FF}{2}}.$
$\sqrt{x+12}=5$
$\left(\sqrt{x+12}\right)^2=5^2$
Solve for $x$
$x+12=5^2$
$x+12=25$
$x=13$
Next, we will check for extraneous solutions. We do that by substituting $13$ for $x$ into the original equation. If the substitution produces a true statement, we know that our answer is correct. If it does not, then it is an extraneous solution.
$8-\sqrt{x+12}=3$
$8-\sqrt{{\color{#0000FF}{13}}+12}\stackrel{?}{=}3$
Simplify
$8-\sqrt{25}\stackrel{?}{=}3$
$8-5\stackrel{?}{=}3$
$3=3\ {\color{#009600}{\Large\checkmark}}$
Because our substitution produced a true statement we know that our answer, $x=13,$ is correct.


text:
# Schwarzschild singularity and black hole

Are a Schwarzschild singularity and a black hole the same thing?

## Answers and Replies

PeterDonis
Mentor
The term "Schwarzschild singularity" has been used with several different meanings. It can mean a black hole; it can mean the horizon of the hole; or it can mean the singularity at ##r = 0##.


text:
Normally distributed data?

1. The problem statement, all variables and given/known data
Suppose I have a set of measurements of a quantity Q, where the resolution R is the same for all data di. However, R is unknown, and I wish to find it.

In my book they do this by writing the likelihood L (or rather, ln(L)) as the Gaussian, so

$$\ln L = \sum\limits_i { - \ln R_i \sqrt {2\pi } } - \sum\limits_i {\frac{{\left( {d_i - Q } \right)^2 }}{{2R_i }}}$$

Now they differentiate wrt. the mean Q and the deviation Ri = R, yielding two equations. Solving these yields

$$R^2 = \frac{1}{N}\sum\limits_i {\left( {d_i - Q} \right)^2 }$$

This is the standard result we are "used" to. But does this mean that every single time I use this formula on a set of data, then I am implicitly assuming that the data is normally distributed?

Cheers.
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity

 Similar discussions for: Normally distributed data? Thread Forum Replies Set Theory, Logic, Probability, Statistics 12 Set Theory, Logic, Probability, Statistics 4 Set Theory, Logic, Probability, Statistics 2 Set Theory, Logic, Probability, Statistics 4 Set Theory, Logic, Probability, Statistics 3


text:
# Thread: Euler's and Möbius function

1. ## Euler's and Möbius function

How to find all positive integers n: n=\phi(n)+\mu(n)+\tau(n)?

2. ## Re: Euler's and Möbius function

Hey HelpMe123.

Can you please show me your working and explain what these variables mean?

3. ## Re: Euler's and Möbius function

I assume your 3 functions are:
$\phi(n)$ the number of positive integers less than n that are prime to n
$\mu(n)$ the Moebius mu function - 1 for square free n with an even number of prime factors, -1 for square free n otherwise and 0 otherwise
$\tau(n)$ the number of positive divisors of n

Here's the answer to your question. I verify the easy direction, but leave to you the proof that these are the only values that are fixed points of f. If you need help on this direction, post again.

Let $f(n)=\phi(n)+\mu(n)+\tau(n)$. Then $f(n)=n$ if and only if $n$ is prime or $n=9$.

$f(9)=6+0+3=9$ and if $n$ is prime, $f(n)=n-1-1+2=n$


text:
# A binary liquid solution is prepared by mixing n-heptane and ethanol.Which one of the following statements is correct regarding the behaviour of the solution?

$\begin{array}{1 1}(a)\;\text{The solution is non-ideal,showing +ve deviation from Raoult's law}\\(b)\;\text{The solution is non-ideal,showing -ve deviation from Raoult's law}\\(c)\;\text{n-heptane shows +ve deviation while ethanol shows -ve deviation from Raoult's law}\\(d)\;\text{The solution formed is an ideal solution}\end{array}$

Since $\Delta H > 0$
$\Delta V > 0$
Hence (a) is the correct answer.


text:
## Cryptology ePrint Archive: Report 2015/079

On the Security of the COPA and Marble Authenticated Encryption Algorithms against (Almost) Universal Forgery Attack

Jiqiang Lu

Abstract: COPA is a block-cipher-based authenticated encryption mode with a provable birthday-bound security under the assumption that the underlying block cipher is a strong pseudorandom permutation, and its instantiation with the AES block cipher is called AES-COPA. Marble is an AES-based COPA-like authenticated encryption algorithm with a full security. In this paper, we analyse the security of COPA and Marble against universal forgery attacks. We present beyond-birthday-bound (almost) universal forgery attacks on the COPA when used with constant or variable associate data, and present (almost) universal forgery attacks on the Marble when used without associated data or with (variable) associate data. Our attacks on the COPA with variable associate data have a complexity very near the birthday bound, and their applications to AES-COPA show that the security claim of AES-COPA against tag guessing may be not correct; and our attacks on the (newest as well as initial version of) Marble with associate data show that Marble does not provide a full security that the designer claimed. Like many recently published cryptanalytic results on message authentication algorithms with a provable birthday-bound security, our attacks on COPA do not violate its security proofs, but provide a comprehensive understanding of its security against universal forgery attack, show that the success probability of a universal forgery on the COPA is larger than the ideal bound $2^{-n}$ of the standard forgery-resistance, and boil down to an existing open question: Should a message authentication algorithm with a weaker security claim than the standard forgery-resistance be regarded as a sound design?

Category / Keywords: secret-key cryptography / Authenticated encryption algorithm, COPA, Marble, Universal forgery attack.

Date: received 3 Feb 2015, last revised 11 Feb 2015

Contact author: lvjiqiang at hotmail com

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2015/079

[ Cryptology ePrint archive ]


text:
# Effect of removal of numbers while calculating average

My question is ,

lets say we have the numbers 1,2,3,.....,n numbers . 2 consecutive numbers are removed. The avg of the numbers after the removal of numbers be m

let the numbers removed be k,k+1

can we come up with a formula that relates m,n,k

-

The average of all the integers from 1 to $n$ is given by $$\frac{\frac{1}{2}n(n+1)}{n},$$ or simply $$\frac{1}{2}(n+1).$$
The sum of the integers from 1 to $n$ with $k$ and $k+1$ removed is given by $$\frac{n(n+1)}{2} - k - (k+1),$$ which we can clean up slightly to $$\frac{1}{2}(n^2 + n - 4k - 2)$$ The expression above is the sum of $n-2$ numbers, so the average of these numbers is $$\frac{\frac{1}{2}(n^2 + n - 4k - 2)}{n-2},$$ or simply $$\frac{n^2 + n - 4k - 2}{2(n-2)}.$$ Thus, the amount by which the average decreased is given by $$\frac{1}{2}(n+1) - \frac{n^2 + n - 4k - 2}{2(n-2)},$$ which simplifies to $$\frac{2k - n}{n-2}.$$
In general, if you have $n$ numbers whose mean is $\mu$, the sum of those numbers is $n \mu$. If you then remove $m$ of those numbers whose mean is $\nu$ (and thus whose sum is $m \mu$), the remaining $n-m$ numbers have mean $\displaystyle\frac{n\mu - m \nu}{n-m} = \mu + \frac{m (\mu - \nu)}{n-m}$.


text:
# 1st principle derivative

• May 29th 2013, 08:47 PM
JamesT
1st principle derivative
I very confuse with the whole "derivative" concept.
Attachment 28487
Really appreciated if someone can tell me how to work this out and get the solution for this example.

thanks guys
• May 29th 2013, 11:31 PM
chiro
Re: 1st principle derivative
Hey JamesT.

Try just unpacking the definition first. As a starting hint consider that if f(x) = -1 / [x^2 - x] then f(x+h) = -1 / [(x+h)^2 - (x+h)]. If you let triangle_x = h, then the point is to cancel out the h on the denominator and evaluate the limit.
• May 29th 2013, 11:38 PM
MINOANMAN
Re: 1st principle derivative
James
It is not dfficult but has an ocean of tricky operations and fractions....try slowly slowly and do it...replace x as x+Δx in the first function and subtruct the initial function.do whatever can be done to simplify it and then divide by Δx .get the limits and find the final answer f'(x) =(2x-1)/x^2(x-1)^2
• May 30th 2013, 04:39 AM
HallsofIvy
Re: 1st principle derivative
$f(x)= \frac{-1}{x^2- x}$ so $f(x+ \Delta x)= \frac{-1}{(x+ \Delta x)^2- (x+ \Delta x)}$
Rather than multiplying that out it is simplest to factor: $(x+ \Delta x)^2- (x+ \Delta x)= (x+ \Delta x)(x+ \Delta x- 1)$

So $f(x+ \Delta x)- f(x)= \frac{-1}{(x+ \Delta x)(x+ \Delta x- 1)}- \frac{-1}{x(x- 1)}$
To subtraction we need to get the "common denominator" and, since there are no common factors, we can do that by multiplying both numerator and denominator of each by the denominator of the other:
$\frac{-x(x- 1)}{x(x- 1)(x+ \Delta x)(x+ \Delta x- 1)}- \frac{-(x+ \Delta x)(x+ \Delta x- 1)}{x(x- 1)(x+ \Delta x)(x+ \Delta x- 1)}$
Ignore the denominator for the moment and multiply out the numerators:
$-x^2- x+ x^2- 2x\Delta x+ (\Delta x)^2+ x- \Delta x= (\Delta x)^2- (2x- 1)\Delta x= \Delta x(\Delta x- 2x+ 1)$
Notice that every term that does not have $\Delta x$ in it cancelled. That had to happen because when $\Delta x= 0$ the two terms would be the same.

So far we have $f(x+ \Delta x)- f(x)= \frac{\Delta x(\Delta x- 2x+ 1)}{x(x- 1)(x+ \Delta x)(x+ \Delta x- 1)}$
where I have just included that common denominator from before.

Next we want $\frac{f(x+\Delta x)- f(x)}{\Delta x}$, the "difference quotient". But it is easy to see that the $\Delta x$ in the denominator will just cancel that $\Delta x$ I factored out of the numerator.

All that is left to do is to take the limit as $\Delta x$ goes to 0. But now that there is no $\Delta x$ in the denominator, we can just replace $\Delta x$ in the formula with 0:
$\frac{0- 2x+ 1}{x(x- 1)(x+ 0)(x+ 0- 1)}= \frac{-2x+ 1}{x(x-1)x(x-1)}= \frac{-2x+ 1}{x^2(x- 1)^2}$

(You will be happy to know that you will soon learn general formulas so you won't have to do this for every derivative!)
• May 30th 2013, 10:39 PM
JamesT
Re: 1st principle derivative
Thank you so much guys!!!


text:
# How do you multiply (x-3)^3?

Apr 24, 2017

See the entire solution process below:

#### Explanation:

We can rewrite this expression as:

$\left(x - 3\right) \left(x - 3\right) \left(x - 3\right)$

We can multiple the two terms in parenthesis on the right of the expression using this rule:

$\left(a - b\right) \left(a - b\right) = {a}^{2} - 2 a b + {b}^{2}$

Substituting $x$ for $a$ and $3$ for $b$ gives:

$\left(x - 3\right) \left(x - 3\right) \left(x - 3\right) = \left(x - 3\right) \left({x}^{2} - \left(2 x \cdot 3\right) + 9\right) =$

$\left(x - 3\right) \left({x}^{2} - 6 x + 9\right)$

We now need to multiply these two terms together. To multiply these two terms you multiply each individual term in the left parenthesis by each individual term in the right parenthesis.

$\left(\textcolor{red}{x} - \textcolor{red}{3}\right) \left(\textcolor{b l u e}{{x}^{2}} - \textcolor{b l u e}{6 x} + \textcolor{b l u e}{9}\right)$ becomes:

$\left(\textcolor{red}{x} \times \textcolor{b l u e}{{x}^{2}}\right) - \left(\textcolor{red}{x} \times \textcolor{b l u e}{6 x}\right) + \left(\textcolor{red}{x} \times \textcolor{b l u e}{9}\right) - \left(\textcolor{red}{3} \times \textcolor{b l u e}{{x}^{2}}\right) + \left(\textcolor{red}{3} \times \textcolor{b l u e}{6 x}\right) - \left(\textcolor{red}{3} \times \textcolor{b l u e}{9}\right)$

${x}^{3} - 6 {x}^{2} + 9 x - 3 {x}^{2} + 18 x - 27$

We can now group and combine like terms:

${x}^{3} - 6 {x}^{2} - 3 {x}^{2} + 9 x + 18 x - 27$

${x}^{3} + \left(- 6 - 3\right) {x}^{2} + \left(9 + 18\right) x - 27$

${x}^{3} + \left(- 9\right) {x}^{2} + 27 x - 27$

${x}^{3} - 9 {x}^{2} + 27 x - 27$

Apr 24, 2017

${x}^{3} - 9 {x}^{2} + 27 x - 27$

#### Explanation:

${\left(x - 3\right)}^{3}$ = $\left(x - 3\right) \left(x - 3\right) \left(x - 3\right)$

Taking into account only the first two terms, we multiply to get ${x}^{2} - 6 x + 9$.

Next, we multiply ${x}^{2} - 6 x + 9$ by $x - 3$.

The result is ${x}^{3} - 3 {x}^{2} - 6 {x}^{2} + 18 x + 9 x - 27$.

We simplify this by combining like terms:
${x}^{3} - 9 {x}^{2} + 27 x - 27$


text:
Computational complexity of Turán-type problems

According to Turán's theorem (with $$r=n/2$$), any graph $$G$$ with $$n$$ vertices and at least $$n(n-2)/2$$ edges must contain a clique of size $$n/2+1$$. My question is: how hard is it to find this clique?$$^*$$ The problem is clearly in $$\mathbf{FNP}$$, and in fact in $$\mathbf{TFNP}$$. Moreover, by looking at the original proof of existence (first proof given here), it seems to be solvable by polynomial-time algorithm which recursively computes the clique (i.e. the problem is in $$\mathbf{FP}$$). Am I missing something here?

$$^*$$The corresponding problem for $$r=2$$ (i.e., Mantel's theorem) is easy since we can enumerate over all triples of vertices in $$G$$.

• The problem is not in NP, as it is not even a decision problem. It is in TFNP. Sep 7 '21 at 12:18
• I wanted to remark that P and NP are defined as collections of decision problems, not search problems. So you should be asking whether this problem is in FP i.e. the set of search problems solvable in polynomial time. Sep 7 '21 at 12:20
• My bad, have amended the question. Sep 7 '21 at 14:34

Since $$r$$ has to be an integer, I assume $$n$$ is even. I’m pretty sure the discussion below works for $$n$$ odd as well, if you decide whether you want $$r=(n+1)/2$$ or $$r=(n-1)/2$$ and adjust the bound according to the statement of Turán’s theorem.

I find it easier to express the problem in terms of the complement of your graph. Then it becomes: given a graph $$G$$ on $$n$$ vertices with at most $$n/2$$ edges, find an independent set of size $$n/2+1$$.

First, there is an off-by-one error: if $$G$$ consists of $$n/2$$ disjoint edges, it does not have any independent set of size $$n/2+1$$. Indeed, the statement of Turán’s theorem as given by your link requires $$G$$ to have strictly more than $$n(n-2)/2$$ edges, so in terms of the complement, the correct problem is: given a graph with less than $$n/2$$ edges, find an independent set of size $$n/2+1$$.

This can be done trivially by the following polynomial-time algorithm: pick one vertex in each connected component of $$G$$.

Indeed, since a component with $$m$$ vertices has at least $$m-1$$ edges, the number of edges in a graph with $$n$$ vertices and $$c$$ components is at least $$n-c$$. Thus, a graph with $$\le n/2-1$$ edges has $$\ge n/2+1$$ components.


text:
### Round and Round the Circle

What happens if you join every second point on this circle? How about every third point? Try with different steps and see if you can predict what will happen.

### Making Cuboids

Let's say you can only use two different lengths - 2 units and 4 units. Using just these 2 lengths as the edges how many different cuboids can you make?

How many DIFFERENT quadrilaterals can be made by joining the dots on the 8-point circle?

# Orange Drink

##### Age 7 to 11 Challenge Level:

This is a $750$ ml bottle of concentrated orange squash.

It is enough to make fifteen $250$ ml glasses of diluted orange drink.

How much water is needed to make $10$ litres of this drink?