CS 3343 Analysis of Algorithms Daily Topics

No class, instructor not yet assigned

Introduction, big-oh notation

Chapter 6, Dijkstra's Algorithm

Dijkstra's Algorithm example, the algorithm, implementation

Dijkstra's Algorithm example, Floyd's Algorithm, transitive closure

Traversal of directed graphs, Depth first search, dags

Distinguishing cross and forward arcs, topological sort, strong components, Chapter 7: Undirected Graphs, Scan IDs

Free trees, minimum-cost spanning tree, MST property, algorithms for generating minimum-cost spanning trees, Prim's Algorithm

Prim's Algorithm, Kruskal's Algorithm, MERGE-FIND (Section 5.5)

Exam 1 review, continue MERGE-FIND

Talk about assignment 1, review of Floyd's algorithm (by special request), questions concerning the exam

Exam 1

Go over the exam, continue Kruskal's Algorithm

More on orders of functions, finish Kruskal's algorithm

depth-first and breadth-first search of undirected graphs, sorting, O(n*n) vs. O(n lg n) algorithms, bubble sort.

Insertion sort, Selection sort, Quicksort

Continue quicksort starting with finding a pivot and through analysis of worst case.

Continue quicksort starting with analysis of average performance.

Finish Quicksort, Heapsort, start bin sort

Continue bin sort

Return and go over assignment 4

Minimum order of a sort

Chapter 9, analysis techniques, recurrence relations, start Mater Theorem

Exam review, continue Master Theorem with examples

Exam 2

Student Evaluations, return and go over exam 2,
more examples of using the Master Theorem

Assignment 5 due, more on recurrence relations, miscellaneous topics

Last class

• Back to CS 3343 Homepage