EMA/D: Overview

These two EMs are applications of graph theory:

  • EMA is a glance of a small part of using graphs/trees in (classical) AI – it is usually what is covered in the first week of any AI class (note: not ML class) like CS370.
  • EMD is a very brief introduction of using graphs/trees in robotics and spatial planning.

Graph/tree search algorithms are a key part of both, hence why the two EMs are implemented together. The subtle difference is for AI applications there’s a flavor/emphasis on modeling the real world using graphs (despite the actual problem might not feel like relevant to graphs), whereas for robotic applications there’s usually some kind of spatial aspects naturally built in the problem.


Concepts used in EMA and EMD:


To earn a satisfactory completion for EMA:

  • Complete individually the EMA/D: Practice (Graph and Tree Search Algorithms) after reading about Difference between Graph/Tree search algorithmsThis quiz is counted for both EMA and EMD.
    • You should get all questions right (there are only a total of 6 of them.)
    • As usual, you have unlimited tries.
    • These practice quizzes are formally due on LDoC, but actually kept open until 5/1 11:59pm.
  • Complete Assignment (individually or in pairs).
    • You might need some techniques in Core Module 7: Combinatorics in this assignment. So if you are stuck, consider revisiting after getting more exposure to CM7.
    • You should submit by LDoC to ensure that you get at least one round of feedback.
    • You can keep submitting until 5/1 11:59pm.’

  • Complete individually the EMA/D: Practice (Graph and Tree Search Algorithms) after reading about Difference between Graph/Tree search algorithmsThis quiz is counted for both EMA and EMD.
    • You should get all questions right (there are only a total of 6 of them.)
    • As usual, you have unlimited tries.
    • These practice quizzes are formally due on LDoC, but actually kept open until 5/1 11:59pm.
  • Complete Assignment (individually or in pairs).
    • You should submit by LDoC to ensure that you get at least one round of feedback.
    • You can keep submitting until 5/1 11:59pm.

EMA/D: Difference between Graph/Tree search algorithms

Note: this asynchronous material is part of EMA (Graph Applications in AI) and EMD (Graph Applications in Robotics). Its corresponding quizzes were native in Canvas and not reproduced here.

We very briefly discussed some graph/tree search algorithms (DFS, BFS, IDS, and UCS) in class. You may have also learned about several of them in other classes.

But when is a search algorithm a graph search algorithm and when is it a tree search algorithm?


The most salient difference is graph search algorithms do not create (duplicated) vertices/nodes/states, whereas tree search algorithms do.

In other words, the search tree for graph search algorithms contains at most one copy of each vertex in the state graph.

graph2-mcs-10.5.png

Again let’s use the division directed graph as an example.

  • Suppose we run BFS tree search starting from vertex 1 without any precautions on avoiding repetitions.
    • Then every vertex, including vertex 1 itself, will appear in level 1 (because there is indeed an edge from vertex 1 to every vertex including itself). So level-1 of the BFS tree will have all 12 vertices.
    • Then, since vertex 1 is also in level 1, when it gets explored again, it will lead to all 12 vertices appearing in level 2 again as children of vertex 1, and so on.
    • Therefore, if none of the states is the goal, the BFS tree has infinitely many levels/vertices and the search does not terminate.
  • Instead, if we run BFS graph search starting from vertex 1, while also maintaining a set of visited vertices (so that we don’t revisit vertices again):
    • Then every vertex other than vertex 1 will appear in level 1 (but vertex 1 itself does not). So level-1 will have 11 vertices.
    • And since every vertex gets discovered already in level 1, we will not find any more unvisited vertices while exploring the vertices in level 1.
    • Therefore, if none of the states is the goal, the BFS terminates after exploring level 1 and declares failure. The resulting tree will have exactly 12 vertices.

It feels graph search is inherently better, but the catch is again that it needs to maintain the set of visited vertices, which can use a prohibitive amount of memory (depending on the size of the problem).

EMB: Overview

This EM is about an application of probability in (differential) privacy.

The whole field of differential privacy is about the tradeoff between accuracy (in publishing statistics from a survey/census, or more generally, aggregating data) and privacy (releasing or leaking information about individuals in the data).

Broadly speaking, privacy appears in many downstream courses offered by the department (though not all of them models privacy using the differential privacy regime):


Concepts used in EMB:


To earn a satisfactory completion for EMB:

  • Complete Assignment (individually or in pairs).
    • You should submit by LDoC to ensure that you get at least one round of feedback.
    • You can keep submitting until 5/1 11:59pm.

EMB Additional Resources

Interactive Webpage on the Randomized Response Mechanism

This interactive webpage (re)-illustrates the randomized response mechanism in EMB Poll 2: Have you cheated? Private Version. It contains visualizations of (a richer version) of the scenario and let you play with the numbers. If you did not fully understand how the randomized response mechanism works (or missed it in class), this page might be a good resource.


DifferentialPrivacy.org

This webpage is a resource list on differential privacy; you can find a lot of DP literature by tracing this resource list.

EMC: Overview

This EM is a brief introduction to social choice theory, or more specifically, rank aggregation voting mechanisms.

Of all social computing/computational economics topics, this one is (in Shao-Heng’s subjective opinion) the best topic for an EM in CS230 because of its discrete nature: usually when people vote, it is to decide among a finite and discrete set of candidates/alternatives.

Downstream CS courses in this direction are CS323D (Computational Microeconomics) and CS535 (Algorithmic Game Theory). There is also some social choice theory covered in CS333 (Algorithms in the Real World).


Concepts used in EMC:


To earn a satisfactory completion for EMC:

  • Complete Assignment (individually or in pairs).
    • You should submit by LDoC to ensure that you get at least one round of feedback. However, since this module is late, there is a built-in bonus mechanism in this Gradescope assignment such that anyone who attends the class and learns the voting mechanisms should be able to get the assignment in one submission.
    • You can keep submitting until 5/1 11:59pm.

EME: Overview

This asynchronous elective module is a glance of classical cryptography.

An oversimplified way of summarizing cryptography in one sentence is that it is all about secure communication. We want to send and receive information from/to trusted parties while ensuring no other (untrusted) parties, potentially with malicious intent, are able to gain access to the information.

As an EM in CS230, we are only going to interact with one specific part of cryptography that happens to build on discrete math tools that we already have. This is therefore not a crash course on the history of cryptography nor even an overview of cryptography.


Concepts used in this EM:


To get credit for EME:

EME: Assignment

This assignment is a simple practice of using the RSA algorithm with sourcing parameters from your NetID. If you complete this assignment in pairs, decide which one’s NetID you will use, and keep it consistent.

  • Obtain the first two **distinct** letters in your NetID. Call them letter1 and letter2. Do not swap the order.
    • If all letters in your NetID are the same, use z for letter2.
  • Obtain the ASCII code of letter1 and letter2 (both in lowercase) respectively. Call them ascii1 and ascii2. Both numbers should therefore be between 97 and 122 (inclusive).
  • Obtain the ascii1-th prime using this webpage. It will be your p.
  • Obtain the ascii2-th prime using this webpage. It will be your q.
  • Choose r (and s) yourself.

If this is a regular programming assignment in CS330, we will have you implement your own code for the Euclidean Algorithm and modular exponentiation. You are still welcome to, but we promise no mandatory programming in this course. Therefore, check out the webpages below:


Then, submit to Gradescope only the following information:

  • The NetID in use
  • The public key pair (r,n)

You do NOT need to include any other intermediate steps/work.


We will then send you (through a comment in your Gradescope submission) a ciphertext. You should then decrypt the ciphertext and update your submission to include the plaintext. Therefore, your final submission should have the information below:

  • The NetID in use
  • The public key pair (r,n)
  • The plaintext

You earn the assignment credit as we verify the plaintext you submit is the plaintext we use.


Note that all EM assignments are due LDoC on paper, but there will not be any penalty until 5/1 11:59pm.

Any submissions by LDoC midnight will get at least one round of feedback, although we will try our best to give everyone feedback.

Since you do need at least one round of feedback for this assignment, we recommend everyone to submit once by LDoC.

EMF: Overview

This asynchronous elective module is a preview of CS334 (Mathematical Foundations of CS).

Broadly speaking, CS334 is about understanding what computers really are, in the most abstract form. It studies the following topics from a theoretical perspective:

  • What can be computed? What does it really mean when we say something can be computed?
  • What is a compiler (conceptually)? How do compilers work?
  • We use regular expressions in Python and Java all the time. But how do regular expressions work under the hood?

As an EM in CS230, we are only going to scratch the surface of these deep topics. More specifically, we will see the concepts of formal languages and deterministic finite automata (DFA). Those are usually the first few things taught in CS334.


Concepts used in this EM:


To get credit for EMF:

  • Complete individually EMF: Conceptual Quiz I (Formal Languages) and EMF: Conceptual Quiz II (DFA) after reading about the concepts.
    • You should get all questions right (there are only a total of 4 of them!)
    • As usual, you have unlimited tries.
    • These conceptual quizzes are formally due on LDoC, but actually kept open until 5/1 11:59pm.
  • Complete the JFLAP assignment (individually or in pairs).
    • All submissions by LDoC will get one round of feedback.
    • You can keep submitting until 5/1 11:59pm, but submissions after LDoC are not promised any feedback.

EMF: Assignment

JFLAP is a visual tool for experimenting with all CS334 concepts, developed by Professor Susan Rodger. You can download JFLAP 7.1 here. The DFAs you saw in the readings and quizzes were created in JFLAP.

JFLAP has a tutorial and a book. For our purposes, you only need to read at most one of the following (the UI is straightforward enough that you might be able to just play with it without reading tutorials):

  • Chapter Finite Automata -> Construct and Run and Manipulating Transitions in the tutorial
  • Chapter 1.1 and 1.2 in the book

After installing it (and potentially reading the tutorial/book), it is recommended that you try to recreate the two DFAs we saw in the material (the one that recognizes even binary numbers, and the one in the quiz). In fact, building the latter in JFLAP will probably help you with answering that quiz question.


After familiarizing yourself with JFLAP and DFAs enough, here is the only assignment question:

Build a DFA (in JFLAP) that accepts the language of at least two 2‘s followed by at least three 3‘s followed by zero or more 0‘s. Here are some strings that should be accepted by your DFA:

  • 22333
  • 223330
  • 222233330000
  • 223333333333333333333300

Save your DFA as a single JFLAP file and submit that file only to Gradescope.


Note: we have to make this assignment a programming assignment in Gradescope for it to accept your JFLAP file. Therefore, it has an “autograded part” by default, despite the fact that it is not autograded. Feel free to ignore anything about autograders in Gradescope for this assignment.

Note that all EM assignments are due LDoC on paper, but there will not be any penalty until 5/1 11:59pm.

Any submissions by LDoC midnight will get at least one round of feedback, although we will try our best to give everyone feedback.

Core Module 1: Logic

To-Do Date: Jan 16 at 11:59pm

The required reading for the first week/module is Chapter 2: Logic of the AIDMA textbook. This is one of the 3 textbooks that we will use as required reading for the core modules; you may want to download a local copy. Although only Chapter 2 is required, you may want to take a glance at the How to use this book page in the preface as well as Chapter 1: Motivation to get to know this book.

This book has many kinds of practice opportunities (Exercises, Fill in the details, Questions, Evaluates, Reading Comprehension Questions, and Problems – see the How to use this book page for details). Most of them are hyperlinked to their solutions for immediate checking of your comprehension of the material/concepts. We will not be using those officially in our class meetings very often (we sometimes do), but do take advantage of these questions to read actively.

If you already have a background and consider yourself adequately familiar with the module topic, you may find it tedious to read through the chapters sentence by sentence. It is okay for you in this case to skim the reading (or at least skip the practice questions in the book). Frankly, it is up to you how you use the reading. The bottom line is, by the start of each module’s first class meeting, we expect everyone to have a solid understanding of the basic concepts in the scope of the required reading. The prepare quiz is partially there to help you examine this.


To earn a satisfactory completion for CM1:

  • Read this required reading (and mark this post as done afterwards)
  • Get 80% or more questions correct in CM1: Logic Prepare Quiz (note that there’s a 1hr 15min cooldown between consecutive attempts)
  • Get a completion on recitation work by either attending or submitting on Gradescope
  • Get a satisfactory or above on the Gradescope assignment

OR

  • Get an excellent on all Gradescope assignment questions