CISC-235 2005

Tue - April 12, 2005

Extra Review Sessions

There will be one additional review session on Monday April 18 from 10:30 -12:00.
There will also be a review session run by Prof. Mary McCollom on Wednesday April 20 at 2:00-4:00.
Both reviews will take place in Goodwin Hall room 254.

Posted at 10:13 AM

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

Tue - April 5, 2005

Experience Using C++

I have been asked to report back to the Chair of the School's Curriculum Committee on the outcome of using C++ in CISC-235. I would appreciate if you could provide me with some feedback on this. 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.

Posted at 05:06 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

Sun - April 3, 2005

Readings

Readings: This list will be updated as the term progresses.

Read : Required reading. Covered in lectures (more or less). Sample questions and tests are based on this material.

Optional: Not central to the course. Reading this material should not be too difficult and would nicely support the required material.

Skip: This material would require more effort to understand than the optional category above. Note: this does not mean that there is anything wrong with the topics covered in these sections, rather this material is tangential to the course this term.

Chapter 6. Read all of it.

Chapter 8.
8.1 – 8.2 Read
8.3 Optional
8.4 Skip
8,5 Read
8.6 Skip
8.7 Skip

Chapter 18. Read all of it.

Chapter 19.
19.1 Read
19.1.2 Optional
19.2 Read
19.2.1.Optional
19.3 Read
19.4 Read
19.5 Read
19.6 Read
19.7 Optional
19.8 Read

Chapter 20. Read all of it.

Chapter 21. Read all of it.

Chapter 13.
13.1.1, 13.1.2 Read
13.1.3 Optional
13.2 Skip

Chapter 11.
11.1 Skip
11.2.1 11.2.2 Read
11.2.3 Optional

Chapter 15.
15.1 Read
15.2.1 Read
15.2.2 Optional
15.3.1 Read
15.3.2 Optional
15.4 Skip
15.5.1 Read
15.5.2 Read
15.5,3 Optional
15.5.4 Optional

And this concludes the reading list for CISC-235 Winter 2005

Posted at 02:01 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

Study Questions for quiz #3

Practice Questions for Quiz #3.

Heap Questions:
Text Chapter 21 questions:

21.1, 21.2, 21.3, 21.6, 21.8, 21.10, 21.11, 21.12

B-Trees Questions:

Use the definition of a B-Tree given below for the next two questions.

A B-tree of order M is a M-ary tree, M >= 2 with the following properties:

1. The root has at least two subtrees unless it's a leaf.
2. Each non-root holds k-1 keys, and each non-root and non-leaf also holds
k pointers to subtrees, where the ceiling of m/2 <= k <= m.
3. All leaves are on the same level.
4. The keys in each node are in non-decreasing order.
5. The children are in order:
the keys in the first i children are less than or equal to the ith key
the keys in the last m-i children are greater than or equal to the ith
key

Question 1. What is the maximum number of keys that a B-Tree of order 6 (at most five keys per node) and of height 4 hold? How many disk accesses in the worst case would be required to find any key, assuming one block on disk can hold one node? How many keys can a B-Tree of order m and of height h hold?

Question 2. Construct a B-Tree of order 3 (at most two keys per node) first for the insertion sequence 1, 5, 3, 7, 2, 4, 6 and then for the insertion sequence 1, 2, 3, 4, 5, 6, 7. Which sequence of insertions is preferable? Why?

External Merge Sorting

Suppose that there are 32 records to be sorted and the data is stored on external memory. Using an I/O model where reading or writing one record counts as one external memory access answer the following questions.

a) How many external memory accesses (reads and writes) are used to sort the data using a 2-way merge sort? Assume that all you can do in internal memory is compare two numbers and output the smallest.

b) How many external memory accesses (reads and writes) are used to sort the data using a 4-way merge sort? Assume that all you can do in internal memory is compare four numbers and output the smallest.

c) What if we have enough internal memory to make initial runs of 8 sorted records. How many external memory accesses (reads and writes) are used to sort the data using a 2-way merge sort? 4-way merge sort?

d) Illustrate how the 2-way and 4-way merge sorts of part c) would work using the following set of random integers.

41 40 35 6 74 8 87 89 99 24 2 8 44 19 93 23

63 91 4 5 70 57 38 59 3 4 83 83 46 18 53 17

Posted at 08:20 PM

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

Two classes cancelled for Easter.

The university is closed on Good Friday, March 25, so there will no class. The university is open on Easter Monday, March 28. However I have cancelled class. For students who have labs on Mondays it is likely that your lab will be held at the usual time on March 28.

Posted at 09:55 PM

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

Study questions for quiz #2

Lecture 18.

Lecture 17.