CS 112 - Introduction to CS II - Summer I, 2017

[Weekly Schedule | Lecture Schedule ]


Staff Contact Information


Wayne Snyder
     Email: waysnyder@gmail.com

     Office: MCS 290
     Office Hours: TBA

     Cell Phone: 617 - 966 - (210 + 41) (email vastly preferred)

Curriculum Assistants: Femke Hermse, Dayuan Wang



Lecture Schedule

Back to Top

Lecture Topic
Readings (Java = "Java in a Nutshell")
Lecture Slides and Code Examples
Homeworks and Tests
T 5/23

Overview of Course & Course Policies; Motivational Lecture: Two algorithms for searching an array---algorithm, implementation, analysis, and experiments; Introduction to Java: compiled languages (Java) vs interpreted languages (Python);


Motivational Lecture: PDF

Java I: PDF

W 5/24

Java continued: Types, operators, and expressions. Java statements, conditionals, and loops; break and continue;

Java arrays

Read Chapter 2 of Java up through while, for, break, and continue;


At LearningJavaOnline: go through exercises for

  • Hello World
  • Variables and Types
  • Conditionals
  • Loops

Or do both!

We will finish the Introduction to Java, and then cover:

Java II: PDF


HW 1 Part A Solution: HTML

Lab 1: HTML
R 5/25 Java concluded: Methods and fields and the structure of basic Java programs. Scope of local variables, fields, and methods;


Please read about methods in the Java text; please read about the difference between local and instance variables here: HTML

For scope of declarations, take a look at this set of notes: HTML





Java IV: PDF


Part A Solution: HTML

4 T 5/30

Breaking a Java program into separate classes and separate files; more on scope (public vs private); static vs non-static members.



Read "Classes and Objects," "Packages and the Java Namespace," and "Java File Structure" in the Java text.


Java V: PDF

Summary of Java Program Structures: PDF

5 W 5/31

Analysis of algorithms, "Big Oh" notation, experimental verification by timing analysis;

Interative sorting algorithms: Selection sort, Insertion sort

Complexity analysis of iterative sorts;




Here is a good Youtube tutorial on Selection Sort;

Here is a good one on Insertion Sort.

There are 1000's of Youtube lectures on sorting algorithms: here is a creepy visualization of Insertion Sort, and here is a downright strange visualization of Insertion sort.

Here is a nice Youtube mini-lecture on sorting, with associated lectures on all the major sorting algorithms.

LectureA:PDF LectureB: PDF


Part A Solution: HTML

Lab 2: HTML
6 R 6/1

Recursive Sorting Algorithms: Mergesort and Quicksort;

Complexity Analysis of Recursive Sorts



Lecture: PDF


7 F 6/2

OOD and Abstract Data Types; Stacks and Queues

Reference types; Array Resizing

Queues implemented as Ring Buffers

Read the section on Reference Types (pp.74-81) CAREFULLY in the Java Text.

Lecture: PDF

8 M 6/5 Deques and Priority Queues; Read the first half of the Wiki Article on Circular Buffers ("How it works" and look at the animated gif).      
9 T 6/6 Interfaces, Subclassing and Inheritances, and Abstract Classes

Interfaces (this starts at p.117 in the Java book pdf available online)

Subclassing and Inheritance (starts at p.111)

Abstract classes (p.115)


10 W 6/7

Linked Lists

Stacks and Queues with LLs.


Here is a very short, clear tutorial on Linked Lists: YouTube There are a number of such tutorials on YouTube, so look around a bit for others if you wish!

You might want to check out the classic Binky Pointer Fun video on YT, but bear in mind it is written for a different language (C or C++).


Lecture: PDF


Solution: HTML

Lab 3: HTML
11 R 6/8


Basics of List Processing: Iterative Algorithms;


Notes on Iterative LL Algorithms


Used the board!    
12 M 6/12 Iterative LL algorithms; Recursion and the run-time stack.

 Notes on Iterative LL Algorithms

Used the board!    
13 T 6/13 Recursive algorithms on LLs;


Notes on Recursion and LLs

Used the board!    
14 W 6/14 Recursive algorithms on LLs; Doubly-linked lists, multi-lists.

Notes on Recursion and LLs

Used the board!   Lab 4: HTML

R 6/15


 Midterm Solution: PDF


HW 05: HTML (due Wednesday, 6/21)

New Dictionary Interface: JAVA

New Main Method for Testing: TXT

16 M 6/19

Java Iterators;

Binary Trees, Binary Search Trees; Searching, Insertion, and Deletion in BSTs.




Professor Attarwalas: Lectures: PDF1, PDF2


Here is the Java Tutorial Page on Iterators: HTML

Also, look at this tutorial on Java Iterators: HTML

Here is an example of a simple iterator for an array-based data structure: JAVA

Here is an example of a simple exception: JAVA

17 T 6/20 Recursive tree traversals; Iterative tree traversals using an explicit stack



Please read the following WikiP article on Tree Traversals: HTML and follow the link to read about breadth first search.

Lectures on Binary Search Trees: PDF1, PDF2    
18 W 6/21 2-3 Trees; B-Trees and external data structures


Here is a good explanation of 2-3 Tree Insertions: YT

Here is a good animation you can play with to verify your understanding: HTML


Lecture: PDF   Lab 5:HTML
19 R 6/22 The (nearly) Perfect Data Structure; Perfect Hashing, Hash Functions; Hash Tables with Separate Chaining



Used the board!


Solution A: HTML

Solution B.2: JAVA

20 M 6/26

Performance of Hash Functions; Linear Probing; Performance of Hash Tables


Here is a Java implementation of a linear probing HT: JAVA Used the board!


21 T 6/27

Resizing a hash table in linear time

Array representation of binary trees; Binary Heaps,

Here is a nice YT video about heaps: HTML

Here is a Java implementation: JAVA

22 W 6/28 Conclusions and course evals.        
23 R 6/29 Final Exam    



Back to Top