Announcements

For students who are not registered and would like to get in, please be patient.
It happens every year that students drop the course by the end of drop/add period.
 Students who are registered in the course should see mycourses for all announcements.

Resources

LECTURES

EXERCISES (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, Class class

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


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)

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, brief review of logarithms

recurrences 2
mergesort, quicksort

big O 1
analogy to limits in Calculus, 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)

EXTRA
 why (or why not) go to grad school ?
 beyond COMP 250, final exam
(slides)

