Introduction
The goal of this assignment is to refamiliarize your Python skills and learn to use it to write some sorting algorithms and in the process develop your problem-solving skills. For each of the problems you will formulate or lookup an algorithm, write the corresponding source code, and thoroughly test it before handing it in. Be sure to carefully read each of the problems, as every detail will play a role in the solution.
This assignment is to be completed individually. You may work with other students on understanding the problems and discussing the algorithms, however, you are not allowed to share nor acquire source code from other students in the class, current or previous. You must start the assignment early in order to get proper help from the TAs and the instructor. You can also post general questions or ask for clarifications on Piazza, however, do not post your own source code on Piazza.
Please read the entire assignment carefully, before starting
Methodology
I expect you to create a source file that will contain the solutions to the questions below.
For each question you will create a method using the provided defintions. You may add any number of helper methods.
PLEASE USE the method definitions exactly as given for each questions. If you do not, then the autograder on Gradescope will not be able to recognize your answer and will give you a zero.
Additionally, you may want to create another file, for example test-assign.py, that will contain code for testing your functions. You are encouraged to test each of your algorithms with various edge and corner cases. You will NOT hand in this file.
Abstain from looking up solutions on the web or textbooks. I am sure you will find partial or even complete
solutions online, but following this approach is detrimental to your development and success in this class.
All you need to submit for this work is ONE file on Gradescope.
Before you proceed, please read each question carefully, several times if needed, work out a plan of action on paper, and then write your code
Question 1 (25 points)
Write a Python function (method) that displays a one-year calendar for ANY year. The program should prompt the user for a year (past, present or future). Then the program should calculate, the weekday for Jan 1 for that year. It turns out there is an equation for calculating this value, which is given as:
Here R(x,y) is remainder after the division of x by y, and Y is the year. This equation, credited to Carl Friedrich Gauss, produces a value between 0 and 6, where 0 is Sunday, 1 is Monday,….6 is Saturday. Once you know which day of the week the January 1 was for the year, you should print the calendar for the entire year.
The calendar should be formatted as shown in the sample execution below. Note that numbers the days must be right-justified under the names of the days and that two spaces separate the names of the days from each other.
Please take care to make sure if the year your entered is a leap year or not. snippet of the execution of the code is given below.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
|
|
|
|
|
1 |
2 |
3 |
|
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
11 |
12 |
13 |
14 |
15 |
16 |
17 |
|
18 |
19 |
20 |
21 |
22 |
23 |
24 |
|
25 |
26 |
27 |
28 |
29 |
30 |
31 |
Use loops to make sure you print the calendar for the whole year automatically. We will consider only years from the Current Era (C.E.) for this question.
Grading
Your method should return a list as it's output. The first value of the list should be the first day of the year, the second the second day, and so on until you have all 365 (366 for a leap year) days of the year in one list.
For example, if the year starts on say a Tuesday, then the first value of the list should be 2. Thus the full
list would be
day of the year. Note that the values in the above list lie between 0 and 6.
with 0<=n<=6 being the last
Question 2 (50 points)
You have seen BubbleSort in the class. You will remember that in BubbleSort, in every iteration, we find the
maximum element in the FIRST n-i elements of the list and push it to the end of the list (n-1-i)th position in the list . Here, i is the current iteration of the algorithm starting at element 0, and n is the number of elements in the list. Eventually, this leads to the list being fully sorted.
PART 1: (25 points)
Please implement an alternative version called that does the opposite? That is, in every
iteration, it finds smallest element in the LAST n-i elements of the list pushes it to the ith position in the list. Again, here, i is the current iteration of the algorithm starting at element 0, and n is the number of elements in the list.
Grading
After every round of the algorithm, your method should store the current state of the list in a lists-of-lists, starting with the orignal list (i.e., the input). Once the algorithm terminates, you should store the final sorted list in the list-of-lists and return the entire list-of-lists.
For example, if you are sorting a list the following list-of-lists
then your algorithm may return
|
[1, |
6, |
10, 3, 9, |
4, |
8, |
7], |
|
[1, |
3, |
6, 10, 4, |
9, |
7, |
8], |
|
[1, |
3, |
4, 6, 10, |
7, |
9, |
8], |
|
[1, |
3, |
4, 6, 7, |
10, |
8, |
9], |
|
[1, |
3, |
4, 6, 7, |
8, |
10, |
9], |
|
[1, |
3, |
4, 6, 7, |
8, |
9, |
10], |
|
[1, |
3, |
4, 6, 7, |
8, |
9, |
10], |
|
[1, |
3, |
4, 6, 7, |
8, |
9, |
10]] |
We list each element of the list of lists in a separate line for clarity reasons.
Please use these exact function prototype for this question as your work will be auto-graded in Gradescope.
PART 2: (25 points)
Now implement yet another version called combines the tradition BubbleSort and Alt-
BubbleSort. That is, it alternates between finding the largest element and pushing it to the end of the list is one iteration and then finding the smallest element and pushing it to the beginning of the list is the next iteration and goes back and forth until the entire list is sorted, which is then returned.
For example, if you are sorting a list the following list-of-lists
then your algorithm may return
|
[1, |
8, |
7, |
6, |
5, |
4, |
3, |
2], |
|
[1, |
7, |
6, |
5, |
4, |
3, |
2, |
8], |
|
[1, |
2, |
7, |
6, |
5, |
4, |
3, |
8], |
|
[1, |
2, |
6, |
5, |
4, |
3, |
7, |
8], |
|
[1, |
2, |
3, |
6, |
5, |
4, |
7, |
8], |
|
[1, |
2, |
3, |
5, |
4, |
6, |
7, |
8], |
|
[1, |
2, |
3, |
4, |
5, |
6, |
7, |
8], |
|
[1, |
2, |
3, |
4, |
5, |
6, |
7, |
8]] |
Note that we first run alt-bubblesort and then run tradtional bubblesort and then switch again. Please follow this order to make sure your output matches with our expectations.
We list each element of the list of lists in a separate line for clarity reasons
Grading
Again, after every round of the algorithm, your method should store the current state of the list in a lists-of-lists, starting with the orignal list and ending with the sorted list
Please use these exact function prototype for this question as your work will be auto-graded in Gradescope
NOTE: The following link might be useful in understanding how to deal with list of lists: https://snakify.org/en/lessons/twodimensionallists_arrays/.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
