Lecture 1: The Role of Algorithms in Computer Science Algorithms { Informally: any well de ned computational procedure Input values Output values { A computational sequence of steps that trans-form an input into an output Algorithm describes such a transforma-tion { Tool to solve a well speci ed computational problem Sorting problem
• The Wikipedia Computer Science Portal: – Theory of computation and Automata theory – Formal languages and grammars – Chomsky hierarchy and the Complexity Zoo – Regular, context-free &Turing-decidable languages – Finite & pushdown automata; Turing machines – Computational complexity – List of data structures and algorithms
4 GRAPH ALGORITHMS 63 4 1 Breadth-first search 64 4 2 Depth-first search 70 4 3 Topological sort 75 4 4 Minimum Spanning Tree 78 4 4 1 Prim’s algorithm 82 4 5 Network Flow 83 4 5 1 Ford-Fulkerson Algorithm 84 4 6 Maximum matchings in bipartite graphs 94 4 7 Shortest Paths 97 4 7 1 Dijkstra’s algorithm 97
Algorithms 1 are methods or procedures that solve instances of problems 1 "Algorithm" is a distortion of al-Khwarizmi , a Persian mathematician Algorithms Formal De nition De nition An algorithm is a sequences of unambiguous instructions for solving a problem Algorithms must be I Finite { must eventually terminate
Genetic algorithms Genetic algorithms mimic the process of natural selection in an attempt to evolve solutions to otherwise computationally intractable problems Implementation details vary considerably, but a standard genetic algorithm includes the following steps: Initialize While true Evaluate If (termination condition) break Select
Programming and problem solving with applications • Algorithm: Data Structures and Algorithms Computational models are replacing mathematical models