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


[Weekly Schedule | Lecture Schedule ]


Resources

Staff Contact Information

Instructor

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
Date
Lecture Topic
Readings (Java = "Java in a Nutshell")
Lecture Slides and Code Examples
Homeworks and Tests
Labs
1
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);

Syllabus

Motivational Lecture: PDF

Java I: PDF

   
2
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;

OR:

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

HW 1 Part A Solution: HTML

Lab 1: HTML
3
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 III: PDF

Java IV: PDF

HW 2: HTML

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.

Packages.

 

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

HW 3: HTML

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

HW 04: HTML

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
15

R 6/15

MIDTERM EXAM

 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.

 

 

 BinaryTreeCode.html

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

 

BinaryTreeCode.html

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

 

HowToImplementHashTables.html

Used the board!

HW 06: HTML

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