data structures and algo homework help

Boost your journey with 24/7 access to skilled experts, offering unmatched data structures and algo homework help

Trusted by 1.1 M+ Happy Students

4.4Trust Pilot

4.4Edu Reviewer

5App Review

4.8Student

WhatsApp Support

Get Instant
Online Homework Help
via WhatsApp

Get instant homework help from top tutors—just a WhatsApp message away. 24/7 hw help support for all your academic needs!

★★★★★

2M+ students trust TutorBin

Your WhatsApp Number

⚡ Instant reply

🔒 100% private

👨‍🏫 Top tutors

🌍 All subjects

^*Get instant homework help from top tutors—just a WhatsApp message away. 24/7 support for all your academic needs!

2M+ Students Helped24/7 Live SupportExpert TutorsAll Subjects CoveredInstant Response100% ConfidentialTop Rated ServiceMoney-back Guarantee2M+ Students Helped24/7 Live SupportExpert TutorsAll Subjects CoveredInstant Response100% ConfidentialTop Rated ServiceMoney-back Guarantee

Recently Asked data structures and algo Questions

Expert help when you need it

Q1:CSE 240 - Assignment 5 Points: 50 pts Topics: . C/C++ Syntax · Pointers . Dynamic Allocation of Memory · Data Structures: Linked Lists · Object Orientation Overall Specifications: You are to create a Doubly-LinkedList data structure from scratch. This should be Templated so that any data could be stored within it. You are creating a data structure here from scratch. You may use std: : string (#include <string>) if needed. You may use other built-in structures to support your algorithms but you are creating your own LinkedList. The primary goal of this assignment is to make a LinkedList that you can use and re-use. The data structure itself is the majority of the specifications grade. Specifications Scoring Breakdown: You are eligible for these points in the Specifications part of the rubric if you accomplish: . Templated Linked List & Zombie Conga makes you eligible for 100% of the Specifications points · Adjusted grading: o A fixed-type Linked List penalizes -15% o Not having the Zombie Conga penalizes -15% . You should provide a thorough test of your linked list functionality . Note: We will be running your Linked List through our own test cases o This means you can create an Integer based Linked List with a THOROUGH test file and still be eligible for 70% of the Specifications points. · A Templated Linked List without Zombie Conga is eligible for 85% of the Specifications points · A Zombie Linked List with a Zombie Conga is eligible for 85% of the Specifications points Eligibility level Templated Linked List Fixed Type List (Zombie/int) Zombie Conga Thorough Test 100% X X X 85% X X 85% X 70% X X The rest of the rubric is graded as normal. Programming Assignment: Instructions: In this assignment, you will create your code from scratch. Stay within the bounds of what we've covered in class. You are to use functions in this assignment. All of the algorithms should be coded by you. Code the algorithms from scratch. Don't just find a library to solve the problems for you. Filename: Filenames are dependent on which options you complete: Templated Linked List (with Zombie Conga) . hw5 _< lastname> _< firstname>. cpp · linkedlist _< lastname>. hpp · zombie _< lastname>.h · zombie _< lastname>. cpp · Makefile Untemplated Linked List (with Zombie Conga) . hw5 _< lastname> _< firstname>. cpp · linkedlist _< lastname>.h · linkedlist _< lastname>. cpp · zombie _< lastname>.h · zombie _< lastname>. cpp · Makefile Templated Linked List (NO Zombie Conga) · linkedlist _< lastname>. hpp . hw5 _< lastname> _< firstname>. cpp · Makefile Untemplated Linked List (NO Zombie Conga) · linkedlist _< lastname>. h · linkedlist _< lastname>. cpp . hw5 _< lastname> _< firstname>. cpp · Makefile Makefile: . The makefile is required so we can easily compile your code . Your makefile should produce an executable named exe Library allowances: You may use std: : string (#include <string>) if necessary. Code Style: For yours, the instructors', and the graders' sake, keep your code well organized. Use proper indentation, variable names, and segmentation. * BIG GIANT NOTE - TEMPLATES AND FILES When you use a templated type in C++, ALL templated code must be done in the . hpp file. This means that ALL of your methods will be defined in the .hpp file as well as your class. You should still forward declare Classes above and then implement the Methods below. Your .hpp file should have both, your LinkedList and Node classes, and their method definitions. Remember to use your :: operator correctly. Feel free to use friendship if needed. Tutorial - Exception Handling With data structures, often we must deal with PEBCAK errors (Problem Exists Between Chair and Keyboard). If we include a method in a Linked List that has the user add "at an index" we must account for that user giving a bad value, such as a negative number or one that is too large. C++ has added exception handling to the std :: namespace and it is fairly similar to Java exception handling. Syntax: try { / / code goes here } catch (/*exception type*/) { } //catch code We raise an exception with the throw command: throw <message>; A big difference between Java and C++ is that you can throw just about anything. throw "an error happened"; throw std: : out of range () ; throw -1; Examples: #include <iostream> using std: : cout; using std: : cin; using std: : endl; int divide (int numerator, int denominator) { if (denominator = 0) { throw std: : runtime error ( "Can't divide by zero!") ; } return numerator / denominator; } int main (int argc, char const *argv [ ] ) { int numerator; int denominator; cout << "Enter two values: "; cin >> numerator >> denominator; try { int test = divide (numerator, denominator) ; } catch (const std: : runtime error& err) { std: : cerr << err.what () << '\n'; #include <iostream> using std: : cout; using std: : cin; using std: : endl; int divide (int numerator, int denominator) { if (denominator = 0) { throw "Can't divide by Zero!"; } return numerator / denominator; } int main (int argc, char const *argv [] ) { int numerator; int denominator; cout << "Enter two values: "; cin >> numerator >> denominator; try { int test = divide (numerator, denominator) ; } catch (const char* messsage) { std: : cerr << messsage << '\n' ; } } return 0; } return 0; } std namespace exceptions Exception Description std: : exception Exception and parent class of all standard C++ exceptions. std: : bad alloc Generally thrown by new. std: : bad cast Generally thrown by dynamic_cast. std: : bad typeid Generally thrown by typeid. std: : bad exception Useful device to handle unexpected exceptions. std: : logic failure Can be detected by reading code. std: : runtime error Cannot be detected by reading code. std: : domain error Thrown when using a mathematically invalid domain. std: : invalid argument Thrown when using invalid arguments. std: : length error Thrown when a large std: : string is created. std: : out of range Thrown by the at method. std: : overflow error Thrown when a mathematical overflow occurs. std: : range error Thrown when attempting to store an out-of-range value. std: : underflow error Thrown when a mathematical underflow occurs. For the sake of Exception Handling in this assignment, you should be able to use the std namespace exceptions Zombie Conga Party! Description: You are going to create a silly Zombie Conga Line using your Linked List. Each node is going to store a Zombie in it. Zombies can be Red, Yellow, Green, Blue, Magenta and Cyan. Every turn you will randomly generate a Zombie object and an action. You will then perform that action using the Zombie object as the parameter for that action. Linked List You will create a Doubly-LinkedList Class and a Node Class. The LinkedList should contain the following methods in its public interface: NOTE: T stands for the template data type, so T data means the variable of type T (whatever T is) . Constructor · Destructor . AddToFront (T data) : void - create a node containing T data and add it to the front of the list . AddToEnd (T data) : void - create a node containing T data and add it to the end of the list . AddAtIndex (T data, int index) :void - create a node containing T data and add it to the list at index. The new node containing the data will be the #index node in the list. Throws std: : out_of_range exception if index is less than zero or greater than the size of the list . AddBefore(Node<T>*, T data) :void - create a node containing T data and add it before a particular node . AddAfter(Node<T>*, T data) :void - create a node containing T data and add it after a particular node . RemoveFromFront () :T - Delete first item and return its contents . RemoveFromEnd () :T - Delete last item and return its contents . RemoveTheFirst(T data) : void - find first instance of T data and remove it · RemoveA110f (T data) : void - find each instance of T data and remove it . RemoveBefore(Node<T>*) :T - delete the node before a particular node, return its contents . RemoveAfter(Node<T>*) :T - delete the node after a particular node, return its contents . ElementExists(T data) :bool - Returns a T/F if element exists in list . Find (T data) : Node<T>* - Look for data in the list, return a pointer to its node . IndexOf (T data) : int - returns an index of the item in the list (zero-based) , returns -1 if the item is not in the list. . RetrieveFront:T - returns the data contained in the first node, does not delete it . RetrieveEnd:T - returns the data contained in the last node, does not delete it Retrieve(int index) :T - returns the data contained in node # index, does not delete • it. Throws std: : out_of_range exception if index is less than zero or greater than the size of the list . PrintList: void - Loop through each node and print the contents of the Node . Empty: void - Empty out the list, delete everything . Length: int - How many elements are in the list Linked List contd More methods private or public should be created as needed to facilitate the functionality of the Interface methods. If you feel your list needs more functionality, feel free to create it. Node Class · Properties o -data:T o -next:Node<T>* o -previous: Node<T>* • Methods o +Node () o +Node (T) o +Node (T, Node<T>*) o +getData() :T o +setData(T) :void o +getNext():Node<T>* o +setNext(Node<T>*) :void o +getPrevious () : Node<T>* o +setPrevious(Node<T>*) :void · Friend (optional) o LinkedList class The node class should be fairly rudimentary. Ideally, it should be templated so you can store anything in it. Zombie Class · Properties o -type : char · Methods o +Zombie () o +Zombie(char) o +getType () :char o +operator ==: bool · Friend o ostream& operator << (ostream&, const Zombie&) The Zombie class is very simple, don't give it any more work to do. Conga (class?) You can create a class for your Conga or you can create a set of functions. Spelling it out for you: You should create the following classes: 1. LinkedList 2. Node 3. Zombie Your Nodes should store Zombies. Your LinkedList is made of Nodes. Actions If you chose to make a Conga class, then these actions should be methods of your Conga class. Methods don't need the list passed in since the linked list should be a property of the Conga class. If you are not making a Conga class, then these actions should be functions. · Engine! o This zombie becomes the first Zombie in the conga line o Suggested function: · void engine_action (LinkedList<Zombie> list, Zombie randomZomb) · Caboose ! o This zombie becomes the last zombie in the conga line o Suggested function: · void caboose_action(LinkedList<Zombie> list, Zombie randomZomb) . Jump in the Line! o This zombie joins the conga line at position X where X <= length of the linked list o Suggested function: . void jump_in_action (LinkedList<Zombie> list, Zombie randomZomb) · Everyone Out! o Remove all matching zombies from the linked list o Suggested function: " void everyone_out_action(LinkedList<Zombie> list, Zombie randomZomb) . You Out! o Remove the first matching zombie from the linked list o Suggested function: " void you_out_action (LinkedList<Zombie> list, Zombie randomZomb) · Brains! o Generate two more matching Zombies and add one to the front (engine_action), one to the end (caboose_action) and one to the middle (round down) . o Suggested function: . void brains_action (LinkedList<Zombie> list, Zombie randomZomb) . Rainbow Brains! o Perform an engine_action on the zombie that was generated o Add one of each zombie color to the end via caboose_action in this order: Red, Yellow, Green, Blue, Cyan, Magenta o Suggested function: . void rainbow_action(LinkedList<Zombie> list, Zombie randomZomb) · Making new Friends! o Find the first Zombie of this color in line. · Do a coin flip - if rand() % 2 == 0 then insert before, else insert after. o If no Zombie of that color exists, then perform caboose_action on the zombie o Suggested function: . void friends_action (LinkedList<Zombie> list, Zombie randomZomb) Notes These actions are external to the Linked List. They are accomplished by calling Linked List methods. These actions are not part of your Zombie class. Zombies are very simple classes and have no responsibility for Conga actions. Note on Random calls: Don't call a random number unless you actually need to !! If you call too many randoms, your output will not match the Gradescope! . The one that people mess up the most is on the Making New Friends action. Don't flip the coin until you know you need to! ! Setting up the List: Set up the initial Conga Line by running these actions: 1. Run a Rainbow Brains! Action 2. Run 3 Brains actions User Interface: Command line argument: Add a command line option -s <integer> to allow the user to provide a seed for the random number generator. This seed value should be given to srand (<int>) . If no -s option is given, then seed the random number generator with time: srand(time(0)); Console input: . Ask the user how many rounds they want to run. . Run the conga party for that many rounds o Start with round 0 o Every time round % 5 == 0 - delete the first and last zombie in the linked list o Choose your action with rand() % 8 . Keep the actions in the order show previously o Choose your zombie with rand() % 6 . Use the order: Red, Yellow, Green, Blue, Cyan, Magenta Run that action with your chosen zombie o . If the conga line ever empties completely due to an action tell the user that the Party is Over. . Once the number of rounds has finished. Ask the user if they want to continue the party or end. . If they choose to continue ask them for a new number of rounds to run. Output: Each round you'll output the entire Linked List. You can represent each zombie as a single character corresponding to their color (R, Y, G, B, M, C) . You'll show the zombie generated and the action generated. Then you'll show the outcome of the action. The output should follow this pattern (see sample output for example) : Round: < round number> Size: < list size> :: [<R| Y | G | B | M | C>]= ... New Zombie: [<R|Y|G| B|M| C>] -- Action: [<Engine! | Caboose! | Jump In! | Everyone Out ! | You Out ! | Brains! | Rainbow! | New Friends ! >] The conga line is now: Size: < list size> :: [<R|Y|G|B|M| C>]= * * ** Hints: . Start by building an Integer version of the doubly linked list. It will get you points if you can't get other things to work and it will be easier to transition to the template after getting all the functionality of the data structure solid. . Build robust constructors and use them! Your Node and your Zombie will benefit highly from good constructors. . Do yourself a favor and overload the == operator in your Zombie. It will make life easier! . Overload the cout for your Zombie. It'll make your printList method easier. . You might consider making the Conga its own class so you can make each of the actions a method in the conga class. Extra Credit: +2 - Color your Zombies in the output. If you use termcolor (https://github. com/ikalnytskyi/termcolor) you must do std: : cout << termcolor: : colorize at the beginning of your program for the color to display correctly on grade scope, otherwise the graders won't see it and you won't get credit. +3 - Zombie Fight! Add a command line argument -EC to run this extra credit. If the program is run with -EC, create a Zombie Conga, but don't prompt the user for how many rounds they want to run. Just arbitrarily run 1000 rounds for them. After that ... Create an array with the counts for each Zombie type. (I suggest writing a function to do this). Then pick 2 random indexes to send zombies to fight each other. "Roll a d6" (rand() % 6) for each zombie and apply any modifier. This table shows who has an advantage when two colors face. If a color has an advantage multiply its roll by 1.5. Whoever has the highest roll wins the fight, reduce the count of the losing Zombie color by 1. Continue until one color remains and announce the winner! The same color should never fight itself. R Y G B C M R X Y X G X X B C X X NOTE - If you didn't do the Zombie Conga you can still do this extra credit! When you program is run with the -EC ... create the array and fill each index with ((rand() % 100) + 50) and then LET THEM FIGHT M Sample output: Round: 0 Size: 16 :: [R]=[M] =[G] =[R]=[R]=[G]=[G]=[R]=[M] =[B] =[Y] =[M] =[C] =[G] = [M] = [R] New Zombie: [B] -- Action: [Engine! ] The conga line is now: Size: 17 :: [B]=[R]=[M]=[G]=[R]=[R]=[G]=[G]=[R]=[M]=[B]=[Y] =[M] =[C] =[G] = [M] = [R] Round: 1 Size: 17 :: [B]=[R]=[M]=[G]=[R]=[R]=[G]=[G]=[R]=[M] =[B]=[Y] =[M] =[C] =[G] =[M] = [R] New Zombie: [M] -- Action: [Engine! ] The conga line is now: Size: 18 :: [M]=[B]=[R]=[M]=[G]=[R]=[R]=[G]=[G]=[R]=[M]=[B]=[Y] =[M] =[C] =[G] = [M] = [R] Round: 2 Size: 18 :: [M]=[B]=[R]=[M]=[G]=[R]=[R]=[G]=[G]=[R]=[M]=[B]=[Y] =[M] =[C] =[G] =[M] =[R] New Zombie: [C] -- Action: [Caboose! ] The conga line is now: Size: 19 :: [M]=[B]=[R]=[M]=[G]=[R]=[R]=[G]=[G]=[R]=[M]=[B]=[Y]=[M]=[C]=[G] =[M] =[R] =[C] * Round: 3 Size: 19 :: [M]=[B]=[R]=[M]=[G]=[R]=[R]=[G]=[G]=[R]=[M]=[B] =[Y] =[M] =[C] =[G] =[M] =[R] =[C] New Zombie: [Y] -- Action: [Rainbow! ] The conga line is now: Size: 26 : : [Y]=[M]=[B]=[R]=[M]=[G]=[R]=[R]=[G]=[G]=[R]=[M]=[B]=[Y]=[M]=[C]=[G]=[M]=[R]=[C]=[R]=[G]=[B] =[Y] =[M] =[C] **** ** Round: 4 Size: 26 : : [Y]=[M]=[B]=[R]=[M]=[G]=[R]=[R]=[G]=[G]=[R]=[M]=[B]=[Y]=[M] =[C] =[G] =[M] =[R] =[C] =[R] =[G] =[B] = [Y] =[M] = [C] New Zombie: [Y] -- Action: [Brains! ] The conga line is now: Size: 29 : : [Y]=[Y]=[M]=[B]=[R]=[M]=[G]=[R]=[R]=[G]=[G]=[R]=[M]=[B]=[Y]=[Y]=[M]=[C]=[G]=[M] =[R] =[C] =[R] =[G] =[B] =[Y]=[M]=[C]=[Y] ... continue for the # of rounds the user asks for Grading of Programming Assignment Turn your files into Gradescope. Make sure to follow the file naming guide so your project can be properly compiled and tested. This project will have an auto grading component. Rubric: Levels of Achievement Criteria A Specifications 100 % The program works and meets all of the specifications B C D E U F 85 % The program works and produces the correct results and displays them correctly. It also meets most of the other specifications. 75 % The program produces mostly correct results but does not display them correctly and/or missing some specifications 65 % The program produces partially correct results, display problems and/or missing specifications 35 % Program compiles and runs and attempts specifications, but several problems exist 20 % Code does not compile and run. Produces excessive incorrect results 0 % Code does not compile. Barely an attempt was made at specifications. 0 % Code is incomprehensible Weight 50.00% Code Quality 100 % Code is written clearly 85 % Code readability is less 75 % The code is readable only by someone who knows what it is supposed to be doing. 65 % 35 % The code is poorly organized and very difficult to read. 20 % Code uses excessive single letter identifiers. Excessively poorly organized. Weight 20.00% Code is using single letter variables, poorly organized Documentation 35 % Comments are poor 20 % Only the header comment exists identifying the student. 0 % Non existent 0 % Code is incomprehensible What to Submit? Follow the instructions in the Filenames section of the specification and turn those files into Gradescope. Weight 15.00% 100 % Code is very well commented 85 % Commenting is simple but solid 75 % Commenting is severely lacking 65 % Bare minimum commenting Efficiency Weight 15.00% 100 % The code is extremely efficient without sacrificing readability and understanding 85 % The code is fairly efficient without sacrificing readability and understanding. 75 % The code is brute force but concise. 65 % The code is brute force and unnecessarily long. 35 % The code is huge and appears to be patched together. 20 % The code has created very poor runtimes for much simpler faster algorithms. Academic Integrity and Honor Code. You are encouraged to cooperate in study group on learning the course materials. However, you may not cooperate on preparing the individual assignments. Anything that you turn in must be your own work: You must write up your own solution with your own understanding. If you use an idea that is found in a book or from other sources, or that was developed by someone else or jointly with some group, make sure you acknowledge the source and/or the names of the persons in the write-up for each problem. When you help your peers, you should never show your work to them. All assignment questions must be asked in the course discussion board. Asking assignment questions or making your assignment available in the public websites before the assignment due will be considered cheating. The instructor and the TA will CAREFULLY check any possible proliferation or plagiarism. We will use the document/program comparison tools like MOSS (Measure Of Software Similarity: http://moss.stanford.edu/) to check any assignment that you submitted for grading. The Ira A. Fulton Schools of Engineering expect all students to adhere to ASU's policy on Academic Dishonesty. These policies can be found in the Code of Student Conduct: http://www.asu.edu/studentaffairs/studentlife/judicial/academic_integrity.h tm ALL cases of cheating or plagiarism will be handed to the Dean's office. Penalties include a failing grade in the class, a note on your official transcript that shows you were punished for cheating, suspension, expulsion and revocation of already awarded degrees./nInstructions for submitting the solution 1. Submit the source code file for every programming assignment like .c file, .java file. 2. If any dataset is used then you need to share all the files with solution in a single zip file. 3. Share the readme file in which you have to include the system specification, required software and the execution instructions. 4. Share the output of the programs. If it is a single program then you can submit the screenshot, if multiple files are included then please share the screen recording. Below are some steps that need to be covered in screen recording. Show the complete solution according to the instructions. Need to cover all the compilation steps. Show the complete output of program/ project. * Show all pass test cases if given in assignment. 5. Always add proper comments in code. If any specific package is used then please mention it in comment./nalso when you guys are creating the different files to code in please code in these 5 files hw5_zhang_theodore.cpp linkedlist_zhang.hpp zombie_zhang.h zombie_zhang.cpp Makefile/n/n/n/n/nSee Answer
Q2:/nDeadline: Friday 10 November 2023 Part 1 Part 2 Total / 60 / 40 / 100 GUIDELINES 1. Your document must be written in LATEX, using the provided LATEX, sources, including the completed cover page. You should submit all your documents in an archive named assign- ment2.zip via Moodle. This archive should contain : — The PDF version of your assignment. - The LATEX, sources required to generate the PDF version of your assignment. — The code for your programs with the appropriate file extensions. 2. Every response must be accompanied by a justification. If this is not the case, a score of 0 will be assigned, regardless of the correctness of the response. 3. Late Submission Policy : Penalty of 2 points out of 100, where m is the number of minutes of delay (equivalent to 10 points for 24 hours). PART 1 - We have a square matrix M, n x n, n ≥ 1, with rows and columns indexed from 0 to n - 1, containing integer values. We want to determine the maximum length of a path that starts at position [0, 0] and reaches either a cell in column n - 1 or a cell in row n - 1. The length of a path is the sum of the encountered elements. The rules are as follows : - The starting point must be the cell [0, 0]. - The next step chooses a neighboring element in the same row, the same column, or diagonally if it exists. For example, if you are at cell [2,3], the next element can be either cell [2,4], [3, 4], or [3,3], assuming that n > 4. - The path ends when either the last row or the last column is reached. The length of the path is the sum of the numbers encountered during the journey. — Here's an example : 1 4 3 -6 5 0 4 2 -3 3 -1 1 The maximum length of a course is 40. Here, there are four courses that give 40 : [0, 0][1, 0][2, 0][3, 0][4, 0][4, 1][4, 2][4, 3][4, 4][5, 5] -1 3 1 9 4 -3 11 2 -10 11 0 -17 9 8 0 1 2 4 [0, 0][1, 0][2, 0][3, 0][4, 0][4, 1][4, 2][5, 2] [0,0][1, 0][2, 0][3, 0][4, 0][4, 1][5, 1] -2 8 8 4 2 5 [0, 0][1, 0][2, 0][3, 0][4, 0][4, 1][5, 2] The naive algorithm involves generating all possible paths, calculating the length of each one, and determining the maximum. It can be shown that the number of possible paths is given by : 2 k=0 (" Fn-1 (n-1) (n-1+k). Here are some values for different values of n to give you an idea of the growth rate. n 5 6 7 321 1683 8989 48639 8 9 1462563 10 11 8097453 45046719 12 (a) (5 points) List all the paths, with their lengths, for the matrix 4 2 -1 0 2 7 -1 5 3 Answer : DO NOT DELETE THIS LINE AND REPLACE THIS PHRASE WITH YOUR ANSWER (b) (15 points) Let ci,j be the maximum length of a path starting from the cell [0, 0]. Establish a recursive scheme for the computation of Ci,j, 0 ≤ i, j < n. Do not forget the base cases and the boundary conditions. Answer : (c) (2 points) Establish the solution (the maximum length of a route) according to the ci,j. Answer : (d) (8 points) Provide the pseudo-code (not code !) of the recursive algorithm that determines the maximum length of a path starting from the cell (0,0) and gives one of the paths of maximum length. Answer : (e) (3 points) Estimate the complexity of your recursive algorithm. You may use the §2 notation but try to have a bound not too far from reality. (An answer like §2(1), Q(logn), or even $2(nk) is not acceptable as it is not close enough). Page 2 Numb 1 3 13 1 2 3 4 63 265729 Answer : (f) (10 points) From the recursive scheme, provide the pseudo-code (not code !) of an algorithm that uses dynamic programming. Answer : (g) (3 points) Give the complexity of your algorithm using dynamic programming. Answer : (h) (8 points) Describe in pseudo-code (not code!) a greedy algorithm to solve the same problem. Explain why it is a greedy algorithm. Answer : (i) (3 points) Give the complexity of your gluttonous algorithm. Answer : (j) (5 points) Does your algorithm always produce a solution ? When it determines a solution, is it optimal ? Answer : PART 2 - You will need to program your three algorithms (recursive, dynamic programming, greedy). You will compare the results obtained with each of the three algorithms and conduct an empirical study of their performance. (a) (20 points) Design a program that will read the matrix M from a file. The first line of the file will contain the value of n ≥ 1. The following lines will contain the rows of the matrix, with elements separated by at least one space. The program must execute your three algorithms with the matrix and provide the maximum length and one of the paths of this maximum length. You must submit a few executions. (b) (20 points) Design a second program that will compare the execution times of your three algorithms for n =1,2,3, 4, .... Here, the answer returned by your algorithms is not impor- tant but the execution time is (the content of the matrices is not important and they will be filled in the program (see later for an example)). Determine what is the value of n from which the execution time is too long (I leave it to you to judge what that means!) for each of your three algorithms. Make graphs for the execution time, as a function of n for each of the three algorithms. Make a link between these graphs and the complexity of each of your algorithms. Discuss the results obtained. Page 3 Your programs should be written in Java, C++, or Python. You must specify the compiler with which your program was compiled and on which platform. You should provide me with the source code. In case of any issues, it is your responsibility to convince me that your code works, and not my responsibility to convince you that your code does not work, if applicable. Voici le code LaTeX pour votre texte en anglais, en respectant l'indentation : "latex Examples of Code 1 1.1 Execution Time Calculation Java long beforeTime; long afterTime; double elapsedTime; beforeTime = System. currentTimeMillis(); / / calculation ... afterTime = System. currentTimeMillis () ; elapsedTime = afterTime - beforeTime; You can also use System. nanoTime () instead of System. currentTimeMillis (). A nanosecond is equal to 10-9 seconds. C++ #include <ctime> #include <iostream> using namespace std; clock_t beforeTime; // time before calculation clock_t afterTime; / / time after calculation double elapsedTime; // time required for calculation beforeTime = clock(); // calculation . . . afterTime = clock() ; elapsedTime = (double) (afterTime - beforeTime) / (double) CLOCKS_PER_SEC; Python from time import time Page 4 beforeTime = time(); // time in milliseconds // calculation ... afterTime = time () ; 1.2 To generate matrices with random content in Java private static Random generator = new Random ( 0 ); // in java.util Returns a random number uniformly distributed between a and b inclusively. * precondition: a <= b (otherwise, the generated numbers will no longer be uniform) * @param a minimum value * @param b maximum value */ private static int random ( int a, int b ) { return (int) Math. floor ( ( b - a + 1 ) * generator.nextDouble () ) + a; } / / random / ** * Generates an n X n square matrix of random integers between inf and sup incl. * @param n: dimension of the matrix * @param inf minimum value of generated numbers * @param sup maximum value of generated numbers */ public static int [] [] randomMatrix ( int n, int inf, int sup ) { int [] [] answer = new int [n] [n] ; for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { answer [i] [j] = random ( inf, sup ) ; } } return answer; } 1.3 Example of Speed Tests in Java public static void speedTest ( int n ) { int [] [] matrix = randomMatrix ( n, 0, 9 ); long beforeRec = System.nanoTime () ; // call the method using the recursive algorithm long afterRec = System.nanoTime () ; long beforeDynProg = System.nanoTime () ; // call the method using the dynamic programming algorithm long afterDynProg = System.nanoTime(); Page 5 long beforeGreedy = System.nanoTime () ; // call the method using the greedy algorithm long afterGreedy = System. nanoTime () ; System. out. println ( "n = " + n , + " + (afterRec - beforeRec) /1000.0 (afterDynProg - beforeDynProg) /1000.0 + + " , " + ", " + (afterGreedy - beforeGreedy) /1000.0 ) ; } Page 6See Answer
Q3:Problem 2 (10 pt.) Find the shortest paths from node 1 to all other nodes on the following graph using Dijkstra's algorithm.See Answer
Q4: Instructions for submitting the solution 1. Submit the source code file for every programming assignment like .c file, .java file. 2. If any dataset is used then you need to share all the files with solution in a single zip file. 3. Share the readme file in which you have to include the system specification, required software and the execution instructions. 4. Share the output of the programs. If it is a single program then you can submit the screenshot, if multiple files are included then please share the screen recording. Below are some steps that need to be covered in screen recording. ❖ Show the complete solution according to the instructions. ❖ Need to cover all the compilation steps. Show the complete output of program/project. Show all pass test cases if given in assignment. 5. Always add proper comments in code. If any specific package is used then please mention it in comment./nSee Answer
Q5: Guidelines and Rubric Overview In this computer science course, you will have the opportunity to explore introductory types of coding and the computational thinking that computer scientists engage in when they design solutions to social and business problems. As you work through the requirements and constraints of certain problems, you will choose the data structures, algorithms, and program organizations you need to achieve optimal, accurate results. In addition, you will explore some of the most important topics in contemporary computer science. Thinking about who you are and who you want to be in relation to those topics will ultimately help you build a professional computer science identity. These are the fundamental building blocks you will take with you as you progress into more advanced and complex computer science courses. There are two parts to the final project in this course. In the first part, you will choose three activities you have completed during the course and gather them into a collection of problem-solving activities. One activity will demonstrate input/output problem solving using flowcharts, another will demonstrate the creation of control structures, and the last will be an activity of your own choosing something that you found particularly interesting or challenging. In the second part of their final project, you will write a professional reflection on who you are and who you want to be in the computer science field. By positioning yourself in relation to key topics in contemporary computer science, you will begin a professional journey into this dynamic discipline. The project is divided into three milestones, which will be submitted at various points throughout the course to scaffold learning and ensure quality final submissions. These milestones will be submitted in Modules Three and Five. The final product will be submitted in Module Seven. In this assignment, you will demonstrate your mastery of the following course outcomes: • Develop a fundamental computer scientist identity through reflecting on the role of computer science and scientists in modern society ● ● ● Explain how data structures and algorithms inform the way computer scientists think about data and its organization Apply basic programming best practices to essential computer science tasks Develop basic problem solving skills in a programming context using industry standard tools Final Project Part I Prompt In the first part of your final project, you will collect three different activities that represent three different problems that you grappled with during this course. The first activity should represent input/output problem solving using flowcharts, the second activity should be related to the creation of control structures, and the third activity should be a problem of your choice that you found particularly interesting or challenging. Using the feedback provided by your instructor and your peers, you will address any issues and make them as perfect as you can. You will annotate your code and submit the text files using Python best practices. Specifically, the following critical elements must be addressed: 1. Submit your input/output activity that uses a flowchart or pseudocode. Note that this is where you submit our flowchart or pseudocode. A. Describe the programming best practices you used in accurately completing this task by annotating your code: Include where best practices were implemented and why you used them. B. Explain the problem-solving approaches you employed while completing this task. Include this information in your code annotations, and be sure to address the tool(s) you used to complete this task. C. Explain in your code annotations why the algorithm and data structure you ultimately chose to accurately complete this task provided the most efficient solution to this problem. II. Submit your control structures activity. A. Describe the programming best practices you used in accurately completing this task by annotating your code: Include where best practices were implemented and why you used them. B. Explain the problem-solving approaches you employed while completing this task. Include this information in your code annotations, and be sure to address the tool(s) you used to complete this task. C. Explain in your code annotations why the algorithm and data structure you ultimately chose to accurately complete this task provided the most efficient solution to this problem. III. Submit an activity of your choice that you found particularly interesting or challenging. A. Describe the programming best practices you used in accurately completing this task by annotating your code: Include where best practices were implemented and why you used them. B. Explain the problem-solving approaches you employed while completing this task. Include this information in your code annotations, and be sure to address the tool(s) you used to complete this task. C. Explain in your code annotations why the algorithm and data structure you ultimately chose to accurately complete this task provided the most efficient solution to this problem. Milestones Milestone One: Collection of Problem-Solving Activities In Module Three, you will submit pseudocode or a flowchart for a basic input/output program. This milestone will be graded with the Milestone One Rubric. Milestone Two: Control Structures and Chosen Topic Significance In Module Five, you will submit a control structure activity a description of the significance of your chosen topic in contemporary computer science. This milestone will be graded with the Milestone Two Rubric. Final Submission: Collection of Problem-Solving Activities (Part I) and Professional Reflection (Part II) In Module Seven, you will submit your final project. It should be a complete, polished artifact containing all of the critical elements of the final product. It should reflect the incorporation of feedback gained throughout the course. This submission will be graded with the Final Project Rubric.See Answer
Q6:7. [10 points] A polynomial P(x) with a single indeterminate x is written in the form: P(x) = x) = Σ a¡x¹ = a„x²¹ + a₁-x²¹−¹ + ... + a₂x² + a₁x + ª i=0 where a; for all i € [0, n] is a real constant. Assume that a; = A[i] for all i. We want to compute the univariate polynomial P(x) at a specific value of x. (i) Design a O(n²) algorithm EVALUATE POLY(A[0...n], x) to solve the problem. (ii) Design a O(n log n) algorithm EVALUATE POLY(A[0...n], x) to solve the problem. (Hint: Ideas from the slides are helpful) (iii) Design a O(n) algorithm EVALUATE POLY(A[0...n], x) to solve the problem. (Hint: Use Horner's method of representing the polynomial as follows.) P(x) = a₁ + x(a₁ + x(a₂ + x(A3 + ··· + x(a₂-1 + xan) · · ·)))See Answer
Q7:5. [10 points] Given a string S[1...2n] containing just the characters '(' and ')', de- sign an algorithm ISVALIDSTRING(S[1...2n]) to determine if the input string is valid. An input string is valid if the open brackets are closed in the proper order. Example: (()) is valid; (())() is valid; )()) is invalid; (())) is invalid; ()(( is invalid. (Hint: Use a stack to solve the problem.)See Answer
Q8:2. [10 points] Consider the algorithm called SIMPLESORT. Consider two example arrays of size 5 and show the array contents with values of i and j (approximately 25 steps for each example). Does this simple algorithm sort an array of unique elements? Does it sort an array even if there are duplicates? If the algorithm does sort, why do you think it sorts? If the algorithm does not sort an array give a counterexample and you will get 5 extra points as bonus points. SIMPLESORT(A[1...n]) 1. Input: Array to be sorted A[1...n] 2. Output: Sorted array in A[1...n] 3. for 1 to n do 5. 6. for j← 1 to n do if A[i] <A[j] then | SWAP (A[i], A[j])See Answer
Q9: Homework 5 Due February 22nd, at 2:30 PM 100 points CS 2235 Data Structures and Algorithms 1. Using the SinglyLinkedList class from the lectures (the code is posted on Moodle), use your code from Homework 4 to create a Scoreboard class that uses a singly linked list rather than the array from Homework 4. Repeat problems 1, 2 & 3 from Homework 4, using your new Scoreboard class. 2. Create a DoublyLinked List class using the SinglyLinked List class as a reference. Note*Hint* Pages 136-137 from the book contain much of the code and you are welcome to reference them; just make sure you understand it (these slides will be posted to Moodle for your reference). 3. Repeat Problem 1 again using your code from Homework 4. However, this time use the Doubly Liked List. (Again, only parts 1-3) As a note, there are several different approaches to this assignment. No one way is the definitive approach. Use the approach you are most comfortable with. Make sure to submit Java files for your SinglyLinkedList, DoublyLinkedList, GameEntry and both Scoreboards. As always, attach screenshots to demonstrate your code works. Note: Sorting with Linked List can be challenging. We have yet to really discuss the nature of sorting algorithms, so for this assignment your Linked Lists do not have to be sorted. Scoring 1. 10% - Code compiles without errors. 2. 25% - SinglyLinkedList class coded and used for first Scoreboard. 3. 15%- Scoreboard properly populated, with contents and summary printed using SinglyLinkedList. 4. 25%- DoublyLinkedList class coded and used for second Scoreboard. 5. 15%- Scoreboard properly populated, with contents and summary printed using DoublyLinkedList. 6. 10%- Meaningful comments and header and proper use of abstraction (Use methods! Do not fill your main with lots of code). See Answer
Q10: Homework 3 CSE 214: Data Structures State University of New York at Stony Brook Instructor: Prof. Pramod Ganapathi Total points = 100. Total questions = 3. Total pages = 1. Submit the single PDF on Brightspace before the deadline. Designing an algorithm means giving: (i) pseudocode covering all corner cases, (ii) diagrams to visualize the working of the algorithm (e.g. dry-run for some examples), (iii) time and space complexity analysis. 1. (a) [4 points] Draw the binary tree representation of the following arithmetic expression: (((5 + 2) × (2 − 1))/((2 + 9) + ((7 – 2) — 1)) × 8) (b) [6 points] Draw a binary tree T that simultaneously satisfies the following: (i) Each internal node of T stores a single character. (ii) A preorder traversal of T yields EXAMFUN. (iii) An inorder traversal of T yields MAFXUEN. 2. Given a binary tree: (a) [10 points] Design an efficient recursive algorithm COUNTNODES (Node curr) to count the number of nodes in the tree. (b) [10 points] Design an efficient recursive algorithm COUNTLEAF NODES(Node curr) to count the number of leaf nodes in the tree. (c) [10 points] Design an efficient recursive algorithm COUNTNONLEAF NODES (Node curr) to count the number nonleaf of nodes in the tree. (d) [10 points] Design an efficient recursive algorithm FINDHEIGHT(Node curr) to find the height of the tree. (e) [10 points] Design an efficient recursive algorithm ISBINARYSEARCHTREE (Node curr) to check if the tree is a binary search tree. (f) [10 points] Design an efficient algorithm to check if the array representation of a binary tree ISBINARYSEARCHTREE(A[1...n]) represents a binary search tree. 3. Given a binary search tree: (a) [10 points] Design an efficient recursive algorithm FINDMINIMUMNODE(Node curr) to find the node with the minimum key in the tree. (b) [20 points] Design an efficient recursive algorithm PRINTELEMENTSINRANGE(Node curr, [a, b]) to print all the elements in the tree that are in the range. 1See Answer
Q11:3. Consider the bottom most BST drawn on page 401 of section 3.2 of the text. In what order are the keys printed out in a post order traversal?See Answer
Q12:3. Given a positive integer n, i.e., n > 0, and a radix r, where r≥ 2, the following pseudo-code computes the number of symbols required to represent n with radix r. Note that r is an integer. Run-time per instruction Frequency 1. 2. 3. 4. num_symbols ← 1 while n>r n ←n/r num_symbols ← num_symbols + 1 C₁ C₂ C3 C4 (a) Fill in for each line of instruction, the number of times (i.e., frequency) the instruction is executed. (b) Derive the expression for the run-time of the pseudo-code in terms of n, r, and C₁, C₂, C3, and C4. See questions 1 and 2 on how the final expression should be written. The parameters "describ- ing" the problem are n and r.See Answer
Q13:1. Consider the following procedure that performs multiplication of two rectangular matrices A[1..1][1..m] and B[1..m][1..n]: MATRIX_MULTIPLY (A[1..[][1..m], B[1..m][1..n]) Run-time per instruction Frequency for i 1 to 1 for 1. 2. 3. 4. 5. 6. j1 to n Cij ←0 for k1 to m Cij ← Cij + aik bkj C₁ C₂ C3 C4 C5 C6 return C (a) Fill in for each line of instruction, the number of times (i.e., frequency) the instruction is executed. (b) Derive the expression for the run-time of MATRIX_MULTIPLY in terms of l, m, n, and C₁, C₂, C3, C4, C5, and C6. In your expression, you should group together all the coefficients of the same term 1¹.m³.nk, where i, j, k are constants. For example, if the run-time expression is C4lm+G+n+C5lm+Can+C₂, we group the co- efficients of 1¹m¹nº (or Im) together, the coefficients of lºmºn' (or n) together, and the coefficients of lºmºnº (or 1) together. Note that each of I'm'nº, lºmºn', and lºmºnº involves the parameters "describing" the problem, i.e., 1, m, and n. The final expression should be (C4+C5)lm+(+C6)n+(+C₂).See Answer
Q14:Q3: Based on the key-based weighted graph below, please apply Dijkstra's algorithm to search the shortest path starting from node A. 1). Show each step by table and, at each step, the calculation and the two sets of nodes and distances; one set for which shortest distances have been determined and the other set of the remaining nodes and distances. (20%) 2). Analyse the complexity of Dijkstra's algorithm. (5%) B x6 XO 8 x7 A x1 x2 C F 77 x3 x4 E x8 x5 D DSee Answer
Q15:Q1: Please operate your keys sequentially by Stack and Queue and show each step by tables. 1).push(x0), push(x1), push(x2), isEmpty(), peek(), pop(), pop(), push(x3), push(x4), size(), pop(), is Empty(); (10%) 2). enqueue(x5), enqueue(x6), enqueue (x7), isEmpty(), front (), dequeue(), dequeue (), enqueue (x8), enqueue (x9), size(), dequeue(), isEmpty(); (10%)/nQ1: Please operate your keys sequentially by Stack and Queue and show each step by tables. 1).push(x0), push(x1), push(x2), isEmpty(), peek(), pop(), pop(), push(x3), push(x4), size(), pop(), is Empty(); (10%) 2). enqueue(x5), enqueue(x6), enqueue (x7), isEmpty(), front (), dequeue(), dequeue (), enqueue (x8), enqueue (x9), size(), dequeue(), isEmpty(); (10%)See Answer
Q16:Question 1 - 10 points Simulated Robot Problem: Use dynamic programming to find the total number of distinct paths from the start to the end position. The robot can only move towards down or right direction. Also, the robot cannot go through road blockers (shaded areas). You must show how you fill the memorization table.See Answer
Q17:Problem 4. (25 points) Consider the problem of searching for genes in DNA sequences using Horspool's algorithm. A DNA sequence consists of a text on the alphabet {A, C, G, T} and the gene or gene segment is the pattern. a. Construct the shift table for the following gene segment of your chromosome 10: ТССТАТТСТТ b. Apply Horspool's algorithm to locate the above pattern in the following DNA sequence: TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTTSee Answer
Q18:Problem 2. (25 points) a. Construct a heap for the list 1, 8, 6, 5, 3, 7, 4 by the bottom-up algorithm. b. Construct a heap for the list 1, 8, 6, 5, 3, 7, 4 by successive key insertions (top-down algorithm). c. Is it always true that the bottom-up and top-down algorithms yield the same heap for the same input?See Answer
Q19:Problems for submission 1. Consider a set A = {a₁,..., an} and a collection B₁, B2,..., Bm of subsets of A (i.e. B, CA for each i). We say that a set HCA is a hitting set for the collection B₁, B2,..., Bm if H contains at least one element from each B that is, if HB; is not empty for each i (so H "hits" all the sets B₁). We now define the Hitting Set Problem as follows: We are given a set A = {a₁,..., an}, a collection B₁, B2,..., Bm of subsets of A, and a number k. We are asked: Is there a hitting set HCA for B₁, B2,..., Bm so that the size of H is at most k? (a) [4] Show that Vertex-Cover Sp Hitting-Set. (b) [1] Show that Hitting-Set is in NP.See Answer
Q20:2. Hidden multi-linear functions (part II) [12 points]. Let p be prime and n ≥ 2. Let a2,...,an € Zp and o: Z → Zp be any permutation (which means that the mapping σ is 1-to-1 and onto). Define f: (Z₂)" → Z, as f(x₁,x2,...,xn) = 0 (₁ + a₂x₂ + + ann mod p), (2) for all x₁, x2,..., In € Zp. Note that this is similar to the function in question 1, Eq. (1), except for these two notable differences: • In Eq. (2), the first coefficient is set to 1 (i.e., a₁ = 1). mod p • In Eq. (2), an arbitrary permutation on Z, is applied to a₁ + a22+ + Ann (whereas, in Eq. (1), the permutation is of the restricted form o(z)=z+ b mod p). Suppose that you are given access to a black-box that, on input (₁, 2,...,n) € (Z₂)", produces f(x₁,x2,...,n) as output, but you do not know what the linear coefficients a2,..., an are, nor the permutation o. Your goal is to determine the linear coefficients a₂....,an. For this question, it suffices to determine the answer with success probability at least 1-in all cases (i.e., for every instance f of the form of Eq. (2)). Give a quantum algorithm that solves this problem making only one f-query (with success probability at least 1-3). Explain why your algorithm works.See Answer

TutorBin Testimonials

I found TutorBin Data Structures And Algo homework help when I was struggling with complex concepts. Experts provided step-wise explanations and examples to help me understand concepts clearly.

Rick Jordon

TutorBin experts resolve your doubts without making you wait for long. Their experts are responsive & available 24/7 whenever you need Data Structures And Algo subject guidance.

Andrea Jacobs

I trust TutorBin for assisting me in completing Data Structures And Algo assignments with quality and 100% accuracy. Experts are polite, listen to my problems, and have extensive experience in their domain.

Lilian King

I got my Data Structures And Algo homework done on time. My assignment is proofread and edited by professionals. Got zero plagiarism as experts developed my assignment from scratch. Feel relieved and super excited.

Joey Dip

Popular Subjects for data structures and algo

You can get the best rated step-by-step problem explanations from 65000+ expert tutors by ordering TutorBin data structures and algo homework help.

TutorBin helping students around the globe

TutorBin believes that distance should never be a barrier to learning. Over 500000+ orders and 100000+ happy customers explain TutorBin has become the name that keeps learning fun in the UK, USA, Canada, Australia, Singapore, and UAE.