Week_01 copy

pdf

School

Brigham Young University, Idaho *

*We aren’t endorsed by this school

Course

381

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by LieutenantPony1531

WEEK 01 1. Tasks 1.1. Determine Correct Order. If you browse the text, Levitin discusses the steps for algorithm creation. I believe these steps can be somewhat ordered to your preference. The steps for the best-known algorithm for creating algorithms are listed out of order here. What order should they be in according to your preference and why? (You can reference the text, however the steps are somewhat self explanatory so you can just order them and provide a short written description of why you ordered them in the way you did) (1) Decide on: computational means, exact vs approximate solving, data struc- ture(s), algorithm design technique. Here is the original layout: (2) Design an algorithm. (3) Understand the problem. (4) Prove correctness of the algorithm. (5) Analyze the algorithm. (6) Code the algorithm. Here is my own personal layout: (7) Understand the problem. (8) Design an algorithm. (9) Code the algorithm. (10) Analyze the algorithm. (11) Prove the correctness of the algorithm. 1.2. Write a short answer. In lecture, we discussed the birthday problem. Pro- vide your own pseudo-code for solving the birthday problem. Pseudo-code: ”’ function birthdayProblemSimulation(trials): countSameBirth- day = 0 for i from 1 to trials: birthdays = generateRandomBirthdays() if hasSameBirth- day(birthdays): countSameBirthday = countSameBirthday + 1 probability = countSameBirthday / trials return probability Date : January 9, 2024. 1

2 WEEK 01 function generateRandomBirthdays(): birthdays = [] for i from 1 to number o f p eople : day = randomlyChooseDay () //Randomlychooseadayoftheyear (1 - 365) birthdays.append ( day ) return birthdays function hasSameBirthday(birthdays): uniqueBirthdays = createEmptyArray(size: 365) for day in birthdays: if uniqueBirthdays[day] is true: return true else: unique- Birthdays[day] = true return false function randomlyChooseDay(): return randomInteger(1, 365) // Choose a ran- dom integer representing a day of the year ”’ 2. Exercises/Problems 2.1. Jen and Berry’s. Jen drives her ice cream truck to her local elementary school at recess. All the kids rush to line up in front of her truck. Jen is over- whelmed with the number of students (there are 2n of them), so she calls up her associate, Berry, to bring his ice cream truck to help her out. Berry soon arrives and parks at the other end of the line of students. He o ff ers to sell to the last student in line, but the other students revolt in protest: The last student was last! This is unfair! The students decide that the fairest way to remedy the situation would be to have the back half of the line (the n kids furthest from Jen) reverse their order and queue up at Berrys truck, so that the last kid in the original line becomes the last kid in Berrys line, with the (n+1)st kid in the original line becoming Berrys first customer. (a) Given a linked list containing the names of the 2n kids, in order of the original line formed in front of Jens truck (where the first node contains the name of the first kid in line), describe an O(n)-time algorithm to modify the linked list to reverse the order of the last half of the list. Your algorithm should not make any new linked list nodes or instantiate any new non-constant-sized data structures during its operation. (1) Find the middle node of the linked list. (2) Reverse the next pointers of the nodes from the middle node to the end of the list. (3) ADjust the pointers to merge the reversed half with the original list. (b) Write a Python function reorder students(L) that implements your algo- rithm. def reorder_students(L): Input: L | linked list with head L.head and size L.size Output: None | This function should modify list L to reverse its last half. Your solution should NOT instantiate:

WEEK 01 3 - any additional linked list nodes - any other non-constant-sized data structures ################## class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next def reorder_students(L): if not L or not L.next: return # Step 1: Find the middle node of the linked list slow = fast = L.head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next # Step 2: Reverse the next pointers of the nodes from the middle to the end prev = None curr = slow.next while curr: temp = curr.next curr.next = prev prev = curr curr = temp # Step 3: Merge the reversed half with the original list slow.next = prev first_half_end = slow second_half_end = prev # Adjust the pointers to merge the reversed half with the original list while second_half_end.next: temp1 = first_half_end.next temp2 = second_half_end.next first_half_end.next = second_half_end second_half_end.next = temp1 first_half_end = temp1

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

4 WEEK 01 second_half_end = temp2 return ################## return

Related Documents

Ocasio_assignment #1.docx

ISSC456_PPT_Ocasio_Miguel.pptx

2.3.8 practice questions.pdf

Larry -Watson Week 3 Writing Assignment Preliminary Field and Laboratory Testing 17 FEB 2020.docx

Larry -Watson Week 4 Assignment The Science of Evidence 24 FEB 2020.docx

CMIT 351 Project 2 Template.docx

Larry -Watson Week 1 Writing Assignment CSI EFFECT 3 FEB 2020.docx

CYB_300_Milestone_One_Worksheet_SG.docx

HW2 Solution.pdf

cs6350_reading_assignment1_vxt200001.docx

CSC522_HW2.pdf

ARCH+150+Midterm+SOLUTIONS+2022.pdf

Recommended textbooks for you

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE

Computer Science

ISBN:9780357392676

Author:FREUND, Steven

Publisher:CENGAGE L

Np Ms Office 365/Excel 2016 I Ntermed

Computer Science

ISBN:9781337508841

Author:Carey

Publisher:Cengage

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

Fundamentals of Information Systems

Computer Science

ISBN:9781305082168

Author:Ralph Stair, George Reynolds

Publisher:Cengage Learning

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

SEE MORE TEXTBOOKS

Recommended textbooks for you

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:9780357392676
Author:FREUND, Steven
Publisher:CENGAGE L
Np Ms Office 365/Excel 2016 I Ntermed
Computer Science
ISBN:9781337508841
Author:Carey
Publisher:Cengage
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Fundamentals of Information Systems
Computer Science
ISBN:9781305082168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage