@DanielFischer I actually have done 2 semester in computer science and next year did Python and Java. However I'm not sure where to start with algorithms and data structures. Will be doing these next year in my CS courses but would like to get ahead
@Sabಠ_ಠ: If you're not familiar with it yet, you can read up Landau notation and compute the runtime of certain algorithms using the Landau notation. Searching and sorting algorithms are usually where you'd start.
computerphile have a couple of good videos that will show you the idea behind some sorting algorithms, but they dont have any code associated with it. If you want code, just add the language before the algorithm name and a good few results will pop up on google
@evinda As far as I recall, googling "median of medians" should turn up a number of relevant hits. It's probably also mentioned (with link) on the wikipedia page on quicksort.
@Sabಠ_ಠ: Have you never run a program before? Also, as I said, look up Landau notation and try to compute the runtime of your algorithms using that notation. It will be helpful to find out which algorithm is efficient and which is not so much.
@Sabಠ_ಠ: I learnt how they work in my class about algorithms and complexity. I'm sure you'll find a lot of information on the internet about it with lots of examples.
function medianOfMedians(list, left, right) numMedians = ceil((right - left) / 5) for i from 0 to numMedians // get the median of the five-element subgroup subLeft := left + i*5 subRight := subLeft + 4 if (subRight > right) subRight := right medianIdx := selectIdx(list, subLeft, subRight, (subRight - subLeft) / 2) swap list[left+i] and list[medianIdx] return selectIdx(list, left, left + numMedians - 1, numMedians / 2)
What does the function selectIdx do? @DanielFischer
There's a guy who knows a lot about topology and works on hyperbolic geometry in there. I visit him often, and that's whom I am referring to as professor.
He'll smack me once or twice a day for either saying "gah, galois theory is better than this stuff" or "bunch of handwaving and thus it follows" or "algebraic topology is stupid" or similiar.
@evinda Because the algorithm is written to search the array in groups of five, and your array has six elements. So the first group gets five elements, and the second group consists of a single element. You could slightly modify the function to use groups of seven, then you'd just have a single group there.
all pair I can make from A to B are {(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)} and these are total of 6 pairs and if I use formula then then it's 2^(6) = 64 and 6 != 64
OH! what a holy crap, my brain is / was whirling I was considering AxB as totoal number of binary relations possible but I guess now even ((1,1), (1,2)) is also one single binary relation correct ?
@evinda First, the median of the first five elements is put in the first slot of the array. That would swap 7 and 15. Then the median of the last group is put in the second slot, then swapping 19 and 15. So the array would then be 7,19,3,1,20,15.
OK, so the problem is find a connected topological space $X \subset \Bbb R^2$ with the subspace topology such that removal of a single point makes it totally disconnected.
@evinda selectIdx(A,left,right,k) returns the index of the element that would be in A[left+k] if the subarry A[left],...,A[right] were sorted in-place.
@evinda It returns the index at which the (right-left)/2+1-th smallest element of that subarray is. Think in extreme cases, a subarray of length $1$. You call selectIdx(A,left,left,0).
OK, since Pedro doesn't want to do it, here's an explicit construction : Take a cantor set. Now join your components of the cantor set with strings, joined at some point. Now make those strings cantor sets in turn. Join the components of each of those cantor sets by strings meeting at the same point as before. Continue ad infinitum.
@evinda Something like that. I don't remember the exact order of the original, and it might be that selectIdx modifies the subarray, then things could look differently after the two medians of the groups.
@MikeMiller Is it true that for a connected space $X$, an open cover $U$ of it and group $G$ acting properly discontinuously and freely on $X$ then there is a SES of Cech fundamental groups $1 \to \check{\pi_1}(X, U) \to \check{\pi_1}(X/G, p(U)) \to G \to 1$ where $p : X \to X/G$ is the projection?
@evinda That depends on the requirements and whatnot. It might be a requirement that it doesn't modify the original array. Or it may be okay if it modifies it. If the implementation that modifies the array is more efficient, and modification is okay, one would use that. If not, one would implement it differently.
@DanielFischer The exercise I am looking at asks the following: Describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set $M$.
Let $M_{i,j}$ be a matrice of the canonical base of size $n>1$.
What is the least number of orthogonal matrices required so that $M$ can be expressed as a linear combination of those ?
It's not true, @Ted. Because $\Bbb{CP}^\infty$ is a loop space, a theorem of Milnor says it is homotopy equivalent to a topological group, which ofc has nontrivial $\pi_2$.
now consider the map pi_1(X/G, x_0) \to G by taking a loop based at x_0 and lifting it to X with base point y_0 and finding a g such that g(x_0) = x_1 where x_1 is the endpoint of the lifted path
Let $M_{i,j}$ be a matrice of the canonical base of size $n>1$.
What is the least number of orthogonal matrices required so that $M$ can be expressed as a linear combination of those ?
