Introduction to Computer Science
Switch branches/tags
Clone or download
Pull request Compare This branch is even with ga-wdi-boston:master.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
bin
grunt
lib
spec
.editorconfig
.eslintrc.json
.gitignore
.remarkrc
.rspec
.rubocop.yml
.ruby-version
CONTRIBUTING.md
Gemfile
Gemfile.lock
Gruntfile.js
LICENSE
NOTES.md
README.md
Rakefile
STYLE.md
package-lock.json
package.json

README.md

General Assembly Logo

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.

Prerequisites

  • Familiarity with a high-level programming language implementing dynamic arrays.

Objectives

By the end of this, developers should be able to:

  • Define abstract data type (ADT).
  • Create stacks and queues from dynamic arrays.

Preparation

  1. Fork and clone this repository. FAQ
  2. Create a new branch, training, for your work.
  3. Checkout to the training branch.
  4. Install JavaScript dependencies with npm install.
  5. Install Ruby dependencies with bundle install.

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.

Stack

A stack implements a last in, first out data store (LIFO).

Stack diagram

Discussion: Stack

Stack operations:

  • 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:

Demonstration: Implementing a stack in JavaScript

Code along: Annotating a stack implementation in JavaScript

Lab: Implementing a stack in Ruby

Queue

A queue implements a first in, first out data store (FIFO).

Queue diagram

Discussion: Queue

Queue operations:

  • 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

Lab: Implementing a queue in JavaScript

Implementation details

Do we need empty? (or isEmpty or isempty) when implementing either ADT in a language that has a "nothing" type (nil in Ruby, undefined in JavaScript, or None in Python)? Why or why not?

How should we handle the limitations of concrete implementations of either ADT?

List

Discussion: List

List operations:

  • empty? - return false if there are any items in the list, or true if there are no items in the list
  • first - return the item at the head (left, bottom) of a list. Ex: [0,1,2,3,4,5].first() should return 0
  • 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: [0,1,2,3,4,5].rest() should return [1,2,3,4,5]
  • 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 list is ['a',1,2,3,4,5], then calling list.delete() replaces our list with [1,2,3,4,5]

Lab: Implementing a list in Ruby

In your squads, discuss implementing these operations using an array, then write a List class in Ruby.

Discussion: Fixed size lists

What if this theoretical array type only provided index based access to elements (i.e. the [] 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?

Additional Resources

License

  1. All content is licensed under a CC­BY­NC­SA 4.0 license.
  2. All software code is licensed under GNU GPLv3. For commercial use or alternative licensing, please contact legal@ga.co.