How can one construct a densest graph with no k-clique? Given integers $k$ and $n$ with $2 \le k &lt; n$,
  how does one construct a graph on $n$ vertices
  that contains no $k$-clique and has the maximal
  number of edges? 


This sounds like basic combinatorics, but I don't know where to find the result.  Pointers would be welcome if this is well-known.

Ideally I would like a deterministic procedure to construct such a maximal graph in $n^{O(1)}$ time.

One graph with $n$ vertices that is guaranteed not to contain $K_k$ is $\overline{K_{n-k+2} + \overline{K_{k-2}}}$, the complement of the graph formed by the disjoint union of $K_{n-k+2}$ and $k-2$ isolated vertices.  Whenever one picks $k$ vertices from it, at least two of these must be from the subset which is completely disconnected, so they cannot form a clique.  This can clearly be constructed in polynomial time, and is quite dense for $k$ close to $n$.  However, this construction yields rather sparse graphs when $k$ is small relative to $n$, so it seems unlikely to be the optimal construction.
Turan's theorem exactly characterizes the densest graphs on n vertices with no k clique. The Turan graphs are the maximal graphs, and they're very easy to construct. Is this what you want?