CSC/CIS 17C讲解、辅导Data Structures、Java，c++，Python编程语言辅导
- 首页 >> Java编程 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∣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∣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.
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∣
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∣
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.