this is for holding javascript data
Jeremy Ting edited q1.tex
almost 10 years ago
Commit id: c5ff3eada6a512d26a0a691597ed3d71b9568556
deletions | additions
diff --git a/q1.tex b/q1.tex
index f8f99ac..c201b0a 100644
--- a/q1.tex
+++ b/q1.tex
...
\section{Question #1}
A. \textbf{A.} First, we will put all of the $S(u_i,u_j)$ values into an array that keeps track of the two people and their similarity level. If there is $n$ people, the number of connections will be on the order of $n^2$.
From this, we can call the total number of connections, $E$.
Now, we can use counting sort to sort all of these values from the largest to smallest.
TO To use
ocunting counting sort, we have to make sure these two assumptions are satisfied
first. first:
1. The values must be an integer (we know this because of how the problem is set up).
2. We must know the range of the
numbers.
We can find the range of these numbers
in linear time by looking through every single value, and keeping track of the max number (at the time). So, in linear time, we can find the max value. Then, we can use counting sort which also costs \textbf{linear time}, so in total, the time for the sort is $n^2$ (to find the max)$+$ $n^2$(to do the sort) = $O(n^2)$. Although it looks like it's not, the efficiency is still linear.
Now, we take the largest value in our list and place those users into the same group. WE will use a graph data structure ot keep track of which nodes are connected to each other. This data structure will be explained in part b.