Lecture Notes for CS 512, Algorithm Design

2 September 1999

1. Introduction

   1. What are algorithms?

      1. Like recipies

         1. individual, collected - eggs, dinner; sorting, payroll.

         2. grouped into classes - desserts, main course; graph, spell checking.

   2. Issues

      1. Suitability - is the algorithm apropriate?

      2. Expense - time, space costs.

      3. Correctness - does the algorithm work?

   3. How algorithms come to be.

      1. Design - many techniques; induction.

      2. Analysis - paper and pencil analysis.

      3. Implementation - sometimes followed by more analysis (measurement).

   4. Preliminaries.

      1. Notation - pseudo-code; if, then, arrows.

      2. Complexity - big-oh notation.

2. Graph algorithms.

   1. Graphs.

      1. What is a graph?

         1. A set of nodes or vertices.

         2. A set of edges or arcs between nodes.

         3. Directed or undirected edges (graphs).

      2. Widely used as models - nodes represent things, edges represent relations between things; road maps, work-flow diagrams.

   2. Graph algorithms.

      1. Given a graph, find a subgraph - tsp, shortest path.

      2. Given a bunch of nodes and a relation for arcs, draw a graph satisfying some properties - resource allocation, scheduling

   3. Eulerian graphs (Euler paths)

      1. The seven bridges of Koingsberg - an edge traversal problem.

This page last modified on 7 September 1999.