Design of Algorithms
当前位置:以往案例 > >Design of Algorithms
2023-01-04

1. (15) Consider a sequence of n Bernoulli trials with success probability p per trial. A string of consecutive successes is known as a success run.
(a) Write a function that returns the counts for runs of length k for each k observed in a dictionary.
For example: if the trials were [0, 1, 0, 1, 1, 0, 0, 0, 0, 1], the function should return {1 : 2, 2 : 1})
1 # function call example
2 num runs = countRuns([0, 1, 0, 1, 1, 1, 0, 0, 0, 1]) 
3 num runs = countRuns(np.random.randint(0,2,1000000))
(b) Continuing from part (a), implement a function that returns the probability of observing at least one run of length k or more for a given n and p value. Your function is expected to estimate this from 100,000 simulated experiments.
  
Hint: you can use numpy’s random choice function to generate the simulated experiments. For instance, np.random.choice([0,1],(expts,n), p = (1 − p, p)) generates ‘expts’ many experiments as n dimensional arrays, where each component of the array is success (i.e., 1) with probability p.
1 #hint
2 expts = 1000
3 n=100
4 p=0.5
5 xxs = np.random.choice([0,1], (expts, n), p=(1−p, p)) 
6 # required function name and sample function call
7 prob val = run prob(expts , n, k, p)

  2.
(20) Write a python function that takes the dimension (n) of a square and a character (s) (e.g., ‘x’, ‘o’, ‘*’ etc.) as inputs, and outputs a numpy array that can be printed to screen for the corresponding shape that consists of the inputed character, which has the shape given in Figure 1 (a-b-c) depending on the dimension parameter along with the number of times the character s is used in creating this shape.
    
3.
Figure 1: Sample shapes
Also note that, if n < 5, the function should raise an error as shown in below sample function call.
1 # required function name, sample function call and outputs
2 ctr , shape array = generate star shape(5, ”+”) # ctr will be 15
3 # print as a pandas df −− generates Figure 1a 
4 print(pd.DataFrame(shape array).to string(header=False, index=False)) 
5 # return value for below function call is
6 # ”ValueError: provided value of the side is 3, minimum value is 5!” 
7 ctr , shape array = generate star shape(3, ”+”)

(20) Write a python function that uses random number generation to create sentences. The program should use a dictionary of lists with the keys article, noun, verb, and preposition as indicated below. The program should create a sentence by selecting a word at random from each array in the following order: article, noun, verb, preposition, article, and noun. As each word is picked, it should be concatenated to the previous words. The words should be separated by spaces. When the final sentence is output, it should start with a capital letter and end with a period. The function should generate n such sentences, where n is an input to the function. Then, the function should concatenate these sentences to produce a short story. The return value for this function is expected to be the story itself and the number of times a specific word target word is used in the story. The dictionary for story generation, and the sample function call is provided below.
1 input dict = {’article ’: [’the’, ’a’, ’one’, ’few’, ’any’], 
2 ’noun’: [’boy’, ’girl’, ’food’, ’cat’, ’city’, ’car’], 
3 ’verb’: [’crossed’, ’slipped’, ’hit’, ’walked’, ’jumped’], 
4 ’preposition’: [’to’, ’from’, ’over’, ’under’, ’in’, ’on’]
5 } 
6
7 # required function name and sample function call with the expected return vals 
8 out story , word ct = write short story(input dict , 3, ”cat”) # n=3, target word
= ”cat”

4 Create a car class with three attributes: year, mpg, speed and list of owners. The class also should have 2 methods called accelerate and brake. Whenever the car accelerates, its speed is increased by 30 and whenever the car brakes, its speed is reduced by 60.
– add a constructor to the class, which takes year, mpg, and speed as input
– implement a magic method that prins the car information including year, speed, and mpg. That is, for a car object, car1=car(2016, 20, 80), print(car) command should print car year 2016 mpg 20 speed 80.
Implement a python function that creates two car objects with the specs “car1=car(2016, 20, 80)” and “car2=car(2013, 25, 60)”, and record the list of previous owners specified for each car to these objects. This function should simply return the two car objects after the above operations are done, as indicated in below function call.
1 class car:
2 def init (self, year, mpg, speed): 
3 # fill out the rest of the car class
4
5 # required function name and sample function call with the expected return vals 
6 obj car1 , obj car2 = record car owners([”John Doe”, ”Jack Jones”], [”John Flack
”, ”Jeff Heath”])
(30) Consider a chain of stores that ship products to customers that are residing in either houses or apart-ments. The distances between the stores and the residences are given in file q5 distance.txt. Shipping costs are dependent on the distance values and each given product have a different cost multiplier for shipping cost calculation. Let pk be the cost multiplier for product k ∈ P, di j be the distance between store i ∈ I (for a set of stores I) and residence j ∈ S ∪S (for a set of houses S and apartments S ). Also, uLB and uUB HAHArr represent the min and max costs for shipment for residence type r ∈ {H, A}. Then, for product k ∈ P, the cost of shipment ci j between store i ∈ I and residence j of type r ∈ {H , A} can be calculated as

在线提交订单