Data Structures and Introduction to Algorithms
Fall 2013
Programming Assignment 2
Singly and Doubly Linked Lists
Due on Sunday, December 2nd, 2013 By Midnight
Fall 2013
Objectives:
- Practice writing functions that manipulate singly and doubly-linked lists.
- Practice extending given implementations of data structures to suit certain applications.
- Practice writing functions that manipulate singly and doubly-linked lists.
- Practice extending given implementations of data structures to suit certain applications.
Question 1
Expand the template based Singly-Linked-list implementation we had in class, by implementing the following extra functions:
(a) Write a new function void Print() that prints the list values. [20 points]
(b) Write a new function bool isSorted() that tests whether the list is sorted in ascending order or not. [20 points]
(c) Write a new function void CleanRedundant(). The function scans the current list, cleans any redundant value (repeated value), and produces a new list with unique values. To get full credit for this part, you are not allowed to reserve any extra memory space such as a temporary list or an array, but you can use additional Node pointers. [40 points]
(d) Write a main function that uses the above List to create a list of floats and another list of integers. Perform the following operations: [20 points]
- Ask the user to input seven values inside each list.
- Use the Print function to print both lists.
- Use the isSorted function to test if each list is sorted or not and print appropriate messages indicating the sorting status of each list.
- Call CleanRedundant on both lists and print the values after that.
(b) Write a new function bool isSorted() that tests whether the list is sorted in ascending order or not. [20 points]
(c) Write a new function void CleanRedundant(). The function scans the current list, cleans any redundant value (repeated value), and produces a new list with unique values. To get full credit for this part, you are not allowed to reserve any extra memory space such as a temporary list or an array, but you can use additional Node pointers. [40 points]
(d) Write a main function that uses the above List to create a list of floats and another list of integers. Perform the following operations: [20 points]
(c) Write a new function void CleanRedundant(). The function scans the current list, cleans any redundant value (repeated value), and produces a new list with unique values. To get full credit for this part, you are not allowed to reserve any extra memory space such as a temporary list or an array, but you can use additional Node pointers. [40 points]
(d) Write a main function that uses the above List to create a list of floats and another list of integers. Perform the following operations: [20 points]
- Ask the user to input seven values inside each list.
- Use the Print function to print both lists.
- Use the isSorted function to test if each list is sorted or not and print appropriate messages indicating the sorting status of each list.
- Call CleanRedundant on both lists and print the values after that.
Question 2 [Bonus: 30 points]
[Using Doubly-Linked Lists to build Dual Ring Computer Network Topologies].
A network topology represents the way computer network devices are interconnected. It is the shape of the network. The Dual Network Topology is a well-known topology used to build a reliable network. The topology is distinguished by having two rings that go in opposite directions. One ring is the primary and another is backup. If something goes wrong in the primary line, the backup line is used. Below is an example of the ring topology:
A network topology represents the way computer network devices are interconnected. It is the shape of the network. The Dual Network Topology is a well-known topology used to build a reliable network. The topology is distinguished by having two rings that go in opposite directions. One ring is the primary and another is backup. If something goes wrong in the primary line, the backup line is used. Below is an example of the ring topology:
The idea of this question is to use the next pointer as a cable connection for the main ring, and the prev pointer as a cable connection for the backup ring.
Expand the template based double linked list implementation we had in class as follows:
(a) Implement a new template based class called DualRing. The class should inherit the DLL class and expand on it.
(b) Define a new function in that class called void ConvertToDualRing(). This function will convert a double link list into a dual ring. It should connect the next pointer of the tail with the head, and the previous pointer of the head with the tail. We assume that this function is called when we have 3 or more nodes. (you can assume that).
(c) Define a new function in that class called void FixFailedConnection(). This function detects if we have a problem in the primary ring (next pointers), and if yes, it fixes the problem by reconnecting the cable to the correct next node. A problem means a link has failed. To simulate a failure, any node with next pointer of value NULL indicates a failure link. Use the backup ring to detect and fix the problem.
Data Structures and Introduction to Algorithms
Fall 2013
Programming Assignment 1
Sorting and Asymptotic Complexity (Big-O)
Due Sunday, November 10th, 2013
Expand the template based double linked list implementation we had in class as follows:
(a) Implement a new template based class called DualRing. The class should inherit the DLL class and expand on it.
(b) Define a new function in that class called void ConvertToDualRing(). This function will convert a double link list into a dual ring. It should connect the next pointer of the tail with the head, and the previous pointer of the head with the tail. We assume that this function is called when we have 3 or more nodes. (you can assume that).
(c) Define a new function in that class called void FixFailedConnection(). This function detects if we have a problem in the primary ring (next pointers), and if yes, it fixes the problem by reconnecting the cable to the correct next node. A problem means a link has failed. To simulate a failure, any node with next pointer of value NULL indicates a failure link. Use the backup ring to detect and fix the problem.
Data Structures and Introduction to Algorithms
Fall 2013
Objectives:
In this project you will experiment with three different
sorting algorithms: Insertion Sort, Selection sort and Bubble Sort. The
objective of this project is to understand the relation between the theoretical
asymptotic complexities (Big-O) computed in class and the actual running
times for different kinds of input.
Description:
The enclosed source file sort.cpp contains a program that
reads two inputs: a letter specifying which sorting algorithm to use (I for
InsertionSort , S for SelectionSort and B for BubbleSort), and an integer
specifying the input size. For example, if the input parameters are I 1000, the
program will run InsertionSort with an input size 1000.
- Add your first name to the beginning of every output line. So, if your first name is Ahmad, the first line in the output when running Selection Sort should appear as:“Ahmad: Sorting Algorithm: Selection Sort”.
- Before building the program, it is highly recommended that you enable compiler optimizations in the production run by going to “Build” then “Set Active Configuration” then selecting Release.
- After building the program, run
it using the following three input sizes for each of the three sorting
algorithms: 10000, 100000 and 1000000.
Store the running times that you get in 3 Tables: one table for each sorting algorithm.
- After completing this baseline test, make the following modifications to the code:
- Modify InsertionSort such that the body of the inner loop has a single unconditional statement.
- Modify SelectionSort such that it avoids any unnecessary swaps, that is, it never swaps an array element with itself.
- Modify BubbleSort such that if, at any point during the sorting process, the array becomes sorted, the algorithm terminates as early as possible. You should do your checking with minimal impact on the running time.
- After making these modifications, rerun the program using the above three input sizes for each sorting algorithm.
What to Submit:
Your submission should include the following:
- The source code for the functions that you have modified. Do not submit the code for any function that you did not modify.
- A printout of the outputs for the test runs of the modified code with an input size of 10 elements. The printout should show correct input and output and your first name should appear in the beginning of each line in the output.
- Six tables summarizing the results (the running times in ms). For each sorting algorithm (Insertion, Bubble and Selection), there should be one table showing the results without your modifications and another one showing the results with your modifications.
- A report discussing the results and how they relate to the asymptotic complexities (Big O) studied in class and to the properties of each sorting algorithm. Your report should consist of 1-2 pages in which you compare the different algorithms against each other and the different input types against each other. This is a very important part of the assignment that each student should write in his/her own words
Grading Criteria:
Modifying the Code
|
30%
|
ABET outcomes: A, I, C
|
Running Time Tables (6 tables)
|
30%
|
ABET outcomes: A, I, C
|
Analysis and Report
|
40%
|
ABET outcomes: B
|
Bonus Work:
Modify the InsertionSort code to use binary search instead
of linear search to find the right position for the key. Then report the new
running time that you get and analyze your results in the report. Your analysis
should calculate the number of comparisons and the number of data moves for
both the original InsertionSort and your modified InsertionSort, then you
should use those calculations to explain the actual running times that you get.
:''''''''''(
ReplyDelete