Skip to content

advanced_algorithms_in_java.md

Latest commit

 

History

History
126 lines (115 loc) · 4.83 KB

advanced_algorithms_in_java.md

File metadata and controls

126 lines (115 loc) · 4.83 KB
Raw

Advanced Algorithms in Java

Introduction

Introduction

  1. About the course:
    1. Complexity theory:
      1. Big Oh, Big Omega, Big Theta notations
    2. Breadth-first search
      1. Web crawling (Google search)
    3. Depth-first search
    4. Shortest path algorithms (GPS, Routing, Forex market)
      1. Dijkstras algorithm
      2. Bellman-Ford algorithm
    5. Minimum spanning trees
    6. Strongly connected components (Reco systems (next video with high probability, facebook friends, ...)
    7. Maximum flow problem (matching)
    8. Travelling salesman problem + heuristics (complex - approx polynomial time)
      1. Simulated annealing
      2. Genetic algorithms

Graph Theory Introduction

  1. Graphs
    1. G(V,E) are mathematical structures to model pairwise relations between given objects
    2. A graph is made up of vertices/nodes and edges
    3. There are two types of graphs: directed and un-directed graphs
  2. How to model graphs in programming languages?
    1. Two options
      1. Adjacency matrices
        1. Matrix A constructed out of vertices of graph
          1. the A(i,j) value in matrix is 1 if
            1. there is a connection between node i and node j
          2. Otherwise
            1. A(i,j) is 0
      2. Edge list representation

Breadth-First Search

Breadth-first search introduction

BFS implementation

BFS - WebCrawler (core of search engines)

BFS - WebCrawler implementation

Depth-First Search

Depth-first search introduction

DFS implementation I - with stack

DFS implementation II - with recursion

Topological ordering introduction

Topological ordering implementation I

Topological ordering implementation II

Cycle detection introduction

Cycle detection implementation I

Cycle detection implementation II

Maze solving algorithm implementation

Memory management: BFS vs DFS

Shortest Path Algorithms

Dijkstra algorithm introduction - basics

Dijkstra algorithm introduction - algorithm

Dijkstra algorithm introduction - example

Bellman-Ford algorithm introduction

Dijkstra algorithm introduction - with adjacency matrix

Shortest path algorithms applications

Dijsktra algorithm implementation I

Dijsktra algorithm implementation II

Bellman-Ford algorithm implementation I

Bellman-Ford algorithm implementation II

DAG shortest path implementation

Arbitrage situations on FOREX introduction

Arbitrage situations on FOREX implementation

Longest path implementation

Spanning Trees

Union-find data structure (disjoint sets)

Union-find data structure illustration

Spanning trees introduction - Kruskal algorithm

Kruskal algorithm implementation I

Kruskal algorithm implementation II

Spanning tree introduction - lazy Prim's algorithm

Prims lazy algorithm implementation I

Prims lazy algorithm implementation II - the core

Spanning trees introduction - eager Prim's algorithm

Eager Prim's algorithm implementation

Applications of spanning trees

Strongly Connected Components

Strongly connected components introduction

Kosaraju algorithm introduction

Kosaraju implementation I - the Graph class

Kosaraju implementation II

Kosaraju algorithm implementation III - test

Tarjan algorithm introduction

Tarjan implementation I

Tarjan implementation II - test

Applications of strongly connected components

Maximum Flow Problem

Maximum flow introduction - basics

Maximum flow introduction - properties

Maximum flow introduction - cuts

Maximum flow introduction - residual networks

Maximum flow introduction - Ford-Fulkerson algorithm

Maximum flow introduction - example

Maximum flow introduction - applications

Maximum flow implementation I - Edge, Vertex

Maximum flow implementation II - FlowNetwork class

Maximum flow implementation III - Ford-Fulkerson algorithm

Maximum flow implementation IV - augmentation

Maximum flow implementation V - testing

Bipartite matching problem introduction

Bipartite matching implementation

Travelling Salesman Problem (TSP)

Travelling salesman problem introduction

TSP implementation with simulated annealing I - city

TSP implementation with simulated annealing II - tour

TSP implementation with simulated annealing III - algorithm

TSP implementation with simulated annealing IV - testing

Tabu search introduction

Tabu search introduction

Euler cycle - Chinese Postman Problem

Euler's cycles introduction

Course Materials (DOWNLOADS)

Course materials

BONUS

DISCOUNT FOR OTHER COURSES!