|
|
CS 116 Tutorial 9: Search & Sorting Algorithms, Dictionaries, and Classes (Module 8 and 9)
Reminders
- Assignment 8 is due on Friday, November 22nd at 10am;
- Vote for preferred weekend for Q&A session on Piazza!
Searching and Sorting Algorithms
-
Sometimes a list could be very close to its sorted version, such tha it looks a like a rotation of a sorted list. For example, [4, 6, 1, 3] is a rotation of a sorted list of [1, 3, 4, 6], when every element is shifted by 2 to the right. We'll called this type of sorted list, r-Sorted list.
Write a function, restore_sorted_list, that consume a r-Sorted list and mutates it to a sorted lists.
Exmaple:
L = [4, 6, 1, 3]
restore_sorted_list(L) => None
L => [1, 3, 4,6]
Dictionaries
Write a function list_multiples that consumes a string s and returns a list
in alphabetical order containing every character in s that appears more than once.
Use dictionaries.
Examples:
list_multiples("abcd") => []
list_multiples("bacaba") => ["a", "b"]
list_multiples("gtddyucaadsa") => ["a", "d"]
Write a function xor that consumes two dictionaries (d1 and d2), and returns
a new dictionary.
The returned dictionary will contain all the keys that
appear in exactly one of d1 or d2 (but not both).
The value associated with each key will be the same as the one found in the original dictionary.
Examples:
d1 = {1:'a', 2:'b', 3:'c', 4:'d'}
d2 = {5:'e', 6:'f', 7:'g', 8:'h'}
d3 = {5:'q', 6:'l', 7:'c', 8:'e'}
xor(d1, d2) => {1:'a', 2:'b', 3:'c', 4:'d', 5:'e', 6:'f', 7:'g', 8:'h'}
xor(d2, d3) => {}
Classes
Student is a class with fields name, faculty, program, year, and courses:
name is a non-empty string representing the student's full name;faculty is a non-empty string representing the student's faculty;
Full version: e.g "Environment" rather than "Env" program is a non-empty string representing the person's program (or major);
e.g. "Honours Mathematics" and "Art and Business" year is a natural number representing the student's academic year;courses is a list of strings representing the courses the student is taking in the current term;
Below is the definition of the __init__, __repr__, __eq__ function for the Student class.
class Student:
""" Fields: name (Str),
faculty (str),
program (str)
year (Nat),
courses for the term (Listof Str)"""
# Constructor for Student:
# Calling Student(full_name, fac, prog, yr, titles) creates an
# object with name, faculty, program, year, courses initialized to
# full_name, fac, prog, yr, titles, respectively
# Requires:
# * full_name is a non-empty string for the student's name
# * fac is a non-empty string for the full faculty name (e.g. Mathematics not Math)
# * prog is non-empty string for program of study (e.g. "Psychology" or "Applied Mathematics")
# * yr is a positive integer, for student's year of study
# * titles is a list containing the abbreviated version of courses student
# is currently taking(e.g. "CS 116" rather than "Intro to Comp Sci 2")
# Note: __init__ is not called directly by name
def __init__(self, full_name, fac, prog, yr, titles):
self.name = full_name
self.faculty = fac
self.program = prog
self.year = yr
self.courses = titles
# Calling student1 == student2 is equivalent to calling self.__eq__(other)
# to compare fields of self and other.
# Note: __eq__ is not called directly by name
def __eq__(self, other):
if isinstance(other, Student):
return self.name == other.name and \
self.faculty == other.faculty and \
self.year == other.year and \
self.program == other.program and \
self.courses == other.courses
else:
return False
# Calling print(s), for Student s, will print the string returned by __repr__.
# Displaying the value in the interactions window will use the returned string
# as well
# Note: __repr__ is not called directly
def __repr__(self):
s = "{} ({}, {}, {}, {})".format(self.name, self.faculty, self.program, self.year, self.courses)
# returns Name (Faculty, Program, Year, Courses)
return s
Examples of Student Objects:
YQ_W = Student("Y.Q. Wang", "Mathematics", "Math/Teaching", 2,
["MATH 239, STAT 231, CO 250, ENGL 109D"])
Nicole_V = Student("Nicole Velocci", "Mathematics", "Statistics", 2,
["ENGL 109", "MATH 237"])
Paul_S = Student("Paul Shen", "Applied Health Science", "Health Studies", 2,
["MATH 106", "CS 234", "CS 200", "HLTH 273", "ECON 101"])
Steve_Z = Student("Steve Zhang", "Arts", "Psychology", 2,
["PSYCH 207", "PSYCH 261", "PSYCH 202"])
Jason_A = Student("Jason Arl", "Mathematics", "Honours Mathematics", 2,
["MATH 235", "MATH 237", "STAT 231"])
Tyler_H = Student("Tyler Hall", "Mathematics", "Mathematical Physics", 1,
["MATH 136", "MATH 148", "STAT 230", "ENGL 119", "CHEM 121"])
Kyle_H = Student("Kyle Hauck", "Mathematics", "Applied Mathematics", 3,
["AMATH 351", "AMATH 363", "AMATH 342", "STAT 332"])
Logan_S = Student("Logan Stanley", "Science","Chemistry", 1,
["CHEM 120", "MATH 127", "PHYS 111"])
Liza_W = Student("Liza Wang", "Engineering", "Software Engineering", 3,
["BUS 121", "CS 343","CS 450"])
Dan_W = Student("Dan Wolczuk", "Mathematics", "Pure Mathematics", 1,
["MATH 148", "MATH 146", "CS 116"])
Write a class method add_courses in the student class, which consumes a list of strings, loc, and prints the number of courses the student current is taking and adds course to the student's courses.
Examples:
Paul_S.add_courses(["HLTH 230"]) will print "Paul Shen is currently taking 6 course(s)."
and Paul_S.courses == ["MATH 106", "CS 234", "CS 200", "HLTH 273", "ECON 101", "HLTH 230"]
Nicole_V.add_courses([]) will print "Nicole Velocci is currently taking 2 course(s)."
and Nicole_V.courses == ["ENGL 109", "MATH 237"]
Write a function organize_by_year which consumes a list of student objects, loS, and returns a dictionary where the names of the students will be in a list, in the same order they appear in loS and categorized by the year.
Examples:
organize_by_year([]) => {}
L = [Paul_S, Nicole_V, Dan_W]
organize_by_year(L) => {1: ["Dan Wolczuk"], 2:['Paul Shen', 'Nicole Velocci']}
Write a function is_same_faculty that consumes a non-empty list of students, los, and returns True if all the students belongs in the same faculty. Otherwise, the method returns False
Example:
is_same_faculty([Nicole_V]) => True
Mathies = [Nicole_V, Dan_W]
is_same_faculty(Mathies) => True
mixed = [Paul_S, Logan_S]
is_same_faculty(mixed) => False
|