CSE2011 EECS 2011: Fundamentals of Data Structures

 Topics Slides Old Videos New Videos Notes (Java,OO) Abstract Data Types Positions and Pointers Contracts and Invariants Running Time Recursion x Balanced Trees Hash Tables Graphs Algorithmic Paradigms Other Review
 Notes Code Ass1 Ass1 Sol Ass2 Ass2 Sol Midterm Review Midterm Sol Ass3 MainGUI Ass3 Sol Ass4 Ass4 Sol

This is your basic data structures course with a focus on systems
invariants and understanding.
Jeff will also teaches how to think about algorithms in an abstract way
so that one can talk about them, design new ones, and know that they
are correct.
Request:
Help Required: It is the second time me teaching it. (oops) I should start relearning Java.
Texts:

Other's web pages:
Introduction: (ppt)

Andy's slides: These are slides of
Andranik Mirzaian.
My current thinking is to not cover it.
(Partly because I don't know it).
But you may find it useful.

Abstract Data Types: (
ppt, Notes Data Structures)
(What the user of the data structure needs to know about how it is
used, without needing to know how it is implemented.)

Abstractions (Hierarchy)
Elements
Sets
Lists, Stacks, & Queues
Trees
Graphs
Iterators
Abstract Positions/Pointers
Implementations

Positions and Pointers: (
ppt)
(One data structure points at another forming linked lists and trees.
They are often a challenge for new programmers in C or Java.)

Abstract Positions/Pointers
Positions in an Array
Pointers in C
References in Java
Implementing Positions in Trees
Building Trees

Contracts, Assertions, and Invariants: (
ppt, Steps, Notes Invariants, Notes Data Structures)
(Big systems need clear specifications about how its parts
communicate. Big systems, data structures, and algorithms alike need
to have clear specifications that never change.)
(Jeff strongly believes that loop invariants is the most important topic in
worry about one step at a time - make progress while maintaining the
loop invariant.)

Contracts
Assertions
Loop Invariants
The Sum of Objects
Insertion and Selection Sort
Binary Search Like Examples
Bucket (Quick) Sort for Humans
Reverse Polish Notation (Stack)
Parsing (Stack)
Data Structure Invariants
Stack and Queue in an Array

Asymptotic Analysis of Time Complexity: (
ppt, Useful Math)
(We classify algorithms based on whether they are polynomial or
exponential time.)

History of Classifying Problems
Growth Rates
Time Complexity
Linear vs Constant Time
Binary Search Time (logn)
Don't Redo Work
Test (linear) vs Search (Exponential)
Bits of Input
Cryptography
Amortized Time Complexity
Worst Case Input
Classifying Functions (BigOh)
Logs and Exponentials
Understand Quantifiers

Recursion: (
ppt, Notes)
(Again do not try to understand the entire computation. Trust your
friends to solve a smaller instances of your problem and use these to

Fibonacci & Ruler Example
Merge Sort
Friends & Strong Induction
Stack Frames
Running Time
Code
Quick Sort, kth biggest, and power
Recurrence Relations & Running Time
Towers of Hanoi
Check List
Recursion on Trees
Things not to do
Trees Representing Equations
Iterate over all s-t Paths
Recursive Images

Balanced Trees:
ppt
(A great data structure storing objects is a binary tree. If it is
balanced than its depth is only log(n) with n nodes. Hence, operations
are quick.)

Binary Search Trees
Insertions and Deletions
AVL Trees
Rebalancing AVL Trees
Union-Find Partition
Heaps & Priority Queues
Communication & Hoffman Codes

Maps Hash Tables and Dictionaries:
ppt
(Items are "randomly" placed in at table.)

Hash Tables
Random Algorithms
Universal Hash Functions
Key to Integer
Separate Chaining
Probe Sequence
Put, Get, Del, Iterators
Running Time
Simpler Schemes

Graph Search Algorithms (ppt, ass, ass sol, Soccer Strategies)
(Graphs, ie nodes and edges, are very useful for representing
data. The first task on them is to search through the nodes. )

Generic Search
Dijkstra's Shortest Paths Algorithm
Depth First Search
Linear Order

ppt, greedy, dynamic programming, NP)
(There are a few programming meta-algorithms that most algorithms fit
into. These should be understood.)

Brute Force: Optimazation Problem
Greedy Algorithm: Minimal Spanning Tree
Dual Hill Climbing: Max Flow / Min Cut
Linear Programing: Hotdogs
Recursive Back Tracking: Bellman-Ford
Dynamic Programing: Bellman-Ford
NP-Complete Problems
(Pattern Matching)
(Tries)
(Text Compression)
(DNA)
(Text Sequence Alignment)
Machine Learning: I would love to cover some.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.