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
Lab 05 - Implementing 2-3 Trees
due Oct 31, 11:59pm
Oct 23-
Oct 27
10 Read Section 4.1

Test 2

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

Path Finding: Depth-/Breadth First Search
Solving mazes with Deques
Connectivity Queries
Read Section 4.2

Graph.java
ConnectedComponents.java
Digraph.java
Edge.java
DirectedEdge.java
DirectedWeightedEdge.java
WeightedGraph.java
EdgeWeightedDirectedGraph.java
TinyEWG.txt
TinyEWDG.txt
Oct 30-
Nov 3
11 Read Sections 4.3, 4.4

Dijkstra's Shortest Path Algorithm
The A* Algorithm
Some Results From Graph Theory
Prim's Algorithm

Graphs - Coloring and Planarity
DijkstraShortestPaths.java
LazyPrimMST.java
Nov 6-
Nov 10
12 If time allows, one of:
    Back Propagating Neural Networks
    Design Patterns
    Functional Programming
Network.java
TestNeuralNetwork.java
Nov 13-
Nov 17
13
Nov 20-
Nov 24
14 Nov 22 - 24 - THANKSGIVING BREAK
Nov 27-
Dec 1
15 EVALUATIONS

Review for Test 3

Test 3

Dec 4 16 Review for Final Exam