CPSC 320 Lecture 4: CPSC_320__Amortized_Analysis_II

8 views4 pages

7111605ying

31 Oct 2022

School

UBC

Department

Computer Science

Course

CPSC 320

Professor

For unlimited access to Class Notes, a Class+ subscription is required.

Document Summary

Beginning of class announcements: unfortunately assignment 4 was not returned today, but it will hopefully be returned by next class. At the conclusion of the previous class we considered three possible potential functions for the analysis of the binary counter. These included: the number of 1s in the counter, the number of bits in the counter, the number of consecutive ones on the right of the counter. We want a potential function to satisfy the following properties: if costreal(opi) is high, then should decrease, if costrealopi is low, then should increase but not by much. Next we consider the third choice for a potential function. When the binary counter is at 0111110, the potential function is 0 since the right-most digit is 0. However, when we increment this counter, the binary counter becomes 0111111. Now the po- tential function is about log2n, the number of bits in the counter, although only one bit was changed.

Related Questions

The University of Southern North Dakota Testing department needs to write a grading program for multiple choice test. It should be capable of grading tests with up to 50 questions and for any number of students. The program should grade individual exams and calculate the grade for the student based on the number of questions, each being the same value out of 100. For example, if there are 25 questions each is worth 4. This program must be written in Ada.

The program must also determine how many times each score was earned on the test. This is a count or frequency. The program must show the number of students graded and the class average.

The program should have

an input file. The program asks the user for the name of the file. The file name is entered at the keyboard. All subsequent data is read from the file.
a score frequency count. Every time a score is computed increment a counter for that value. Any score from 0 to 100 is possible (integer only), so the program needs 101 counters!
A record type Student_Type containing the student ID and their answers, and t he final grade for the exam.
A package containing Student_Type as private and operations for reading Student_Type, grading the exam and displaying the student ID and grade.

Behavior not assigned to functions may be done in main.

The program will accept the input file name from the keyboard after prompting the user for the file name.

The first line in the input files contains the number of questions on the exam, the second the answer key, and all following lines contain the student ids and responses to the questions.

The input shown here

2 1 1 3 4 4 5 3 2 1 2 4 5 2 1 1 3 4 4 2

12345 2 1 1 1 4 4 3 3 2 1 2 4 5 2 2 1 4 4 4 3

23456 2 1 1 2 3 4 5 3 2 1 2 4 5 2 1 2 3 4 4 1

14567 1 2 1 3 4 4 3 3 2 1 2 4 5 2 2 1 4 4 4 2

15678 2 1 2 3 3 4 5 3 1 1 3 4 5 2 1 1 3 4 4 2

16789 2 1 1 3 4 4 5 3 2 1 2 4 5 2 1 1 3 4 4 2

17890 2 1 1 3 4 4 5 3 2 1 2 4 5 2 2 1 4 4 4 3

12245 1 2 1 3 4 4 3 3 2 1 4 4 5 2 2 1 4 4 4 2

12256 2 1 2 3 3 4 5 3 1 1 2 4 5 2 1 1 3 4 4 2

22345 2 1 1 2 3 4 5 3 2 1 2 4 5 2 1 2 3 4 4 1

22456 1 2 1 3 4 4 3 4 2 1 2 4 5 2 2 1 4 4 4 2

13244 2 1 1 3 3 4 5 3 1 1 3 4 5 2 1 1 3 4 4 2

22458 2 2 1 3 4 4 5 3 2 1 2 4 5 2 1 1 3 4 4 2

23678 2 1 3 3 4 4 5 3 2 1 2 4 5 2 2 4 4 4 4 3

24567 2 1 2 3 3 4 5 3 2 1 2 4 5 1 1 2 3 3 4 1

11412 2 1 2 3 3 4 5 3 1 2 2 4 4 2 1 1 3 4 4 2

produces this output:

Enter file name:scantron.txt

Student ID Score

===================

12345 75

23456 80

14567 75

15678 80

16789 100

17890 85

12245 70

12256 85

22345 80

22456 70

13244 85

22458 95

23678 75

24567 70

11412 75

===================

Tests graded = 15

===================

Score Frequency

===================

100 1

95 1

85 3

80 3

75 4

70 3

===================

Class Average = 80

(*** Beware!! The data files can vary in number of questions up to 50, and there can be any number (at least 1) of students. Your program must be flexible! ***)

dha2021

29. Consider the Cocktail Sort (code 4) algorithm described in the appendix. What is the fewest number of lines of code that would have to be added, removed, or changed in order for this algorithm to sort from largest to smallest? (A) Everything inside the second for loop. (B) 3 (C) 1 (D) 2 (E) Everything inside both for loops. Binary answers For the following questions you are to use your choices as they were the representation of a binary number. More precisely, A = 24, B = 23, C = 22, D = 21, and E = 20 position in a base 2 number. For example if you wanted to answer the number 23, you would translate it first as base 2 number, which is 10111, you would blacken A, C, D and E.2 Lets look at this process on your answer sheet, we have these 5 circle you can blacken. Normally you only pick one, here you might have to blacken more than one! @ ® © D ® Following the previous example, the answer we want to input is 23, its binary representation is 10111, hence the circle you would blacken are the following:

3. Consider the following method, which returns the number of times the parameter String word occurs in the parameter array wordArray: public static int countOccurrences (String[] wordArray, String word) { int result; result = 0; for (int i = 0; i < wordArray.length; i++) { if (wordArray[i] == word) { result = result + 1; return result; Unfortunately, the above method contains a bug. This bug causes the method to return 0 instead of the expected value of 2 when it is called in the following code fragment: String[] animalism = { new String ("four"), new String ("legs"), new String ("good"), new String ("two"), new String ("legs"), new String ("bad") }; int count = count Occurrences (animalism, "legs"); System.out.println("Number of occurrences: " + count); Describe what the problem is, and suggest a simple way to fix it. BE BRIEF; overly long answers will be grounds for mark deductions.

CPSC 320 Lecture 4: CPSC_320__Amortized_Analysis_II

Document Summary

Get access

Related Documents

CPSC 320 Lecture 3: CPSC_320__Amortized_Analysis_III

MATH 317 Lecture 3: CPSC_320__Amortized_Analysis_IV

FRHD 1100 Chapter Notes - Chapter 11: Nicotine Patch, Aerosol Spray, Hypodermic Needle

Related Questions