Jing Yi (Jimmy) Li - Portfolio

Description:
Inspired by dlmalloc, the standard dynamic memory allocator used in the standard GNU library. dlmalloc is a very good example of how a simplistic idea can be generalized to many applications. The main idea of dlmalloc is the Segregated Free List, which is used to achieve high performance - amortized O(1) allocation and free - while maintaining low fragmentation and high peak memory utilization.
This allocator is optimized for specific workloads using various techniques such as:

• Preallocation (a technique extensively used in dlmalloc)
• Deferred free
• On-demand coalescing of free neighbor blocks

Description:

Designed to aide users to find their way around facitilies with complex layouts - e.g. Costco, Walmart, malls. Using their browsers, users are able to construct a 2D layout which matches that of the concerning facility. Users are able to place rectangles, which represent stores/locations, and also paths to indicate path/walkways which connect the stores/locations.

While the layout design scheme seems very simplistic, most interior layouts can be represented simply with rectangles.

After the layout has been inputted, the user then inputs a list of destinations which he/she would like to visit within this facility, and, with the layout provided, the application will do its best to compute the shortest possible distance which visits all destinations.

Shortest Path & Traveling Salesman Problem (TSP)
Naturally, shortest path is implemented using Dijkstra's Algorithm. We decided to approach TSP by: (1) Performing the Nearest Neighbor algorithm to find an initial solution; (2) To improve upon the initial solution, a global minimum can be closely approximated by using Simulated Annealing (SA), which iteratively and randomly performs local improvement using the 2-Opt algorithm until improvements can no longer be made.

To benchmark performance of 2-opt and SA implementations, an approximated Held-Karp algorithm (which yields a lower-bound distance on the optimal TSP solution) was implemented. The algorithm was implemented using the top-down dynamic programming approach.

• 2-Opt: 10-15% improvement over Nearest Neighbor
• SA: 20-30% improvement over 2-Opt
• SA within 5% of Held-Karp Lower Bound

Description:

This is my first attempt at using OpenGL to render 3D graphics. OpenGL is a difficult library to learn from the onset, and this was a consistent challenge. Here is a list of features currently present:

• .OBJ file processing
• Per-fragment Blinn-Phong Shading
• 2D Textures
• Shadow Maps - FBOs and 3D Textures

As this project is ongoing, I hope to expand to include:

• World generation
• Animations
• Water: Animations + Reflections
• Skybox & Environment Maps

Description:
Implemented from scratch with Scalar Vector Graphics:

• Compute and visualize the frequency-variant, time-invariant response of the circuit (Bode plots - phase, magnitude)
• Compute and visualize the frequency-invariant, time-variant response of the circuit
• Sample input signals as mathematical functions and output as discrete points to be plotted

Description:

MapReduce is a Single-Instruction-Multiple-Data (SIMD) distributed processing framework developed by Google. Its advantages are providing a framework which leverages Google's massive compute infrastructure to enable the processing of massive workloads (in the order of terabytes) across thousands of machines while guaranteeing reliability.

This project is an imitation of MapReduce. It first implements a distributed Key-Value storage system, which is replicated at least 3 times, and available up to half of the total number of active nodes in the network. MapReduce, then, is placed atop this reliable, distributed Key-Value store (much like Google's MapReduce is placed atop the Google File System).

Storage servers also serve as MapReduce workers. All communication occurs over reliable TCP channel. Please see the report for implementation details as well as performance testing results.

Description:

The function of the Circuit Schematic Visualizer is to render each circuit component at predefined positions and orientations. Separate sub-modules were created for each unique component including: resistor, capacitor, dependent/independent voltage & current sources, wires, and ground nodes.

The SFG Overlay solves the curve-generation problem by employing a heuristical variation of Bézier curves, a polynomial interpolation technique where a curve is procedurally generated based on a set of predefined control points.

Description: Closely resembling MS-Paint, but works for Mac and Linux. Features include:

• Copy + Paste pictures onto canvas
• Draw on canvas
• Tools:
  • Pencil (free hand)
  • Line
  • Circle
  • Rectangle
  • Colour selection
  • Fill
  • Eraser tool
• Resizable canvas
• Selection tool:
  • Rectangle
  • Circle
  • Lasso (Freehand)
• Undo/Redo