闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

ECS 50: Programming Assignment #2

Winter Quarter 2022

1 Changelog

You should always refer to the latest version of this document.

● v.1: Initial version.

● v.2:

– Autograder details.

– Recommended against using printf() in part #5.

2 General Submission Details

Partnering on this assignment is prohibited. If you have not already, you should read the section on academic misconduct in the syllabus.

This assignment is due the night of Wednesday, 01/26. Gradescope will say 12:30 AM on Thursday, 01/27, due to the “grace period” (as described in the syllabus). Be careful about relying on the grace period for extra time; this could be risky.

3 Purpose of This Assignment

● To increase your understanding of the concepts covered in the ﬁrst slide deck.

● To introduce you to bit operators, such as bitwise AND.

● To continue to increase your comfortability with the C programming language (although not all parts of this assignment require you to write C code), since – as stated in prog_hw1.pdf – being comfortable with such a relatively low-level programming language will help you understand the low-level concepts in this course.

4 Reference Environment

The autograder, which is talked about at the end of this document, will compile and run your code in a Linux environment. That means that you should make sure your code compiles and behaves properly in a suﬃciently similar environment. The CSIF is one such environment. Each student should have remote access to the CSIF, and I expect that in-person access to the CSIF (which is in the basement of Kemper Hall) will be restored once lectures are back in person. (I talk more about the CSIF in the syllabus.)

Do not assume that because your code compiles on an insuﬃciently similar environment (e.g. directly on your Mac laptop), it will compile on the Linux environment used by the CSIF.

You should avoid causes of undeﬁned behavior in your code (i.e. you should avoid things that make your code behave diﬀerently in one environment/context vs. another), such as uninitialized variables or forgetting the null byte in a C-style string. If you have things like this in your code, then your code could end up generating the wrong answer when autograded, even if it generated the right answer when you tested it in a suﬃciently similar environment.

5 Bit Operators

You must learn and study the following bit operations:

● Bitwise AND.

● Bitwise OR.

● Bitwise XOR.

● Bitwise NOT.

● Left shift.

● Right shift (logical right shift and arithmetic right shift).

I have included a tutorial on Canvas called bit_operators.pdf that you can use, or you can look the above operators up online. You may ﬁnd some of the bit operators useful in some parts of this assignment.

You may be tested on the above bit operators on the exams in this course.

6 Programming Problems

6.1 General Remarks

Parts #1 through #3 require you to write C code. Because part #4 speciﬁcally relates to the C++ feature of private member variables, that part requires you to write C++ code. Part #5 requires you to write C++ code, just to make things easier, since reading from a ﬁle (which part #5 has you do) is a bit complicated in C.

Do not worry about input validation / reacting to improper inputs in this assignment.

6.2 File Organization

You will submit ﬁve ﬁles for this assignment:

● print_signed_rep.c

● bit_toggler.c

● subset_sum.c

● de_private.cpp

● decode_float.cpp

6.3 No Makeﬁle For This Assignment

You will not submit a makeﬁle for this assignment. If you do submit a makeﬁle, Gradescope will ignore it. Of course, you are encouraged to write a makeﬁle anyways, since it makes compilation more convenient, and you will only get better at writing makeﬁles if you force yourself to do it.

6.4 Part #1: Signed Integer Representations

File: print_signed_rep.c

You must write C code for this part.

In this part, you will write a program that takes an integer as a command-line argument and prints the two’s complement and signed magnitude representations of the integer. Assume that an integer is represented with 32 bits (as is the case for int on the CSIF, the reference environment) and that the given integer can be represented (with both representations) with 32 bits.

Here are examples of how your program should behave on a Linux command line.

1 $ gcc - Wall - Werror p r i n t _ s i g n e d _ r e p . c -o p r i n t _ s i g n e d _ r e p

2 $ ./ p ri n t _ s i g n e d _ r e p 5

3 2 ’ s complement : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

4 Signed magnitude : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

5 $ ./ p ri n t _ s i g n e d _ r e p -5

6 2 ’ s complement : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1

7 Signed magnitude : 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

8 $ ./ p ri n t _ s i g n e d _ r e p 255

9 2 ’ s complement : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

10 Signed magnitude : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

11 $ ./ p ri n t _ s i g n e d _ r e p 2147483647

12 2 ’ s complement : 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

13 Signed magnitude : 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

14 $ ./ p ri n t _ s i g n e d _ r e p 0

15 2 ’ s complement : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

16 Signed magnitude : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Hint #1 : The value of an int variable is represented/stored in two’s complement, not signed magnitude.

Hint #2 : You may ﬁnd atoi() (from <stdlib.h>) useful for converting a C-style string to an integer. (There are other ways to do this in C, such as strtol() and sscanf(), but atoi() is the simplest when you do not have to worry about erroneous input.)

6.5 Part #2: Bit Toggling

File: bit_toggler.c

You must write C code for this part.

In this part, you will write a program that ﬁrst prompts the user to enter an unsigned integer (let’s call this x). The program should then continously print x and prompt the user to enter an input (that you can assume will always be either the character ‘s’ or an integer between 0 and 31 (inclusive)) until the user enters an ‘s’. Each time the user enters an integer (let’s call this i) between 0 and 31, your program should toggle bit i of x (i.e. switch bit i from 1 to 0 or vice-versa).

Below are examples of how your program should behave.

1 $ gcc - Wall - Werror bit_toggler . c -o bit_toggler

2 $ ./ bit_toggler 3 Enter initial value : 20 4 Current value : 20 5 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : 1 6 Current value : 22 7 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : 2 8 Current value : 18

9 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : 2 10 Current value : 22 11 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : 4 12 Current value : 6 13 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : 6 14 Current value : 70 15 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : 0 16 Current value : 71 17 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : 4 18 Current value : 87 19 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : 6 20 Current value : 23 21 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : 2 22 Current value : 19 23 Enter bit to toggle (0 -31 , or ’s ’ to stop ) : s

Hint : Depending on your approach in this assignment, you may ﬁnd that you are comparing two strings at some point. In C++, comparing two std::string objects is easily done with the == operator1. In C, using == to compare two strings (i.e. two character arrays) compares the starting addresses of the two strings. In other words, == checks if the two strings are the exact same array in the exact same location in memory, which is probably not what you want. Comparing two strings in C is typically done with strcmp() or strncmp() from <string.h> .

6.6 Part #3: Brute-Force Subset Sum

File: subset_sum.c

You must write C code for this part.

In the subset sum problem, one of the problems you may study in ECS 122A, the inputs are the following:

● A set of items and their values.

● A target value.

In this problem, the goal is to ﬁnd an optimal solution, where an optimal solution is deﬁned as a selection of items whose total value equals the target value.

To solve this problem, you will implement isSubsetSum() in subset_sum.c. (There is a skeleton version of this ﬁle provided on Canvas, to help you get started.) The signature of the function is shown below.

1 unsigned * isSubsetSum (const int * itemVals , unsigned numItems , 2 int target , unsigned * numIndices ) ;

itemVals is an array of items’ values, and numItems is the length of this array.

If there is an optimal solution (i.e. at least one selection of items whose combined value equals target), then your function should return an array containing the indices of the items that make up an optimal solution. (By “indices”, I mean the indices in relation to itemVals .) Those indices must be in ascending order, i.e. the lowest index should come ﬁrst. In this case, your function should also set the unsigned variable referenced by numIndices to the number of items in the optimal solution you have chosen.

If there is no optimal solution, then your function should return NULL and set the variable referenced by numIndices to 0.

Restrictions: On Canvas, you can ﬁnd a document called brute_force.pdf that talks about creating a brute-force algorithm. Your solution for this part must use the bitstrings-based approach that is described in brute_force.pdf. Expect a heavy penalty if you violate this requirement. I will manually verify fulﬁllment of this requirement after the deadline. I will design the autograder such that so long as you do a reasonable job in your brute-force implementation, the autograder won’t time out. However, if you do a sloppy, needlessly ineﬃcient job such that the autograder times out, then you’ll have to improve your approach.

At least one item must be chosen. That is, the empty set (i.e. a selection of no items) can never be considered an optimal solution (i.e. when the target value is 0).

For any input used by the autograder, there will be at most one optimal solution.

You may assume that there will never be more than 16 items.

As already mentioned, your function is returning an array. That array should be dynamically allocated. If the array is automatically allocated (i.e. if the array is a non-dynamically allocated local variable), then the array will be destroyed at some point (not necessarily immediately after) isSubsetSum() ends, even if you return the array. On the other hand, if the array is statically allocated (i.e. if the array is a global variable), then you will run into issues if isSubsetSum() is called more

than once.

l If you were to look at the implementation of the overloaded operator== for std::string objects, you would ﬁnd that it does all the work of comparing the underlying character arrays for you, whether with a loop, with strcmp(), etc.

Do not include an implementation of main() in your subset_sum.c ﬁle when you submit it to Gradescope. You are implementing a single function for this part; you are not implementing a program. As you can see in the example below, your subset_sum.c will be compiled with another C ﬁle that has an implementation of main() in which your isSubsetSum() function is called.