An Introduction to Mathematical Computer Science

Author: Kasturi Viswanath

Price : INR.425.00 (About $10.00)

ISBN  978-81-7371-630-0

Page Extent : 304

Year : 2008

Binding : Paperback

Publisher :  Universities Press, Hyderabad, India

Copies may be ordered online from here: http://www.universitiespress.com/display.asp?categoryID=26&isbn=978-81-7371-630-0

The Book

An Introduction to Mathematical Computer Science explores an alternative approach to teaching of computer science, an approach that is independent of technology, using a methodology that simultaneously deals with both theory and practice.

The ‘mapcode’ formalism introduced here is based on classical ideas, but this book is the first to explore the possibilities of the formalism extensively to evolve the subject as an area of mathematics. Using only the algebra of sets and maps and no advanced mathematics or formal logic, the book suggests a unified point of view for understanding the structure of finite automata, Turing machines, von Neumann machines, and neural systems. It also introduces a 10-step design process for devising algorithms and verifying their termination and correctness. Recursion and sorting algorithms are examined. Data types and Boolean function theory are explained from a novel point of view. A chapter on topological algorithms relates the mapcode formalism to some tools of analysis and numerical analysis.

The book, with its several illustrative diagrams and exercises, will serve as textbook for mathematics and computer science students at both undergraduate and graduate levels.

  Table of Contents:  

Foreword by Prof. Kesav Nori

 

Preface

 

Chapter 2:  Discrete Flows

    21. The Limit Map
    2.2 Patches and Quilts
    2.3 New Maps from Old
    2.4 Knuth's Definition of an Algorithm
    2.5 Hoare Axiomatics
    2.6 Dijkstra's wp Formalism
    2.7 Undecidability
    2.8 Universality
    2.9 Exercises

Chapter 3:  Mapcode Machines

    3.1 Mapcode Machines
    3.2 Documentation
    3.3 Standard Programs and Mapcode Algorithms
    3.4 Proof Techniques
    3.5 Efficiency
    3.6 Complemantary Remarks
    3.7 Exercises

Chapter 4:  Finite Automata

    4.1 Definitions
    4.2 Examples
    4.3 Exercises

Chapter 5: Turing Machines

    5.1 Motivation
    5.2 Turing Maps
    5.3 Recognition and Acceptance of Languages
    5.4 Numerical Computations
    5.5 Exercises

Chapter 6: What is Programming?

    6.1 Formulation of the Problem
    6.2 The 10-Step Design Process
    6.3 The Dijkstra-Gries Methodology
    6.4 Method of Variation of Specificagtions
    6.5 Detecting Zero Strings
    6.6 Complementary Remarks
    6.7 Exercises

Chapter 7: Mapcode Theorems

    7.1 Maximum of Two Numbers
    7.2 Location and Value of Maximum
    7.3 Remainder and Quotient
    7.4 Integeral Part of a Square Root
    7.5 Integral Powers of Integers
    7.6 Dictionary Order of Permutations
    7.7 Greatest Common Divisor
    7.8 Egyptian Multiplication
    7.9 Radix Representation and Change of Base
    7.10 The Square Root Revisited
    7.11 Fibonacci Numbers
    7.12 Towers of Hanoi
    7.13 Exercises

Chapter 8: Recursion

    8.1 Introduction
    8.2 Recursive Computations
    8.3 Exercises

Chapter 9: Sorting Algorithms

    9.1 Bubblesort
    9.2 Subroutine for Bubblesort
    9.3 Insertion Sort
    9.4 Subroutine for Insertion Sort
    9.5 Quicksort
    9.6 Subroutine for Quicksort
    9.7 Exercises

Chapter 10: Data Types

    10.1 Representing Numbers in a Computer
    10.2 Preparation
    10.3 Unsigned Magnitude
    10.4 Addition of Bit Strings
    10.5 Addition of Non-Negative Integers
    10.6 Signed Magnitude
    10.7 Ones' Complements
    10.8 Two's Complements
    10.9 Addition of Integers
    10.10 Decimal Floating Point Representation
    10.11 Binary Floating Point Representation
    10.12 Exercises

Chapter 11: Boolean Spaces and Maps

    11.1 Boolean Algebras
    11.2 Boolean Algebras and Logic
    11.3 Boolean Polynomials
    11.4 Normal Forms
    11.5 Decoders and Multiplexers
    11.6 Exercises

Chapter 12: What is a Computer?

    12.1 A Model Computer
    12.2 Machine Language Programming
    12.3 Exercises

Chapter 13: Topological Computations

    13.1 Introduction
    13.2 Definitions and Examples
    13.3 The EDSAC Algorithms
    13.4 The Real Square Root Algorithm

Chapter 14: Neural Systems

    14.1 Learning
    14.2 Perceptrons
    14.3 Perceptron Convergence Theorems
    14.4 Hopfield Nets
    14.5 Associative Memories
    14.6 General Neural Systems
    14.7 Examples of Neural Maps
    14.8 Cybenko's Theorem
    14.9 The Central Problem
    14.10 Multilayer Perceptrons
    14.11 Hopfield Nets Revisited
    14.12 Exercises
   

Appendix A Number Representations

 

 Appendix B Arithmetic with Limited Storage

 

Bibliography/  Index

 

About the Author:

 

Kasturi Viswanath received his PhD degree from the Indian Statistical Institute, Kolkata. He worked at the University of Illinois at Urbana-Champaign and the Madurai Kamaraj University before joining the University of Hyderabad in 1978. His interest is in the theory of dynamical systems with special reference to applications in computer science.