Computer Science encompasses theoretical and practical approaches to computation. It’s been said that the four essential subdisciplines are:
|Knowledge Area||Code||Some Topics|
|Algorithms and Complexity||AL||Algorithmic Analysis; Algorithmic Strategies; Data Structures and Algorithms; Automata; Computability; Computational Complexity.|
|Architecture and Organization||AR||Digital Logic and Digital Systems; Machine-level Data Representation; Assembly-Level Machine Organization; Memory System Organization and Architecture; Interfacing and Communication; Functional Organization; Multiprocessing and Alternative Architectures; Performance Enhancements.|
|Computational Science||CN||Modeling and Simulation; Processing; Interactive Visualization; Data, Information and Knowledge; Numeric Analysis; Symbolic Computation; Mathematical Modeling; High-Performance Computing.|
|Discrete Structures||DS||Logic; Sets, Relations, and Functions; Proof Techniques; Basics of Counting; Graphs and Trees; Discrete Probability.|
|Graphics and Visualization||GV||Media Applications; Digitization; Color Models; Rendering; Modeling; Animation; Visualization.|
|Human-Computer Interaction||HCI||Interactive Systems; Testing; Collaboration and Communication; Statistical Methods; Human Factors; Mixed, Augmented, and Virtual Reality.|
|Information Assurance and Security||IAS||Defensive Programming; Threats and Attacks; Network Security; Cryptography; Web Security; Platform Security; Policy and Governance; Digital Forensics; Secure Software Engineering.|
|Information Management||IM||Database Systems; Data Modeling; Indexing; Key-Value, Document, Relational, and Graph Databases; Query Languages; Transaction Processing; Distributed Databases; Physical Database Design; Data Mining; Information Storage and Retrieval; Multimedia Systems.|
|Intelligent Systems||IS||Knowledge Representation and Reasoning; Search; Machine Learning; Reasoning Under Uncertainty; Agents; Natural Langauge Processing; Robotics; Speech Recognition and Synthesis; Perception and Computer Vision.|
|Networking and Communication||NC||Networked Applications; Reliable Data Delivery; Routing and Forwarding; Local and Wide Area Networks; Reource Allocation; Mobility; Social Networking.|
|Operating Systems||OS||Operating System Organization; Concurrency; Scheduling and Dispatch; Memory Management; Security and Protection; Virtual Machines; Device Management; File Systems; Realtime and Embedded Systems; Fault Tolerance; System Performance and Evaluation.|
|Platform-Based Development||PBD||Web Platforms; Mobile Platforms; Industrial Platforms; game Platforms.|
|Parallel and Distributed Computing||PD||Parallel Decomposition; Communication and Coordination; Parallel Algorithms, Analysis, and Programming; Parallel Architecture; Parallel Performance; Distributed Systems; Cloud Computing; Formal Models and Semantics.|
|Programming Languages||PL||Object Oriented Programming; Functional Programming; Event-Driven and Reactive Programming; Type Systems; Program Representation; Language Translation and Execution; Syntax Analysis; Semantic Analysis; Code Generation; Runtime Systems; Static Analysis; Concurrency and Parallelism; Type Systems; Formal Semantics; Language Pragmatics; Logic Programming.|
|Software Development Fundamentals||SDF||Algorithms and Design; Fundamental Programming Concepts; Fundamental Data Structures; Development Methods.|
|Software Engineering||SE||Software Processes; Project Management; Tools and Environments; Requirements Engineering; Software Design; Software Construction; Software Verification and Validation; Software Evolution; Software Reliability; Formal Methods.|
|Systems Fundamentals||SF||Computational Paradigms; Cross-Layer Communications; State and State Machines; Parallelism; Evaluation; Resource Allocation and Scheduling; Proximity; Virtualization and Isolation; Reliability through Redundancy; Quantitative Evaluation.|
|Social Issues and Professional Practice||SP||Social Context; Analytic Tools; Professional Ethics; Intellectual Property; Privacy and Civil Liberties; Professional Communication; Sustainability; History; Economics of Computing; Security Policies, Law, and Crime.|
We can’t really separate data structures and algorithms because:
While it’s possible to study algorithms and data structures exclusively at a theoretical level, we often study them together with introductory software engineering concepts; the major topics, grouping them roughly as follows:
During the design of a system, before the algorithms are written and before the data structures are sketched out, we must first identify the kinds of objects we need and how they should behave.
Some terminology would be nice here. Surprisingly, not everyone agrees on official terminology. I’ll try my hand and it: A type is a collection of values, for example:
A data type is a type together with operations. Operations specify the things you can do to the values of the type. We can draw what the types and operations are, for example:
The same thing can be said without pictures, for example:
CLUBS : Suit TEN : Rank HEARTS : Suit JACK : Rank DIAMONDS : Suit QUEEN : Rank SPADES : Suit KING : Rank ACE : Rank makeCard : Suit × Rank → Card TWO : Rank getSuit : Card → Suit THREE : Rank getRank : Card → Rank FOUR : Rank newDeck : Deck FIVE : Rank positionOf : Deck × Card → int SIX : Rank cardAt : Deck × int → Card SEVEN : Rank topCard : Deck → Card EIGHT : Rank shuffle : Deck → Deck NINE : Rank split : Deck → Deck
The operations need to be specified in more detail than the pictures show, but it should give you the basic idea.
You will sometimes hear the term abstract data type (ADT). People use this term to emphasize the fact that the “internal structure and internal workings of the operations” are somehow unknown to the outside world. Only the effects of the operations matter. To me, anyway, saying data type is enough; all datatypes are “abstract” in that sense.
A collection is a group of elements treated a single object. Collection types can be:
The latter classification looks like this:
|Unrelated items, such as people in a class or a hand of cards.|
|One-to-one relationship, as in a printer queue, ring LAN, or a line at the deli.|
|One-to-many relationship, as in a family tree, organization chart, expression tree, or folders and files in a file system.|
|Many-to-many relationship, as in a road map, schedule, belief network, or communication net.|
Operations common to most collections include:
A data structure is an arrangement of data for the purpose of being able to store and retrieve information. Usually a data structure is some physical representation of an ADT.
Data structures are built with
The data structure chosen for a data type must meet the resource constraints of the problem. Figure out the constraints before you start coding!
These are the extremely important questions you must ask to determine acceptable tradeoffs:
We design algorithms to carry out the desired behavior of a software system. Good programmers tend to use stepwise refinement when developing algorithms, and understand the tradeoffs between different algorithms for the same problem.
There are several classification schemes for algorithms:
This classification has proved useful:
|Decision||Given $f$ and $x$, is it true that $f(x)$?|
|Functional||Given $f$ and $x$, find $f(x)$|
|Constraint||Given $f$ and $y$, find an $x$ such that $f(x)=y$|
|Optimization||Given $f$, find the $x$ such that $f(x)$ is less than or equal to $f(y)$ for all $y$.|
Choosing the right algorithm is both