- Randomized QuickSort and Randomized Select Analysis - apr 04, 2015
I am a Ph.D. student in Computer Science and Engineering at The Ohio State University (OSU). My broad research interests include Erasure Coding, Remote Direct Memory Access (RDMA), and Distributed File System. I am a Graduate Research Associate in LuLab, led by Dr. Xiaoyi Lu. Prior to graduate school, I worked as a Big Data Engineer at MiningLamp and a Software Engineer at Weibo, China. I finished my Bachelor’s degree in Tianjin University, China.
Graduate Research Associate
This project aims to implement and compare variant machine learning techniques for predicting house prices. It is an expanded project from Kaggle House Prices: Advanced Regression Techniques, such that the project is going to use the same dataset provided under this Kaggle competition. The machine learning techniques in this project include Linear Regression, Random Forest, Adaptive Boosting, Support Vector Regression, Gradient Boosted Decision Tree, K Nearest Neighbors, and Neural Network.
Trie is an ordered tree data structure which stores words in it so that users can search a word or a prefix quickly. Time complexity for adding a word to a Trie is $O(l)$, and for searching a word or a prefix is $O(l)$ too ($l$ is the length of the word or the prefix being added or searched). So it’s why we prefer Trie rather than Set and Hash Table in some situations, such as Dynamic Set, Associative Array and a predictive text or autocomplete Dictionary.
Though hash table is one of the most efficient data structures, it has some weaknesses.
Randomized QuickSort is an efficient sort algorithm requiring only $\Theta(n\log n)$ expected time on any input.
function RANDOMIZED-QUICKSORT(Array, low, high)
Randomized Select is an efficient algorithm to find $i$th smallest element of Array[low…high] with only linear expected time on any input.
function RANDOMIZED-SELECT(Array, low, high, i)