tailieunhanh - Faculty of Computer Science and Engineering Department of Computer Science Part 1

.Faculty of Computer Science and Engineering Department of Computer Science Part 2. Stack Suppose that the following algorithms are implemented: - PushStack (ref s , val n ): push the value n to the stack s - PopStack(ref s , ref x ): remove the top element of the stack s and assign the data of that top element to x - EmptyStack(val s ): check whether the stack s is empty Required Questions Question 3. Imagine we have two empty stacks of integers, s1 and s2. Draw a picture of each stack after the following operations: 1: 2: 3: 4:. | Faculty of Computer Science and Engineering Department of Computer Science DATA STRUCTURES ALGORITHMS Tutorial 1 Questions COMPUTATIONAL COMPLEXITY Required Questions Question 1. Reorder the following efficiencies from the smallest to the largest a. 2n3 n5 b. 2000 c. 4n 1 d. n4 e. n-1 f. nlog2 n b g f d a c e g. 2klogk n k is a predefined constant Question 2. Determine the big-O notation for the following a. 2n6 O nx6 b. 100n 3 7 O n c. 9lc g2 n O iog2 n d. 5110 2logn O nA10 e. n k k is a predefined constant z O n f 100log2 n 5 n 2n O n Question 3. Calculate the run-time efficiency of the following program segment 1 i n-1 2 loop i n 2 1 j 1 2 loop j n 2 1 print i j O nA 2 j j 2 nzv 3 end loop 4 i i - 2 3 end loop Question 4. Calculate the run-time efficiency of the following program segment 3 1 i n 2 loop i n 2 1 j 1 2 loop j n 2 1 print i- j n 4 log2 nA3 2 j j 2 3 end loop_ 4 i i 2 nlog2 n 3 end loop Released on 24 08 2012 20 06 39 1 4 Faculty of Computer Science and Engineering Department of Computer Science Question 5. If the algorithm dolt has an efficiency factor of 2n calculate the run time efficiency of the following program segment 1 i 1 2 loop i n 1 j 1 2 loop j n 1 k 1 2 loop k n 1 dolt . 2 k k 2 3 end loop 4 j j 1 3 end loop 4 i i 1 3 end loop Question 6. nA3 log2 n 40 2A1024 10A-9 Given that the efficiency of an algorithm is 2nlog2 nv if a step in this algorithm takes 1 nanosecond 10-9 how long does it take the algorithm to process an input of size 1024 Question 7. Write a recurrence equation for the running time T n of g n and solve that recurrence. Algorithm g val n integer Pre n must be greater than 0 Return integer value of g corresponding to n 1 if n 1 2 else1 return 1 . Un Un-1 1 1 return g n - 1 1 End g U1 1 O n Released on 24 08 2012 20 06 39 2 4 Faculty of Computer Science and Engineering Department of Computer Science Advanced Questions Question 8. Prove that for any positive functions f and g f n g n and max f n g n are .

• Kỹ thuật lập trình
• Engineering Department
• Computer Scienc
• Feaculty of Computer Science
• remove the median element
• computer architecture
• computer engineering
• Lecture Fundamentals of Biochemical engineering
• Fundamentals of Biochemical engineering
• Biochemical engineering
• Chemical engineering department
• Anaerobic fermentation processes
• Sterilization of microbial medium
• Oregon department of transportation
• Digital Signatures for Engineering Documents
• Electronic Vs Digital Signatures
• The Problems with Wet Signatures
• Signatures and the Law
• Oregon State Law
• Reinforcement Materials
• Pavement Test Facility
• road maintenance
• Traffic maintenance
• TE Highway engineering
• Roads and pavements Civil engineering
• composite materials
• National Aeronautics
• Space Administration
• Department of Defense
• Department of Energy
• Science Foundation
• Current State of the Art
• Technologes
• Systems Engineering
• robotic
• mechanical
• anatomy
• data and information
• Materials Courses
• Engineering Tripos
• process data
• material property
• process attribute charts
• Standards and Measuring Devices
• electrical engineering curriculum
• teaching electronics
• electrical systems
• electronics engineering
• electronic lecture
• ESP vocabulary
• Simulation task
• English for Automotive Engineering
• Automotive Engineering Technology Department
• Learning ESP vocabulary
• Technologies
• simple way
• lectures
• data
• objective
• litting 2
• linked list
• object
• Lab session 2
• objecttive
• listing 2
• exercises
• required excercises
• develop method
• báo cáo khoa học
• báo cáo hóa học
• công trình nghiên cứu về hóa học
• tài liệu về hóa học
• cách trình bày báo cáo
• Notarisation
• Real estate
• Transaction of property
• ownership and transfer
• portfolio property
• Tenancy agreements