Programming Projects
Family Search Server and Client
Introduction
Family Map is an application that provides a geographical view of your family history. It displays information about important events in your ancestors’ lives (birth, marriage, death, etc.), and plotting their locations on a Google map. Family Map uses a client/server architecture.
The Family Map client is an Android app that lets a user view and interacts with their family history information
The Family Map server is a regular, non-Android Java program that runs at a publicly-accessible location on my laptop.
-
The first half of the video: family search server coded with Java. Json is used for browser-server communication
-
The second half of the video: Android app client used Json to talk to the server
This document describes the functionality and layout of all the features
Algorithm design
This program will use the Fermat primality and the Miller-Rabin test to check if the given number is a prime.
Detail algorithm is given in the link above that leads to Wikipedia.
Since it may give false-positive results, multiple random testing trials can be set. The probability of prime is calculated. Carmichael number is tested as well since it can deceive Fermat test occasionally
A simple polygon is convex if, given any two points on its boundary or in its interior, all points on the line segment drawn between them are contained in the polygon's boundary or interior.
Divide and conquer algorithm is implemented to solve this problem. All the points are recursively split in half. During merging, exterior line segments are drawn to make sure all points are contained within the boundary to form the convex hull. (detail about divide and conquer algorithm is shown in the above link to Wikipedia)
The time is displayed to show the efficiency.
This program uses Dijkstra’s algorithm to find paths through a graph representing a network routing problem. (see the link for detail algorithm)
In this program, I implemented a regular array and a binary heap, which is faster to find a minimum value within Dijkstra's algorithm. This program will show that the heap structure is faster than the array structure, especially in a larger number of points.
It can find the shortest distance between the farthest two points in 1,000,000 points map in a reasonable time with heap implementation.
I implemented dynamic programming algorithms for computing the minimal cost of aligning gene sequences and for extracting optimal alignments.
The final value is calculated as followed:
-
Substitutions, which are single character mismatches, are penalized 1 unit.
-
Insertions/Deletions (“indels”), which create gaps, are penalized 5 units.
-
Matches are rewarded -3 units
Therefore, lower value means those two genomes are more easy to align. If the box is clicked, it will show how those two genomes are aligned "-" means insertion.
I also implemented a folded structure, which increases speed if we try to align more digits, but it can not obtain an optimal solution.
NOTE: I only code the backend algorithms. I did not design the GUI for python for all projects here
Traveling salesman problem is a famous NP-hard problem. In my program, there is a random method, which finds a feasible path randomly. Another method is the greedy method, but sometimes it can run into a dead end. The third method is the branch and bound algorithm, which can find the optimal solution.
I incorporate the depth of the branch and bound layer into the priority of expanding the node, so it can balance between expanding good prospect solution node and getting to leaf node for a solution (so it can return something good before the given time is out). This method works great for less than 50 cities for 10 minutes.
The fourth algorithm is the genetic algorithm, which is a stochastic method that will run until the given time ends. This method works great with a number of cities less than 400 given 10 minutes.
In the problem, it has 3 difficulties: Easy (symmetric), Normal (asymmetric), Hard (asymmetric and some infinite distances), Hard deterministic (cities being generated in the same locations for a give size/seed pair, the edges removed will be consistent )
MATLAB Graphical User Interface
This GUI simulates a golf trajectory for two different angles. This program can adjust wind direction, speed, as well as swing power and angle. It uses aerodynamic equations to calculate drags.
This GUI calculates and plots the shear and moment diagram, which is used in determining the mechanics of material. There are a few simply supported models for the user to choose from.