Introduction

第一代Galaxian游戏在1979年登场，之后在1981年推出了升级版Galara，以及1984年的加强版Gaplus。作为早期电子游戏，Galaxian在街机市场是十分火爆的。
相比同时代的Space Invaders，由于Galaxian采用了当时的最新技术，游戏体验有了质的飞跃，是当时最受欢迎的街机游戏之一。

Requirement

In this assignment you develop an arcade style name Galaxian. The game needs to be implemented in OpenGL engine. You should define your own game objectives, such as final goals and the level of player interaction. Lives and scoring should also be planned.
The difficulty lies in how to manage the objects on the screen, the enemy flight path, in particular, and how they can track the ship. The algorithm can avoid the enemy collisions between each other, and how to aim at the player’s position.
Your program provide the following functions:

1. OOP design
2. OpenGL graphics
3. a simple intro menu
4. texture animations
5. sound

Introduction

市场上有一些成熟软件可以做Digital image process，如Matlab和R。这两款软件提供了丰富的图像处理函数，以及优秀的交互，和简易的调试功能，因此受到图像处理工程师的青睐。
C++虽然也可以使用二维数组的存储方法来存储图像，并实现等同于Matlab和R的算法。但是编程的复杂性远远大于前者。
虽然说，用C/C++编出的图像处理软件性能会超过Matlab和R，但是这种差异需要大规模的图像才会体现出来。而目前业内对于大规模的图像处理，往往会采用云计算分布式的做法，而不是单纯的使用一台计算机进行运算。

Requirement

In this assignment, you are required to build a simple software framework for digital image processing.
Your program should be able to read and write PPM / PGM image files (either binary or ASCII), and perform color or geometric transformation.
The programming language is C/C++. The preferred programming environment is Visual C++ (VC) 2012. If you choose to use a different platform, your submitted source code should be compatible with a Visual C++ .Net compiler, i.e., one can build a working executable for Windows from your source code.

Introduction

工程编程中，Sorting通常都是出现在三方库中直接调用。Sorting的种类繁多，有下面几类：

插入排序

Straight Insertion Sort，直接插入排序
Shell’s Sort，希尔排序

选择排序

Simple Selection Sort，简单选择排序
Heap Sort，推排序

交换排序

Bubble Sort，冒泡排序
Quick Sort，快速排序

其他排序

Merge Sort，归并排序
Radix Sort，桶排序/基数排序

掌握以上几种基本排序算法的原理和实现，是每个工程师的基本功。刚开始的时候可以先研究其中一两个感兴趣的算法，自己动手画排序图，并编写简单代码来实现。
同时，可以使用一些三方算法库，来进行实际的编程操练。

Requirement

Implement void quicksort(unsigned int *a, int n) as a “C” style function in the file quicksort.cc

1. The pivot should always be chosen as the first element of the array.
2. See the given quicksort.cc file for how to determine running times. You can modify this file as you wish but I should be able to run it to get your output in the file specified.
3. The main function in quicksort.cc reads from the file “quicksortinput” the n integers and writes the n integers to the file “quicksortoutput” in ascending sorted order. See “quicksortsampleinput” and “quicksortsampleoutput” for formatting details. Please make sure that your program can EXACTLY reproduce that output file given the input file. You may want to use the “diff” program to test this.
4. The function sorts the array a of n positive integers with the quick sort algorithm.

Implement void radixsort(unsigned int *a, int n) as a “C” style function in the file radixsort.cc

1. The elements of the array are positive and are represented with 32 bits.
2. See the given radixsort.cc file for how to determine running times. You can modify this file as you wish but I should be able to run it to get your output in the file specified.
3. The main function in radixsort.cc reads from the file “radixsortinput” the n integers and writes the n integers to the file “radixsortoutput” in ascending sorted order. See “radixsortsampleinput” and “radixsortsampleoutput” for formatting details. Please make sure that your program can EXACTLY reproduce that output file given the input file. You may want to use the “diff” program to test this.
4. The function sorts the array a of n positive integers using the radix sort algorithm.

Introduction

AVL Tree也就是AVL树，是早的自平衡二叉查找树。其任意节点的两颗子树最大高度差仅为1，因此也被称为高度平衡树。
相对红黑树，AVL树目前的应用场景已经非常下了，大部分还是用于学习和研究。
AVL树最大的特点是，树的查找、插入和删除在平均和最坏情况下都是O(log n)，但增加和删除节点可能需要旋转这颗树，使其重新平衡。

Requirement

Implement a C++ AVL Tree class AVLTree in files AVLTree.h and AVLTree.cpp

1. The constructor AVLTree () builds the AVLTree.
2. The destructor ~AVLTree() deallocates all dynamically allocated memory.
3. The void insert(int k) method inserts the key k into the AVLTree, and does not do anything if the key is already stored.
4. The void remove(int k) method removes key k from the AVLTree and does not do anything if AVLTree does not contain key k.
5. The items stored are positive integers which serve both as keys and as elements.
6. The void printInorder() method prints the tree to the standard output using an inorder traversal; it prints a (key, height) pair for each node and ends with a newline.
7. The void printPostorder() method prints the tree to the standard output using postorder traversal; it prints a (key, height) pair for each node and ends with a newline.

Introduction

Random Number只是一个数学的概念，在计算机领域，由于精度原因，并不存在严格的数学意义上的随机数，所有所谓的随机数实质上都是伪随机数。
但是，结合外部系统，计算机也是能产生真随机数的。一个典型的例子就是UNIX内核中的随机数发生器，也就是(/dev/random)设备。
它是怎么做到的呢？
UNIX本质上维护了一个熵池，不停的采集外部设备的非确定性/随机事件，如I/O，中断等，并将这些事件作为随机数的种子来使用。
因此，虽然程序和算法本身不能产生真随机数，但是作为计算机整体，还是可以依赖外部熵来产生真随机数的。

Requirement

Write a program that generates a random number and asks the user to guess what the number is. If the user’s guess is higher than the random number, the program should display “Too high, try again.” If the user’s guess is lower than the random number, the program should display “Too low, try again.” The program should use a loop that repeats until the user correctly guesses the random number.
You should also keep a count of the number of guesses that the user makes. When the user correctly guesses the random number, the program should display the number of guesses.

Introduction

使用Visual Studio开发中小型程序是十分快捷的。由于VS强大的生态系统，可以很容易的将各种组件集成在一起。但也因为如此，对于初学者来说上手难度较大。
C#(C Sharp)作为Delphi之父Anders Hejlsberg跳槽到微软后的一门新编程语言，也是同时兼顾应用开发与系统开发，简单、现代、通用以及面向对象的程序设计语言。结合Visual Studio，其开发速度直线上升。
和Visual Studio同样，框架的复杂性导致C#对于初学者来说，上手较难。

Requirement

Whether you develop programs for enterprise solutions, high performance computing, digital signal processing, games or mobile applications you are likely to develop them in either Java or C# in the future – in fact you are likely to develop programs in both languages as a Gartner Group survey shows that 30% of enterprise applications will have code in both languages.
In this course you need to do the following exercises.

1. Follow the instructions on Visual Studio 2013 Express Editions: Creating a Console Application with Visual C# Express
2. Follow the instructions on Visual Studio 2013 Express Editions: Creating a Windows Application with Visual C# Express
3. Try out the Visual C# Samples
   阅读全文 »

Introduction

用Python的一个优势便是十分适合Text processing，由于Python内建了许多函数，对于文字、字符的处理十分便捷，如字符串连接、字符串截取、字符串查找、字符串替换、字符串比较、字符串分割、字符串翻转、字符串编码等，都有对应的函数进行处理。相比C语言，节省了很多开发工作量。

Requirement

This question prints the leaves of a symmetric tree. A user will be prompted for a symbol and a positive position for the tip of the leaves. Starting from the tip, the tree will fan out on both sides symmetrically until left side of the leaves reaches the left edge, assuming that the right edge has no limit. For example,

1
2
3
4
5
6
7
8
9
10
11
12
13

Please enter a symbol: *
Please enter a positive position
of the symbol on the first line: 10
         *
        ***
       *****
      *******
     *********
    ***********
   *************
  ***************
 *****************
*******************

Introduction

Rat in a maze problem，是用回溯法求解迷宫问题的经典例题。回溯法是一种优选的搜索法，根据择优的条件向前或向后搜索，最终获得目标。当向前搜索到某一步，根据目标函数得到的结果不是最优时，进行回溯，重新选择探索方向。由此得到最优解。
回溯法解决问题的基本步骤一般为：

1. 根据给定问题，定义目标函数，并保证该问题至少有一个解
2. 确定搜索的空间结构，确保回溯法可以遍历整个解空间
3. 通过深度优先算法的形式，搜素整个解空间，并通过适当剪纸来减少冗余的搜索

回溯法的一个应用场景便是解决迷宫问题。

Requirement

In this problem you will solve the “Rat in a maze problem”, using Stacks and Queues (Lectures 12-14).
The main points we shall be covering are:

1. Using Stacks and Queues in an application
2. Re-enforcement of the usage and advantages of makefiles / make utility in UNIX/Linux
3. Use of abstract data types in C++, and separate compilation
4. Use of header files and libraries for Stacks and Queues
   阅读全文 »

Introduction

Matrix和Vector是Linear algebra中最基础的概念。而利用计算机求解数学问题，是一种常见的做法。
将数学公式、定理用计算机编程实现，看起来并不是一件难事，但是对于某些算法，在不考虑时间复杂度的情况下，编写出来的代码运行效率将极其低下。尤其是I/O操作和循环结合的地方，在数据量大的情况下，往往不能快速地得到答案。因此在求解问题的过程中，对于原数学公式、定理的简化与改写，是很有必要的。
而本次作业需要在给定的时间复杂度条件下，求解一些基本的线性代数的问题。

Requirement

This assignment is to write a parallel program to multiply a matrix by a vector, and to use this routine in an implementation of the power method to find the absolute value of the largest eigenvalue of the matrix. You will write separate functions to generate the matrix and to perform the power method, and you will do some timing experiments with the power method routine.

Introduction

古典密码在密码学中，有着举足轻重的作用。做为Data security领域的基础算法理念，离不开其中的置换和置乱两大算法。
置换，即保持明文中的字符本身，但对字符的顺序进行重新排列的算法。
置乱，即将明文中的字符，用其他字符或字符序列进行替换。
而将经过加密的密文，找到其中的统计规律，并还原出其中的原文，称为密码破解。
而本次作业就是需要找到统计规律，进行密码破解。

Requirement

An encrypted file, cryptfile1.txt, is given. Your task is to decrypt it. The file was encrypted using some substitution algorithm. The easiest way to break such encryptions is by an analysis of letter frequency. You can go to the library or the Web and get information on the relative frequency of letters in the English language. A program, LetterCount.java, is also given which would allow you to find this yourself. You would simply have to choose a source text file that is sufficiently long and sufficiently representative of English that the relative frequencies of letters in it is pretty much the same as the relative frequencies given in published sources. The real value of LetterCount.java is that it provides sample code that you code adapt to decryption purposes. This encryption is simple enough that in theory you could do it by hand. If you find that your initial attempt by hand is netting nothing, you may want to write a program to help. You should hand in the results of your decryption effort.