Fri - March 2, 2007
C++ Homework for week 8.
The goal of this assignment is to implement the
FWI (section 8.3.1 in our text describes this algorithm in detail) all-pair
shortest path algorithm on a graph representing the London Underground. This
program will be developed over the next three weeks, that is weeks 8, 9 , and 10
to be demonstrated in weeks 9, 10, and 11.
Data files are attached. They are text files for the London Underground and Montreal Metro. Java source code for parsing the text files, and a map of the London Underground
• The file
LondonUnderground
describes the London Underground in a simple text format. First, all station
names are listed, one per line. Then, all edges are listed, again one per line.
The edge list is separated from the station list by an empty line. The precise
format of the file is given below. The file
GraphInput.java
will help you write code to read in the contents of the above file and build an
internal representation of the graph that the FWI algorithm will operate on.
• Your task is to do the
following:
1. Week
8: Write code that reads the contents of a
file specified by the user, builds an internal representation of the graph
specified in the file, and computes the lengths of the shortest paths between
any pair of vertices using the FWI algorithm. This means you have to write code
to do the following:
a. Read in a string from the user representing
the name of a file containing the graph data.
b. Open the file and read in the list of station
names as strings and build the vertices of the graph.
c. Read in the list of triples (name1, name2,
line) as strings and build the edges of the graph. To help you with the parsing
of each triple, the file
GraphInput.java
contains methods that will break up a string for the form "(name1, name2, line)"
into its components. This java program writtem by Margaret Lamb, should be
translated to C++. The third component of an edge is a string describing which
line the edge is on. Note that you will not need this line information for this
assignment.
d. Once the internal representation of the graph
is constructed, apply the FWI algorithm to compute a table that contains the
length of the shortest paths between every pair of stations in the system. You
can assume that the length of each edge is one. The shortest path between two
stations is thus is given by the path that connects the two stations using the
smallest number of edges.
2. Week 9:
After the computation of the shortest
distances between all pairs of stations, your program should repeatedly prompt
the user for pairs of station names until the user input indicates that no more
shortest distances are required. After two station names have been input, your
program should use the table constructed by the FWI algorithm to look up and
output the length of the shortest path between the two stations. It should also
retrieve a path that realizes this shortest path and print it out as well. For
example, Given the source station Westminster and the destination station
Clapham_Common the output could look something like
this:
The distance between Westminster and Clapham_Common is 7
From station Westminster go to station
St_James's_Park followed by
Victoria followed by
Pimlico followed by
Vauxhall followed by
Stockwell followed by
Clapham_North followed by
Clapham_Common
Notice that you don't have to take the LINE
travelled on into consideration, nor do you have to report transferring from one
LINE to another.
3. Week
10: You have an extra week to get
everything done if you haven’t already finished by week 9. Alternately you
can use week 10 for the challenge part of this assignment. An annoying
short-coming of the current implementation is that transferring from one line to
another is not taken into consideration. On the surface there does not seem to
be a quick way to remedy this problem. Your challenge is to determine and
implement a means to incorporate line transfers into the shortest path
calculation. A reasonable weighting for a line transfer is a cost of k, that is,
the time it takes to change lines is equivalent to the time it takes to travel
from k stations. In my experience the value of k should be somewhere around 2 or
3.
• Assumptions, remarks, and
hints
• The graph description file lists all
stations using one line per station. Then all edges are listed using one line
per edge. The list of edges is separated from the list of stations by an empty
line. More precisely, the format of the file is as
follows:
• s1
• s2
• .
• .
• .
• sn
•
• (s11, s12, l1)
• (s21, s22, l2)
• .
• .
• .
• (sm1, sm2, lm)
•
• s1
• s2
• .
• .
• .
• sn
•
• (s11, s12, l1)
• (s21, s22, l2)
• .
• .
• .
• (sm1, sm2, lm)
•
• where the
si and
sij are
station names and the
li are the
names of the lines that the edge is on. If the specified file is not in this
format, your code should notify the user.
• Note that the file describing the London
Underground contains symmetric edges, that is, for every edge (s1, s2, l) in
LondonUnderground,
there also is an edge (s2, s1, l) in the file. This models the assumption that
subway trains can always be used in both directions.
• For this assignment, the
length of
a path will simply be the number of edges on the path, that is, the weight of
every edge will be 1.
• While you may want to test your code on
simpler graphs initially, your final test runs should use the London Underground
graph.
• The data for the Underground was obtained
from the map by Michelle Crane, a PhD student. The
MontrealMetro
file follows the same format as the
LondonUnderground.
It's a smaller system so it might be a good place to start when debugging your
program.
• For the FWI algorithm an adjacency matrix
of the graph is appropriate. To quickly obtain a path an adjacency list of the
graph is better. So use both representations in your program. Use a map on keys
that are station names to quickly access the index in the adjacency matrix
associated to a station name. Use the C++ map class for this.
Posted at 01:39 PM
Thu - February 15, 2007
C++ Homework for Week 7.
Be prepared to demonstrate this program
for your TA in your designated tutorial slot in week 8.
Over the next few weeks I will be asking you to implement various stages of a Huffman data compression scheme. Last week all you had to do is to was compute the so called "probabilities" of characters in some text. This week you will use the frequencies to build a Huffman tree. Recall that Huffman's algorithm operates on a forest of trees. At each iteration two trees of minimum weight are replaced by a new tree that is a merge of the two trees. See section 11.2 of your text for the detailed algorithm. An efficient way to implement the forest of trees is to build a heap of trees as illustrated in figure 11.5. That said, to satisfy the requirements of this assignment you may implement the forest of trees using an array, or a linked list, or a heap. I will leave this choice up to you. There is no need to implement the compress/decompress routine sin this assignment. To demonstrate that your program works simply print out the code for each symbol. An interesting statistic that you can also print is the compression rate, or the average number of bits used per symbol.
I wrote this program over reading week. In the interest of simplifying your programming experience I have decided to provide you with my code.
Huffman.cpp
You will notice that I used STL classes and methods to achieve a very compact solution. There is an interesting article about using the C++ STL in a program for obtaining a Huffman tree, here .
On the surface using a heap to implement Huffman's algorithm seems like an important improvement to the running time of the algorithm. However, as will be asked on this week's data structures homework, using a heap will make a minimal difference, if any at all, of a "real" Huffman encoder/decoder.
Over the next few weeks I will be asking you to implement various stages of a Huffman data compression scheme. Last week all you had to do is to was compute the so called "probabilities" of characters in some text. This week you will use the frequencies to build a Huffman tree. Recall that Huffman's algorithm operates on a forest of trees. At each iteration two trees of minimum weight are replaced by a new tree that is a merge of the two trees. See section 11.2 of your text for the detailed algorithm. An efficient way to implement the forest of trees is to build a heap of trees as illustrated in figure 11.5. That said, to satisfy the requirements of this assignment you may implement the forest of trees using an array, or a linked list, or a heap. I will leave this choice up to you. There is no need to implement the compress/decompress routine sin this assignment. To demonstrate that your program works simply print out the code for each symbol. An interesting statistic that you can also print is the compression rate, or the average number of bits used per symbol.
I wrote this program over reading week. In the interest of simplifying your programming experience I have decided to provide you with my code.
Huffman.cpp
You will notice that I used STL classes and methods to achieve a very compact solution. There is an interesting article about using the C++ STL in a program for obtaining a Huffman tree, here .
On the surface using a heap to implement Huffman's algorithm seems like an important improvement to the running time of the algorithm. However, as will be asked on this week's data structures homework, using a heap will make a minimal difference, if any at all, of a "real" Huffman encoder/decoder.
Posted at 01:32 PM
Wed - February 7, 2007
C++ Homework for Week 6.
Be prepared to demonstrate this program
for your TA in your designated tutorial slot in week 7. (That's the week after
reading week.)
Over the next few weeks I will be asking you to implement various stages of a Huffman data compression scheme. This week all you have to do is to compute the so called "probabilities" of characters in some text. You need to use file I/O to read in a text file. Reading in characters one at a time you can obtain the occurrence frequency of each character. It will be most convenient if you use your binary search tree to help in computing character frequencies. The probability for any given character is just its frequency divided by the total number of characters in the text. To demonstrate your program print a listing of the characters in the file together with the probability of the character.
Over the next few weeks I will be asking you to implement various stages of a Huffman data compression scheme. This week all you have to do is to compute the so called "probabilities" of characters in some text. You need to use file I/O to read in a text file. Reading in characters one at a time you can obtain the occurrence frequency of each character. It will be most convenient if you use your binary search tree to help in computing character frequencies. The probability for any given character is just its frequency divided by the total number of characters in the text. To demonstrate your program print a listing of the characters in the file together with the probability of the character.
Posted at 12:45 PM
Thu - February 1, 2007
C++ Homework for Week 5.
Be prepared to demonstrate this program
for your TA in your designated tutorial slot in week 6. (And yes I know that
there will be a quiz in week
6.)
This week's program uses an ordered dictionary to support an n body simulation that goes by the name the "Jumping Leprechauns".
(Note this problem is from Data Structures and Algorithms in Java 4th Edition , by Goodrich and Tamassia. )
The simulation involves n leprechauns numbered from 0 ... n-1. Each leprechaun possesses a bag of gold, with gi. Initially gi = 1000000 dollars for all i.
Each leprechaun stands at a location xi, a double precision floating point value. Initially xi = i*gi.
One iteration of the simulation processes the leprechauns from 0 ... n-1. Processing a leprechaun moves (jumps) a leprechaun to a location xi + rgi, where r is a random number between -1 ... 1. The leprechaun then steels half the gold from the nearest leprechauns to its right and left, if he indeed has both neighbours. If the position moved to is either the largest or smallest value of all xi, then there is only one neighbour that is nearest. In this case he steals all of the gold from the nearest leprechaun and the bankrupt leprechaun is out of the game. The simulation ends when a single leprechaun is left.
Write a program to perform a sequence of iterations of this simulation for a given number of leprechauns n. You should maintain the positions of the leprechauns in a binary search tree. Your program should output the state of the simulation at the end of every iteration, by printing xi and gi for every leprechaun. Be creative in the presentation of your results, striving for aesthetics and clarity.
This week's program uses an ordered dictionary to support an n body simulation that goes by the name the "Jumping Leprechauns".
(Note this problem is from Data Structures and Algorithms in Java 4th Edition , by Goodrich and Tamassia. )
The simulation involves n leprechauns numbered from 0 ... n-1. Each leprechaun possesses a bag of gold, with gi. Initially gi = 1000000 dollars for all i.
Each leprechaun stands at a location xi, a double precision floating point value. Initially xi = i*gi.
One iteration of the simulation processes the leprechauns from 0 ... n-1. Processing a leprechaun moves (jumps) a leprechaun to a location xi + rgi, where r is a random number between -1 ... 1. The leprechaun then steels half the gold from the nearest leprechauns to its right and left, if he indeed has both neighbours. If the position moved to is either the largest or smallest value of all xi, then there is only one neighbour that is nearest. In this case he steals all of the gold from the nearest leprechaun and the bankrupt leprechaun is out of the game. The simulation ends when a single leprechaun is left.
Write a program to perform a sequence of iterations of this simulation for a given number of leprechauns n. You should maintain the positions of the leprechauns in a binary search tree. Your program should output the state of the simulation at the end of every iteration, by printing xi and gi for every leprechaun. Be creative in the presentation of your results, striving for aesthetics and clarity.
Posted at 04:27 PM
Thu - January 25, 2007
C++ Homework for Week 4.
Recognizing that there is a quiz this
week, all I'm asking is that you add a delete function to the binary search
tree that you implemented last week. It's up to you to come up with a reasonable
way to test your delete function.
Posted at 09:35 AM
Thu - January 18, 2007
C++ Homework for week 3
For this homework you have to implement a
binary search tree. Each node of your binary search tree should store a float
element value as well a left and right pointer.
A good place to start is the implementation in your text found in figure 6.8. This week implement some of the most basic functions, that is insert, search, and the recursive traversals, preorder, inorder, postorder.
To test the workings of your binary tree generate a sequence of random values k, with 0 < k < 1, and insert them into the tree. Then use the traversals , preorder, inorder, postorder, to print the key values in your test tree. You may also want to test some of the functions in your answers to this week's Data Structures questions.
A good place to start is the implementation in your text found in figure 6.8. This week implement some of the most basic functions, that is insert, search, and the recursive traversals, preorder, inorder, postorder.
To test the workings of your binary tree generate a sequence of random values k, with 0 < k < 1, and insert them into the tree. Then use the traversals , preorder, inorder, postorder, to print the key values in your test tree. You may also want to test some of the functions in your answers to this week's Data Structures questions.
Posted at 10:11 AM
Wed - January 10, 2007
C++ Homework for Week 2.
Write a program using the stack algorithm
to solve the "pillar" problem.
Recall the pillar problem can be described as follows.
Input: A sequence of height values h[0 .. n-1], such that h[0] = 1 and 0 < h[i] < 1 for all i = 1, ..., n-1.
Output: For every pillar i, with 0 < i < n 1 report s[i], the label of the pillar to the left of pillar i that is illuminated by a point laser light
emitting from the top of pillar i.
Your program should allow you to easily change the value of n.
Your stack implementation is your choice. You may use an array (circular), a linked list, write your own generic stack class, or even use the STL stack class. Your choice of implementation method can be based on the method you think you need the most practice with. Or perhaps your current workload is heavy and you want to take an easy way out. If you have time you may actually try more that one method. Nevertheless, to get your point all you need to do is demonstrate a running program.
However, if you are up for a challenge, then the student(s) who has implemented a stack in the largest variety of ways will be singled out for special distinction!
Recall the pillar problem can be described as follows.
Input: A sequence of height values h[0 .. n-1], such that h[0] = 1 and 0 < h[i] < 1 for all i = 1, ..., n-1.
Output: For every pillar i, with 0 < i < n 1 report s[i], the label of the pillar to the left of pillar i that is illuminated by a point laser light
emitting from the top of pillar i.
Your program should allow you to easily change the value of n.
Your stack implementation is your choice. You may use an array (circular), a linked list, write your own generic stack class, or even use the STL stack class. Your choice of implementation method can be based on the method you think you need the most practice with. Or perhaps your current workload is heavy and you want to take an easy way out. If you have time you may actually try more that one method. Nevertheless, to get your point all you need to do is demonstrate a running program.
However, if you are up for a challenge, then the student(s) who has implemented a stack in the largest variety of ways will be singled out for special distinction!
Posted at 12:51 PM
Wed - December 20, 2006
C++ Homework for Week 1.
Be prepared to demonstrate this program
for your TA in your designated tutorial slot in week 2.
This program is intended to familiarize yourselves with programming with arrays and linked lists.
Using the c++ random number generator rand to generate 25 random integers in the range 0..RAND_MAX. Note you will need to use <cstdlib>.
Store these numbers in an array, and then in a linked list. Also provide a method to print out all of the elements of the array or linked list.
This program is intended to familiarize yourselves with programming with arrays and linked lists.
Using the c++ random number generator rand to generate 25 random integers in the range 0..RAND_MAX. Note you will need to use <cstdlib>.
Store these numbers in an array, and then in a linked list. Also provide a method to print out all of the elements of the array or linked list.
Posted at 11:24 AM
Quick Links
Calendar
| Sun | Mon | Tue | Wed | Thu | Fri | Sat |
Categories
Archives
XML/RSS Feed
Statistics
Total entries in this blog:
Total entries in this category:
Published On: Mar 09, 2007 10:27 AM
Total entries in this category:
Published On: Mar 09, 2007 10:27 AM