COMP 550-002 (old 122) Web Links

# Fall 2019

Course Syllabus
INTRODUCTION (Lecture 1)

Course Introduction (Lecture 1)

Algorithms and Analysis (Lecture 1, Chapter 2)

Insertion Sort, Review of Loop Invariants (Lecture 1, Chapter 2)

MATHEMATICAL TECHNIQUES (Lectures 2 - 6)

Asymptotic Notation, Functions and Summations (Lecture 2, Chapter 3, Appendix A)

Divide and Conquer (Merge Sort), Recurrence Relations (Lecture 3, Chapter 2.3, 4)

Recurrence Relations (Lecture 4, Chapter 4)

How to Shuffle on a Computer (Lecture 5,6, Chapter 5)

SORTING AND SELECTION (Lectures 7 - 14)

Elementary Sorting Algorithms (Lecture 7)

Heapsort (Lecture 7, Chapter 6)

Quicksort, Recurrence Relations (Lecture 8, Chapter 7; Lecture 4, Chapter 4)

Randomized Quicksort, Probabilistic Analysis of Algorithms, Discrete Probability (Lecture 8, Chapter 7; Lecture 5,6, Appendix C, Chapter 5)

Exam 1 (Lecture 9)

Lower Bounds for Comparison Sorting, Linear Time Sorting, Hash Tables
(Lecture 10, Chapter 8.1; Lecture 11,12 Chapter 8; Lecture 15, Chapter 11)

Lower Bounds for Comparison Sorting, Linear Time Sorting (better version)
(Lecture 10, Chapter 8.1; Lecture 11,12 Chapter 8)

Order Statistics (Selection) (Lecture 13,14, Chapter 9)

HASHING AND TREE SEARCHING (Lectures 15 - 18)

Hash Tables (Lecture 15, Chapter 11)

Examples of multiplicative hashing (Lecture 15, Chapter 11)

Example of universal hashing (Lecture 15, Chapter 11)

Hash Tables (Lecture 16, Chapter 11)

Binary Search Trees (Lecture 17, Chapter 12)

Red Black Trees (Lecture 18, Chapter 13)

Animation of red black tree insert (Lecture 18, Chapter 13)

Insertion and deletion in a red black tree (Lecture 18, Chapter 13)

Deletion in a red black tree (Lecture 18, Chapter 13)

Comparison of Dictionary Data Structures (Lecture 18, Chapter 13)

ADVANCED ALGORITHM DESIGN TECHNIQUES (Lectures 19 - 23)

Dynamic Programming (Lecture 19, 21, Chapter 15)

Exam 2 (Lecture 20)

Dynamic Programming (Lecture 19,21, Chapter 15)

Dynamic Programming (Lecture 19,21, Chapter 15)

Greedy Algorithms, Minimum Spanning Trees (Lecture 22,23, Chapter 16; Lecture 26, Chapter 23)

GRAPH ALGORITHMS (Lectures 24 - 28)

Graphs, Breadth First and Depth First Search (Lecture 24, Chapters 22)

Topological Sort, Strongly Connected Components, (Lecture 25, Chapter 22)

Minimum Spanning Trees, Kruskal's Algorithm (Lecture 26, Chapter 23)

Minimum Spanning Trees, Prim's Algorithm (Lecture 26, Chapter 23)

Single Source Shortest Paths (Lecture 27, 28, Chapter 24)

HOMEWORK

PRACTICE EXAMS