Uncertainty Quantification (UQ) deals with the study of variation in the response due to the presence of uncertainties in input parameters and governing models. Among the prevalent probabilistic techniques for UQ, non-intrusive Polynomial Chaos Expansion (PCE) has become more popular recently due to its mean square convergence property and ability to integrate deterministic codes as black-box. However, the number of basis terms in the expansion increases exponentially with the number of random inputs - ‘curse of dimensionality,’ and demands a huge number of function evaluations. Hence, this dissertation has attempted to extensively explore new robust algorithms for PCE while maintaining a proper balance between accuracy and computational efficiency. At first, a new non-intrusive method for PCE called Polynomial Chaos Decomposition with Differentiation (PCDD) is developed. The PCDD utilizes higher-order sensitivities of the responses and requires samples equal to the number of basis terms only. Secondly, the PCDD is utilized to develop a stochastic multi-scale modeling framework for composite structures since the response of composites is hugely influenced by the uncertainties existing at different scales such as micro-scale and macro-scale. Another framework for stochastic progressive failure analysis (PFA) of composites is also developed that allows performing global sensitivity analysis (GSA) to identify the relative importance of random inputs as a post-processing step. To further reduce the number of samples and make the stochastic problem more tractable, an adaptive L2-minimization algorithm that allows basis adaptivity along with sequential adaptive sampling is developed. Finally, an adaptive algorithm to obtain sparse PCE models with L1-minimization and sequential sampling is also proposed for high-dimensional problems. The L1-minimization is capable of solving the under-determined system when the number of samples is minuscule. It is also advantageous in terms of computational storage and memory because of its ability to provide a sparse solution. In general, the overarching goal of obtaining high-fidelity stochastic response models while maintaining a balance between accuracy and computational cost was successfully achieved by the novel algorithms developed in this dissertation. Furthermore, the invaluable information obtained with PCE for composite structures highlighted the benefits of its implementation in engineering problems.