Review Session For Quiz 1 Q&A

Administrative Updates

• Quiz #1: Scheduled for February 25, 2026 on Brightspace

  • Covers material from Lectures 1-7: foundational concepts through reductions
  • Satisfiability definition will appear in both Quiz #1 and the next quiz

• Paper Selection Deadline: February 26, 2026

  • TWO required items must be completed (in separate locations—this ensures you actually review the papers before committing to a choice):
    • (A) Upload PDF files: Under Assignments tab, upload actual PDF files (NOT links or cloud shares). Download PDFs from original source and manually upload to Brightspace
    • (B) Enter publication information: Under Quizzes tab, enter publication details (Title, Author, Year published, etc.) for each paper in order of preference (most interested first, then second, then third)
  • After completing both: Email the class designated email with subject line “Paper Selections” and include all publication information entered in Quizzes
  • Professor will check eligibility and assign you one paper
  • If papers are ineligible or already assigned to another student, you’ll be asked to submit three additional PDF options
  • Each student receives a DIFFERENT paper (no duplicates)
  • Questions? Email from Qmail to class designated email only

• Project Deadline: March 12, 2026 (All Phases)

  • BRIGHTSPACE DISCREPANCY ALERT: Brightspace incorrectly shows Phase 1 due on February 24th. The correct deadline per the syllabus is March 12th
  • If you see February 24th on Brightspace, email the professor immediately (do not send screenshots; describe the issue in text)
  • Implementation project involving set membership with hash tables
  • Three phases due respectively: March 12th, April 12th, May 12th
  • Two related documents required:
    • Requirements Document: Summary of features and project concepts
    • Submission Protocol Document: Students must identify where in the code each required feature is implemented, and provide C-Cloc statistics of the final code
  • C-Cloc (Counts Lines of Code): Freely available tool for code analysis
    • Run this tool on your completed project code (you don’t use C-Cloc in your program; it’s a post-submission analysis tool)
    • Provides statistics: blank lines, code lines, comment lines
    • Java-aware code counter
    • Link available in submission protocol document

• Project Overview: Set Membership Implementation with Command-Line Interface

  • This theory class intentionally includes practical programming experience beyond Turing machine theory. You’ll learn real-world programming skills while implementing theory concepts
  • Core concept: Hash table-based set operations
  • Phase 3 includes Turing machine implementation
  • Command-line flag processing (Unix-style flags with - prefix and = assignment)
  • Required flags: -firstname, -lastname, -id, -age, -newyork, -output
  • Data types: strings, integers, booleans, file names
  • Input file reading and hash table storage

• Review Session Format

  • Students submit questions via chat during review
  • Instructor provides answers and clarifications
  • All Q&A will be compiled and emailed to students
  • Material coverage: All lectures including reduction definitions and notation

• Technical Notes

  • Command-line arguments in Java: Parameters passed through main(String[] args)
  • Program naming convention: Membership class
  • Flag implementation follows Unix conventions
  • Implementation language: Java with emphasis on new programming features

Lecture Content

Session Overview

Today is a review day. Students submitted questions via chat about projects and assignments. All questions and answers are compiled in these notes, which will be emailed to students.

Project Documentation

Two project documents work together:

(a) Requirements Document: Lists the features and functionality you must implement (what to build)

(b) Submission Protocol Document: Specifies how you’ll prove you built it. You’ll identify where each required feature appears in your code and provide code statistics. This is the assessment mechanism—there’s no separate assessment rubric.

Command-Line Interface

Why Command-Line Processing?

The professor emphasized that while this is a computability/complexity theory class focused on Turing machines, the project intentionally includes practical programming experience. The command-line interface requirement serves several pedagogical goals:

1. New programming concepts: Students learn command-line argument processing beyond typical coursework
2. Data type parsing practice: Practice processing different data types (strings, integers, booleans, file names) from user input
3. Real-world programming: Understanding how programs receive configuration and data from the operating system
4. Language-specific features: In Java and C++, the main() method receives these arguments via argc/argv (C++) or String[] args (Java)

What is the “Membership” Program?

The project you’re implementing is called Membership. It’s an elaborated set implementation using hash tables. Here’s what it does:

1. Takes input: Receives person records (first name, last name, ID, age, residence info) from a command-line specified input file
2. Stores data: Places these records into a hash table for efficient lookup and management
3. Outputs results: Writes processed data to a specified output file
4. Persists state: Saves the hash table so it can be reused across multiple program runs (persistence feature)

The project is essentially implementing a membership database—think of it like managing a club or organization roster, where you need to efficiently store, retrieve, and manage member information.

Command-Line Basics

Terminal/Console: The interface where you type commands to run programs.

In Windows: From the search bar (run bar) on the bottom left of screen, type cmd.exe to open Command Prompt

In C-based languages, the main method receives parameters (inputs) from the command line via argc/argv (arguments = command-line parameters, sometimes from system environment).

Unix Flags

This project uses Unix-style flags, a convention introduced by the Unix operating system.

Format: User-defined flag names preceded by a minus sign (-), with values assigned using equals (=).

Why this matters: This allows flexible, human-readable command-line interfaces where flags can appear in any order.

Example Command

To run the Membership program with input:

java Membership -firstname=Steve -lastname=Smith -id=1234567890 -age=23 -NewYork=false -outputFile=results.txt -inputFile=members.txt

What’s happening here:

• You’re launching the Membership Java program
• Providing 7 pieces of information (for a single member) via flags
• These flags can be specified in any order (you could swap -firstname and -lastname, for example)
• The program parses each flag name and assigns its corresponding value

Flag Details:

Flag	Type	Purpose	Example Value
-firstname	String	Person’s first name	Steve
-lastname	String	Person’s last name	Smith
-id	Number/String	Unique identifier	1234567890
-age	Number	Person’s age	23
-NewYork	Boolean	Lives in New York?	true or false
-outputFile	File name	Where to save data	results.txt
-inputFile	File name	Where to read data	members.txt

Critical Requirement: Flag Order Independence

Your program must parse these flags in ANY order. Do not assume the user will provide them in a specific sequence.

For example, all of these should work identically:

java Membership -firstname=Steve -lastname=Smith -id=123
java Membership -id=123 -firstname=Steve -lastname=Smith
java Membership -lastname=Smith -id=123 -firstname=Steve

This requires your program to:

1. Read each flag name
2. Identify which flag it is based on the name (not position)
3. Assign the value to the appropriate variable
4. Handle all flags being present (or some being optional, depending on requirements)

Data input: Extra data will be read from the input file specified via -inputFile.

Additional Submission Protocol Details

Code Analysis Tool (Cloc): Freely available tool that conducts statistical analysis of your code:

• Number of blank lines
• Number of code lines
• Number of comment lines

Persistence: After your program exits, the data stored in your hash table must survive. On a second run, you should be able to load the previously stored hash table rather than starting fresh. This prevents data loss and demonstrates understanding of object serialization (Java’s persistence mechanisms).

Key Uniqueness: Hash tables require unique keys to avoid data loss. Since multiple people might share the same first and last name, assign each member a unique internal membership_id as the actual key. The professor gave an example: after 30 years of teaching, two students once had identical names in the same class—this is rare but possible, so your implementation must handle it.

Data Object Wrapping: Encapsulate member information (name, age, ID, location) into a dedicated object or data structure. This separates concerns and makes persistence simpler.

Output File Details: Your program should write membership records to the output file specified by -outputFile. Format and content requirements are in the submission protocol document.

Quiz Administration

Quiz Topics for Review

Coverage: Lectures 1-7. Topics include:

• Fundamentals: Difference between algorithm and process, role of infinite loops
• Complexity Analysis: Measures for analyzing algorithm complexity, order of notation, base arithmetic considerations
• Heuristics: Heuristics analysis techniques for simplifying complexity evaluation
• Edmonds’ Classification: Polynomial vs exponential time distinction
• Problem Categories: Decision problems vs optimization problems
• Randomness: Role of randomness in algorithms
• Determinism: Distinction between deterministic and non-deterministic algorithms, probabilistic algorithms
• Mathematical Foundations: Mathematical mappings and functions, partial functions and their handling
• Automaton: How automaton handle partial functions
• Search Spaces: Exhaustive searches, mathematical structures, search space size estimation
• Non-determinism: Concept and simulation through deterministic methods, cost implications
• Reduction: Definition and application of reduction notation
• NP-Hardness & Completeness: NP-hard and NP-complete problem definitions
• P vs NP: What “P equals NP” means
• Cook’s Problem: Satisfiability as the canonical NP-hard problem (definition required for exam)

Satisfiability Definition (required for exam): Given a Boolean predicate with input variables through , find values for through such that . You only need to find one satisfying assignment.

Question Count

How many questions? Unknown—the quiz has not yet been written.

Timing: Questions vary by type. True/False questions allow more questions than multiple-choice; fill-in questions allow the fewest (no hints provided).

Duration: Wednesday morning during regular class time plus five additional minutes.

Important: Do not assume the Brightspace clock is synchronized with your clock. This has happened before—students’ clocks have been out of sync with Brightspace’s clock, causing late-submission issues. Time your submission carefully and submit early.

Quiz Interface & Rules

Access: Solely via Brightspace under the QUIZZES tab (find Quiz #1).

Format: Each question appears one at a time. You cannot go back to a previous question once you advance.

Question order: Randomly selected by Brightspace for each student.

Question pool: Questions are drawn from a pool. While each student’s quiz is generated from the same pool, Brightspace randomly selects which questions appear. Students may receive different questions, but they share a thematic structure.

Example: If the lesson covered solving for in equations, the system generates 1,000 similar equations, each with a correct solution. These 1,000 questions form a pool—each student gets different equations, but all test the same concept.

Submission & Grading

Answer entry: Enter all answers directly into Brightspace. Do not email answers.

Monitoring: Professor monitors only the class designated email (CS722ProjectsQC@gmail.com).

Grading: Brightspace provides a report containing every student response and the timestamp of each answer (to the second). Manual grading follows. Grades are emailed via grade code for anonymity.

Brightspace score: Do not rely on any score Brightspace displays (even if it shows a score, ignore it). Historical note: incorrect scores have appeared (e.g., 22,400 due to settings errors). Instead, professor manually grades all responses and emails grades using grade codes to protect student anonymity. Do not share your grade code with anyone.

Security & Proctoring

Why strict security measures: The professor has observed students cheating in the past. One method: waiting for friends to finish the exam, then starting it to copy answers. The 10-minute start requirement prevents this.

Security implementation: A student cannot enter the quiz unless manually added to the roster.

Registration process (first 10 minutes only, until 7:55 AM):

(1) Email the professor from Qmail to the class designated email stating you are present and ready for the quiz

(2) Professor manually enters you into the quiz roster

(3) You must start the quiz within the first 10 minutes (not just email—you must actually click “start”)

If you do not start within 10 minutes (even if you emailed), your name will be removed from the quiz roster.

Timestamp recording: Brightspace records the exact second you start the quiz and the exact second you start and complete each question, plus time spent on each question. Long pauses are flagged as potentially suspicious activity.

Virtual Classroom Note

There is NO virtual classroom for the quiz. Brightspace automatically schedules virtual classrooms for all Monday/Wednesday sessions (even during breaks), and technically lists one for Wednesday. Do not enter it. The quiz exists only under the QUIZZES tab. Entering the virtual classroom would allow communication, which violates exam protocols.

Reduction

Notation: (read as ” reduces to ”)

The Irony of Reduction: The naming convention creates an apparent paradox:

• We say ” reduces to ”
• Yet it is that solves ‘s problem
• Typically, is already known to be hard, while ‘s hardness is unknown

Core Definition: When we write :

(1) is known to be hard (we’ve proven this)

(2) solves ‘s problem (there exists a relationship between the two)

(3) is not yet known to be hard

Conclusion from Reduction: By demonstrating that reduces to , we can conclude that is also as hard as is.

The Translation Cost: The letter "" in represents polynomial cost. This concerns a critical question:

• and may be entirely different problems that, at first glance, have nothing to do with each other
• Example: Euclidean geometry and Turing machines (as shown by Sam Weinberger’s research) - seemingly unrelated, yet complexity relationships exist
• When provides a solution, it may “speak a different language” than expects
• There is a cost to translate or transform what outputs into a form that can use

Translation Cost and NP-hardness: The translation cost must be polynomial:

• In the context of NP-hardness, this translation cost is the verification cost
• Alternative definition (Levin’s notion): The cost of providing the witness or certificate information (extra information needed to verify a solution)
• If this cost remains polynomial, then is confirmed to be NP-hard

Important Note for Exams: You only need to know Cook’s satisfiability definition for this quiz. The Karp reductions (21 NP-complete problems) and practical applications will be covered over 2-3 weeks in subsequent lessons with guided practice.