Computer Science

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Philo Vivero (talk | contribs) at 12:33, 30 July 2001 (Discovered duplicate work -- computation). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

This page appears to cover the same subject matter as Computation.


Computer Science is a field of mathematics dealing with the capabilities and limitations of computing devices. I will describe the training I got from the University of Kansas, where it was considered a purely mathematical field.


Initially, you learn discrete mathematics and probability. Concepts you learn are combinations, permutations, proofs, and Boolean math.


Then you move into theory of computing. Early concepts are finite deterministic automata (acceptors), and grammars.


Finite automata are simple state machines which have a certain power to recognise an input and compute a useful output. Further study shows that non-deterministic automata have no more power than deterministic automata in solving problems.


Later, it is shown that grammars (also called generators) can generate sequences of strings that finite automata cannot recognise, and thus are more powerful computing constructs.


Eventually, it is shown that the Turing Machine can solve problems of infinite complexity. A modern computer is a finite version of a Turing Machine and cannot solve problems of infinite complexity.


In the advanced areas of Computer Science, algorithms are analysed for their ability to solve problems of a known complexity in a certain amount of time. For example, it is known that sorting a list of N items is a problem of N2 complexity (in Big O notation, it is said that the problem is O(n2). However, it is possible using clever algorithms to bring the Average Case Complexity of a problem down. The Quick Sort sorting algorithm is known to have an average case of O(n * logn) even though the algorithm is O(n2).


The average case analysis of the Quick Sort is actually quite complex math, and students are required to work through the average case analysis for advanced algorithms classes.


Some other Computer Science concepts which should be written on:


  • Polynomial time algorithms
  • NP-Complete problems
  • NP-Hard (??? is that the term?) problems
  • Showing an algorithm as equivalent to a known NP-Complete problem



Retrieved from "https://en.wikipedia.org/w/index.php?title=Computer_Science&oldid=242719"