Computer Science: Algorithms, Complexity, and Pioneers
Classified in Computers
Written at on 
English with a size of 4.6 KB.
Algorithm Complexity
- O(1): Parity Check
- O(log n): Binary Search
- O(n): Sequential Search
- O(n log n): QuickSort
- O(n2): Bubble Sort
Computer Science Fields
Theoretical Computer Science
- Mathematical Logic
- Automata Theory
- Computability
- Computational Complexity
- Cryptography
- Combinatorial Optimization
Practical Computer Science
- Artificial Intelligence
- Computer Architecture
- Computer Graphics
- Databases
- Software Engineering
- Distributed Systems
- Computer Security
- Human-Computer Interaction
Turing Machine Elements
- Possible States
- Initial State
- Final State
- Current State
- Finite Set of Symbols
- Input Symbols
Abstract Machines
Theoretical models for analyzing computability and algorithm complexity. Includes Automata and State Machines.
Deterministic Turing Machine (DTM)
For each state, there is only one transition.
Non-Deterministic Turing Machine (NDTM)
For one or more states, there can be multiple transitions.
Complexity Classes
- Feasible: Problems solvable by DTM (O(log n)), NDTM (O(log n)), or DTM (O(nk)).
- Maybe Not Feasible: NP (Non-deterministic Polynomial Time) optimization problems, NP-Complete problems.
- Not Feasible: EXPTIME problems requiring DTM with O(2pn) time, NEXPTIME problems requiring NDTM with unlimited space.
Pioneers in Computing
- Tim Berners-Lee (1955, British): World Wide Web, HTTP protocol.
- Vint Cerf (1943, American): Father of the Internet, TCP/IP protocol.
- Bob Kahn (1938, American): Father of the Internet, TCP/IP protocol.
- James Gosling (1955, Canadian): Design and implementation of Java.
- Donald Norman (1935, American): Human-Computer Interaction, user-centered design.
- Ted Nelson (1937, American): Concepts of Hypertext & Hypermedia.
- Douglas Engelbart (1925 – 2013, American): Invented the mouse, hypertext pioneer.
- Bjarne Stroustrup (1950, Danish): Design and implementation of C++.
- James Rumbaugh (1947, American): Object-Oriented Modeling (OMT), UML.
- Alan Kay (1940, American): Object-oriented programming (Smalltalk), GUI, laptop & tablet concepts.
- Ken Thompson (1943, American): UNIX, UTF-8 code.
- Dennis Ritchie (1941 – 2011, American): C language, UNIX.
- Niklaus Wirth (1934, Swiss): Structured programming languages (PL/0, PASCAL).
- Donald D. Chamberlin (1944 – 2003, American): SQL, with Raymond Boyce.
- Edgar F. Codd (1923 – 2003, British): Databases (relational model).
- Donald Knuth (1938, American): Algorithm Analysis, The Art of Computer Programming, data structures.
- Edsger W. Dijkstra (1930 – 2002, Dutch): Structured programming, recursion (ALGOL 60).
- John McCarthy (1927 – 2011, American): Artificial Intelligence, functional programming (LISP), trees (data structures).
- Seymour Cray (1925 – 1996, American): Design of Supercomputers, parallel computing.
- Peter Naur (1928, Danish): Programming language syntax description, first language with programming structures (ALGOL), fundamentals of software engineering.
- John Backus (1924 – 2007, American): First widely used programming language (FORTRAN), formal notation for defining programming languages.
- Noam Chomsky (1928, American): Formal Languages, formal grammars, political activist.
- Claude Shannon (1916 - 2001, American): Information Theory, game theory, digital circuits design.
- John Vincent Atanasoff (1903 - 1995, American): First electronic digital computer (ABC).
- Konrad Zuse (1910 - 1995, German): First electromechanical programmable computer.
- John von Neumann (1903 – 1957, Hungarian): Digital computer architecture, merge sort.
- Norbert Wiener (1894 - 1964, American): Electronic control, fundamentals of robotics, cybernetics.