Assigned: Monday July 26 2021 Due: 5:00PM, Friday August 6 2021 Clear, neat and concise solutions are required in order to receive full credit so revise your work carefully before submission, and consider how your work is presented. If you cannot solve a particular problem, state this clearly in your write-up, and write down only what you know to be correct. For involved proofs, first outline the argument and then delve into the details. 1. (10pts) Give a θ(n)-time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for the list itself. 2. (10pts) Suppose that we are storing a set of n keys into a hash table of size m. Show that if the keys are drawn from a universe U with |U| > nm, then U has a subset of size n consisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is θ(n). 3. (10pts) What is the difference between the binary-search-tree property and the min-heap property (see page 153)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Show how, or explain why not. 4. (10pts) Write the TREE-PREDECESSOR procedure. 5. (10pts) Consider a binary search tree T whose keys are distinct. Show that if the right subtree of a node x in T is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x. (Recall that every node is its own ancestor.) 6. (10pts) An alternative method of performing an inorder tree walk of an n-node binary search tree finds the minimum element in the tree by calling TREE-MINIMUM and then making n ? 1 calls to TREE-SUCCESSOR. Prove that this algorithm runs in θ(n) time. 7. (10pts) We can sort a given set of n numbers by first building a binary search tree containing these numbers (using TREE-INSERT repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm? 1 8. (10pts) Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees? 9. (10pts) Let (u, v) be a minimum-weight edge in a connected graph G. Show that (u, v) belongs to some minimum spanning tree of G. 10. (10pts) Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is nonhamiltonian.
Overview These activities challenge you to attempt wide ranging tasks of skills in order to gain exposure to using many different tools and techniques. Through these experiences, you will be gaining familiarity with more independent thinking. Descriptions of each lab give an idea of what to deliver, your job is to figure out how to complete it. Decisions will be made along the way as you work on completing tasks. A couple of hints here and there may be provided to help guide you on a productive path but by no means intended to restrict you. The best way to ‘figure things out’ is to actively discuss trade-offs of options with your classmates. The important thing is to recognize the essence of each task, so that you deliver quality work. What you turn in should clearly (1) delineate what your objective is/was and how you went about achieving that, and (2) the work you completed. Together this is presenting your project planning alongside your work. Developing Technical Proficiency Questions will arise along the way while you complete tasks, since much of it will be new to you. If your question starts with “what is…'' or “how to….”, these are good candidates to find answers via research 2 , such as with a search engine. Not knowing how to complete a task is an opportunity to practice solving a new problem. Technical expertise in problem solving is a matter of several components, namely: fluency in articulating the problem, laying out possible options with their trade-offs, then presenting the best option and rationale for the selection. Using this document You should have the permissions to comment on this document. To make a comment on a google doc: highlight text, add comment (a '+' icon), then write your question in that box. Disclaimers - With each lab (with exception to group activities), problem scope described can be further refined by you. Project planning is the skill you’re practicing with each lab (which is further broken down into technical tasks). - Exams may contain questions that are drawn from any of the tasks described in this document. Frequently asked questions: ? What is the grading rubric for assignments? Unless specified otherwise for a particular task, scoring is on a scale of weak or strong effort. Tasks are worth 2pts unless otherwise noted. ? Do I have to complete all the tasks listed in each lab? Please read the overview section above for breakdown of scoring. 2Brooklyn College Librarians have a helpful guide titled Getting Started with Research that explains general advice on conducting research to any topic. They also have another helpful guide Evaluating Sources that advises on evaluations of credibility of your sources. ? Can I useto create the files? Yes. You may decide how you are to complete tasks for each Lab. Use any text editor or program of your choice as long as you can save the right kinds of files. It would be ideal to discuss with your classmates the pros and cons of using each tool. ? I already have a github account. Can I use that? Yes. ? Can I save these tasks in dif erent files? Dif erent repositories? Yes. It’s a good idea to split each of the tasks into a different folder. Software developers should be conscious of organizing files such that it’s easy to find things again. ? I have my own web server, can I use that instead of github pages for hosting? Yes. ? I have my own domain name, can I use that? Yes. Lab 1: The Software Development Environment Task 1.1. Professional Readiness Reflection Task Objective: Prepare an essay describing the skills you believe to be important to excelling in the profession of, i.e. software engineer. What are example scenarios where those skill(s) are used? Include a reflection of where you feel you have room to improve on each of the skills. If you were to pick one of the skills to work on immediately, which would it be and why? How would you get to the next level? How will you know you’ve reached the level expected as a full professional? Grading rubric: Scoring for this task is primarily based upon readability, and adhering to length requirements (1-2 pages, single spaced or 3-5 pages double spaced). If any visuals are accompanied (i.e. screenshots, charts, etc) do not count that towards page length. Please cite any sources used with a proper citation format. If it is written in the style of an FAQ format it will count as weak effort. Instructions on Submitting this task: Upload your PDF file to this link by the due date, Thursday before class. It would help to see your filename containing the substring ‘Task1.1’ http://www.dropbox.com/request/OUNJ77OYXmheB4W2uKsX Task 1.2. Decentralized VCS practice with Git Task Objective: Show the process for creating a new Git repository on your machine. Add a new file to be tracked by the repository, commit changes. Slightly modify the file (to create a versioning diff), then commit the changes. Be nice to your future self by writing a descriptive commit message for your log. Upload the changes to a GitHub Repository3 . Grading rubric: Using a GUI to complete this task is eligible up to 1 point. Showing the terminal equivalent commands used in the terminal interface is eligible for 2 points. Same scoring breakdown for weak vs strong effort apply. Instructions on Submitting this task: 3 The word GitHub is used in this task to denote your VCS hosting platform of choice that is compatible with Git. Before you begin the task you'll need to have Git installed on your machine (the machine you want to have connected with GitHub). The first time you connect a machine with GitHub you will have to save your SSH keys to your GitHub account. Fill out this form (http://forms.gle/b3yzeFS3PsQ2xqM76). There is a field on the form where you can provide the URL to your GitHub repository. Task 1.3. Group activity (4 points) Task Objective: Collaboratively produce a tutorial on a technical skill. The tutorial can be any format, such as written instructions and/or video presentation to the class. Cite any sources used On Monday, you will be given time to split into groups and pick a topic. On Thursday every group will present and also will share with the class a link to their tutorial. Please keep notes on how you work together, that will come in handy for the next lab. Topic Suggestions Grading Rubric: Scoring is based on tutorial topic, scope, and presentation (both presentation of the tutorial itself and the class presentation). Strong effort means going above and beyond the descriptions/suggestions provided in the ‘Topic Suggestions’ page and also lab description. Strong effort also indicates ensuring accuracy of contents, using proper citations and the like. Instructions on Submitting this task: Fill out the PDF form (task1.3) that can be found at http://bit.ly/3140su1b, follow instructions on that page for submitting. Only one copy per group needs to be submitted.