Announcements
 The ordering of lectures for Fall 2018 is shown below. It is a bit different than last year.
We will not update the lecture notes for this year, please use
Fall 2017's lecture notes instead. We will try to update the Exercises:
see mycourses/Exercises.

Resources

LECTURES

EXERCISES from Fall 2017 (with solutions) 
Preliminaries: basic math
 introductions
(slides)
 grade school algorithms for arithmetic
 logarithms & modular arithmetic
 number representations and base conversions

Exercises 1: grade school arithmetic, number representations
(PDF)

Object Oriented Design in Java 1
 Char, unicode, primitive type casting
 packages, modifiers, UML
 inheritance
 inheritance and modifiers, Object class
 type conversion, Polymorphism

Exercises 13: object oriented design
(PDF)

Linear Data Structures
 array lists
 singly linked lists
(Mon. Oct. 1 class cancelled because of QC elections)
 doubly linked lists
 iterative sorting algorithms
bubble, selection, & insertion sort
 stacks
 queues
+ ADTs, Java API, interfaces

Exercises 2: arrays and array lists
(PDF)
Exercises 3: linked lists
(PDF)
(code)
Exercises 4: iterative sorting
(PDF)
Exercises 5: stacks and queues
(PDF)

Object Oriented Design in Java 2

interfaces, abstract classes

examples of interfaces
Comparable, Iterable, Iterator
 Class class, introduction to memory management in Java


Induction and Recursion
 mathematical induction
 recursion 1
factorial & Fibonacci, reverse/sort list, Tower of Hanoi; call stack
 recursion 2
power, binary search
 recursion 3
mergesort, quicksort

Exercises 6: induction and recursion
(PDF)

Nonlinear Data Structures
 rooted trees
 tree traversal
 binary trees e.g. expression trees
 binary search trees
 priority queue, heaps 1
 heaps 2
 maps, hash codes
 hash maps
 graphs
 graph traversal (breadth vs depth first)
 graph applications: Google page rank, garbage collection

Exercises 9: trees
(PDF)
Exercises 10: heaps
(PDF)
Exercises 11: hashing
(PDF)
Exercises 12: graphs
(PDF)

Mathematical Tools for Analysis of Algorithms

recurrences 1
back substitution method, examples

recurrences 2
mergesort, quicksort

big O 1
formal big O definition

big O 2
rules for big O, big Omega, some incorrect proofs

big O 3
big Theta, best and worst case, limits rules

Exercises 7: recurrences
(PDF)
Exercises 8: big O
(PDF)
