# TSM_Alg

Algorithmische Geometrie
Algorithmische Geometrie, Sommersemester 2014
Computational Geometry, Summer 2018

Geometric Algorithms (INFOGA) 2018, Block 2, Frank Staals

# Woche 1

time complexity


### Comparison sorts

#### Simple sorts

• Insertion sort
• Selection sort

• Merge sort
• Heap sort
• Quick sort

• Bubble sort

#### Exotic sorts

• Binary tree sort
• Cycle sort
• Library sort
• Patience sort
• Smooth sort
• Strand sort
• Tournament sort
• Cocktail sort
• Comb sort
• Gnome sort
• Block sort
• Odd–even sort
• Curve sort
2d line intersection


### Aufgabe 1

Line–line intersection

# Woche 2

Sweep (Informatik) (Sweep-Line)
Rot-Schwarz-Baum (red–black tree oder RB tree)
Wikipedia: JTS Topology Suite
LocationTech JTS Topology Suite

github.com/locationtech/jts, The JTS Topology Suite is a Java library for creating and manipulating vector geometry.
github.com/locationtech/jts/releases
github.com/locationtech/jts/blob/master/MIGRATION.md
github.com/locationtech/jts/blob/master/USING.md
github.com/locationtech/jts/blob/master/DEVELOPING.md

### Convex Hull – Divide & Conquer

Convex Hull, COMP 215 Lecture 5, PDF
An efficient way of merging two convex hulls

Tangents to & between 2D Polygons

# Woche 4

Kreisgraph

#### Graph

Families of Graphs (PDF)

#### CGAL

2D Arrangements – Arrangement on Surface

#### Maths Resource

Planar Graphs – Worked Examples

#### freeCodeCamp.org

Algorithms Course – Graph Theory Tutorial from a Google Engineer (6:44:39) => 6h!

overlay

#### Gokul Raghuraman

Planar mesh data structure that uses vertices, half-edges and faces

Subdivision Surfaces Part 1

# Woche 5

Eulerscher Polyedersatz

Freie Universität Berlin – Lecture 4 (CGAL)

# Woche 9

• Maximum Regret
• Branch-and-bound
• Branch-and-cut

https://github.com/jackspyder/2-opt, Java 2-opt solution for TSP Coursework
2-opt
Lin–Kernighan heuristic, K. Helsgaun (LKH), LK local search

#### Knoten mit gegebenen Kanten

Tiefensuche, (depth-first search, DFS)
Iterative Tiefensuche, (Iterative Tiefensuche)
Bestensuche, (best-first search)

#### Knoten ohne Kanten, resp. mit einem vollständigen Graph

Nearest neighbor search
Suchverfahren, Informierte Suche = Heuristik

# Woche 11

github.com/thiagodnf/jacof, Java Ant Colony Optimization Framework
github.com/LazoCoder/Ant-Colony-Optimization-for-the-Traveling-Salesman-Problem, A population based stochastic algorithm for solving the Traveling Salesman Problem
TSP ACO Applet
Ant Colony Optimization Tutorial
github.com/eugenp/tutorials/tree/master/algorithms-genetic

meta-heuristics
Lineare Optimierung, Simplex-Verfahren, Operations Research (Linear Programming)

# Woche 13

### C

PROJ – a generic coordinate transformation software
github.com/OSGeo/proj.4, PROJ.4 – Cartographic Projections Library
PROJ.4
Lat/long (Geodetic alias)
Mercator

### JavaFX

• Sphere
• PhongMaterial
• RotateTransition
• PointLight

### PHP

github.com/mfeldheim/hermap, Hermap libraries: stuff related to maps

# John Levine

John Levine’s Videos

• CS103: Proof by Induction
• CS103: Another Direct Proof
• CS103: Direct Proof
• CS103: Infinite Sets and Definitions
• Iterative Deepening
• Depth First Search
• Breadth First Search – Part 2
• Breadth First Search – Part 1
• A* Search
• Uniform Cost Search
• Minimax with Alpha Beta Pruning
• Monte Carlo Tree Search

# Dynamic Programming

What Is Dynamic Programming and How To Use It

# HackerRank

Algorithms

• Recursion
• Solve ‘Ice Cream Parlor’ Using Binary Search
• Binary Search
• Solve ‘Shortest Reach’ Using BFS
• Solve ‘Connected Cells’ Using DFS
• Solve ‘Recursive Staircase’ Using Recursion
• Quicksort
• Merge Sort
• Bubble Sort
• Solve ‘Coin Change’ Using Memoization and DP
• Memoization and Dynamic Programming
• Sort An Array with Comparator
• Bit Manipulation
• Graph Search, DFS and BFS
• Solve ‘Lonley Integer’ Using Bit Manipulation

Data Structures

• Balanced Parentheses in Expression
• Queue With Two Stacks
• Stacks and Queues
• Cycles in a Linked List
• Binary Search Tree
• Trees
• Solve ‘Contacts’ Using Tries
• Tries
• Heaps
• Solve ‘Find the Running Median’ Using Heaps
• Anagram Problem Solution
• Hash Tables
• Solve ‘Ransom Note’ Using Hash Tables