Login

Create Account
+14156709189
info@expertsmind.com
Submit Homework/Assignment
Get quote & make Payment
Get Solution
Small program on Algorithms , Data Structure & Algorithms
Objective
The goal of this project is to extend and implement an algorithm presented in the course and to apply notions introduced by the course to this program/algorithm. The assignment is relatively openended. The instructor will answer any question you may have. However, when in doubt, work toward the project goal stated above. This is an individual project. You may discuss it with other students, but the work you present must be your own only.
Deliverable
You will produce two items: (1) the code of the program specified below, and (2) a narrative of your work specified below. You will email both items to the TA (whose address will become available in the syllabus early in the course). The items will be transmitted as attachments to your email. The code will be formatted as ASCII text. The narrative will be formatted as either ASCII text or PDF. The deadline follows the rules of the homework, the beginning of the first lecture of the week following the assignment, except that you will email the material rather than bringing a hard copy to class. Late submission will be accepted up to 3 days and will be penalized at 10% a day.
Code spec
Your code will extend and implement the Knapsack Problem as presented in Section 8.2 of the textbook. The extension will become clear while describing the output. Your program is expected to read a file called "input2.txt" containing 3*k lines, li,j for i in 1,2,... k and j in 1,2,3. An example of input file is input2.txt. For any i, line li,1 contains n positive integers separated by a comma. They are the weights W1,W2,... of a Knapsack Problem instance with n items, where n is less than 100. Likewise, line li,2 contains n positive integers separated by a comma. They are the values V1,V2,... of the items whose weights are in the previous line. Finally, line li,3 contains a single integer, the knapsack capacity. No other characters beside digits and commas are in each line.
Your program is expected to write a file called "output2.txt" containing 5*k lines, mi,j for i in 1,2,... k and j in 1,2,...5. The output file corresponding to input2.txt is output2.txt. For i in 1,2,... k and j in 1,2,3, mi,j=li,j. Line mi,4 contains a single integer, the Knapsack Problem instance optimal solution. Line mi,5 contains a sequence of positive integers in increasing values. They are the indexes, starting with 1, of the items that make up an optimal solution. The general format of the output is the same as the format of the input. The extension with respect to the textbook algorithm is the generation of a set of items witnessing an optimal solution. If there is more than one set, any set is acceptable.
The weights, values, capacities and other parameters will be within reasonable ranges for a modern laptop or desktop. The programming language can be any of Java, Python, Ruby, C, and C++. Deliver all your code in a single file that can be compiled and executed on cs.pdx.edu. Your program should perform reasonably efficiently both in theory and in practice.
Narrative spec
The narrative is intended to show that you know and understand the aspects of the project related to this course, in particular, ability to: (1) extend and implement an algorithms, (2) relate theoretical complexity to practice, (3) code correct, readable and efficient programs, and (4) communicate your work clearly and concisely.
I would expect to find one or more of the following: (1) a description of the extension in the same style as the algorithm in the textbook, (2) a description of key data structures and algorithms used in the program, (3) the running time analysis of your algorithm/program, and (4) any benchmarking, profiling and/or testing employed for development.
Hints
You are encouraged to start your work early. Reading and writing the files are tasks that you already partially solved in Project 1. The Knapsack Problem is very easy to understand. Initially, you can implement a brute force program without computing the indexes. This will work for small problem instances. Then, you can replace the brute force approach with the dynamic programming approach presented in the textbook. Finally, you can introduce the extension. As the code evolves, you can use the previous version to test the current version''s correctness.
Posted Date: 10/30/2012 10:22:25 PM  Location : United States
Ask an Expert
Related Discussions:
Small program on Algorithms , Assignment Help, Ask Question on Small program on Algorithms , Get Answer, Expert's Help, Small program on Algorithms Discussions
Write discussion on Small program on Algorithms
Your posts are moderated
Write your message here..
Related Questions
How do you rotate a binary tree, How do you rotate a Binary Tree? Rot...
How do you rotate a Binary Tree? Rotations in the tree: If after inserting a node in a Binary search tree, the balancing factor (height of left subtree  height of right
Quicksort and bubble sort algorithms, Task If quicksort is so quick, w...
Task If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many sorting algorithms? Your
Data Structure, Ask consider the file name cars.text each line in the file ...
Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1read the file 2add each car which is repr
Need help with working out. I dont really get it, Suppose there are exactly...
Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr
What is a container taxonomy, What is A Container Taxonomy It's useful ...
What is A Container Taxonomy It's useful to place containers in a taxonomy to help understand their relationships to one another and as a basis for implementation using a class
Process of decision making under uncertainty, (a) Describe the steps involv...
(a) Describe the steps involved in the process of decision making under uncertainty. (b) Explain the following principles of decision making: (i) Laplace, (ii) Hurwicz. (c
Arithmetic expression, How to convert infix postfix and prefix??
How to convert infix postfix and prefix??
Insertion of a node into a binary search tree, A binary search tree is cons...
A binary search tree is constructed through the repeated insertion of new nodes in a binary tree structure. Insertion has to maintain the order of the tree. The value to the lef
What is Oscillating Sort?, For the Oscillating sort to be applied, it is ne...
For the Oscillating sort to be applied, it is necessary for the tapes to be readable in both directions and able to be quickly reversed. The oscillating sort is superior to the po
Adjacency matrix representation of a graph, An adjacency matrix representat...
An adjacency matrix representation of a graph cannot having information of : Parallel edges
Assignment Help
Accounting Assignment Help
Economics Assignment Help
Finance Assignment Help
Statistics Assignment Help
Physics Assignment Help
Chemistry Assignment Help
Math Assignment Help
Biology Assignment Help
English Assignment Help
Management Assignment Help
Engineering Assignment Help
Programming Assignment Help
Computer Science Assignment Help
IT Courses and Help
ExpertsMind Services
Online Tutoring
Projects Assistance
Exam Preparation
Coursework Help
Programming Courses
Engineering Courses
Why Us ?
~Experienced Tutors
~24x7 hrs Support
~Plagiarism Free
~Quality of Work
~Time on Delivery
~Privacy of Work