ChatGPT and co-pilot AI Programme Practice

Assignment Help Data Structure & Algorithms

Reference no: EM133330176

Abstract Data Types and Algorithms

ChatGPT and co-pilot AI Programmers.

It is not appropriate or ethical to use ChatGPT or any other tool to cheat on programming assignments. Here are a few reasons why:

• Cheating undermines the educational process and devalues the effort of those who have completed the assignment honestly. It is unfair to other students and can damage the reputation and integrity of the course or program.
• Cheating can have serious consequences, including failure of the course, academic probation, or even expulsion. These consequences can have a lasting impact on your academic and professional career.
• Learning to code is about more than just completing assignments. It is about developing the skills and knowledge to understand and solve complex problems. Cheating does not foster these skills and can actually hinder your ability to learn and grow as a programmer. In your programming career you will find that there is generally not one perfect answer, but rather a few "okay" answers that have advantages and disadvantages that you have to weigh critically. This course is about learning how to assess the pros and cons of various approaches. You cannot learn how to do this with an AI programmer, and frankly, it is not very good at it.
• There are resources available to help you understand and complete programming assignments honestly. We offer student hours and 24/7 course forums where you can get help from instructors or peers. Utilizing these resources can help you gain a deeper understanding of the material and improve your coding skills.

Workshop

Two of our TAs will hold a lab-specific workshop at a time TBD (announced on piazza). This workshop is completely optional, and there will be a video posted afterwards if you don't want to attend synchronously. The idea of the workshop is to give you a guided, hands-on start with the concepts of the lab. The TAs will ensure that you all understand what the main goals of the particular lab are and the main goals of the particular parts (time permitting). It is not a debugging session, nor is it student hours, but the idea is that time spent on the workshop can possibly save you a lot of time on the lab itself.

Problem Solving & Programming Tips Document
• A document specifically for this course, full of tips to help you complete your labs faster and better! It is a live document and might be beefed up as the course progresses.

Piazza
• Our primary forum where most course communication should happen.
• Good for getting a quick response, since it goes to a wider audience than email.
• Good for viewing questions that other students have. Chances are, if you have the question, so does someone else. Tags (e.g. "lab2" for lab 2) help manage questions.
• Good for general questions that don't divulge your approach (e.g. "Am I allowed to use standard JCF data structures in my solution?" "Does anyone else get this strange "file not found" error when submitting?" etc.) These questions can/should be posted publicly.
• Good for asking specific-to-you questions of the course staff, which you can/should post "privately" to Instructors on piazza. This gets you the benefits of a wider audience yet keeps your personal details private to course staff.
• Use private posts to Prof Alexa on piazza rather than email to ensure it gets to her.

Purpose & Goals

Generally, the labs in this course are meant to give you the opportunity to practice with the topics of this course in a way that is challenging yet also manageable. At times you may struggle and at others it may seem more straight-forward; just remember to keep trying and practicing, and over time you will improve.

Specifically, Lab 2 aims to encourage students:
• to think about the pros and cons of the ArrayStack, ArrayQueue, ArrayDeque, DualArrayDeque, RootishArrayStack, SLList, DLList, SEList, and SkiplistList implementations of a List, Stack, Queue, or Deque interface by deciding which of these to use, if any, to solve a variety of problems (Interface Practice);
• to only store the data you need in order to solve the problem;
• to deeply understand the implementation of the DLList and SkiplistList data structures, by implementing some new methods in the MyDLList and MySkiplistList classes (Implementation Practice), and
• to construct algorithms and/or use ideas similar to those seen in lecture so far, such as
- using two stacks to store data (similar to a DualArrayDeque),
- using nested data structures to store data, and find data within the nested structure (similar to a RootishArrayStack),
- using nested data structures to store data, moving data around those nested structures (similar to a SEList),
- using a pointer (e.g. an iterator) to iterate through a linked list to save time (as in an SLList, DLList, and SkiplistList).
• to maintain or adopt good academic and programming habits through the pre-lab, and
• to re?ect on your choice of data structures and algorithms through the post-lab,
• to get practice with JCF, that is, Java's implementation of the data structures from lecture, except through the textbook's code (since that best matches up with the methods from lecture-there are some differences). This is not a course about the actual programming, but you use programming to get concrete practice with the concepts from lecture.

Pre-lab
Do the pre-lab 2 (multiple-choice questions) on brightspace after reading this specifications document carefully, and optionally watching the lab 2 workshop video once it is available. The pre-lab is due 7 days before the lab programming deadline (in this case, by Wednesday February 1st, 3:00pm.) No lates accepted.

The pre-lab questions are meant to encourage good study and programming habits, such as reading the specifications in their entirety, trying the problems out on examples before starting to code, knowing what resources you have available to you if you get stuck, and last but not least, starting early!

Programming Setup
Start by downloading and decompressing the Lab 2 Zip File (Lab2.zip on brightspace under the lab 2 module), which contains a skeleton of the code you need to write. You should have the following files in the comp2402w23l2 directory: Part1.java, Part2.java, Part3.java, Part4.java, Part5.java, Part6.java, MyDLList.java, MySkiplistList.java, MyList.java, and then a bunch of files that you will not edit but might use (ArrayStack, ArrayQueue, ArrayDeque, RootishArrayStack, SLList, DLList, SEList, SkiplistList); in the tests/ directory you should have a lot of .txt files.

The skeleton code in the zip file compiles fine. Here's what it looks like when you unzip, compile, and run Part1 from the command line:

Lab2 % pwd
/Users/asharp/2402/Lab2
Lab2 % ls Lab2.zip

Lab2 % unzip Lab2.zip Archive: Lab2.zip
creating: comp2402w23l2/
in?ating: comp2402w23l2/Part6.java in?ating: comp2402w23l2/MyList.java
. . . <lines omitted> . . . creating: tests/
extracting: tests/lab2-p2-1-out.txt
. . . <lines omitted> . . .

extracting: tests/lab2-p6-0-in.txt
Lab2 % ls
Lab2.zip student_config_lab2p3.json
comp2402w23l2 student_config_lab2p4.json
run_local_tests.py student_config_lab2p5.json student_config_lab2p1.json student_config_lab2p6.json student_config_lab2p2.json tests
Lab2 % ls comp2402w23l2
ArrayDeque.java MyList.java Part5.java
ArrayQueue.java MySkiplistList.java Part6.java ArrayStack.java Part1.java RootishArrayStack.java DLList.java Part2.java SEList.java DefaultComparator.java Part3.java SLList.java MyDLList.java Part4.java SkiplistList.java
Lab2 % javac comp2402w23l2/*.java Lab2 % java comp2402w23l2.Part1 Execution time: 2.52683E-4
Lab2 % java comp2402w23l2.Part1 2 tests/lab2-p1-2-in.txt Execution time: 1.9521E-5
Lab2 % python3 run_local_tests.py student_config_lab2p1.json Compiling comp2402w23l2/Part1.java
Compilation of comp2402w23l2/Part1.java successful.

Interface Practice
The 6 parts in this section ask you to choose the best data structure (interface) to solve the following problems efficiently (with regards to both time and space).

You might first write solutions that just "get it done" (that is, are correct); once you have those submitted to the autograder and you are thus confident you understand the problem, only at that time think about how you are using data and whether the data structure you've chosen (if any!) is the best one for the task at hand.

You should not need any data structure other than those provided: (textbook implementations of) ArrayStack, ArrayQueue, ArrayDeque, DualArrayDeque, RootishArrayStack, SLList, DLList, SEList, and SkiplistList.

Do not modify the main(String[]) methods for any PartX.java file, as they are expected to remain the same for the autograder tests.

Sample input and output files for each part are provided in the tests/ directory of the Lab2.zip file. If you find that a particular question is unclear, you can probably clarify it by looking at the sample files for that question. Part of problem solving is figuring out the exact problem you are trying to solve.

You may assume that all lines are integers under 32 bits. If you need some help with modular arithmetic, try this khan academy page. In particular, to avoid integer over?ow, you might want to use the mathematical fact that (a+b)%X = ((a%X) + (b%X))%X and (a*b)%X = ((a%X)*(b%X))%X. Note that Java's version of modulo is slightly different, in that the modulo of a negative number in java is negative. Also note that s += b%X is doing s = s + (b%X) which is not probably what you're looking for. Best to expand += and -= and %= if you're doing mods.

Part 1. Given a file where each line is a single (32-bit) positive integer, read in the lines of the file one at a time; let s1, s2, ... , sk be all multiple of x2, and t1, t2, ... , tj be all multiples of x that occur (strictly) after the last multiple of x2. Return the sum modulo 240223 of (s1*t1) + (s2*t2) + ... + (sm*tm) where m=min{k, j}. For example, if x=2, x2=4 and the input is
4 ← multiple x2
10 ← multiple x but not x2
5 ← neither multiple of x nor x2
16 ← multiple of x2
9 ← neither multiple of x nor x2
8 ← multiple of x2 ← this is the last multiple of x2
30 ← multiple of x but not x2
6 ← multiple of x but not x2
Then the output is (4*30) + (16*6) = 216, because the multiples of 4 are 4, 16, 8, and the multiples of 2 after the last multiple of 4 are 30, 6. Therefore k=3, j=2, so m = min{3,2}=2.

Note that you might have integer over?ow for large values of si*ti, but try to avoid it as much as possible (use the mod-related math facts highlighted above; the autograder is not using Longs, for what it's worth.)

Since you'll be using interfaces and implementations from our textbook, you won't need to import anything.

For more examples, see the tests in the tests/ directory that have the form lab2-p1-X-in.txt for the input, and the matching lab2-p1-X-out.txt for the expected output; you might look at the student_config_lab2p1.json to look at the values of the parameter x that are used for the given input-output pairs.

Part 2. Given a file where each line is a single (32-bit) integer, read in the lines of the file one at a time; output n sums computed the following way: sum i is the sum modulo 240223 of every vth line starting from the 0th until you've summed (i+1) lines, where v>0 is the value of the last line. That is, first you output the 0th line. Then you output the sum of the 0th and vth line. Then you output the sum of the 0th, vth, and 2vth line, etc. All of this is modulo 240223, and you treat the list circularly using modular arithmetic. If the file is empty, output 0. For example, if the input is
10
20
30
40
50
4 ← v = 4, n = 6 then the output is

10
60 (=10+50)
90 (=60+30)
100 (=90+10)
150 (=100+50)
180 (=150+30)
because we output 6(=n) sums, and the sum on line i is the sum of the lines obtained from the 0th, vth, 2vth, ..., (i*v)th lines.

For more examples, see the tests in the tests/ directory that have the form lab2-p2-X-in.txt for the input, and the matching lab2-p2-X-out.txt for the expected output.

Part 3. Given a file where each line is a single (32-bit) non-negative integer, read in the lines of the file one at a time; each line x represents a list command (x%4) and a value (x/4), where the commands are:
x% 4 == 0: add(x/4) to the left of the current cursor
x% 4 == 1: remove the element most recently iterated by next/previous x% 4 == 2: next (move the cursor right by one) (iterates over an element) x% 4 == 3: previous (move the cursor left one) (iterates over an element)
This is modeled off of the JCF ListIterator, so it might be helpful to read its interface notes. The commands in your file will always be "valid," that is, you will never try to remove something that doesn't exist, nor will you try to call next or previous when there is no next or previous.

Note that remove will only ever be called if it is preceded by a call to next or previous (as in the JCF listIterator specifications.) If you get an IllegalStateException, it is likely that your code is accidentally violating this property. (The input is such that this should never happen, if your code is correct.)

Part 4. Given a file where each line is a single (32-bit) non-negative integer, read in the lines of the file one at a time; as with Part 3, each line x represents a list command (x%4) and a value (x/4), where the commands are:
x% 4 == 0: add(x/4) to the left of the current cursor
x% 4 == 1: remove the element most recently iterated by next/previous
x% 4 == 2: move cursor to the right by x/4, wrapping around if necessary (iterate the last one)
x% 4 == 3: move the cursor to the left by x/4, wrapping around if necessary (iterate the last one)
This is very similar to Part 3, except next and previous are replaced by more general "right" and "left" commands, and the remove removes the last element iterated by left and right. If x/4=0 then nothing is iterated.

For example, initially we have an empty list with the cursor at the start [^]. Consider input 44 → 44 % 4 = 0, 44 / 4 = 11; this is add(11) → [11^]
48 → 48 % 4 = 0, 48 / 4 = 12; this is add(12) → [11, 12^]
4 → 4 % 4 = 0, 4/4 = 1; this is add(1) → [11, 12, 1^]
11 → 11 % 4 = 3, 11/4 = 2 ; this is previous(2) → [11^, 12, 1] (12 iterated)
20 → 20 % 4 = 0, 20/4 = 5; this is add(5) → [11, 5^, 12, 1]
10 → 10 % 4 = 2, 10/4=2; this is next(2) → [11, 5, 12, 1^] (1 iterated)
1 → 1 % 4 = 1; this is remove of the most recently iterated item (1) → [11, 5, 12^]
3 → 3 % 4 = 3, 3/4=0; this is previous(0) → [11, 5, 12^] (nothing iterated)
15 → 15 % 4 = 3, 15/4=3; this is previous(3) → [^11, 5, 12] (11 iterated) 1 → 1 % 4 = 1; this is remove of the most recently iterated item (11) → [^5, 12] 6 → 6 % 4 = 2, 6/4=1; next(1) → [5^, 12] (5 iterated)
1 → 1 % 4 = 1; this is remove of the most recently iterated item (5) → [^12] The output is therefore
12
Note that when you iterate next, if it takes you to the exact end of the list, your cursor should remain just off the end. Symmetrically, if prev takes you to the exact front of the list, your cursor should remain just before the first element. As you cycle around, you should be iterating over one element at a time, but depending on which direction you are going (previous or next) your cursor may end before index 0, or after index n-1.

For more examples, see the tests in the tests/ directory that have the form lab2-p4-X-in.txt for the input, and the matching lab2-p4-X-out.txt for the expected output.

Part 5. Given a file where each line is a single (32-bit) non-negative integer, read in the lines of the file one at a time; create a new list out of the original by reading in groups of i lines for i=1, 2, 3, 4, ... and reversing the order of each group of lines (but the groups themselves stay in the original order.) From this new list, consider the last group of values: use these as circular indices to access and sum modulo 240223 the elements of the new list. Output this sum. If the file is empty, output 0. For example, if the input is
10
20
30
40
50
60
2
3
15
then the modified list is
10
30
20
60
50
40
15
3
2
Thus n=9 and the last group is 15, 3, 2 so we will sum the elements at indices (15%9=6, 3%9=3, and 2%9=2 for a final sum of (15 + 60 + 20)%240223 = 95.

For more examples, see the tests in the tests/ directory that have the form lab2-p5-X-in.txt for the input, and the matching lab2-p5-X-out.txt for the expected output.

Part 6. Given a file where each line is a single (32-bit) non-negative integer, read in the lines of the file one at a time into groups of size x, where x is an input to the program. Consider the last such group, which has between 1 and x values (depending on whether n is divisible by x). As with Parts 3 and 4, each line v in the last group represents a command (v%2) and an index (v/2), where the commands are:

v%2 == 0: (shift R) shift the right-most element of group (v/2) to be the left-most element of group (v/2+1), where we treat the groups as a circular list (i.e. mod the # groups)
v%2 == 1: (shift L) shift the left-most element of group (v/2) to be the right-most element of group (v/2-1), where we treat the blocks as a circular list (i.e. mod the # groups).
If either of these commands causes a group to become empty, remove it from the list of groups. These commands may ``target'' the final group (from which we took our commands); the commands should not be affected (as in: they are fixed before any of the operations occur.) Once all the operations are performed, print out each group followed by "****", but where each group itself is output in reverse order. For example, for x=2 if the input is
4
2
1 → 1 % 2 = 1, 1/2=0; shift L from group 0 to group -1 (which is group 1, circularly)
3 → 3 % 2 = 1, 3/2=1; shift L from group 1 to group 0 after the first instruction we have the groups
2
1
3
4
then after the second instruction we have the groups 2
1
3
4
And then we output these, each in reverse, separated by **** 1
2
**** 4
3
****
If we had the same input but with x=3 we'd have 4
2
1
3 → 3 % 2 = 1, 3/2=1; shift L from group 1 to group 0 which would lead to groups
4
2
1

3
and the output of 3
1
2
4
****
For more examples, see the tests in the tests/ directory that have the form lab2-p6-X-in.txt for the input, and the matching lab2-p6-X-out.txt for the expected output.

Implementation Practice
The 2 parts in this section ask you to implement a single (new) method in each of the MyDLList and MySkiplistList classes, with the goal of getting your hands dirty with the implementations of these classes. Construct algorithms for these methods that are time- and space-efficient, using the underlying implementation that we discussed in lecture.

As with the interface problems, it is good practice to first write solutions that just "get it done" (that is, are correct); once you have those submitted to the autograder and you are thus confident you understand the problem, only at that time think about your algorithm and whether the goal can be accomplished in a more efficient way.

The (provided) MyDLList and MySkiplistList classes are (incomplete) implementations of the (provided) MyList interface. Your task is to complete the implementation of the MyDLList and MySkiplistList classes, as specified below. Default implementations are provided for the 2 methods so that you can compile and run the main methods of the relevant classes right out of the gate; these defaults will not pass any of the tests, however.

Part 7. In the MyDLList class, implement public void copy(int k)
This replaces each element x with k copies of element x (as separate elements). You may assume that k ≥ 0.

For example,
• If the MyDLList ml originally represents the list [a,b,c] then after ml.copy(3), ml now represents [a, a, a, b, b, b, c, c, c].
• For any k ≥ 0, if ml=[ ] then after ml.copy(k), ms now represents [ ].
• For any MyDLList ml, after ml.copy(0), ms represents [ ].
The idea is to implement this method using the class variables provided. You should not need to use an ArrayStack or any other JCF data structure to solve this problem. You should not change the underlying class variables nor the implementation of the provided methods.

Part 8. In the MySkiplistList class, implement public void copy(int k)
This replaces each element x with k copies of element x (as separate elements). You may assume that k ≥ 0. This is the same functionality as with the MyDLList, but with a different underlying implementation (an SkiplistList is certainly more complex than a DLList, if you recall from lecture, although it will help you to focus on their similarities.) The idea is to implement this method using the class variables provided. You should not need to use an ArrayStack, an ArrayDeque, a DLList, or any other data structure to solve this problem. You should not change the underlying class variables nor the implementation of the provided methods.

Post-Lab
Do the post-lab 2 (multiple-choice questions) on brightspace after the programming deadline has passed (and the solutions video is available). The post-lab is due 7 days after the lab programming deadline (in this case, by Wednesday February 15th, 3:00pm.) No lates accepted.

The post-lab questions are meant to encourage retrospection on what you were meant to learn from the programming lab. If you were stuck on a problem, this is an opportunity to look at the solutions and at the lab 2 sample solutions video, to figure out what went wrong for you, and to still learn what you were meant to learn.

Local Tests
For Parts 1-6, you can view some sample input and output files in the tests/ directory. For example, you can run Part1 on lab2-p1-2-in.txt as follows:

Lab2 % java comp2402w23l2.Part1 tests/lab2-p1-2-in.txt
. . . < the output here is what your program outputs both to System.out and w> . . .

You can compare what your program outputs (the w.println statements, at least) to the expected output, which in this case would be in tests/lab2-p1-2-out.txt.

If you want to compile Part1.java and then run Part1 on all the tests and diff your output with the expected output, I've provided a python3 script for that:

Lab2 % python3 run_local_tests.py student_config_lab2p1.json
. . . < this outputs a lot of information about each test and whether it passed/failed> . . .

Of course, you have to have python3 installed on your machine in order for this to work. This script is not release-quality, but I hope it holds up for our purposes.

Once you get a sense for how to test your code with these input files, write your own tests that test your program more thoroughly (the provided tests are not exhaustive!) You can add them to the student_config_lab2pX.json file, if you wish.

If you find local tests that are illustrative / informative / helpful, feel free to share them on piazza; label the post "Lab 2 Part X local input/output test" or something like that.

Note that these tests are just checking correctness, not performance (as the performance test files are necessarily big). You might pass the local tests but fail performance autograder tests. You might even fail correctness autograder tests, as the local tests are not meant to be exhaustive, but rather try to point out some of the common expected errors, and give you a sense for how to write your own tests. As the course progresses, the local tests will be pared down and you will be expected to test more on your own.

Attachment:- Abstract Data Types and Algorithms.rar

Reference no: EM133330176

Questions Cloud

Explain your understanding of the four key principles : As a Disability Support Worker, you encompass these values in all that you do to ensure that the people you support are protected, and their rights are upheld.

What happened as families got involved : What is the element of this project that supports diversity in your school? What is the activity? What happened as families got involved?

Summarize macy efforts and commitments : discussed in the text is ESG (Environment, Social and Governance) . ESG is becoming an increasingly important measure for financial investors.

Has the internet shaped how humans process and develop : Has the internet shaped how humans process and develop thought? Compare and contrast these articles' perspectives on the digital consumption and/or circulation

ChatGPT and co-pilot AI Programme Practice : COMP 2402 Abstract Data Types and Algorithms, Carleton University - It is not appropriate or ethical to use ChatGPT or any other tool to cheat on programming

Why did richard go to a group home : While Sasha's high school is diverse in sexual orientation and identity, how is Richard's school diverse? Why did Richard go to Kaprice for help?

How does author use view of children in that particular work : Write 3 or more paragraphs about Insider/Outsider theme in The Kite Runner by Khalid Hossen and use in text citations. Write 2 or more paragraphs about

What is the relationship between race and police brutality : What is the relationship between race and police brutality. What role does in causing police brutality Why is police brutality so prevalent in the society

Provide an analysis of the statements : Provide an analysis of the statements below: Moral educationis important because it is the means by which one can rectify a nation's unpleasant situation

User Account

All Pages