COMP 550-001 Web Links

COMP 550-001 Web Links

Spring 2020

Course Syllabus

Class Introduction

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)

Robo Cop

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)

Jobs being lost

Linear Time Sorting

Skills in demand for programmers

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

Fast Median Finding

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)

Cryptographic Hashing

Problems with Hash Functions

New Hash Function

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

Homework 1

Homework 2

Homework 3

Homework 4

Homework 5

Homework 6

Homework 7

Homework 8

Homework 9

PRACTICE EXAMS

Practice Exam 1

Another Practice Exam 1

Practice Exam 2

Another Practice Exam 2

Practice Final Exam