TSM_Alg

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

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

Vier Lerntypen

Wahrnehmung
Die vier Lerntypen
Die vier Lerntypen – der auditive Lerntyp
Die vier Lerntypen – der visuelle Lerntyp
Die vier Lerntypen – der haptische Lerntyp
Die vier Lerntypen – der kommunikative Lerntyp

Erster Teil

Algorithmen 1

Algorithmen 1, Vorlesung, SS 2019, 27.07.2019
21: Übung: Ameisenalgorithmen, Vertex Cover, Nachbarschaftsmetaheuristiken, 2.07.2017

Algorithmen 2

Algorithmen 2, Vorlesung, WS2017/18, 08.02.2018
Algorithmen 2, WS 2018/19, 01.08.2019
19: Geometrische Algorithmen, Streckenschnitt, Überlappungen, 07.02.2019
20: Streckenschnitt, Konvexe Hülle, Geometrische Methoden, Übung, 12.02.2019
23: Online Algorithmen, Geometrische Algorithmen, Streckenschnitt, 26.01.2017
24: Konvexe Hüllen, Bereichssuche, Kleinste einschließende Kugel, 26.01.2017
25: Wavelet Tree, Sweepline, Linienschnitt, Geometrische Algorithmen,01.02.2017

Das Sweep-Verfahren der algorithmischen Geometrie
Closest Pair of Points | Divide and Conquer | GeeksforGeeks
Computational Geometry Lec 4 ( Sweep Line Algorithm ) ( in Arabic )
Computational Geometry – Line Sweep – 2 – Segments Intersection (Arabic)
Sweep line algorithm part 1
Sweep line algorithm part 2
Coding Math: Episode 32 – Line Intersections Part I
Coding Math: Episode 33 – Line Intersections Part II
11 2 Line Segment Intersection 546
11 1 1d Range Search 851
11 3 Kd Trees 2907
11 4 Interval Search Trees 1347

Given n line segments, find if any two segments intersect
Algorithmen und Datenstrukturen – Suchbaum (PDF)
MIT: Introduction to Algorithms – Lecture 24: Geometry (PDF)
Wikipedia – Binärer Suchbaum

Point location
Point set triangulation
Planar straight-line graph
Voronoi diagram
Voronoi-Diagramm
Delaunay triangulation
Delaunay-Triangulierung

Woche 1

time complexity

Analysis of Algorithms: Average Case Analysis
Analysis of Algorithms
Analysis of Algorithms | Set 1 (Asymptotic Analysis)
Analysis of Algorithms | Set 2 (Worst, Average and Best Cases)
ec 1 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005

Time complexity: Best and Worst cases | Quick Sort | GateAppliedcourse
Stochastik Übersicht, Wahrscheinlichkeit, beschreibende/beurteilende Statistik
Kombinatorik, Permutation mit Wiederholung, Beispiel am Wort Wetter | Mathe by Daniel Jung
Kombinatorik, Permutation, Variation, Kombination, Beispiele, Abzählverfahren | Mathe by Daniel Jung

Comparison sorts

Simple sorts

  • Insertion sort
  • Selection sort

Efficient sorts

  • Merge sort
  • Heap sort
  • Quick sort

Bubble 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

Time complexity
Zeitkomplexität
Laufzeit (Informatik)
Sortierverfahren

AVL-Baum/
B-Baum

codeadventurer.de
codeadventurer.de: Die O Notation. Wie schnell ist dein Code?
How to analyse time complexity: Count your steps
Time complexity of recursive functions [Master theorem]
Big O notation: definition and examples
Zeitkomplexität und O-Notation
Analysis of Algorithms
2.3. Big-O Notation
Problem Solving with Algorithms and Data Structures using Python

2d line intersection

Line–line intersection
How do you detect where two line segments intersect? [closed]
Line and Segment Intersections

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

JavaDoc JTS Topology Suite 1.15.0-SNAPSHOT API
github.io JTS Topology Suite
JTS Frequently Asked Questions

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

GIS Wiki: Java Topology Suite
OSGeoLive JTS Topology Suite

Wikipedia: Open Source Geospatial Foundation (OSGeo)
OSGeo – The Open Source Geospatial Foundation
OSGeo Libraries (GEOS, JTS Topology Suite)

Aufgabe 1

Array sortieren mit Java
Converting between an Array and a List in Java
A Guide to TreeSet in Java
TreeSet in Java
Binary Search Tree Complete Implementation
Binary Search Tree – Java Implementation

Convex Hull – Divide & Conquer

Convex hull algorithms
Complexity of the QuickHull Algorithm?

Convex Hull Algorithms: Divide and Conquer
Divide and Conquer algorithm to find Convex Hull
Quick Hull Algorithm to find Convex Hull

Quickhull Algorithm for Convex Hull
Convex Hull using Divide and Conquer Algorithm
Tangents between two Convex Polygons

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

Tangents to & between 2D Polygons

Woche 3

Wikipedia

Planarer Graph
Dreiecksgraph
Eulerscher Polyedersatz
Vollständiger Graph
Grad (Graphentheorie)

Line segment intersection
Bentley–Ottmann algorithm

Schleife (Graphentheorie)
Zyklus (Graphentheorie)

Dreieckszahl
Satz von Kuratowski
Satz von Wagner
Bipartiter Graph

Line Segment Intersection (LSI)

Freie Universität Berlin – Computational Geometry: Line segment intersection
The intersection of two line segments

YouTube

Mathematik (WiSe 2013/2014 und SoSe 2014) (Playlist)
Planare Graphen
Vollständige Graphen

Woche 4

Graph (Graphentheorie)
Nachbarschaft (Graphentheorie)
Isomorphie von Graphen

Kreisgraph

Planar graph
Cycle graph
Star (graph theory)
Wheel graph
Cubic graph
Ladder graph

Category:Planar graphs
Category:Triangulation (geometry)
List of graphs by edges and vertices

Doubly-connected edge list
Half-Edge-Datenstruktur

Wolfram MathWorld

Star Graph
Wheel Graph
Cubical Graph
Platonic Graph
Hypercube Graph
Halved Cube Graph

Graph

Families of Graphs (PDF)

DCEL

Freie Universität Berlin – DCEL: Eine Datenstruktur für ebene Unterteilungen (PDF)
Plane Graphs and the DCEL (PDF)
Computergeometrie (Senior)
Computergeometrie (Senior) (übersetzt!)
Index of /farshi/Teaching/CG3921/Slides
Computing the Overlay of Two Subdivisions
Geometric Algorithms (INFOGA) 2018, Block 2
Computational Geometry – Lecture 2b: Subdivision representation and map overlay
Overlay of Two Subdivisions – PowerPoint PPT Presentation

CGAL

2D Arrangements – Arrangement on Surface

Truncation (geometry)
Archimedean solid
Conway polyhedron notation

YouTube

Sarada Herke

Graph Theory: 04. Families of Graphs
Graph Theory: 07 Adjacency Matrix and Incidence Matrix
Graph Theory: 27. Hamiltonian Graphs and Problem Set
Graph Theory: 57. Planar Graphs
Graph Theory: 61. Characterization of Planar Graphs
Do Maths with Pigeons and Handshakes

Maths Resource

Planar Graphs – Worked Examples

freeCodeCamp.org

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

SDMLab

overlay

mycodeschool

Data structures
Graph Representation part 01 – Edge List
Graph Representation part 02 – Adjacency Matrix
Graph Representation part 03 – Adjacency List

Gokul Raghuraman

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

UC Davis Academics

Subdivision Surfaces Part 1

Woche 5

Eulerscher Polyedersatz

Freie Universität Berlin – Lecture 4 (CGAL)

CGAL

2D Triangulation
github.com/CGAL/cgal/tree/master/Triangulation_2/examples/Triangulation_2

Woche 6

Woche 7

Heap (Datenstruktur)
Min-Max-Heap
Vorrangwarteschlange
Stapelspeicher

14_Algorithmen&Datenstrukturen || Heap (Aufbau & Daten einfügen)
15_Algorithmen&Datenstrukturen || Heap (Daten löschen & Arraydarstellung)
Vorrangwarteschlange
Priority Queue Introduction
2.6.3 Heap – Heap Sort – Heapify – Priority Queues
Fastest Sorting Algorithm. Ever!
AlgoDat – 03: Heaps, Heapify-Funktion und Heapsort mit Beispiel und Code (C#)

Woche 8

Problem
Optimierungsproblem
Suchproblem
Heuristik
Komplexitätsklasse
Liste von Komplexitätsklassen
NP (Komplexitätsklasse)
NP-Schwere, NP-hard
P-NP-Problem
Polynomialzeit
Polynom
Laufzeit (Informatik)
Zeitkomplexität
Landau-Symbole

Single-machine scheduling, Performance measures: Tardiness, Earliness, Lateness Flowtime
Google OR-Tools: Job Shop
Sequencing and Scheduling – Johnson’s Algorithm
Job Sequencing Problem with Deadline, Greedy Algorithm
ICAPS 2015: “Iterated Local Search Heuristics for Minimizing Total Completion Time in …”
Michael Sambol Algorithms
4. Search: Depth-First, Hill Climbing, Beam (Beam Search: 35:15)
Hill Climbing – Bergsteigeralgorithmus Suchalgorithmen
beam search, search wrap up (4:30)
Solution Space Search,Beam Search
What is Beam search in artificial intelligence in hindi | lec 14 | Nauman Malik | CS607 | easy methd
mod10lec83-Beam Search (not exactly)
Beam Search Algorithm (Draft by Andrew Jungwirth)
Representing graphs
Graph and its representations
Graph Representation part 01 – Edge List
Graph representation. set, adjacency matrix and adjacency list
Data Structures using C Part 29 – Adjacency List Representation of Graph in c programming
Meta-Heuristic Optimization Techniques and Its Applications in Robotics

H.W. Lang Hochschule Flensburg

Algorithmen
Asymptotische Komplexität
Obere und untere Schranken

Approximation algorithms – Heuristic Algorithms (PDF)
Wikipedia: Approximation algorithm
Wikipedia: Algorithmus von Christofides
ApproximationAlgorithms
What does the 2 in a 2-approximation algorithm mean?

Algorithmen und Datenstrukturen
Erdős-Zahl
Bacon-Zahl

Interval Partitioning ( Greedy Algorithm ) – Algorithms
Rate Monotonic Scheduling
Sequencing Problem For More than 3 Machines|| Processing n Jobs on m Machines By JOLLY Coaching
Minimum tardiness problem
Scheduling with deadlines: minimizing lateness
Dijkstra’s Algorithm ( incl. Example and Step-By-Step Guide ) – Algorithms
Sequencing n jobs on 1 machine – Example 2
N jobs and 2 machines using Johnson’s algorithm in Hindi ( Lecture.40)
n jobs and 3 machines ( Johnson’s algorithm ) in Hindi ( Lecture.41)

Woche 9

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

Graph traversal
Tree traversal
Search tree

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

Complexity Zoo
APX
Optimierungsproblem
Kombinatorische Optimierung
Optimierung (Mathematik)
Approximationsalgorithmus
Time complexity – Polynomial time
Polynomial-time approximation scheme
List of NP-complete problems
NP-completeness
Linear programming
Dynamic programming

Knoten mit gegebenen Kanten

Breitensuche, (breadth-first search, BFS)
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 10

A Practical Introduction to Simulated Annealing
A Practical Introduction to Genetic Algorithms

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)

Quadratic Assignment Problem

Quadratic assignment problem
Quadratic Assignment Problem
Quadratic Assignment on Different Data Models
Yuehaw Khoo — Clique-Based Semidefinite Relaxation of the Quadratic Assignment Problem

Assignment Problem / Branch and Bound

Assignment Problem using Branch and Bound
Assignment problem by branch and bound method
7.3 Traveling Salesman Problem – Branch and Bound

Woche 12

Steinerbaumproblem
Santa’s Stolen Sleigh
Geographische Länge
Geographische Breite
Geographische Koordinaten, Geographische Lage
Gradnetz
Hilbert R-tree
R-Baum, R-tree
Environment for DeveLoping KDD-Applications Supported by Index-Structures (ELKI)
Closest pair of points problem
Dichtestes Punktpaar

Woche 13

github.com/OSUCartography/JMapProjLib, JMapProjLib: Java Map Projection Library
Converting longitude/latitude to X/Y coordinate
Convert latitude/longitude point to a pixels (x,y) on mercator projection
Mercator projection
Mercator-Projektion

C

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

Java OpenGL

Java OpenGL (JOGL)
Where can I find the package javax.media.opengl?

JavaFX

  • Sphere
  • PhongMaterial
  • RotateTransition
  • PointLight

Position of PerspectiveCamera in JavaFX 8
JAVA PROGRAMMING: ADD, ANIMATE, AND LIGHT UP OBJECTS IN 3D

PHP

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

R

Overview of Coordinate Reference Systems (CRS) in R (PDF)
R Spatial – Coordinate Reference Systems
Choosing the correct value for proj4string for shapefile reading in R?

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

Other Metaheuristics

Learn Particle Swarm Optimization (PSO) in 20 minutes
Artificial Bee Colony (ABC) Visualized – Artificial Intelligence
Honey Bee Optimization (HBO) Algorithm
Bat Algorithm BA

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
  • Linked Lists
  • 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

Scheduling / Project Planning / Critical Path

Scheduling projects: How to determine the critical path using activity slack calculations?
Activity slack: Total, safety and free slack definitions
Scheduling, precedence diagramming and the critical path
How to Calculate Critical Path, Float, Early Start & Late Start, and Early Finish & Late Finish
Understanding Critical Path in Project Management (Example Included)
he Ultimate Guide to the Critical Path Method

Netzplan / Kritischer Pfad

Statt Projekte mit Arbeitspaketen nun nur Abhängigkeiten zwischen Tasks in EINEM Job. Etwas anderes Problem Projektplan/Netzplan vs. Scheduling.
Netzplan | Kritischer Pfad | Beispiel | Berechnung | Produktion (2/3) | Einfach sehr gut erklärt!
Kritischer Pfad im Projektablauf

Leave a Reply

Your email address will not be published. Required fields are marked *