kwjesse/TravelingSalesperson kwjesse/TravelingSalesperson

  • Stars
    star
    1
  • Language
    Python
  • Created over 4 years ago
  • Updated over 4 years ago
Twitter logo Share LinkedIn logo Share Facebook logo Share
kwjesse/TravelingSalesperson
github

kwjesse

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

This project implements a branch and bound algorithm to find solutions to the traveling salesperson problem (TSP) giving me exposure to NP-complete problems. The branch and bound algorithm finds a reduced cost matrix to determine the lower-bound and then performs a depth-first search which expands the most promising partial path first in order to identify a final solution quickly. A breadth-first search was not chosen because all possible paths must be explored before reaching a final solution resulting in a slow algorithm.

More Repositories

1

InternetRelayChat-IRC

This Internet Relay Chat (IRC) is a complex piece of software that supports communication between users, various IRC commands such as USER, NICK, & JOIN, a configuration file, and a log file. The server utilizes threading and mutexes permitting safe handling of various actions by multiple clients.
C
1
star
2

ConvexHull

This project implements finding the convex hull of a set of points using a divide and conquer algorithm.
Python
1
star
3

SpellChecker

I implemented a Trie in order to spell check a series of documents or phrases. The spell checker determines a list of possible words that are one or two edit distances away from the actual word including insertions, deletions, replacements, and transpositions.
Java
1
star
4

GeneSequencing

This project implements two versions of a dynamic programming algorithm for computing the minimal cost of aligning gene sequences and extracting an optimal alignment. An unrestricted alignment was executed that contains an unrestricted number of insertions or deletions with a space complexity of length of a sequence by the length of another sequence. The banded alignment of the sequences only computes scores for a certain width or band around the diagonal of the scoring matrix reducing the space complexity to the length of the shorter sequence by the bandwidth.
Python
1
star
5

NetworkRouting

This project implements Dyskstra’s algorithm to find paths through a graph simulating a network routing problem. Two different data structures were used to execute a priority queue, an unsorted array and a binary heap.
Python
1
star
6

NeuralNetworks

These projects explore Principal Component Analysis (PCA), Unsupervised Learning vs Semi-Supervised Learning, Sequential API vs Functional API, Artificial Neural Networks (ANNs), Deep Neural Networks (DNNs), and Convolutional Neural Networks (CNNs).
Jupyter Notebook
1
star
7

IdahoStateUniversityExpenditures

I performed exploratory data analysis on the 2018 and 2019 fiscal year expenditures for Idaho State University. I found the average increase or decrease in expenditure between 2018 and 2019 by exploring the Agency Name, Summary Object Name, Sub Object Name, and Vendor Name. I identified areas of potential cost savings for health care, travel costs, and gross salary & wage costs at Idaho State University.
Jupyter Notebook
1
star
8

Fermat

This project implements two primality tests using the modular exponentiation and greatest common denominator algorithms. The Fermat and Miller-Rabin algorithms determine whether a number is prime. However, the Miller-Rabin algorithm correctly identifies Carmichael numbers as non-prime numbers whereas the Fermat algorithm misclassifies these numbers as prime numbers.
Python
1
star
9

StringLibrary

Implemented strcat, strncat, strchr, strrchar, strcmp, strncmp, strcpy, strncpy, strdup, strndup, strlen, and strstr in ARM.
Assembly
1
star
10

ClassificationTree

I developed an application that learns from its user to identify and classify animals. A linked binary tree was created containing a hierarchy of binary tree nodes. The animal’s characteristics, such as furry, lives in water, has legs, are the internal nodes and the animal names are the leaf nodes. Depth first traversals, including pre-order, in-order, and post-order, and breadth first traversal were implemented to provide a list of nodes in the desired order. The user can save and retrieve a tree from a file.
Java
1
star
11

PunGenerator

My group designed a computational humorous system called PAUL BOT,” puns are usually lame but occasionally terrific”. Visit our survey to see the artefacts produced by PAUL BOT. The 2-Gram word list was omitted because COCA requires the list to remain private and thus code will not compile. If you would like access to the full repository, please contact me. Credit to Brad Tyler for being a part of the project.
Python
1
star