Programming Assignments, CSci 227: Programming Methods, Hunter College

Programming Assignments
CSci 227: Programming Methods
Department of Computer Science
Hunter College, City University of New York
Spring 2024

All students registered by Wednesday, 24 January are sent a Gradescope registration invitation to the email on record on their Blackboard account. If you did not receive the email or would like to use a different account, write to csci227@hunter.cuny.edu. Include in your email that you not receive a Gradescope invitation, your preferred email, and your EmpID. We will manually generate an invitation. As a default, we use your name as it appears in Blackboard/CUNYFirst (to update CUNYFirst, see changing your personal information). If you prefer a different name for Gradescope, include it, and we will update the Gradescope registration.

General Notes

These program builds on the concepts and code developed during lecture and through the reading. Mastery of material is assessed via

Autograding of the program submitted to Gradescope, and
Final exam on the material.

Autograder Notes

Submitted code must be in Python, using only the specified libraries. The autograder expects a .py file and does not accept iPython notebooks. Since all assignments are designed to be uploaded as a single file, the autograder is set up for direct file upload instead of Github. If submitting directly (drop-and-drag onto the webpage), the file name is flexible but must have the extension .py. Also, to receive full credit, the code should be compatible with Python 3.6 (the default for the Gradescope autograders).

To encourage starting early on programs, bonus points are given for early submission. A bonus, up to 10% of the program grade, are possible. Programs submitted 48 hours early receive 1 points, prorated by hour. For example, if you turn in the program 24 hours early, then the bonus poins are: (28 hours/48 hours)*1 points = (1/2)*1 points = 0.5 point.

To get full credit for a program, the file must include in the opening comment:

Your name, as it appears in your Gradescope registration.
The email you are using for Gradescope.
A list of any resources you used for the program. Include classmates and tutors that you worked with, along with any websites or tutorials that you used. If you used no resources (other than the class notes and textbooks), then you should include the line: "No resources used."

For example, for the student, Thomas Hunter, the opening comment of his first program might be:


"""
Name:  Thomas Hunter
Email: thomas.hunter1870@hunter.cuny.edu
Resources:  Used python.org as a reminder of Python 3 print statements.
"""

and then followed by his Python program.

Good style accounts for 30% of the program grade. We are following the standard PEP 8 style guide for Python code. As part of the autograder scripts, your program is run through a static code analyser (aka a "linter").

We are using Pylint which reports warnings and errors, including message codes, and then scores the code on a scale from 0 to 10. We multiply your percentage score by 3 (25% of the total) to determine the style grade. For example, if pylint scores your program 9, your style grade is (9/10) * 2.5 = 2.25
See the Pylint website for tutorials, FAQ's and standard warnings.
PEP 8 specifies that variable names should be at least 3 characters long, but it is long standing convention that DataFrames are named df. For the autograders, we have included df in the "good-names" that are accepted. This can be done locally with .pylintrc files or using the command-line option pylint --good-names=df.
Most IDE's have linting available: for example, see pylint in PyCharm and Linting Python in VSCode.

Programming Assignments

Due Date: 5pm, Friday, 2 February
Reading: Textbook: Chapter 1 & Lab 1
Available Libraries: Core Python 3.6+

Hello

Write a Python program that prints "Hello, World!" to the screen. For full credit, make sure to follow Python style guide and include introductory comments.
Hint: See style & pylint in Lecture 1 and Lab 1.
Due Date: 5pm, Monday, 5 February
Reading: Textbook: Chapter 1 & Lab 1
Available Libraries: Core Python 3.6+

Leap Years

Write a function is_leap() that takes an integer between 1000 and 10,000 and returns True if it is leap year and False otherwise. The following conditions are used to determine leap years:
If the year is divisible by 4 but not divisible by 100 unless the year is divisible by 400.
For example, 2000 and 2400 are leap years, while 1900 and 2100 are not leap years.
Notes:
- You should submit a file with only the standard comments at the top, the specified functions, and any helper functions you have written. The grading scripts will then import the file for testing.
- If your file includes code outside of functions, either comment the code out before submitting or use a main function that is conditionally executed (see Think CS: Section 6.8 for details).
Hint: See HackerRank function challenge from Lecture 1.
Due Date: 5pm, Thursday, 8 February
Reading: Textbook: Chapter 1 & Lab 1
Available Libraries: Core Python 3.6+

Duplicate Names

Write a function duplicates() that takes a list of names and returns a list of the names that occur more. If there are no duplicated names, your function should return an empty list (e.g. [])
For example:
```
names = ['Daniel','Dorothy','Bethany','Beth','Daniel','Georgi']
print(duplicates[names])
```
would print:
```
["Daniel"]
```
Hint: See classwork from Lecture 1 and the Program 2 notes above.
Due Date: 5pm, Friday, 9 February
Reading: Textbook: Chapter 1 & Lab 1
Available Libraries: Core Python 3.6+
Unique Visitors

When students visit the lab, their EmpID is stored as an 8-digit string. Many students visit multiple times, but we are interested in the total number of unique visitors to the lab. Write a function unique_visitors() that takes a list of 8-digit strings and returns the number of unique strings that occur.

Your function should also screen out any strings that are too long (more than 8 digits) or too short (less than 8 digits) and not include those in the final count returned.

For example:
```
ids = ['12345678','11223344','123','12345678']
print(f"The number of unique visitors is {unique_visitors(ids)}.")
```
would print:
```
The number of unique visitors is 2.
```
since there are 3 entries of the correct length but only 2 unique ones (the first and fourth entries are duplicates of each other).
Hint: See classwork from Lecture 1 and the Program 2 notes above.
Due Date: 5pm, Tuesday, 13 February
Reading: Textbook: Chapter 1 & Lab 2
Available Libraries: Core Python 3.6+

Hexadecimal Plus One

In Lab 2, we worked through LC 66 (Plus One), which took a large number, represented as a list of digits and returned its value incremented by one. For this question, write a function:
```
def hex_plus_one(digits: List[str]) -> List[str]:
```
that takes a large number stored as a list of hexadecimal digits (the characters from '0','1',...'9','A','B','C','D','E','F' representing the digits 0,1,...9,10,11,12,13,14,15) and returns the large number incremented by 1.

For example, if the list is ['1','2','F'], then the function should return ['1','3','0'] since incrementing the last digit, 'F', by 1 gives 10, or '0' with a carry of 1. The next to last digit is '2' with the carry becomes '3'.

Hint: See Lab 2.
Due Date: 5pm, Friday, 16 February
Reading: Textbook: Chapter 1 & Lab 2
Available Libraries: Core Python 3.6+

Longest Words

Write a program that asks the user for the names of an input file and output file. Your program should read in the input file and for each line, write the longest word to the output file (if there are more than longest word on a line, the first is written).

For example, if you ran your program:
```
Enter your input file name:  milne.txt
Enter your output file name:  longest.txt    
    
  
```
If the input file, milne.txt contained:
```
It is more fun to talk 
with someone who doesn't use long, 
difficult words but rather short, 
easy words like 'What about lunch?'

--A.A. Milne
```
Then the output file, output.txt, would contain:
```
more
someone
difficult 
lunch?'
  
--A.A.
```
Note: to simplify this program, words are contiguous characters, separated by spaces (no need to strip off punctuation marks).
Due Date: 5pm, Tuesday, 20 February
Reading: Textbook: Chapter 1 & Lab 2
Available Libraries: Core Python 3.6+

Average Grades

Write a program that asks the user for the names of an input file and output file. Each line of the input file has a name, followed by grades, separated by spaces. Your program should read in the input file and for each line, write the name to the output file and the average of the grades, separated by a space.

For example, if you ran your program:
```
Enter your input file name:  grades.txt
Enter your output file name:  ave.txt
  
```
If the input file, grades.txt contained:
```
Amy 10 8 8 4 
Beth 10 11 
Chaaya 10 0 11 9 9 9 
Daiyu 8 8 5 10 10 10
Esme 3 9 6
```
Then the output file, ave.txt, would contain:
```
Amy 7.5
Beth 10.5 
Chaaya 8.0 
Daiyu 8.5
Esme 6.0
```
Due Date: 5pm, Friday, 23 February
Reading: Textbook: Chapter 1 & Lab 2
Available Libraries: Core Python 3.6+

Proper Nouns

Write a function that takes a string and returns a list of all words that start with capital letter. Words in the string are separated by spaces.
```
def find_proper_nouns(data: str) -> List[str]:
```
For example, if you ran your program:
```
data = "Jack and Jill went up the hill."
nouns = find_proper_nouns(data)
print(nouns)
```
Then the output would be:
```
["Jack","Jill"]
```
Hints:

See notes for Program 2 about code outside of functions.

There's lots of ways to test for the first letter capital. One easy way is if word, then word[0] == word[0].upper() will return true if the first letter is upper case.

Due Date: 5pm, Tuesday, 27 February
Reading: Textbook: Chapter 2 & Lab 3
Available Libraries: Core Python 3.6+

Anagram

Write a function that takes two string and returns True if they are anagrams and False otherwise. The strings will only consist of letters, and your function should be case insensitive (e.g. 'A' and 'a' are considered the same).
```
def anagram(word_1: str, word_2: str) -> bool:
```
For example, if you ran your program:
```
word_1 = 'coast'
word_2 = 'water'
word_3 = 'tacos'
print(f'{word_1} and {word_2}:  function returns {anagram(word_1,word_2)}.')
print(f'{word_1} and {word_3}:  function returns {anagram(word_1,word_3)}.')
```
Then the output would be:
```
coast and water:  function returns False.
coast and tacos:  function returns True.
```
Hints:

See notes for Program 2 about code outside of functions.

See Classwork 3 and Lab 3 where we sketch out this problem.

Due Date: 5pm, Monday, 4 March
Reading: Chapter 2 & Lab 3
Available Libraries: Core Python 3.6+, time

Function Timer

Following the textbook's example in Section 2.2, write a function that returns the result and time taken by an inputted function and returns the result of the function and the time it takes. Your function should also have a keyword argument, num, with default value 10 that is the input when running the function.

fnc_timer(fnc, num = 10)

For example, if you had defined the summing functions we had in lecture (and Section 2.2 of the textbook):

def sum_form(num):
    """
    Computes sum of first n numbers, using formula.
    """
    return num*(num+1)/2

def sum_loop(num):
    """
    Computes sum of first n numbers, using loop.
    """    
    result = 0 
    for iii in range(1,num+1):
        result = result + iii

    return result

Then we can use those functions to test the fnc_timer:


def main():
    """
    Testing the timer:
    """
    print(f"For sum_form: {fnc_timer(sum_form)}\n")

    for num in range(1000,20_000,1000):
        result, time_taken = fnc_timer(sum_form,num=num)
        print(f"For sum_form with num={num}, result = {result} in time {time_taken:.10f}.")
    
    print()
    for num in range(1000,20_000,1000):
        result, time_taken = fnc_timer(sum_loop,num=num)
        print(f"For sum_loop with num={num}: result = {result} in time {time_taken:.10f}.")    

if __name__ == "__main__":
    main()

Then the output would be:

For sum_form: (55.0, 1.4781951904296875e-05)

For sum_form with num=1000, result = 500500.0 in time 0.0000021458.
For sum_form with num=2000, result = 2001000.0 in time 0.0000021458.
For sum_form with num=3000, result = 4501500.0 in time 0.0000011921.
For sum_form with num=4000, result = 8002000.0 in time 0.0000009537.
For sum_form with num=5000, result = 12502500.0 in time 0.0000011921.
For sum_form with num=6000, result = 18003000.0 in time 0.0000009537.
For sum_form with num=7000, result = 24503500.0 in time 0.0000011921.
For sum_form with num=8000, result = 32004000.0 in time 0.0000009537.
For sum_form with num=9000, result = 40504500.0 in time 0.0000009537.
For sum_form with num=10000, result = 50005000.0 in time 0.0000011921.
For sum_form with num=11000, result = 60505500.0 in time 0.0000009537.
For sum_form with num=12000, result = 72006000.0 in time 0.0000007153.
For sum_form with num=13000, result = 84506500.0 in time 0.0000009537.
For sum_form with num=14000, result = 98007000.0 in time 0.0000009537.
For sum_form with num=15000, result = 112507500.0 in time 0.0000011921.
For sum_form with num=16000, result = 128008000.0 in time 0.0000009537.
For sum_form with num=17000, result = 144508500.0 in time 0.0000011921.
For sum_form with num=18000, result = 162009000.0 in time 0.0000009537.
For sum_form with num=19000, result = 180509500.0 in time 0.0000009537.

For sum_loop with num=1000: result = 500500 in time 0.0001218319.
For sum_loop with num=2000: result = 2001000 in time 0.0002119541.
For sum_loop with num=3000: result = 4501500 in time 0.0003182888.
For sum_loop with num=4000: result = 8002000 in time 0.0004231930.
For sum_loop with num=5000: result = 12502500 in time 0.0005140305.
For sum_loop with num=6000: result = 18003000 in time 0.0006108284.
For sum_loop with num=7000: result = 24503500 in time 0.0007030964.
For sum_loop with num=8000: result = 32004000 in time 0.0008106232.
For sum_loop with num=9000: result = 40504500 in time 0.0009038448.
For sum_loop with num=10000: result = 50005000 in time 0.0010118484.
For sum_loop with num=11000: result = 60505500 in time 0.0011117458.
For sum_loop with num=12000: result = 72006000 in time 0.0011761189.
For sum_loop with num=13000: result = 84506500 in time 0.0012700558.
For sum_loop with num=14000: result = 98007000 in time 0.0013661385.
For sum_loop with num=15000: result = 112507500 in time 0.0015220642.
For sum_loop with num=16000: result = 128008000 in time 0.0015380383.
For sum_loop with num=17000: result = 144508500 in time 0.0015838146.
For sum_loop with num=18000: result = 162009000 in time 0.0016670227.
For sum_loop with num=19000: result = 180509500 in time 0.0017712116.

The first line comes from our first call to fnc_timer that uses the default value for num when timing the function. The next lines are from the for-loops where we supply a value for num.

Hints:

Don't overthink the question-- the function that you have to write is very short. The difficulty lies in putting the pieces together (functions as arguments, using keywords) into one function.

Make sure to include the module for timing code (e.g. import time.)

See Section 2.2 of the textbook and Lecture 3 where we discuss timing code and Lecture 4 where we recap function arguments.

See notes for Program 2 about code outside of functions.

Due Date: 5pm, Tuesday, 5 March
Reading: Textbook: Chapter 2 & Lab 4
Available Libraries: Core Python 3.6+

Binary Search

For Classwork 4, we traced through the pseudocode for linear search and binary search. Convert the pseudocode for binary search into a function:
```
def binary_search(cards, min_ind, max_ind, target):
```
The pseudocode from Classwork 4:
If min_ind > max_ind, Return False Let mid = (min_ind+max_ind)//2 If cards[mid] is target, Return True If cards[mid] < target, Return binary_search( cards, mid+1, max_ind, target ) Return binary_search( cards, min_ind, mid-1, target )
For example, if you ran your program:
```
cards = [1,1,2,3,8,9,10,11,12]
purples = ["amethyst","eggplant","grape","indigo","lavendar","lilac","magenta","plum","violet"]


print(f"Is 7 in the cards? {binary_search(cards,0,len(cards)-1,7)}")
print(f"How about 8? {binary_search(cards,0,len(cards)-1,8)}\n")

print(f"Is mauve one of our purples?  {binary_search(purples, 0,len(purples)-1,'mauve')}")
```
Then the output would be:
```
Is 7 in the cards? False
How about 8? True
  
Is mauve one of our purples?  False
```
Hints:

See notes for Program 2 about code outside of functions.

See Classwork 4 where we sketch out this problem.

Due Date: 5pm, Thursday, 7 March
Reading: Textbook: Chapter 1 & Lab 4
Available Libraries: Core Python 3.6+

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number. Your function should be:
```
def find_duplicate(nums : List(int)) -> int:
```
Note: You must solve the problem without modifying the array nums and uses only constant extra space.
```
Example 1:
    
  Input: nums = [1,3,4,2,2]
  Output: 2

Example 2:
    
  Input: nums = [3,1,3,4,2]
  Output: 3
```
Hints:

This is LeetCode 287. As with all the programming challenges, try to program it on your own before seeking help from the lab or on-line.

Many of the solutions you will find on-line use techniques we have not learned yet. There is a way to do this using binary search. Here's an approach:

All the integers in nums appear only once except for precisely one integer which appears two or more times.

Let's do binary search on values [1,...,n], instead of the indices (of which there's n+1, since there's a duplicate).

To find the duplicate, let's look at the middle value. For the first example above, nums = [1,3,4,2,2], it's 4/2 = 2. How many elements are at most 2? And how many are larger than 2?

We can compute that with a simple loop that check each value and counts those <= 2. 3 entries in the list are at most 2 and 2 entries are more than 2. So, we have 3 elements that are 1 or 2 and 2 entries that are 3 or 4. Since only one number is duplicated and we have 2 entries that are in [3,...,4], the duplicate number must be either 1 or 2.

Let's repeat our loop with guess of 1. This time, we have 1 entry in the list with value < 1 and 4 entries that are 2,3,4. 1 is not the answer. So, it must be 2.

Due Date: 5pm, Friday, 8 March
Reading: Textbook: Chapter 1 & Lab 4
Available Libraries: Core Python 3.6+

Median Value

In lectures and labs, we have compute minimum, maximum, mean (average), and mode (most common value) for lists of numbers. For this program, we're computing the median, or value for which half the numbers in the list are smaller and half the list are larger. For lists of even length, we will arbitrarily choose the larger of the two middle values, if they differ.

An elegant way to compute the median, is to split the list into smaller lists, say each of length 5. Find the median of each and save those to a list. And repeat this on your new list. If you keep repeating, you will, recursively, found the median value.

(From Wiki: Pashapanther. )
The pseudocode for computing the median of medians is:
median_of_medians(nums) Let n be the length of nums. If n <= 2, return nums[-1]. Let med_list be an empty list. Divide nums into n/5 sublists of length 5, except possibly the last sublist which has the remaining elements (1 to 5 of them). For each sublist, compute median and append to med_list. Call median_of_medians(med_list).
For this question, write the function that finds the median of lists of 5 or fewer values (that is, implement line 5 above):
```
def median_5(nums: List) -> int:
```
that takes a list of numbers of 5 (or fewer) elements and returns the median value. If the list is of even length, it returns the larger of the two middle values.

For example, if nums = [1,8,2,3,7], the number for that has half the elements below it and half above it is 3, so, your function would return 3.

For example, if nums = [10,3,3,4], the values in the middle are 3 and 4, so, your function returns the larger, or 4.
Due Date: 5pm, Monday, 11 March
Reading: Textbook: Chapter 1 & Lab 5
Available Libraries: Core Python 3.6+

Fraction Class

Building on the Fraction class (fraction.py) from Lab 5, write two functions:
- __eq__(self, other): which returns True if self and other are equivalent fractions and False otherwise.
- __mul__(self, other): which multiplies the fractions self and other and returns the simplified product.
For example, if the Fraction class is in the file fraction.py
```
from fraction import *
f1 = Fraction(1, 2)
f2 = Fraction(2, 3)

f3 = f1 * f2
print(f"{f1} times {f2} is {f3}.")
print(f"Is f3 equivalent to f1:  {f3 == f1}.")
```
would output:
```
1/2 times 2/3 is 1/3.
Is f3 equivalent to f1:  False.
    
```
Hints:

In Lab 5, we worked through the Fraction class from ThinkCS Chapter 18. In the textbook, addition (__add__) is written. Follow that template for the functions above.

A list of the function names for arithmetic and boolean operators can be found at the end of the Geeks for Geeks tutorial.

Due Date: 5pm, Tuesday, 12 March
Reading: Textbook: Chapter 1 & Lab 5
Available Libraries: Core Python 3.6+, pandas

Senators

Write a program, using the pandas package, that asks the user for the name of an input CSV file and the name of an output CSV file. The program should open the file name provided by the user. Next, the program should select rows where the field senate_class is non-empty and write the first_name and last_name to a file with the output file name provided by the user.

For example, if the file was legislators-current.csv with the first 3 lines of:

last_name,first_name,middle_name,suffix,nickname,full_name,birthday,gender,type,state,district,senate_class,party,url,address,phone,contact_form,rss_url,twitter,facebook,youtube,youtube_id,bioguide_id,thomas_id,opensecrets_id,lis_id,fec_ids,cspan_id,govtrack_id,votesmart_id,ballotpedia_id,washington_post_id,icpsr_id,wikipedia_id
Brown,Sherrod,,,,Sherrod Brown,1952-11-09,M,sen,OH,,1,Democrat,https://www.brown.senate.gov,503 Hart Senate Office Building Washington DC 20510,202-224-2315,http://www.brown.senate.gov/contact/,http://www.brown.senate.gov/rss/feeds/?type=all&,SenSherrodBrown,SenatorSherrodBrown,SherrodBrownOhio,UCgy8jfERh-t_ixkKKoCmglQ,B000944,00136,N00003535,S307,"H2OH13033,S6OH00163",5051,400050,27018,Sherrod Brown,,29389,Sherrod Brown
Cantwell,Maria,,,,Maria Cantwell,1958-10-13,F,sen,WA,,1,Democrat,https://www.cantwell.senate.gov,511 Hart Senate Office Building Washington DC 20510,202-224-3441,http://www.cantwell.senate.gov/public/index.cfm/email-maria,http://www.cantwell.senate.gov/public/index.cfm/rss/feed,SenatorCantwell,senatorcantwell,SenatorCantwell,UCN52UDqKgvHRk39ncySrIMw,C000127,00172,N00007836,S275,"S8WA00194,H2WA01054",26137,300018,27122,Maria Cantwell,,39310,Maria Cantwell

Then a sample run of the program:

Enter input file name: legislators-current.csv
Enter output file name:  senatorNames.csv

And the first three lines of senatorNames.csv would be:

first_name,last_name
Sherrod,Brown
Maria,Cantwell

Hint: Use pandas to read in the CSV and select the name columns. When saving to the file, only save the columns (not the index). For example, df_out.to_csv(out_name, index=False)

Due Date: 5pm, Friday, 15 March
Reading: Textbook: Chapter 3 & Lab 6
Available Libraries: Core Python 3.6+

Linked List Search

Using the Node class from Lab 6, write a function that searches a linked list and returns True if found and False otherwise. Your function should be of the format:

def search_list( lst : Optional[ListNode], target : int) -> bool:

where a ListNode is:

class ListNode:
  def __init__(self, val=0, next_node=None):
    self.val = val
    self.next = next_node

For example, if target is 3 and lst_1 is:

then search_list( lst_1, target ) would return True. Writing this in Python:

lst = ListNode(2)
lst.next = ListNode(4)
lst.next.next = ListNode(3)

print(f"Is 3 in lst?  {search_list(lst,3)}")
print(f"Is 10 in lst?  {search_list(lst,10)}")

The resulting output:

Is 3 in lst?  True
Is 10 in lst?  False

A helpful function for printing out your list:

def list_2_str( lst ):
  """
  Helper function for printing out lists
  """
  current = lst
  lst_str = ""
  while current is not None:
      lst_str = lst_str + "->" + str(current.val)
      current = current.next
  if len(lst_str) > 0:
      #Get rid of leading "->" in string 
      lst_str = lst_str[2:]
  return lst_str

Due Date: 5pm, Monday, 18 March
Reading: Textbook: Chapter 3 & Lab 6
Available Libraries: Core Python 3.6+

Balanced Parenthesis

Given a string line that contains alphanumeric characters as well as '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
```
def is_valid(line: str) -> bool
```
Examples:
1. If line is print("Hello"), then is_valid(line) returns True since the opening ( is matched with ).
2. If line is words[-1].join(), then is_valid(line) returns True since the opening [ is matched with ] and ( is matched with ).
3. If line is words[0), then is_valid(line) returns False since there is an opening [ but no matching ].
4. If line is (((words[0] == 'Hi') or (words[0] == 'Hello')) and (words[-1] == 'Bye')), then is_valid(line) returns True since if we look at the parentheses: ((()())()) they follow the matching rules.
Note: This is a variation on LC 20. See Classwork 6 in Lecture 6.

Due Date: 5pm, Tuesday, 19 March
Reading: Textbook: Chapter 3 & Lab 6
Available Libraries: Core Python 3.6+

Increment Number

Using the Node class from Lab 6, assume each val in a node contains a digit: 0 to 9. Each linked list represents a large number in reverse order. For example, the list:

The smallest part, or ones column, is 2. The tens column is 4. And the hundreds column is 3. So this represents 342.

Write a function that adds one to a large number and returns the value. Your function should be of the format:
```
def increment_num( lst : Optional[ListNode] ) -> Optional[ListNode]:
```
where a ListNode is:
```
class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
```
For example, if lst_1 is 2 -> 4 -> 3, then increment_num( lst_1 ) would return a linked list with 3 -> 4 -> 3.

If lst_2 is 9 -> 9 -> 1 then increment_num( lst_2 ) would return a linked list with 0 -> 0 -> 2 since adding one to 199 yields 200.
Hint: Think about what happens when a digit is 9. See Classwork 7 and Lecture 7 for an example of adding large numbers.

Due Date: 5pm, Friday, 22 March
Reading: Textbook: Chapter 3, Lab 5 & Lab 6
Available Libraries: Core Python 3.6+

Palindromes
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return True if it is a palindrome, or False otherwise:
```
def is_palindrome(input_s: str) -> bool
```
Examples:
1. If input_s = "A man, a plan, a canal: Panama", then the output is True since "amanaplanacanalpanama" is a palindrome.
2. If input_s = "race a car", then the output is False since "raceacar" is not a palindrome.
3. If input_s = " " , then the output is True since s is an empty string "" after removing non-alphanumeric characters, and an empty string reads the same forward and backward, it is a palindrome.
Note: This is LC 125. See Classwork 6 in Lecture 6 and Classwork 7.2 in Lecture 7.

Due Date: 5pm, Monday, 25 March
Reading: Textbook: Chapter 3 & Lab 7
Available Libraries: Core Python 3.6+

Checkout Lines

Write a function that models a grocery store checkout lines

def checkout_lines(carts: List) -> int

that takes a list of integers representing the number of items in customers carts and returns the amount of time it takes for all customers to checkout.

There are 3 checkout lines, and at each time step, one item can be processed. Any checkout with 0 items left to process takes the next customer from carts.

Example: Say carts = [5,1,2,4,2].

At time 0, all checkers are available and we send the first 3 customers to checkers: 5,1,2 items to be processed.
At time 1, we have processed an item, so, there's 4,0,1 items.
Since Checker #2 is available, we send the next customer to them and decrease the other two checkers to get 3,4,0.
Now, Checker #3 is available, so, we send the next customer there and decrease the other two to get 2,3,2.
We continue sending customers to open checkers and decrementing counts until we reach 0,0,0. The function returns the total time which is 7.

More details:

Time	Checker #1	Checker #2	Checker #3
0	0	0	0
1	5	1	2
2	4	0	1
3	3	4	0
4	2	3	2
5	1	2	1
6	0	1	0
7	0	0	0

Due Date: 5pm, Tuesday, 26 March
Reading: Textbook: Chapter 3 & Lab 7
Available Libraries: Core Python 3.6+

Number Converter

In Section 3.8 from Lab 7, code was developed to convert decimal numbers into binary.

For this program, write a function that will convert decimal numbers into other base numbers (where the base is <= 10):
```
def number_converter(num: int, base=2:int) -> str
```
The default is to convert the number to binary (base = 2) but your function should allow the user to specify other bases.

For example:
```
print(f"15 base 2 is {number_converter(15)}.")
print(f"15 base 8 is {number_converter(15,base=8)}.")
```
would print:
```
15 base 2 is 1111.
15 base 8 is 17.
```
Due Date: 5pm, Tuesday, 2 April
Reading: Textbook: Chapter 5 & Lab 8
Available Libraries: Core Python 3.6+

Find All Duplicates

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
```
def find_all_duplicates(nums: List) -> List
```
You must write an algorithm that runs in O(n) time and uses only constant extra space.

Examples:
1. ```
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
```
2. ```
Input: nums = [1,1,2]
Output: [1]
```
3. ```
Input: nums = [1]
Output: []
```
Hint: This is LC 442 (Find All Duplicates in an Array). See Lab 8.
Due Date: 5pm, Friday, 5 April
Reading: Textbook: Chapter 5 & Lab 8
Available Libraries: Core Python 3.6+

Numbers Disappeared

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
```
def nums_disappeared(nums: List) -> List
```
Examples:
1. ```
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
```
2. ```
Input: nums = [1,1]
Output: [2]
```
Hints:
- It is very straightforward if you use extra space. Can you do this in O(n) time and O(1) space?
- This is LC 448 (Find All Numbers Disappeared in an Array). See Hints at LeetCode for how to use only constant space and Lab 8.
Due Date: 5pm, Tuesday, 9 April
Reading: Textbook: Chapter 5 & Lab 9
Available Libraries: Core Python 3.6+

Minimum in Rotated Sorted Array

Given a sorted rotated array nums of unique elements, return the minimum element of this array.
```
def min_rotated(nums: List) -> int
```
You must write an algorithm that runs in O(log n) time.

Examples:
1. ```
Input: nums = [3,4,5,1,2]
Output: 1
```
2. ```
Input: nums = [4,5,6,7,0,1,2]
Output: 0
```
3. ```
Input: nums = [11,13,15,17]
Output: 11
```
Hint: This is LC 153. Find Minimum in Rotated Sorted Array.
Due Date: 5pm, Friday, 12 April
Reading: Textbook: Chapter 5 & Lab 10
Available Libraries: Core Python 3.6+

Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.
```
def sort_by_parity(nums: List) -> List
```
Return any array that satisfies this condition.

Examples:
1. ```
Input: nums = [3,2,1,4]
Output: [2,4,3,1]
```
  Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
2. ```
Input: nums = [0]
Output: [0]
```
Hint: This is LC 905. Sort Array By Parity and see Lab 10.
Due Date: 5pm, Monday, 15 April
Reading: Textbook: Chapter 5 & Lab 10
Available Libraries: Core Python 3.6+

Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.
```
def group_anagram(strs: List) -> List
```
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

Examples:
1. ```
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
```
2. ```
Input: strs = [""]
Output: [[""]]
```
3. ```
Input: strs = ["a"]
Output: [["a"]]
```
Hint: This is LC 49. Group Anagrams and see Lab 10.
Due Date: 5pm, Monday, 6 May
Reading: Textbook: Chapter 5 & Lab 11
Available Libraries: Core Python 3.6+

Kth Smallest Element

Write a function that takes a list of numbers and returns the kth smallest number:
```
def kth_smallest(nums: List, kth = 1: int) -> int
```
Examples:
1. If nums = [19,8,1,20,5,45,7,10], then kth_smallest(nums) returns 1.
2. If nums = [19,8,1,20,5,45,7,10], then kth_smallest(nums, kth=3) returns 7.
3. If nums = [30,25,20,15,10,5,0], then kth_smallest(nums, kth=4) returns 15.
Hint: The built-in Python library heapq may be useful.
Due Date: 5pm, Tuesday, 7 May
Reading: Textbook: Chapter 5 & Lab 12
Available Libraries: Core Python 3.6+

BST Insert

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
```
def insert(root: TreeNode, val: int) -> TreeNode:
```
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

The tree node class is:
```
# Definition for a binary tree node.
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
```
Example: The val = 5 inserted into the tree:

The file p28_driver.py contains some more examples that test the function. The first part sets up a new tree:
```
my_tree = None
my_tree = insert(my_tree, 10)
print("added first node")
print(inorder(my_tree))
```
The inorder() function is a helper function that prints out a node with arrows pointing to its left and right children. Since there's only a root node to start, the left and right have no values, just parenthesis to show that they are there:
```
() <- 10 -> ()
```
We can more nodes to binary search tree:
```
some_vals = [3,5,20,15,1]
for val in some_vals:
    my_tree = insert(my_tree, val)
    print(inorder(my_tree))
```
As we loop through the list, we insert the value and then print out the modified tree:
```
(() <- 3 -> ()) <- 10 -> ()
(() <- 3 -> (() <- 5 -> ())) <- 10 -> ()
(() <- 3 -> (() <- 5 -> ())) <- 10 -> (() <- 20 -> ())
(() <- 3 -> (() <- 5 -> ())) <- 10 -> ((() <- 15 -> ()) <- 20 -> ())
((() <- 1 -> ()) <- 3 -> (() <- 5 -> ())) <- 10 -> ((() <- 15 -> ()) <- 20 -> ())
```
Similarly, we can build another tree from the list, [1,2,4,8,16,32]:
```
#Making another tree from [1,2,4,8,16,32]
double_vals = [1,2,4,8,16,32]
another_tree = None
for val in double_vals:
    another_tree = insert(another_tree, val)
    print(inorder(another_tree))
```
Since the values are in order, inserting into the binary search tree yields are very long, stringy tree with no left children:
```
() <- 1 -> ()
() <- 1 -> (() <- 2 -> ())
() <- 1 -> (() <- 2 -> (() <- 4 -> ()))
() <- 1 -> (() <- 2 -> (() <- 4 -> (() <- 8 -> ())))
() <- 1 -> (() <- 2 -> (() <- 4 -> (() <- 8 -> (() <- 16 -> ()))))
() <- 1 -> (() <- 2 -> (() <- 4 -> (() <- 8 -> (() <- 16 -> (() <- 32 -> ())))))
```
Hint: This is LC 701. Insert into a Binary Search Tree and see Lecture 12 and Lab 12.
Due Date: 5pm, Friday, 10 May
Reading: Textbook: Chapter 7 & Lab 12
Available Libraries: Core Python 3.6+

Find the Town Judge

In a town, there are num people labeled from 1 to num. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:
1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.
You are given an array trust where trust[i] = [a_i, b_i] representing that the person labeled a_i trusts the person labeled b_i. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.

Your function should be of the form :
```
def find_judge(num: int, trust: List[List[int]]) -> int:
```
and return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Examples:
1. Input: n = 2, trust = [[1,2]]
  Output: 2
2. Input: n = 3, trust = [[1,3],[2,3]]
  Output: 3
3. Input: n = 3, trust = [[1,3],[2,3],[3,1]]
  Output: -1
Hint: This is LC 997 (Find the Town Judge) and see Lecture 12 and Lab 12.
Due Date: 5pm, Tuesday, 14 May
Reading: Textbook: Chapter 7 & Lab 13
Available Libraries: Core Python 3.6+

Providence Size

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given the number of a city, num and an n x n matrix is_connected where is_connected[i][j] = 1 if the ith city and the jth city are directly connected, and is_connected[i][j] = 0 otherwise.

Write a function:
```
def province_size(num: int, is_connected: List[List[int]]) -> int:
```
that return the total number of cities in the province containing num.

Examples:

The return value is 2 for num = 1 since there are 2 cities in the province containing 2. If num = 3, then the return is 1 since city 3 is isolated and its province contains only it.

The return value is 1 for num = 1 since city 1 is isolated and its province contains only it. Similarly, the return value is also 1 for cities 2 and 3 since they are also isolated and their provinces contain only themselves.

Hint: This is a simplier version of LC 547 (Number of Provinces) . See Lecture 13 and Lab 13.

Programming Assignments CSci 227: Programming Methods Department of Computer Science Hunter College, City University of New York Spring 2024

General Notes

Autograder Notes

Programming Assignments

Programming Assignments
CSci 227: Programming Methods
Department of Computer Science
Hunter College, City University of New York
Spring 2024