Laboratories for
Introduction to Data Structures and Algorithms II
- Lab1
- Accessing your server account
- Determine your NT server account. We will determine this by opening a DOS window and "pinging" YourUserName.web.lynchburg.edu.
>PING YourUserName.web.lynchburg.edu
Your server name should be studentserv.lynchburg.edu.
- Verify your username and password by logging into the network
- Verify that your "P:" drive exists.
- Use "My Computer" to access your P: drive and create a folder called CS242.
- Create a text file with an ordinary text editor and save the file there.
- Use WS-FTP to connect to studentserv.lynchburg.edu
- If you are not in your server directory (same as your P: drive) then change directory to People and you will see a list of users. From there move to your own main directory and then to the class subdirectory and you should see the text file you created.
- Next you will grant me (roussos_c) full control to this (and only this) folder so that I can grade your assignments.
- Right click on your CS242 folder and click on Properties.
- Click on the Security Tab and then click on "Add"
- In the box at the bottom of the window, erase the content and type in login-domain\roussos_c
- Click OK. This should add me to the list of users/groups who have access to your CS242 folder.
- Next, highlight roussos_c and click on "full control"
- Always be sure to log yourself out before leaving a public PC. Otherwise anyone who accesses that PC will have full access to all of your files.
- Lab2
- Heaps and Heapsort
In this lab we will learn how to implement a heap utilizing a complete binary tree. The heap can then be used to implement a priority queue.
Next we will learn how to program Heapsort. Heapsort is an order N*log(N) sort that utilizes a Heap.
- Lab3
- Finding the Median of a List Efficiently
In this lab we will use a partition function to find the median of a list of numbers. We will, then, analyze the algorithm for best case, worst case and average case order of complexity. Finally we will extend our median finder into a sorting algorithm called median sort.
- Lab4
- Efficient Sorting Algorithms
In this lab we will investigate programming several efficient sorting algorithms. These will include QuickSort, ShellSort, RadixSort, BucketSort and BinSort.
- Lab5
- InsertSort - One more time
Since InsertSort plays a role in several other optimized sorts (ShellSort, QuickSort, MergeSort and others) we will
- more closely analyze InsertSort's behavior.
- analyze a modification of InsertSort that first finds the insert point using a linear search and then inserts the new item
- analyze a modification that finds the insert point using a binary search and then inserts the new item.
- Compare the running time of the above and
- Compare the running time to QuickSort for small data sets.
- Lab6
- Create a Visual C++ Project to implement a graph.
- Launch Visual C++
- Click on File and then New to create a new project. The project creation wizard will aid in setting up the various files and directories required for a new project.
- Select the Projects tab if it is not already selected. Then select "Win32 Console Application". Ensure that the directory selected is your course subdirectory. Give the project the name FindLarg. Note that the Create New Workspace option button is on. After typing in the project name the project name will be appended to the directory name. I.e., each new project we create will be located in its own Workspace, located in its own directory whose name will be the name of the project.
- The next window the project creation wizard presents asks what kind of Console Application you would like. Click on an empty project and then click on Finish. The wizad will inform you that no program source files have been created. We will create one next.
- At the bottom of the Workspace window (on the left) click on File View and you should see directory icons for Source, Header and Resource files. None of these contain any files yet. At this stage we are only concerned with Source files. Source files contain C++ source code.
- Next, click on Project, then Add to Project and then New to create a new source file. Select the Files tab if it is not already selected and then select C++ Source file. Fill in the file name box with Graph. Note that the add to project check box is checked and then click OK.
- You should now see an editing window for Graph.cpp and the Source directory icon in the left Workspace window should have a plus sign next to it. Click on the plus sign and you should see that Graph.cpp is now part of your project.
- Click on File and then Save All to save your work so far.
- Next we will deisign the ADT for Graphs and Edges, write the source code for Graph and test it. Graph will contain a main driver program that will call graph operations. Graph will create a graph from a list of edges.
- Clicking on the Build icon will build (compile and link the necessary files) the project and clicking on ! (the run icon) will run the program.
- More details will be given in lab.
- Lab7 - Write a C++ program that creates classes for nodes, edges and graphs. I.e., we will be creating ADTs for nodes, graphs and edges.
The program's first major functions will be the following:
- Read a graph file that contains the number of nodes in the graph, a flag that indicates whether the graph is directed and a list of edges into our internal graph representation consisting of the following:
- a graph which is an array of nodes, together with the number of nodes and a "directed" flag.
- a node which consists of two components; a string of information about the node and a pointer to a list of incident edges.
- an edges that consists of the edgeweight, the destination node and a pointer to the next edge in the list.
We will discuss this more fully in lab.
- Lab8 - Here is a C++ program that uses the random number generator. The random number function in this program allows the caller to specify a range for the random numbers. You will need the random number generator for some of the exercises above. The C++ random number generator's seed function depends on the clock and sometimes does not produce a good set of random numbers when called multiple times in succession since the PC clock does not change very frquently. Here is another program that includes a modification of the seed function to produce better results and a random number function that returns a random number between 0 and a user-defined limit.
- Lab9 - In this lab we will write a function to generate a random tree and another to generate a random graph. Pseudocode for algorithms given in this file include the generation of random trees & graphs
Top of this page 
Home page 
