Please read the remarks about programming problems for this course.
Chapters 8-11 Practice
These are practice problems not to be handed in.
8.1, 8.2
9.1, 9.2, 9.5, 9.15,
10.43, 10.54
11.13a
Knowledge Systems
(Worksheets handed out in class)
Chapter 9
Dijkstra's Algorithm Due Tuesday, April 6
Implement the dijkstra function that is part of the code found in the Dijkstra folder of the course code repository. This function uses Dijkstra's single source shortest path algorithm to find the shortest path to all vertices.
All the support code is provided:
- VertexInfo: provides the support for the shortest path algorithm.
- VertexList: represents a list of VertexInfo objects; if V is a VertexList, V[i] is the vertex information for vertex i.
- Code is available to load adjacency information from a file.
You may add helper functions if you like; for example, I wrote a find_min_unknown function to return the index of the vertex with known = false and minimum distance value from a VertexList.
You do not need to use a min-heap for the minimum vertex selection required by Dijkstra's algorithm. You may instead use a simple linear search.
The file graph1.txt contains the adjacency matrix:
-1 10 -1 5 12 7
10 -1 2 2 -1 -1
-1 2 -1 3 -1 -1
5 2 3 -1 -1 1
12 -1 -1 -1 -1 4
7 -1 -1 1 4 -1
(-1 represents no connection.)
A correctly implemented dijkstra function will
result in the provided framework printing
. 10 . 5 12 7 10 . 2 2 . . . 2 . 3 . . 5 2 3 . . 1 12 . . . . 4 7 . . 1 4 . Node | Dist. | Path -----+-------+-------- 0 | 0 | 0 1 | 7 | 0 -> 3 -> 1 2 | 8 | 0 -> 3 -> 2 3 | 5 | 0 -> 3 4 | 10 | 0 -> 3 -> 5 -> 4 5 | 6 | 0 -> 3 -> 5 |
First it prints the adjacency matrix, then it prints the shortest path results. While this sample file is useful for testing your code, your function must work for any valid adjacency matrix with nonnegative edge weights.
You should not modify any existing code in the provided framework; simply complete the dijkstra function and possibly add a few other helper functions.
In this project you will program the artificial intelligence for an object modeling a Reversi player. Your player object must be compatible with the sample code provided. Your team's player will compete in a tournament against players from other teams.
Note: This project is a longer term project. There will be shorter problems assigned to be done concurrently with this project.
- Part 1
Team assembly and project orientation
- Self assemble into teams of 3. Familiarize
yourself with the Reversi game
(see
Wikipedia's Reversi entry).
One person on your team should email me your team
roster and team name. All team members
should begin keeping an electronic log of
their individual work on the project. In your log
(best kept on a spreadsheet) list the date,
activity, and time spent for that activity.
- Part 2
Preliminary Coding
Due Tuesday, March 30
[2 points]
- Demonstrate that your team has the basic Reversi
common codebase working. Both the interactive and
random players should be working. The code is
available
here.
- Part 3
Basic AI Strategy
Due Tuesday, April 6
[5 points]
- Submit a brief (1-2) description of your team's
brainstorming ideas for your player's AI
strategy. You are not committed to any of these
ideas, and your ideas will not be revealed to
other teams.
- Part 4
Reversi Tournament
Wednesday, April 21
[5 points]
- The detailed tournament rules will appear later.
- Part 4
Player Source Code
Due Wednesday, April 21
[10 points]
- Submit your player's source code at the end of the
tournament.
- Part 5 Log of Individual Activity Due Wednesday, April 21 [5 points]
- Submit a printed copy of your individual log of
work you did on the Reversi project. Hours and
fractions thereof should be listed and totalled.
- Part 6 Brief (1-2 page) description of your AI strategy Due Wednesday, April 21 [5 points]
- Document the exact strategy you used in
implementing your tournament player.
Explain the heuristics you used, and describe any
search techniques involved. Indicate the
data
structures and algorithms you employed
and justify their inclusion.
Diagrams are appropriate. Your write up should be
interesting, informative (to CS majors), and
attractive enough to be posted on the bulletin
board in the CS hallway for all to see.
(Individual names can be removed from the bulletin
board exhibit if you wish.)
You are welcome to make a
poster, but that is not required.
- Part 7
Peer Review Form and Presentation
Due Friday, April 23
[5 points]
- Submit a completed peer review form for each
teammate other than yourself.
Be prepared to give to
the class
a 10 minute overview of your
AI strategy, coding cleverness, and lessons
learned along the way.
Chapters 4-7 Practice
These are practice problems not to be handed in.
4.1, 4.2, 4.3, 4.4, 4.5, 4.8, 4.21, 4.25, 4.32, 4.33
5.1, 5.8
6.1, 6.2, 6.3
7.1, 7.2, 7.19
Chapter 7
Implement each of the following sorts as individual functions that accept a vector of integers:
- Selection sort
- Insertion sort
- Shellsort
- Heapsort
- Quicksort
Use a Stopwatch object to time the execution of each of the functions for vectors of size 10, 100, 1000, 10,000, and 100,000. Include a table summarizing the results.
Chapter 6
Heap Priority Queue Due Tuesday, March 9
You will implement a priority queue using an array-based binary heap.
Create the minheap.cpp file that implements the methods specified in the file minheap.h. The comments indicate what the methods do and what parameters they expect. The file test_heap.cpp is provided for your convenience for testing your code.
As usual, you may not modify minheap.h. Your minheap.cpp file should be perfectly compatible with minheap.h. Please submit only your minheap.cpp file to eclass.
Chapter 5
Hash Table Due Tuesday, February 23
You will implement a hash table that can use either linear or quadratic probing to resolve collisions. You are not to use external chaining with linked lists for this assignment.
Create the hashtable.cpp file that implements the methods specified in the file hashtable.h. The comments indicate what the methods do and what parameters they expect. The file test_hashtable.cpp is provided for your convenience for testing your code.
As usual, you may not modify hashtable.h. You are encouraged to modify test_hashtable.cpp--for example, use the hashpjw function, experiment with quadratic probing, and use a bigger (prime-sized) table.
Your hashtable.cpp file should be perfectly compatible with hashtable.h. Please submit only your hashtable.cpp file to eclass.
Chapter 4
AVL Tree Due Tuesday, February 16
Create the avl_tree.cpp file that implements the un-implemented methods specified in the file avl_tree.h. The comments indicate what the methods do and what parameters they expect. The file test_avl.cpp is provided for your convenience for testing your code.
Note: You may adapt the code found in your textbook, but be aware the author's insert method expects a node pointer passed by reference and the function does not return anything. In contrast, my code (and, therefore, your code) expects simply a node pointer; the function returns a node pointer result through which the client would update the actual parameter. Also, you will need to provide the symmetric rotations that the author omitted--because of the symmetry involved they are not difficult to write.
Chapter 3
Multilists Due Tuesday, February 2
A multilist is a linked structure that allows data to be sorted in more than one way. For example, a set of records containing an identification number (int) and a name (string) can be stored simultaneously in numerical order by ID and lexicographical order by name.
The following figure shows a typical node within a multilist sorted by ID numbers and names:
Given the Multilist interface multilist.h and sample client code testmultilist.cpp, provide the multilist implementation (multilist.cpp) that completes the program. You may not change multilist.h.
A name will contain only alphabetic characters, and not contain spaces. The input of names may contain a mixture of capitalized and uncapitalized letters within the names, but the printed names should be in all upper case. The printing methods traverse the multilist in the appropriate way, printing each record as follows:
- Each record (name, ID pair) is printed on its own line
- The pair is printed within parentheses, name first,
then ID number, with a comma in between, without
any spaces; for example, the following
sequence of commands
+ 145 Fred + 200 Wilma + 300 Betty + 85 Barney + 420 Dino + 50 Pebbles m
issued to the testmultilist.cpp program would output
Printing by name reverse (WILMA,200) (PEBBLES,50) (FRED,145) (DINO,420) (BETTY,300) (BARNEY,85)
Chapter 1
- Page 39, Exercise 1.1 The selection problem Due Friday, January 15
- Provide two different implementations (functions)
based on
the two descriptions found on page 1.
Your program should get its input from a text
file.
The format of the
file is N k n1 n2 n3 ..., where
- N is the number of integers to be considered
- k corresponds to k in the problem.
- n1, n2, n3, ... is the list of integers; there will be N of these. The list contains no duplicates.
Your program should output two numbers: the kth largest element in the data set as determined by the two different functions. Your program should produce no other output.
For this assignment you need not worry about malformed data files.
You may use the sample inputs found at http://perl.cs.southern.edu/repository/Misc/314/Assignments/Chapter01/1.1/. You'll see in one file the sample input has 100 integers, and you are looking for the 24th largest integer. In the other file you will find the 130th largest element amongst 1000.
In Excel or Word produce a table comparing the running times of both implementations on lists of sizes 100, 1000, 10000, 50000, 100000, 200000, and 500000. Any data files you construct yourself should comply with the above format with no duplicate elements.
You may use a Stopwatch object to time the execution of the functions.
- Page 40, Exercise 1.12 A proof concerning summations Due Tuesday, January 19
- Do part a only. Prove this for all
integers > 0 by mathematical induction.
- Page 40, Exercise 1.13 C++ templates as containers Due Wednesday, January 20
- Your template code should appear in a header file
named collection.h to be #included
by clients.
Here are details for the methods:
- isEmpty takes no parameters and simply returns true or false depending on the contents of the collection.
- makeEmpty takes no parameters and returns nothing.
- insert accepts a single generic object as an argument. It returns true if the object could be inserted; otherwise, it returns false. An element may not be added to a collection that is full. Attempting to insert into a full collection does not alter the collection.
- remove accepts a single generic object as an argument. If an object equalling the parameter is in the collection, it removes the first occurrence of it. If the object is not there, the collection is unaffected. The method returns true if successful (removed an element); otherwise, it returns false (did not remove anything).
- contains accepts a single generic object as a parameter and returns true or false depending on whether or not the object is present in the collection.
The class should have a contructor that fixes the collection's size at the time of the collection's creation; this makes array management easier (no need to dynamically reallocate the array as the program runs).
A simple test file is provided on at http://perl.cs.southern.edu/repository/Misc/314/Assignments/Chapter01/1.13/. (You will find a makefile there as well if you want to use the command line compiler.) Your template class should work with the test file. This test program performs minimal checking; you should perform more exhaustive tests yourself.