From PBDN

Lecture Summary

All the topics on one page.

Lecture 1: Insertion Sort

• [pp.15-17] — wp:Insertion sort

Lecture 2: Time Complexity, Asymptotic Notation

• [p.19] — Pseudocode Conventions
• [p.21] — Analyzing Algorithms
• [pp.23-25] — Analysis of wp:Insertion sort
• [pp.25-27] — Worst-case and Average-case Analysis
• [pp.41-46] — wp:Asymptotic notation
• [p.49] — Comparison of Functions
• Small o-notation and ω-notation

Lecture 3: Divide and Conquer, Merge Sort

• [pp.29-39] — Divide and conquer, wp:Merge sort.

Lecture 4: Heaps, Heapsort

• [pp.127-144] — wp:Heapsort, heaps, heap operations, priority queues.

Lecture 5: Priority Queues, Quicksort

• [pp.144-164] — wp:Quicksort: worst-case, best-case, balanced partitioning, randomized Quicksort.

Lecture 6: Quicksort. Sorting in Linear Time

• [pp.165-182] — Sorting in linear time: wp:Counting sort, wp:Radix sort, wp:Bucket sort.

Lecture 7 & 8: Sorting in Linear Time, Hashing

• [pp.221-232] [pp.237-245] —
  • Direct addressing
  • wp:Hash tables
  • Chaining
  • Hash functions: the division and multiplication methods
  • Open addressing
  • Linear and quadratic probing

Lecture 8: Hash Tables

As Lecture 7.

Lecture 9: Binary Search Trees

• [pp.253-264]
  • wp:Binary search trees (BSTs)
  • BST Operations: walk, insert, delete, successor, predecessor, minimum, maximum, search.

Lecture 10: Graph Algorithms: Breadth First Search

No page range given. Estimate [pp.527-538]. Page ranges below are not from Parosh.

• [pp.527-530] — Graphs.
• [pp.531-538] — wp:Breadth-first search (BFS)

Lecture 11: Graph Algorithms (contd.)

No page range given. Estimate [pp.540-557] with gaps. Page ranges below are not from Parosh.

• [pp.540-545] — wp:Depth-first search (DFS)
• [pp.549-551] — wp:Topological sorting
• [pp.552-557] — wp:Strongly connected components (moved to Lecture 12?)

Lecture 12: Strongly Connected Components

• Section 22.5 [pp.552-557] — wp:Strongly connected components

Lecture 13: Guest Lecture: Randomized Binary Search

No contents listed. Below from my notes.

General Topic: Maintenance of Balance in Binary Search Trees

Guest Lecturer: Arne Andersson.

This was an interesting lecture looking at different ways of preserving and/or enforcing balance on BSTs, delivered using software which illustrated all of the graph operations with step-by-step animation. The software was written many years ago, by the guest lecturer himself, for MacOS 9.

• Randomizing Node Age
  • Operations: left-rotation and right-rotation
• AA-trees (Binary B-Trees)
  • Operations: skew and split
  • Compare: red-black trees (mention)
• General Balanced Tree
  • Rebuild tree when h > clgn (c = 1.2 used in example)
  • Only rebuild smallest violating subtree
• Splay Tree
  • Operations: zigzig and zigzag
  • On every operation (insert, delete or search), drag node to root.
• Concluding Remarks
  • Randomness can be useful!
  • There are many different kinds of BST