CS 171 - Introduction to Computer Science II

Important Resources


To access the server when not on the Oxford College campus, you will need to setup VPN access

Tentative Schedule

DatesWeekRead / UnderstandLabs / Related Code
Aug 23-
Aug 25
1 Syllabus
Read Section 1.2

Review of Java (as necessary)

Postfix Expressions
Evaluating Infix Expressions
Delimiter Matching
Make sure you have access to requisite software

Applications of Stacks:
    PostFixEvaluator.java
    FullyParenthesizedInfixEvaluator.java
    DelimiterChecker.java
Aug 28-
Sep 1
2 Read Section 1.3

Abstract Data Types

Stacks
Generics & Type Parameters
Autoboxing & Auto-unboxing
Iterating over Collections
Resizing Arrays

The Shunting Yard Algorithm

Lab 01 - Infix to Prefix
due Sept 5, 11:59pm


The Command Line
(for those not coming from CS 170)

How to Submit Labs

StackOfStrings.java
(quick & dirty, fixed capacity, array-based)

Stack.java (interface)
    StackArray.java

ShuntingYard.java
Sep 4-
Sep 8
3 Monday, Sept 4th - LABOR DAY HOLIDAY

Read Section 1.4

Queues, Priority Queues, and Bags
Linked Lists
Garbage Collection

The N-Queens Problem & Backtracking

Running Time Experiments
Algorithm Analysis - Avg vs. Worst Case and Misleading Averages
Lab 02 - N-Queens Problem
due Sept 14, 11:59pm

Queue.java (interface)
    QueueArray.java
    QueueList.java

Bag.java (interface)
    BagArray.java

LinkedList.java
StackList.java

Deque.java (interface)
    DequeList.java
    (a double-ended queue, doubly-linked)

Applications of Queues: Josephus.java
Sep 11-
Sep 15
4 Read Section 2.1

Analysis of Algorithms
Sorting - First Thoughts
The Comparable interface
Bubble Sort
Selection Sort
Insertion Sort

Loop Analysis
Big O Notation and Growth Rates
Analysis of linear search
Analysis of binary search
Rectangle.java
(implements Comparable)

Sep 18-
Sep 22
5 Read Sections 2.2, 2.3

Merge Sort and Analysis
Quicksort
Quick Sort Analysis
Comparing Sorting Algorithms

Test 1 (Friday)
Lab 03 - Comparing Sorting Methods
due Sept 28, 11:59pm

MergeSorter.java
QuickSorter.java

ArraySorter.java
ArraySearcher.java

Review A1
Review A2
Sep 25-
Sep 29
6 Read Sections 2.4, 3.2

Binary Search Trees
Operations on Binary Search Trees

Tree Traversals (in/pre/post-order)
Infix, prefix, and postfix expressions

BST.java
Oct 2-
Oct 6
7 More on Trees (min, max, rank, select)
Hibbard Deletion

BST/Quicksort Partition Connection

Heaps and heapsort
Lab 04 - Searching the IMDB Dataset
due Oct 17, 11:59pm

PriorityQueueHeap.java
Oct 9-
Oct 13
8 Monday Oct 9 - FALL BREAK

Read Section 3.3

Balanced Search Trees
2-3 Trees
Red-Black Trees (height, insertions, rotations)
Review B1
Review B2

Quick Sort Trace
Merge Sort Trace
Heap Sort Trace
Binary Search Tree Trace
Red Black Tree Trace

RedBlackBST.java
Oct 16-
Oct 20
9 Read Section 3.4

Hashing, Hash Codes
Collision Handling, Separate Chaining, Linear Probing

Rock Eagle
Chain.java
HashTableChained.java
HashTableLinearProbe.java

Lab 05 - Implementing 2-3 Trees
due Nov 3, 11:59pm
Oct 23-
Oct 27
10 Read Section 4.1

Test 2

Graphs
Web Search Engines
Representing Graphs
Six Degrees of Separation
Examples of Digraph Applications

Read Section 4.2

Graph.java
Oct 30-
Nov 3
11 Read Sections 4.3, 4.4

Traversing Graphs
Connected Components
DepthFirstTraversal.java
BreadthFirstTraversal.java
ConnectedComponents.java
DepthFirstPaths
BreadthFirstPaths
Nov 6-
Nov 10
12 Dijkstra's Shortest Path Algorithm
Team Project - FaceSpace

Digraph.java
Edge.java
WeightedGraph.java
TinyEWG.txt
DirectedEdge.java
WeightedDigraph.java
TinyEWDG.txt
IndexMinPQ.java
MinPQ.java
DijkstraShortestPaths.java
LazyPrimMST.java
Nov 13-
Nov 17
13 Some Results From Graph Theory
Prim's Algorithm

If time allows, one of:
    Design Patterns
    Back Propagating Neural Networks
    Functional Programming
The Observer Pattern:
CoolEvent.java
CoolEventListener.java
FirstOnTheSceneListener.java
GossipyListener.java
ConfusedListener.java
Publicizer.java
WorkThePublicizer.java

The Singleton Pattern:
Conductor.java
Drummer.java
Band.java

Nov 20-
Nov 24
14 Nov 22 - 24 - THANKSGIVING BREAK The Visitor Pattern:
Book.java
Visitable.java
Visitor.java
PostageVisitor.java
ShoppingCart

The Simple Factory Pattern:
Dog.java
GoldenRetriever.java
Poodle.java
Rottweiler.java
DogFactory.java
DogFun.java

The Strategy Pattern:
Behavior.java
ConfidentBehavior.java
WimpyBehavior.java
Spaceship.java
SpaceshipFun.java
Nov 27-
Dec 1
15 The A* Algorithm

EVALUATIONS

Review for Test 3

Test 3

AStarPathFinder.java

Hash Table (Separate Chaining) Trace
Hash Table (Linear Probing) Trace
Breadth-First Paths Trace
Depth-First Paths Trace
Dijkstra Shortest Paths Trace
Prim's MST (Lazy Version) Trace
A* Algorithm Trace

Review C
Dec 4 16 Review for Final Exam