Computer Science: An Introduction
Computer science as an area of study comprises everything necessary for the design, construction, and use of computers.
What does computer science have to do with modern web development? Not much, on the surface. As application developers, we can do our job well by following best practices, guided by our experience. There will rarely be a time when you are interested in the time-complexity of a method you write. Complexity and data structures are something language designers worry about, not developers, right?
Well, no. While it is true that we don't usually care much about optimization, there are a few reasons why developers should care a bit about classic topics in introductory computer science (CS). First, classic problems allow us to practice our problem solving skills; in fact, most of our lesson today can be completed without coding. Second, being familiar with the tradeoffs inherent in choosing an algorithm or a data structure have direct parallels in choices you make writing your application code. Lastly, some of your colleagues will have CS degrees, and being able to understand the jargon and figures of speech they use will help you communicate with them. Perhaps most importantly, these colleagues will probably have a say in hiring you! Nearly every technical interview touches on these topics.
We'll focus on one area of theoretical computer science, algorithms and data structures, and begin with abstract data types.
- Familiarity with a high-level programming language implementing dynamic arrays.
By the end of this, developers should be able to:
- Define abstract data type (ADT).
- Create stacks and queues from dynamic arrays.
- Fork and clone this repository. FAQ
- Create a new branch,
training, for your work.
- Checkout to the
- Install Ruby dependencies with
Abstract data type (ADT)
An ADT is a type defined by what it does, rather than how it is implemented. Specific implementations have limitations not found in the ADT and must be able to create instances of the type.
A stack implements a last in, first out data store (LIFO).
empty?- check to see if there are any items on a stack.
push- add an item onto the top of a stack.
pop- remove and return an item from the top of a stack.
Visualizing stack implementations:
Lab: Implementing a stack in Ruby
A queue implements a first in, first out data store (FIFO).
empty?- check to see if there are any items in a queue.
enqueue- add an item to the tail of a queue.
dequeue- remove an item from the head of a queue.
Visualizing queue implementations:
Demonstration: Implementing a queue in Ruby
Code along: Annotating a queue implementation in Ruby
Do we need
isempty) when implementing either ADT in
a language that has a "nothing" type (
nil in Ruby,
None in Python)? Why or why not?
How should we handle the limitations of concrete implementations of either ADT?
falseif there are any items in the list, or
trueif there are no items in the list
first- return the item at the head (left, bottom) of a list. Ex:
rest- return the tail of a list - the list comprised of all elements except the head (the element containing the item returned by first). Ex:
prepend- insert the element at the head, or beginning, of the existing list
delete- replace a list with
rest, removing the head. Ex: if our
['a',1,2,3,4,5], then calling
list.delete()replaces our list with
Lab: Implementing a list in Ruby
In your squads, discuss implementing these operations using an array, then write
List class in Ruby.
Discussion: Fixed size lists
What if this theoretical array type only provided index based access to elements
 operator) and required explicit allocation of space for elements?
Would this change your implementation significantly? How would you handle
adding an item to a "full" array?
- Data Structure Visualizations.
- Linked List
- Basics of CS
- Teach Yourself Computer Science
- Data Structures and Algorithms
- CS Cheat Sheets
- All content is licensed under a CCBYNCSA 4.0 license.
- All software code is licensed under GNU GPLv3. For commercial use or alternative licensing, please contact email@example.com.