CSC/CIS 17C代做、代写Data Structures、Java，c++，Python编程语言代写

日期：2020-05-07 11:10

CSC/CIS 17C – Data Structures Midterm

NAME _____________________ DATE______________________

You should create a folder labeled Midterm that has folders labeled for each Problem when many files

clearly are required in the problems solution.

Midterm 17C – Section Code

For Problems 1 to 3 – Provide Project Code, Spreadsheets, Plots, and written derivations. Note: The

answers are well known. Stating the answer is not the solution. I want you to prove the answer in 3

different ways as we showed in class with an example sorting routine. A correct submission of all 3

types of analysis would rate an A for the problem, submission of 2 would rate a B for the problem and

submitting only the timing analysis with curve fit data, plots, and analysis would rate a C.

Problem 1) Analyze and compare the linear and binary search. See Github/Book/Midterm Folder. I

have provided a project folder with the code.

Show O() by mathematical analysis – Show all work/algebraic summative derivations.

Show O() by operational analysis – Curve Fit with my program and tables/plots in Spreadsheet

Show O() by timing analysis – Curve Fit with my program and tables/plots in Spreadsheet

Problem 2) Analyze, compare and contrast bubble sort with selection sort. See

Github/Book/Midterm Folder. I have provided a project folder with the code.

Show O() by mathematical analysis – Show all work/algebraic summative derivations.

Show O() by operational analysis – Curve Fit with my program and tables/plots in Spreadsheet

Show O() by timing analysis – Curve Fit with my program and tables/plots in Spreadsheet

Problem 3) Compare insertions, i.e. 1) push method with Simple Vector using arrays, 2) with

Optimized Simple Vector using arrays, and 3) Simple Vector implemented with a Linked List. See

Github/Book/Midterm Folder. I have provided a project folder with the code.

Show O() by mathematical analysis – Show all work/algebraic summative derivations.

Show O() by operational analysis – Curve Fit with my program and tables/plots in Spreadsheet

Show O() by timing analysis – Curve Fit with my program and tables/plots in Spreadsheet

Problem 4) Complete the table, given the Order, Scale accordingly.

Big O() Second Minute Hour Day Month Year Decade Century

N^(1/3)

N^(1/2)

N 10^3

N ln N

N^2

N^2 ln N

2^N

N!

CSC/CIS 17C – DataStructures Midterm

Problem 5) Derive the order of the error with respect to the sin and cosine approximations.

Approximation sin(1/N )≈1/N cos(1/ N )≈1?1/(2?N2)

errorsin (1/N )=O(?) error cos(1/N )=O(?)

Problem 6) Derive the O() for the Recursive vs. non-Recursive Fibonacci Function. See repository.

Problem 7) Given 4 cards with 13 possible face values, calculate the probability of 1 pair, 2 pair, 3 of

a kind and 4 of a kind. Simulate the results and compare to calculations.

Problem 8) Given a biased coin analogy, if a bit vector is 40% full, what are the odds that 5 bits

randomly chosen all fall within the filled section. Simulate the results and compare to calculations.

Problem 9) Recursive function. Provide code and test sufficiently.

Create 2 types of Power functions

(Hint for O(ln n) split into even and odd conditions)

y=xn,( y(n)=O(n) ∩ y (n)=O(ln n)) where y , x∈R, n∈N 0

Problem 10) Recursive function. Provide code and test sufficiently.

Let g(2x) =2g( x)1+g2( x), ?1≤x≤1, x∈R , ? x=0.1f

with base conditions of ∣x∣<tol ,tol<106,

g (x )=x?x3/6

Problem 11) Mutual Recursive functions. Provide code and test sufficiently.

Let C (2x) = 1/ 2C (x )S ( x) ∩ S(2x) =C2( x)S2( x)C2(x )?S2(x ), ∣x∣≤atan (1), x∈R , ? x=0.1f

with base conditions of ∣x∣<tol , tol<106, C ( x)=1/ x+x/ 6, S (x)=1+x2/2

Problem 12) Code the mode problem first with the Set container, then use the Map container from the

STL. I have already coded the problem for you without those containers. You are to take my code and

reduce the number of lines required for the mode function by showing your expertise of Sets first then

using Maps second. The idea is that Sets should reduce the code required and Maps should reduce it

even further. Implement the function in the least amount of code for each container.