Computer Science
http://hdl.handle.net/10066/453
2019-07-13T00:23:52ZPlane and Simple: Characterizing and Testing
Planarity
http://hdl.handle.net/10066/20807
Plane and Simple: Characterizing and Testing
Planarity
Emery, Dylan
An exploration of previous work on planarity with a relatively simple and complete proof of Kuratowski's theorem and an in depth explanation of the foundations of the Left-Right Planarity algorithm.
2018-01-01T00:00:00ZSpeed up Three Dense Matrix Multiplications By
Changing Iteration Order
http://hdl.handle.net/10066/20808
Speed up Three Dense Matrix Multiplications By
Changing Iteration Order
Chen, Zongchang
Improving the performance of dense numerical programs is an area that has been studied for decades. There are numerous approaches that people have applied on those problems, including upgrading the algorithm, running the program in parallel and so on. My thesis is mainly focused on improving the performance by changing the iteration order of loops. Because of locality of reference, the CPU tends to collect the data which are more recently used in terms of access time, and those which are closer to each other in terms of memory locality so that the performance of the program can be improved to some degree. Sometimes programs do not notice such potential memory level improvements when they were coded so our goal is that, when given a program, under the premise that the output of the program is never altered, we reorder the iteration within loops to gather the data stored in memory more closely or possibly change some parts of the data structure so that fewer variables can be used and be accessed more frequently. This area has actually been studied for decades [1, 2, 4, 6] and people mainly make additional modules for compilers to automatically complete the optimization. But sometimes the built-in optimization approaches in compiler do not perfectly fit some certain problems. Hence, people write some more specific libraries to expand the solution space of iterators with different orders for different problems, i.e. the Chapel library. [9] In this thesis, the discussion is mainly basically around a simple linear algebraic program - three matrix multiplications (3mm). We will talk about different techniques that the compiler and human programmers can apply to the benchmark program for performance improving. The algorithm may look simple, but the reasons why they can work are worth noting.
2018-01-01T00:00:00ZA Comparison of Fairness-Aware Machine Learning
Algorithms
http://hdl.handle.net/10066/20803
A Comparison of Fairness-Aware Machine Learning
Algorithms
Roth, Derek
Fairness, as it applies to algorithms,
implies that the decisions made by an algorithm are being made such that there is no
discrimination against individuals or groups in labeled data sets. In this paper, I give a
summary of the relevant endings by computer scientists regarding fair algorithms, discuss
three techniques used to reduce/remove bias in algorithms, and examine three case studies
that clearly demonstrate the importance of this field of study. The goal of this thesis is
to determine the best practices for case studies on this topic and to discover ways of
developing algorithms that are unbiased. I apply existing algorithms to four data sets and
compare their results in order to determine which are the most useful in a specifc
situation.
2018-01-01T00:00:00ZCOMPARATIVE ANALYSIS OF DISTRIBUTED METHODS FOR
PAGERANK COMPUTATION
http://hdl.handle.net/10066/20804
COMPARATIVE ANALYSIS OF DISTRIBUTED METHODS FOR
PAGERANK COMPUTATION
Weinstein, Noah
The PageRank of a vector is a measure of centrality for nodes in a network. Three ways to calculate the PageRank are using power iteration, Monte Carlo methods, and iterative graph methods using Spark. The graph methods built in to spark and the power iteration method demonstrated a small difference in their performance when increasing the number of machines in a cluster. Running on AWS, the graph methods improved more when increasing the number of machines from 2 to 10 when compared to the power iteration methods. Experiments were carried out using Amazon Web Services and run on a subset of the web graph from Google. Improvements in partitioning could change these results, and could increase the performance of the matrix methods overall.
2018-01-01T00:00:00Z