week1tak

pdf

School

Brigham Young University, Idaho *

*We aren’t endorsed by this school

Course

381

Subject

Computer Science

Date

Nov 24, 2024

Type

pdf

Pages

Uploaded by PrivateStarPartridge3

WEEK 01 Name: Bridger Hackworth Collaborators (if any): 1. Tasks 1.1. Determine Correct Order. If you browsed the text, Levitin discuses 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) Understand the problem. (2) Decide on: computational means, exact vs approximate solving, data struc- ture(s), algorithm design technique. (3) Design an algorithm. (4) Analyze the algorithm. (5) Prove correctness of the algorithm. (6) Code the algorithm. 1.2. Before you can start doing anything you need to know what your goal is, so you first must understand the problem. Deciding on: also goes along with deciding what your goal is. Next you can start solving the problem. Designing the algorithm in pseudo-code is also like creating a goal for your code. Next look over your work, anazlyze and make sure that it works. If it does, now go ahead and spend the time coding it. In lecture, we discussed the birthday problem. Provide your own pseudo-code for solving the birthday problem. 1. Interview each student for their birthday to have a record, while keeping each birthday in a fixed order on the record. 2. Survey the record with eyes. Start at the first birthday and then check if all subsequent birthdays are the same as first birthday. a. if yes return the two matching students 3. Repeat step 2 with the 2nd birthday, 3rd birthday, etc. until the 2nd to last birthday is reached, only checking subsequent birthdays to the current birthday being tested each time. Date : September 17, 2023. 1

2 WEEK 01 2. Week 01 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 offers 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 be- coming Berrys first customer. (a) Given a linked list containing the names of the 2n kids, in order of the orig- inal 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. Start a counter i at n + 1 2. j = i + 1 3. Switch the i th item’s pointer to point to the j th item. 4. Increase i and j by one 5. Repeat steps 3 and 4 until j > 2 n . (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: - any additional linked list nodes - any other non-constant-sized data structures ################## # YOUR CODE HERE # ################## # assuming L.size gives the total amount of nodes

WEEK 01 3 # L.head returns a node object # nodeObj.next returns the next node object in line n = L.size/2 # get node object at n+1 spot i = 0 current = L.head while n >= i: current = current.next i+=1 # go one step past nth node # 1st iteration previous = current current = current.next next = current.next previous.next = None current.next = previous # finish the rest of the nodes while next: previous = current current = next next = current.next current.next = previous return

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

Related Documents

CS 4402 LJ 3.edited.docx

Long Quiz 003 - (5).png

CHEVENING ESSAY QUESTIONS AND ANSWERS.docx

Screenshot 2023-11-29 at 7.51.34 PM.png

2022-Study-Guide-for-Form-N-400.pdf

disc21-regular-sols.pdf

010-160 Exam – Free Actual Q&As, Page 2 _ ExamTopics.pdf

CIS 123 - 1.3 Guided Practice Lab Report .docx

LearningJournal3.docx

PHOTO-2023-12-14-10-49-40 (3).jpg

Project_Three_Daniel Williams_Option 1.docx

Screenshot (1150).png

Recommended textbooks for you

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

Np Ms Office 365/Excel 2016 I Ntermed

Computer Science

ISBN:9781337508841

Author:Carey

Publisher:Cengage

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE

Computer Science

ISBN:9780357392676

Author:FREUND, Steven

Publisher:CENGAGE L

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

Programming Logic & Design Comprehensive

Computer Science

ISBN:9781337669405

Author:FARRELL

Publisher:Cengage

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

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

SEE MORE TEXTBOOKS

Recommended textbooks for you

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