# Portal:Computer science

﻿
Portal:Computer science
• Wikipedia portals:
• Culture
• Geography
• Health
• History
• Mathematics
• Natural sciences
• People
• Philosophy
• Religion
• Society
• Technology

This portal is for the academic discipline of computing science. For other related portals such as computer networking, computer security and information technology, please see portals: technology and applied sciences.

## The Computing Science Portal

Computing science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. Computing science encompasses many branches; some emphasize the computation of specific results (such as computer graphics), while others (such as computational complexity theory) relate to properties of computational problems. Still others focus on the challenges in implementing computations. For example, programming language theory studies approaches to describing a computation, while computer programming applies specific programming languages to craft a solution to some concrete computational problems.

## Selected article

An example of a red-black tree
A red-black tree is a type of self-balancing binary search tree, a data structure used in computing science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer: who called them "symmetric binary B-trees", but acquired its modern name in a paper in 1978 by Leonidas J. Guibas and Robert Sedgewick. It is complex, but has good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is total number of elements in the tree. Put very simply, a red-black tree is a binary search tree which inserts and removes intelligently, to ensure the tree is reasonably balanced.

A red-black tree is a binary search tree where each node has a color attribute, the value of which is either red or black. In addition to the ordinary requirements imposed on binary search trees, the following additional requirements apply to red-black trees:

1. A node is either red or black.
2. The root is black. (This rule is used in some definitions and not others. Since the root can always be changed from red to black but not necessarily vice-versa this rule has little effect on analysis.)
3. All leaves are black.
4. Both children of every red node are black.
5. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

These constraints enforce a critical property of red-black trees: that the longest path from the root to any leaf is no more than twice as long as the shortest path from the root to any other leaf in that tree. The result is that the tree is roughly balanced. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red-black trees to be efficient in the worst-case, unlike ordinary binary search trees.

## Selected picture

A partial map of the Internet, rendered based on ping delay and colored based on TLD.

## Selected biography

Frances Elizabeth "Fran" Allen (born 1932) is an American computing scientist and pioneer in the field of optimizing compilers. Her achievements include seminal work in compilers, code optimization, and parallelization. She also had a role in intelligence work on programming languages and security codes for the National Security Agency.

Allen is a fellow of the IEEE, the Association for Computing Machinery (ACM) and the Computer History Museum. She is currently on the Computer Science and Telecommunications Board, the Computer Research Associates (CRA) board and National Science Foundation's CISE Advisory Board. She is a member of the National Academy of Engineering, the American Academy of Arts and Sciences and the American Philosophical Society.

In 1997, Allen was inducted into the WITI Hall of Fame. She retired from IBM in 2002 and won the Augusta Ada Lovelace Award that year from the Association for Women in Computing.

In 2007 Allen was recognized for her work in high performance computing when she received the A.M. Turing Award for 2006. She became the first woman recipient in the forty year history of the award which is considered the Nobel Prize for computing and is given by the Association for Computing Machinery. In interviews following the award she hoped it would give more "opportunities for women in science, computing and engineering". In 2009 she was awarded an honorary doctor of science degree from McGill university for "pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel execution".

More about Fran Allen...

## Computer science topics

Taxonomic classification ACM Computing Classification System Binary search | Brute-force search | Divide and conquer | Dynamic programming | Greedy | Recursive descent | Regular expressions Relational databases | Spreadsheets | OLAP | Text editors | Word processors | Integrated Development Environments | Search engines | Numerical integration | Computational linguistics Distributed computing | Parallel computing | Real-time computing | Quantum computer | DNA computing Central processing unit | Computer architecture | CPU cache | Computer storage | History of computing hardware Windows NT group | BeOS | BSD | Haiku | Lisp machine | Linux kernel | Unix | OpenVMS HTML | XML | MediaWiki | SQL | MDX AppleScript | DCL | JavaScript | JCL | PHP | TECO | Unix shell (Csh) | Windows PowerShell Ada | ALGOL | BASIC | C | C++ | C# | Erlang | Forth | Fortran | Haskell | Java | JavaScript | Lisp | Objective-C | Perl | PHP | PL/I | Prolog | Python | Ruby | Scala | Scheme Functional programming | Imperative programming | Literate programming | Logic programming | Object-oriented programming | Structured programming Ackermann function | Automata theory | Computational complexity theory Kent Beck | Ward Cunningham | Edsger Dijkstra | Jean Ichbiah | Gary Kildall | Donald Knuth | Marvin Minsky | Alan Turing | Niklaus Wirth Artificial intelligence | Bioinformatics | Computational linguistics | Computer graphics | Computer networking | History of computer science

## Related WikiProjects

• C++
• Computational biology
• Computer science
• Computer vision
• Computing
• Cryptography
• Databases
• Java
• Logic
• Mathematics
• Software

## Things you can do

• Copyedit: Computing
• Expand: Computer science, Computer science stubs, Computer science articles needing expert attention
• Create new articles - Requested articles

## Associated Wikimedia

 Computer science on Wikibooks Computer science on Wikimedia Commons Computer science on Wikinews Computer science on Wikiquote Computer science on Wikisource Computer science on Wikiversity Computer science on Wiktionary Manuals and books Images and media News Quotations Texts Learning resources Definitions
Directory of pages for Portal:Computing_science
What are portals· List of portals · Featured portals

Purge server cache

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Computer science — or computing science (abbreviated CS) is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems. Computer scientists invent algorithmic… …   Wikipedia

• Computer Science and Engineering — is the discipline formed by the union of Computer Science and Computer Engineering.It is an ABET accredited major [ [http://www.seasoasa.ucla.edu/curric05 06.html/HTML/compsci.html#marker 1005090 UCLA CS E Curriculum] Accessed August 14 2006]… …   Wikipedia

• Computer Science — Informatik ist die Wissenschaft von der systematischen Verarbeitung von Informationen, insbesondere der automatischen Verarbeitung mit Hilfe von Rechenanlagen. Historisch hat sich die Informatik als Wissenschaft aus der Mathematik entwickelt,… …   Deutsch Wikipedia

• Kernel (computer science) — In computer science, the kernel is the central component of most computer operating systems (OS). Its responsibilities include managing the system s resources (the communication between hardware and software components). As a basic component of… …   Wikipedia

• Object (computer science) — In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure. (With the later introduction of object oriented programming the same word,… …   Wikipedia

• Generator (computer science) — In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates …   Wikipedia

• Consensus (computer science) — Consensus is a problem in distributed computing that encapsulates the task of group agreement in the presence of faults.[1] In particular, any process in the group may fail at any time. Consensus is fundamental to core techniques in fault… …   Wikipedia

• Outline of computer science — The following outline is provided as an overview of and topical guide to computer science: Computer science (also called computing science) – study of the theoretical foundations of information and computation and their implementation and… …   Wikipedia

• McGill University School of Computer Science — The School of Computer Science is a School in the Faculty of Science at McGill University located in the McConnell Engineering Building at 3480 University, Montreal. The school is the second most funded computer science department in Canada[1].… …   Wikipedia

• Dalhousie Faculty of Computer Science — Coordinates: 44°38′17″N 63°35′13″W﻿ / ﻿44.63806°N 63.58694°W﻿ / 44.63806; 63.58694 …   Wikipedia