Lectures for CMSC 251

Lecture 1: OVERVIEW and SHORTEST PATHS PROBLEM We started out with a general introduction to the notion of a problem an algorithm, and a program. We discussed one example of a problem, which was finding the shortest path between a pair of cities in a map (given distance information about highways connecting various cities on a map). We discussed an approach, which essentially tries to enumerate all simple paths (paths that do not repeat vertices) between the desired pair of cities. We then argued that the running time of this algorithm was pretty bad (since the number of simple paths could be huge!). We then discussed the notion of "running time" as well as the "space required" by an algorithm. We then discussed insertion sort in some amount of detail and computed its WORST CASE running time. We informally studied how to compare two different algorithms and did a brief introduction to the Order notation. Next time, we will discuss insertion sort in more detail as well as the order notation. We will also talk about AVERAGE CASE analysis, and why it is somewhat harder to compute.

Lecture 2: INSERTION SORT and COMPUTING RUNNING TIMES We discussed Insertion Sort in more detail, and computed more precisely what the running time of this algorithm is. We defined the Order notation formally, and did a few examples of how one can prove that a given function f(n) belongs to the set of functions O(g(n)).

HOMEWORK 1 was handed out today. Each homework will specify which chapters in the book I expect you to read.

Lecture 3: INTRODUCTION TO ORDER NOTATION O,Theta, Omega etc. Examples.

Lecture 4: REVIEW OF SERIES AND SUMMATIONS Summations, examples where they arise, how do we solve them? Arithmetic series, geometric series etc. Obtaining bounds on series using integrals as well as splitting summations.

Lecture 5: DIVIDE AND CONQUER ALGORITHMS Mergesort and its analysis. Details of merging, setting up a recurrence, solving it by induction and expansion.

Lecture 6: DIVIDE AND CONQUER: LONG NUMBER MULTIPLICATION How do we multiply two n bit numbers? Can we reduce the number of bit operations by using a divide and conquer approach?

Lecture 7: MASTER THEOREM Solving recurrences in general and proving the master theorem.

Lecture 8: MASTER THEOREM Solving recurrences in general, applying the master theorem.

Lecture 9: CLOSEST PAIR PROBLEM This material is from Chapter 35 in the book. You can read it if you found this problem and the algorithm interesting. Its not really important from the exam's point of view. The main idea was to show you a non-trivial divide and conquer algorithm.

Lecture 10: MORE DIVIDE AND CONQUER ALGORITHMS Tennis tournament example. Handout

Lecture 11: Dealing with summations, recurrences etc.

Lecture 12: EXAM REVIEW Design of simple algorithms, understanding of Order notation, Theta notation, Omega etc. Designing simple divide and conquer algorithms and solving recurrences.

Lecture 13:EXAM

Lecture 14:DISCUSS EXAM AND START NEW TOPIC -- SORTING AND SEARCHING

Lecture 15:HEAPS Chapter 7 We discussed HEAPIFY and BUILDHEAP.

Lecture 16:HEAPS Chapter 7 We discussed the running time of BUILDHEAP and HEAPSORT.

Lecture 17:HEAPS Chapter 7 We discusse PRIORITY QUEUES (INSERTION/EXTRACT MAX)

Lecture 18:QUICKSORT Chapter 8 We discussed Quicksort, PARTITION and Randomized Algorithms.

Lecture 19:QUICKSORT Chapter 8 We discussed the average running time of Quicksort.

Lecture 20:COUNTING SORT AND RADIX SORT Chapter 9

Lecture 21: MEDIAN FINDING Chapter 10

Lecture 22: MEDIAN FINDING Chapter 10

Lecture 23: EXAM REVIEW

Lecture 24: EXAM

Lecture 25: DISCUSS EXAM We also started discussing graphs. Read Chapter 5.4, 23.1 and 23.2. Graph Handout

Lecture 26: GRAPHS/BFS/DFS

Lecture 27: NP-COMPLETENESS (Chap 36.1, 36.2 and parts of 36.3) NP-completeness Handout

Lecture 28: NP-COMPLETENESS: Reduction of SAT to CLIQUE.