Lectures

Fri - April 8, 2005

Lecture 36.

I completed the term review for the final. I surveyed the different types of search trees used this term. We also looked at some open ended problems that explore the used of different data structures for solving problems.

I have prepared some problems based on the material in Chapter 15 for you to work on in preparation for the final test.

Chapter 15 exercise 15.2 and 15.3 15.4 and

Consider the graph in figure 15.1. Can a topological ordering of the graph be obtained?
If not suggest some changes to the graph that would permit a topological ordering. Explain

This concludes the regular lectures for CISC-235 Winter 2005.
There will be one additional review session on Monday April 18 from 10:30 -12:00. I will announce the room number on this web log.
There will also be a review session run by Prof. Mary McCollom on Wednesday April 20 at 2:00-4:00. Room to be announced also on this web log.

Posted at 02:20 PM

Wed - April 6, 2005

Lecture 35

At the beginning of class we had a short informal discussion regarding the pros and cons of using C++ this term.
If you have an opinion that you would like to be heard please send me an e-mail message. Alternately you can hand me your comments on paper if you wish.

Today we began a review of the material that we studied in CISC-235 this term. I have prepared an annotated outline, that is, annotations on the reading list that has been maintained this term. The annotations are specifically concerned with what material will, and what material will not be examined on the final exam. We went through the entire outline together today using the data projector. This outline is also attached below.

I spent a few minutes discussing breadth first and depth first traversals of graphs, as this was only touched upon in an indirect way during our discussion of graphs and trees.

I will continue with the review on Friday.

annotatedoutline.pdf

Posted at 02:02 PM

Mon - April 4, 2005

Lecture 34

Today we looked at a single source shortest path algorithm for Directed Acyclic Graphs (DAGs). As a preliminary step we performed a topological ordering of the vertices of the DAG. The computational cost of performing the topological ordering is O(|E|). The cost of the shortest path algorithm is also O(|E|).
I have a bit more to discuss regarding graph algorithms, but that can be incorporated in with the review.

Thus we have finished the material for the course. I have updated the Readings. The readings list is now complete. On Wednesday I will go over an annotated version of the list to help you with your studying strategy.

Posted at 05:33 PM

Fri - April 1, 2005

Lecture 33

I went over review questions for quiz #3. I was asked to focus on the multi-way external merge sort and B-tree questions, and that is what I did.

Next week is the final week of classes. My plan for next week is:

Mon. Single source shortest path algorithm for a directed acyclic graph.
Wed. and Fri, I will review for the final exam.

Posted at 01:56 PM

Wed - March 30, 2005

Lecture 32

Today we saw a template for single source shortest path algorithms. Common to all of the algorithms is an iterative step that moves vertices one by one from an "Unseen" , U, part to the the "seen" or "Tree", T, part. The differences are in how the decisions are made for moving a vertex from U to T.

We saw a very nice and clever implementation of Dijkstra's algorithm for positive weighted digraphs. This algorithm uses a priority queue to help decide which vertex to move from U to T.

The second algorithm we saw is for undirected graphs where the edges are unweighted, and the implicit cost of every edge is 1. Here a breadth first traversal of the graph is used to decide which vertex to move from U to T.
.

On Friday I will review questions for quiz #3.

Posted at 01:53 PM

Mon - March 28, 2005

Lecture 31

Class cancelled. Note: Labs are held today as usual.

Posted at 01:47 PM

Fri - March 25, 2005

Lecture 30

Good Friday no class.

Posted at 01:46 PM

Wed - March 23, 2005

Lecture 29

The class began with USAT surveys.
I went over Dijktsra's shortest path algorithm today.
I gave an informal argument for why the algorithm works.
A naive implementation of the algorithm yields a O(|V|²) algorithm.
This happens to be the best we can do when the graph is dense, that is, the number of edges is O(|V|²).
However, when the graph is sparse we can do better. I will elaborate next time we meet which will be on Wednesday March 30.

Posted at 01:45 PM

Mon - March 21, 2005

Lecture 28

Today I began a sequence of lectures dealing with paths in graphs. We consider a connected graph as input and want to determine the costs of shortest paths from single source to all other vertices. We will consider this problem on directed, and undirected graphs, and when the edge weights are arbitrary positive values, or all 1.

Today we saw the main ideas behind a greedy approach that determines a new shortest path value at each iteration. On Wednesday I will flesh out the details. This includes an argument to justify the correctness of the greedy approach. We will also consider efficient implementations of the algorithm.

The algorithm we discussed today goes by the name of Dijkstra's algorithm. A very nifty applet that demonstrates this algorithm can be found here.

This material is covered in Chapter 15 of the text.

Posted at 03:13 PM

Fri - March 18, 2005

Lecture 27

A strategy when playing so called zero-sum two person games, is to do a depth first traversal of an implicit game tree. We saw how game trees can be used to play Tic-Tac-Toe using the minimax algorithm. Searching the entire game tree is usually not feasible. We saw two heuristics that allow an abbreviated search.

Alpha-beta pruning is a method of deciding that there is no point traversing the next child of the current node, because the current child has returned a result that can't possibly be bettered.

Transposition tables are a map that are used to store the value of Tic-Tac-Toe boards that have already been seen. We discussed implementing this map using a hash table.

Posted at 09:51 PM

Wed - March 16, 2005

Lecture 26

Today I covered Huffman's algorithm. We went over every stage of the process from obtaining frequencies of the symbols in the source message. Building the tree, and encoding and decoding with tree.

On Friday we will look at game trees for playing Tic-tac-Toe.

Posted at 09:43 PM

Mon - March 14, 2005

Lecture 25

A few more questions pertinent to quiz #2 were answered at the beginning of the hour.

I then showed a short presentation discussing different variations of the B tree. I also demonstrated an animated B+ tree that I found on the web. My presentation is attached. BandBplusTrees.pdf

We then turned to the topic of data compression. I defined some terminology and stated the ground rules for the compression problem we are going to solve. More to follow on Wednesday.

Posted at 04:02 PM

Fri - March 11, 2005

Lecture 24

Today we reviewed for Quiz #2. I covered most of the questions from chapter 18, but ran out of time when it came to chapters 19 and 20.
However, most of the practice questions for those chapters seem quite straightforward. If you have any further questions I will address them on Monday.

Regarding some confusion on Red-Black trees. No question on any quiz will examine your knowledge of Red-Black trees.

Next week's topic (starting on Monday if I get to it) will be data compression using Huffman's algorithm. See Chapter 13 of the text.

Posted at 01:05 PM

Wed - March 9, 2005

Lecture 23

Today I worked through an example that helped us calculate the number of disc accesses used in a K-way merge sort.
In our example I had to determine the value of log₄(200,000). The correct value is log₄(200,000) = 8.8048.
On Friday I will briefly discuss B+ trees. I will also review for quiz #2 that is to be held next week.

Posted at 02:03 PM

Mon - March 7, 2005

Lecture 22

Today we addressed external memory issues when sorting. MergeSort was discussed in it's usual form as well as versions that
- start with block of sorted data.
- use k-way merges.

These modifications are motivated by the need to reduce the number of disc accesses.

This more or less brings us to the end of chapter 21 of the text. On Wednesday I will fill in a few missing pieces regarding B-trees and external sorting with tapes. All of chapter 21 is required reading. I have updated the "Readings" entry to reflect this.

Also note that Section 19.8 is back on the reading list.

Posted at 03:33 PM