CS 121 Fall 2023
Learning Goals
• Introduction & Representing objects as strings
• Defining computation: Boolean circuits and straightline programs • Completeness: Computing every finite function
See the course syllabus for the full policies.
• Collaboration: You can collaborate with other students who are currently enrolled in this course (or, in the case of homework zero, planning to enroll in this course) in brainstorming and thinking through approaches to solutions, but you should write the solutions on your own, without sharing notes.
• Owning your solution: Always make sure that you “own” your solutions to problem sets. That is, you should always first grapple with the problems on your own, and even if you participate in brainstorming sessions, make sure that you completely understand the ideas and details underlying the solution. This is in your interest as it ensures you have a solid understanding of the course material and will help in the midterms and final. Especially given the generous bonus points policies for homework, getting 80% of the problem set questions right on your own will be much better to both your understanding and your course grade than getting 100% of the questions through gathering hints from others without true understanding.
• Serious violations: The following are examples of serious violations of the honor code: (1) Sharing questions or solutions with anyone outside this course, including posting on outside websites. (2) Collaborating with anyone except students currently taking this course. (3) Obtaining solutions using material from past years, other websites, or large language models.
• Submission Format: The submitted PDF should be typed and in the same format and pagination as ours. Please include the text of the problems and write Solution X: before your solution. Please mark in Gradescope the pages where the solution to each question appears. Points will be deducted if you submit in a different format.
• Late Day Policy: To give students some flexibility to manage your schedule, you are allowed a net total of six late days through the semester, but you may not take more than two late days on any single problem set.
• Attempting problems and “I don’t know” policy. Some problems might be harder than others, so don’t despair if they require more time to think or you can’t do them all. Just do your best. Also, you should only attempt the bonus questions if you have the time to do so. If you don’t have a proof for a certain statement, be upfront about it. You can always explain clearly what you are able to prove and the point at which you were stuck. Also, for a non bonus question, you can always simply write “I don’t know” and you will get 15 percent of the credit for this problem. If you are stuck on this problem set, you can use Ed to send a private message to all staff.
CS 121 Fall 2023 PSET 1
By writing my name here I affirm that I am aware of all policies and abided by them while working on this problem set:
Name: HUID: Collaborators:
[[TODO: Put your name here]]
[[TODO: Put your HUID here]]
[[TODO: Put your collaborators here, if any.]]
CS 121 Fall 2023
1 Question 1 Name
You may use a calculator/spreadsheet for both parts of this question.
10 (2 per part)
The 1977 Apple II personal computer had a processor speed of 1.023 Mhz or about 106 operations per second. In 2023 the world’s fastest supercomputer (Frontier) performs about 1.2 exaflops per second; i.e. 1.2×1018 basic steps per second. (For comparison’s sake, it is estimated that evaluating GPT4 to produce a single word/token requires 560 terraflops or 5.6×1014.) For each of the following running times (as functions of the input length n), compute for each of the two computers how large an input it could handle in a week (i.e., T = 604, 800 seconds) of computation, if it runs an algorithm with that running time: (a) n operations, (b) n2 operations, (c) 106n log2 n operations, (d) 2n operations and (e) Tower(n) operations, where Tower(0) = 1 and Tower(m) = 2Tower(m−1). Your answers can be approximate, up to a factor of two. (Note that an input length is always a non-negative integer.)
Solution 1.1:
[[TODO: Answer Question 1.1 here.]]
1.2 10 (2 per part)
Moore’s law posits that the number of operations that computer can perform per time unit doubles about every two years, or equivalently, it grows by an order of magnitude every 2 · log2 10 ≈ 6.6 years.1 So in 2100 we may expect computers to perform about 1030 operations per second. Under this assumption, how would you compare the largest input that computers can handle in 2100 per unit time vs. what they could handle in 2023 if they run an algorithm that uses the following number of operations: (a) n operations, (b) n2 operations, (c) 106n log2 n operations, (d) 2n operations and (e) Tower(n) operations. For each case show mathematical justification and express your answer as “The largest n in 2100 (roughly) grows/shrinks by an additive/multiplicative factor of X compared to 2023.” for the best number X and choice of “additive” and “multiplicative” you can determine.
Solution 1.2:
[[TODO: Answer Question 1.2 here.]]
1For those comparing carefully with the previous problem: the Apple II was not the fastest computer of 1977.
CS 121 Fall 2023 PSET 1
2 10 2.1 5
A company named SuperParts sells four classes of products. Products of Class A (of which there are at most 32) are described by a 5-bit product code, Class B by a 4-bit code, and Classes C and D each by 2-bit codes. Design a class-name coding scheme E : {A, B, C, D} → {0, 1}∗ such that, if you prepend the class-name coding to the product code, the result is a 6-bit encoding of every product sold by SuperParts. (You should justify that all products have distinct encodings. i.e. for your class encoding function E, ∀ product p, E(Classp)[Product code of p] are distinct)
Solution 2.1:
[[TODO: Answer Question 2.1 here.]]
Prove that if E′ is a class-name coding scheme satisfying the requirements of the previous problem part, then E′ is a prefix-free code. (You may use the fact that for every class there is a product associated with every product code within that class. e.g., there is a Class A product with code 00010, and there is a Class C product with code 10, a Class D product with code 10, etc.)
Solution 2.2:
[[TODO: Answer Question 2.2 here.]]
Programming Help, Add QQ: 749389476
CS 121 Fall 2023 PSET 1
For n ≥ 1, let Oddn : {0,1}2n → {0,1} be the function such that Oddn(x0,…,x2n−1) = 1 if there exists an odd i ∈ [2n] such that xi = 1 and xj = 0 for every j < i. Otherwise Oddn(x0,...,x2n−1) = 0. Show that Oddn has O(n)-sized NAND circuits. For partial credit, you can show that Oddn has circuits of size O(n log n) or O(n2).
Hint: You might first want to prove that the function ORn(x0, . . . , xn−1) has O(n) sized cir- cuits, where ORn is given by ORn(x0,...,xn−1) = 1 if there exists i such that xi = 1 and ORn(x0, . . . , xn−1) = 0 otherwise. Then give a recursive way to compute Oddn in terms of Oddn−1 and some OR? function.
Solution 3.0:
[[TODO: Answer Question 3.0 here.]]
程序代写 CS代考 加QQ: 749389476
CS 121 Fall 2023
20 + BONUS 10 20
Define a {MAJ,MIN,ZERO} circuit to be one that uses the following gates:
• MAJ : {0,1}3 → {0,1} outputs 1 on inputs a,b,c ∈ {0,1} if and only if the majority of a,b,c
are equal to 1 (i.e., if a + b + c ≥ 2).
• MIN : {0,1}3 → {0,1} outputs 1 on inputs a,b,c ∈ {0,1} if and only if the majority of a,b,c
are equal to 0 (i.e., if a + b + c ≤ 1).
• ZERO : constant function with zero inputs and output 0
Prove that for every function f : {0,1}n → {0,1}, there is a {MAJ,MIN,ZERO} circuit that computes f.
Solution 4.1:
[[TODO: Answer Question 4.1 here.]]
4.2 BONUS 10
Define a {M AJ, AN D, OR} circuit to be one that uses the following gates: M AJ : {0, 1}3 → {0, 1} (defined as above), and OR : {0, 1}2 → {0, 1}, AN D : {0, 1}2 → {0, 1} defined as in the text. Prove that there does not exist a {MAJ,AND,OR} circuit that computes the function MIN : {0,1}3 → {0, 1} (defined as above).
Solution 4.2:
[[TODO: Answer Question 4.2 here.]]
Code Help