The programs in this directory are my works in the course “Data Structure and Algorithm”.
These programs not only produce the correct result, but also aim to run as fast as possible by implementing certain data structures or algorithms.
Nonogram is a kind of puzzle (https://en.wikipedia.org/wiki/Nonogram), and the program "nonogram_ed2" aims to solve this puzzle. First, the program figures out the possible combinations of filling the cells for each row and column, and eliminates the contradicting combinations. Then "Depth First Search" is implemented to find the solutions.
The program "preposition_ed4" is basically a preposition checker. Given a query string, the program produce a list of modified strings by inserting prepositions in several positions and search each string in the "Google's Web 1T" dataset. If the string is found, then the program will recommend the phrase.
The program "recommendation_ed4" deals with a large database that store the recommendation records of a network company. The database was also given as a problem in KDD Cup 2012. A multi-level unorderedmap is used to store the data so that the program can carry out several operations in a efficient way.
The program "singing" aims to find a song in a pool that matches the query pitch vector most using dynamic programming.
The program "spell_check" create a list of possible modified words according to the query word and search each word in the "CMU pronuncing dictionary". If the word is found, then the program will recommend the word.
The program "stock" simulates the transaction of shares in a stock market. Two heaps are used to store the buying bid and selling bid respectively.
The program "traversal" gives the outcomes of pre-order, in-order, post-order traversal of the input tree.