General techniques for developing algorithms. Divide and conquer Greedy dynamic programming. Search and traverse. Backtracking. Branch and Bound. Some theoretical results will be discussed, for example, those relating to NP - completeness.

Project 1. Binary Search: Implement a modified Binary Search algorithm to find all occurrences of a target value in a sorted array in the most efficient way and analysis it time complexity

Project 2. Find a way to use the pair of dice to generate a random number in [1, 4] unevenly: it should produce 1 in 40% of the time, 2 in 30%, 3 in 20%, and 4 in 10%. Justify the algorithm both by analysis and by simulation.

Project 3. Dynamic Programming: There is a 1-by-1 tile on an m-by-n board. Initially the tile is at the top-left corner of the board, and in each step it can move to the right or down by one position (as far as remaining on the board), and at the end the tile will be at the bottom-right corner. Given different costs from one position to another one, the problem is to design an algorithm that can find the path with the least overall cost.

Project 4. Amortized Analysis: The basic idea is to use multiple arrays, each with a length of 2k, to store n elements, according to the binary representation of n. Each array is sorted, though elements in different arrays are not ordered in any way.In this data structure, SEARCH is carried out by a sequence of binary search on each array, and INSERT is carried out a sequence of merge of arrays of the same length until an empty array is reached. Analyze the worst-case cost and amortized cost.