Resources 
Staff Contact Information 

Instructor
Curriculum Assistants: Femke Hermse, Dayuan Wang 

Lecture Schedule 

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 arrayalgorithm, 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 OR: At LearningJavaOnline: go through exercises for
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 nonstatic 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 minilecture 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.7481) 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 runtime stack.  Used the board!  
13  T 6/13  Recursive algorithms on LLs; 

Used the board!  
14  W 6/14  Recursive algorithms on LLs; Doublylinked lists, multilists.  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.


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 arraybased 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  23 Trees; BTrees and external data structures 
Here is a good explanation of 23 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!  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 
