User Account

All Pages

Small program on Algorithms , Data Structure & Algorithms

Assignment Help:
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 open-ended. 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 e-mail 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 e-mail. 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 e-mail 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 "input-2.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 input-2.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 "output-2.txt" containing 5*k lines, mi,j for i in 1,2,... k and j in 1,2,...5. The output file corresponding to input-2.txt is output-2.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.

Related Discussions:- Small program on Algorithms

Operations on sequential files, Insertion: Records has to be inserted at t...

Insertion: Records has to be inserted at the place dictated by the sequence of keys. As is obvious, direct insertions into the main data file would lead to frequent rebuilding of

SORTING ALGORIthm, the deference between insertion,selection and bubble sor...

the deference between insertion,selection and bubble sort

State algorithm to insert node p at the end of a linked list, Algo rithm t...

Algo rithm to Insert a Node p at the End of a Linked List is explained below Step1:   [check for space] If new1= NULL output "OVERFLOW" And exit Step2:   [Allocate fr

Explain insertion procedure into a b-tree, Ans: I nsertion into the B...

Ans: I nsertion into the B-tree: 1.  First search is made for the place where the new record must be positioned. As soon as the keys are inserted, they are sorted into th

Explain what is stack. describe ways to execute stack. , ST AC K is ...

ST AC K is explained as follows : A stack is one of the most usually used data structure. A stack is also called a Last-In-First-Out (LIFO) system, is a linear list in

Cache simulator, how to design a cache simulator with 4-way set associative...

how to design a cache simulator with 4-way set associative cache

Chaining Method as Method of Collision Resolution , Q. The given values are...

Q. The given values are to be stored in a hash table 25, 42, 96, 101, 102, 162, 197 Explain how the values are hashed by using division technique of hashing with a table

A bst is traversed in which order recursively, A  BST is traversed in the ...

A  BST is traversed in the following order recursively: Right, root, left e output sequence will be in In Descending order

Road transport booking system, what algorithms can i use for the above titl...

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

Elaborate the symbols of abstract data type, Elaborate the symbols of abstr...

Elaborate the symbols of abstract data type length(a)-returns the number of characters in symbol a. capitalize(a)-returns the symbol generated from a by making its first cha

Write Your Message!

Captcha
Order Assignment

Featured Services

Order Now

Popular Subjects

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +91-977-207-8620

Phone: +91-977-207-8620

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd