Here's a nice data-structures / algs / Python review assignment to make sure that everyone is comfortable with the essentials for this course!

This is a rare individual Classwork exercise just to make sure everyone is set up!

In particular, this exercise will make sure you:

• Understand all of the course's policies and tools that we'll be using

• Have your Python development environment set up

• Review all necessary Python, Data Structures, and Algorithms concepts to succeed in this class

Start with the solution skeleton in-hand! The following will also serve as your submission mechanism (see submission instructions below).

PostCommit

Included in the skeleton are:

• review_exercises.py containing the skeletons of all exercises you'll need for the programmatic component of this classwork. Read on for more specifications on what to do herein.

• review_tests.py to validate your solutions to the review exercises. These will serve as a checklist for when you've successfully completed a component!

• mypy.ini, pytest.ini configuration files for mypy, pytest respectively. Do not change these!

• .gitignore a set of patterns for git to avoid committing. You may modify this file if your commit attempts to add any project files to the repo (e.g., VSCode .project files or pycache folders, which should not be submitted).

Note: please read this section carefully -- to get full credit for this assignment, there are some components both within and outside of the provided skeleton above!

Some Light Reading

Make sure you're apprised of all of the class' mechanics and policies!

1. Read through the class' syllabus.

   Course Syllabus

   
   

2. Read through the CMSI Academic Honesty slides:

   LMU CMSI Academic Honesty

   
   

Much Ado About You

Let's get to know each other a bit! Especially because...

On Brightspace, under the class' Discussion tab, you'll find a forum Topic for Introductions. Make a new Thread here with the following information:

• Required: List your name in the Thread title, any nicknames or pronunciation you want in the thread itself, any background information you'd like me and your classmates to know about you, and what your interests are in artificial intelligence.

• Optional: feel free to also include your picture / pictures of pets or other important parts of your life, hometown, hobbies, if you're working on or want to work on side projects with anyone in the class, etc. just keep everything appropriate and polite.

An example post from yours truly has been made on the forum for your illustrative pleasure.

Remembering the Taste of Py

If you are already familiar with Python Development Environment, Git, Dependencies like mypy, pytest and Python style, you may skip this task--but be warned that you will be graded on all of the above!

Note: All of the following setup guides are available as references in the course page's Materials tab!

Let's make sure you're ready to hit the ground running with the Python development in this course!

1. Make sure you understand how to use Git + GitHub (which will be employed in all assignments on the course):

   PostCommit

   
   

2. Read through the Python Development Environment Setup guide and install an IDE or setup a new workspace for this course.

   Python Development Setup

   
   

3. Read through the minimal Python programming style expectations for this class (though know that this is an *additive* guide to be included atop all of the good style habits you've learned from previous courses):

   Python Style Guide

   
   

4. Although many of you may be familiar with dynamically typed Python, this course will push you to think about types and data structures very carefully and instead uses statically typed Python, as through the mypy syntax.

   A later part of this introduction exercise will walk you through more of this paradigm, but you should first acquaint yourself with the mypy documentation.

   Read the "Getting started", "Type hints cheat sheet", and "Built-in types" pages located at the following link (about a 10-15 minute read):

   mypy Docs

No Lax Lexicons

One of the easiest ways to prepare for the coming semester is making sure that you understand some important vocabulary! Make sure you recall all of the following and look up anything you've forgotten from your prerequisite classes! (The checkboxes don't do anything and are just to help you tick off what you recall or don't)

For anything that looks unfamiliar, feel free to stop by TA or Professor office hours for review -- the first TA recitation will also review some of this!

Classes vs. Objects

Attributes in Python classes and the self keyword

Overriding Methods, esp. __eq__, __hash__, __lt__, __str__

References and Aliasing vs. Values and Literals

Property vs. Identity Equivalence

Asymptotic Runtime Analysis and Big-O Notation

Search, Components of Search Problems, Heuristics

Game Trees and Utility

Dynamic Programming: esp. Top Down vs. Bottom Up

Constraint Satisfaction Problems

Local Search Methods: esp. objective functions and hillclimbing

Test-driven Development, Unit Tests, Assert Statements

Tutorials

---

[Optional] Need a refresher on some Python and data structures topics? Take a look at a few video tutorials below! They contain everything you'll need for the exercises that follow.

Classes and Mypy Typing

Equivalence

Hashing

Priority

	GenAI use for the entirety of the next portion is BANNED for code production as it will shortcut your learning and generalizable skills (besides, there's not much code to write, the exercise is meant to refresh *your* memory) though is always OK for understanding error messages, interpreting skeleton code, etc. as outlined in the syllabus.

Finally, time for a little Python and Data Structures review! Head on over to the PostCommit assignment linked in the Solution Skeleton above.

Conflict Resolution

Let's start with a simple function, get_conflict as defined below, whose solution might be useful as a helper method in a future assignment!

  def get_conflict(dict1, dict2):
      '''
      Given 2 dictionaries of string keys mapped to boolean values, returns the first
      key that is mapped to True in one dictionary but False in the other. In the event
      of no such "conflicts," returns None, and if multiple conflicts exists, can return
      any one of them.
      
      Parameters:
          dict1, dict2: dict[str, bool]:
              Dictionaries of string keys mapped to boolean values.
      
      Returns:
            Optional[str]:
                The first key with a conflicting boolean value between dictionaries, or
                None if no such key exists. 
          
      Examples:
          get_conflict({"A": True, "B": False, "C": True}, {"A": False, "B": False, "C": True}) => "A"
          get_conflict({"A": True}, {"B": False}) => None
      '''
      # [!] TODO: Complete with your implementation!

There are a few things that we need to do above.

1. Missing Type Hints: If we navigate into the folder containing review_exercises.py and execute the mypy type checker via the command mypy review_exercises.py, we'll notice a couple of errors complaining that error: Function is missing a type annotation.

   This is because, although we are specifying the types of parameters and the return of the get_conflict function in the docstring, we have yet to provide type hints to the function signature that will allow static type checking for more robust code.

   To fix this:

   • Add the type hints to the function signature, specifying the parameter and return types as given in the docstring. For review of this syntax, see the reading materials and video above.

   • After successfully completing the above, if you re-run mypy review_exercises.py, there will now be only 1 error (that you'll fix in the next exercise) instead of 2 -- progress!

2. Implement Solution: Try to solve the method *paying careful attention to computational effeciency!*.

   • Hint: remember that you're operating on two dictionaries, which are implemented as hash tables! These data structures perform best with membership tests and O(1) access to keys.

   • Once you've implemented your changes, run pytest -k get_conflict. You can continue when all tests pass!

   • Once your tests are passing and you've added your type hints, make a Git commit and then progress to the next section.

   Warning: make sure you've installed the pytest-timeout package before testing, otherwise your tests may appear to pass when they shouldn't! Simply: pip install pytest-timeout

Compatible Sets

Next up, count_set_member_pairs as defined below!

  def count_set_member_pairs(sets):
      '''
      Given a list of sets of strings, counts the number of pairs that can be made between
      these sets where a pair can be formed whenever at least one string is common between
      both sets. Should count each possible pair exactly once.
      
      [!] Hint: use a particular method in the itertools package to simplify your life!
      
      Parameters:
          sets: list[set[str]]:
              A list of sets of strings.
      
      Returns:
            int:
                The number of pairs that could be formed between sets in the given list.
          
      Examples:
          count_set_member_pairs([
              {"A"},
              {"B", "A"},
              {"C", "B"}
          ]) => 2     # (the first two and last two sets can be paired)
          
          count_set_member_pairs([
              {"A", "C"},
              {"B", "A"},
              {"C", "B"},
              {"A", "B", "C"}
          ]) => 6    # (can you count all of the pairs?)
          
          self.assertEqual(0, count_set_member_pairs([
              {"A", "D"},
              {"B", "E"},
              {"C", "G"},
              {"X", "Y", "Z"}
          ])) => 0    # (no common strings in these sets)
      '''
      # [!] TODO: Complete with your implementation!

There are a few things that we need to do above.

1. Missing Type Hints: Same as the previous exercise, start by fixing the type hints to make mypy happy!

   • Add the type hints to the function signature, specifying the parameter and return types as given in the docstring. For review of this syntax, see the reading materials and video above.

   • After successfully completing the above, if you re-run mypy ., there should be NO errors!

2. Implement Solution: Try to solve the method *paying careful attention to computational effeciency!*.

   • Hint: take a look at the itertools package's methods to simplify your life at examining pairs of sets!

   • Once you've implemented your changes, run pytest -k count_set_member_pairs. You can continue when all tests pass!

   • Once your tests are passing and you've added your type hints, make a Git commit and then progress to the next section.

Signing a Few Things in Blood (i.e., a Git Commit)

---

• Once you have completed the review, head on over to the README.md file to acknowledge several last items requiring your initials.

  Most README files are in Markdown (.md) format, which is a handy language for generating quick documentation and will render on your repository page on GitHub. If you're unfamiliar, begin by reading a bit about Markdown here:

  Markdown Quick Reference

  
  

• Commit your final changes to the review_exercises.py and README.md files and then push to your GitHub repository to submit!

• Classworks are *typically* group assignments, but this one is solo to make sure everyone is comfortable with their development environment before continuing.

• Remember that you're always free to consult me by Slack, email, or office hours (as well as our helpful TAs!) if you get stuck!

• Since the above are primarily syntax-related tasks, feel free to ask ChatGPT for help reviewing; here are some acceptable queries you might use to get unstuck:

  • Show me an example of parameters vs. arguments in Python.

  • How do I give type hints for attributes in a Python class constructor?

  • Give me some examples of the itertools methods in Python.

You will be submitting your assignments through PostCommit per the instructions in the syllabus!

What

Push your modified review_exercises.py and README.md to your GitHub repository.

How

To clone this assignment (if you need a refresher), consult the guide here:

GitHub Tutorial

To submit this assignment:

• Place your name at the designated spot in README.md.

• Simply push your final, submission copy to the GitHub repository associated with your account.

PostCommit Quiz!

Recall: sometime following the deadline of this assignment, there will be a take-home PostCommit Quiz for you to practice your technical interview skills! See in-class announcements for date and preparation.

In future assignments, the quiz will be taken in-person during class, but this one is meant to get you calibrated to what such a quiz will look like!