Lecture Schedule

CSE 100 Section A&B (Fall 2015)

Lecture Schedule

The purpose of lecture is to introduce the basic material we will be covering in this course. You will be responsible for this material on the exams, and you will need to know it to do the programming assignments.

The lecture slides are in PDF format.


Special posts
Week 1

Monday

  • No class

Wednesday

  • No class

Friday

  • Introduction
  • Structure and requirements of the course
  • Overview of trees and their properties
  • Lecture 1 slides
Week 2

Monday

  • The C++ programming language
  • Comparison of C++ and Java
  • Introduction to OO programming in C++
  • Lecture 2 slides

Wednesday

Friday

Week 3

Monday

Wednesday

Friday

Week 4

Monday

  • Treaps
  • Find, insert, delete, split, and join in treaps
  • Randomized search trees
  • Lecture 8 slides

Wednesday

  • Random number generation
  • Skip lists and skip list operations
  • Analysis of skip lists
  • Lecture 9 slides

Friday

  • Red-black trees
  • Analysis of red-black trees
  • Red-black search tree algorithms
  • Lecture 10 slides
Week 5

Monday

Wednesday

  • Trees for representation
  • Tries, decision and classification trees, discrimination nets
  • Intro to Huffman coding
  • Lecture 11 slides

Friday

Week 6

Monday

  • Priority queues and heaps
  • Priority queues in Huffman's algorithm; Priority queues in C++;
  • the std::priority_queue class template
  • alternative representations of Huffman tries
  • Lecture 13 slides

Wednesday

  • I/O in C++;
  • C++ standard library I/O classes
  • Binary and text file I/O
  • Buffering; Bitwise I/O
  • Lecture 14 slides

Friday

  • Intro to Graphs, vertices, edges, paths, cycles
  • Sparse and dense graphs
  • Adjacency matrices and adjacency lists
  • Lecture 15 slides
Week 7

Monday

  • Algorithms on graphs
  • Breadth-first, depth-first search
  • Shortest path in unweighted graphs
  • Lecture 16 slides

Wednesday

  • Djikstra's algorithm for shortest paths in weighted graphs
  • Greedy algorithms
  • NP-completeness
  • Lecture 17 slides

Friday

  • Connectedness in graphs
  • Spanning trees
  • Prim's and Kruskal's algorithms for the minimum cost spanning tree problem
  • Lecture 18 slides
Week 8

Monday

  • Applications of disjoint subsets
  • Union-by-height and union-by-size
  • Find with path compression
  • Amortized cost analysis
  • Lecture 19 slides

Wednesday

  • (Nov 11st) Veteran's day
  • No Lecture

Friday

  • Review for midterm 2
Week 9

Monday

Wednesday

  • Hashing
  • Hash table and hash function design
  • Hash functions for integers and strings
  • Lecture 20 slides

Friday

  • Open addressing and separate chaining collision resolution strategies
  • Analysis of hashing
  • Lecture 21 slides
Week 10

Monday

Wednesday

Friday

  • (Nov 27th) Thanksgiving
  • No Lecture
Week 11

Monday

  • Time costs in a memory hierarchy
  • B-trees and B-tree find, insert, delete
  • Lecture 24 slides

Wednesday

Friday