MIT 6.100L — Introduction to CS and Programming using Python

Complete, verified solutions to all problem sets and finger exercises of 6.100L — Introduction to CS and Programming using Python (MIT, Fall 2022), an independent from-skeleton implementation, part of a csdiy.wiki full-catalog build.

Overview

6.100L is MIT's introductory Python programming course: variables, control flow, functions, recursion, exceptions and assertions, object-oriented programming, data structures (lists / tuples / dicts / trees), algorithmic complexity, and a few substantial applications (a Hangman game, document-similarity statistics, a one-time-pad cipher, and LSB image steganography).

This repository imports the official Fall 2022 problem-set skeletons and completes every function to spec, then verifies each pset against the course's own student testers (which assign the same points the autograder does). It also implements the per-lecture finger exercises, grounded in the official OCW handouts, with a pytest suite that uses the handouts' worked examples as oracles.

Results (measured on Windows, CPU-only, Python 3.11.2)

Every problem set was run through its official student tester; every score is the tester's own reported score (see results/).

Assignment	What it does	Result (measured)
PS1 — Compound Interest	saving for a down payment; semi-annual raises; bisection search for the required rate	ps1_tester.py: 8/8 (A 3/3, B 2/2, C 3/3)
PS2 — Hangman	full interactive game; vowel/consonant penalties; ! help reveal	test_ps2_student.py: 5/5
PS3 — Document Distance	word/letter frequencies, similarity score, most-frequent words, TF-IDF	test_ps3_student.py: 5/5 (23 tests)
PS4A — Binary Trees	tree data representation, recursive height, min/max heap check	test_ps4a_student.py: 100%
PS4B/C — One-Time-Pad Cipher (OOP)	Message/PlaintextMessage/EncryptedMessage, encrypt/decrypt, brute-force pad search	test_ps4bc_student.py: 3.5/3.5
PS5 — Image Steganography	colour-deficiency filter (matrix multiply), LSB reveal of hidden BW & RGB images	test_ps5_student.py: 3/3
Finger Exercises (lectures 1–23)	one exercise per lecture, official prompts	pytest: 21/21

Real runs producing evidence in results/:

• PS4C decoded Bob's hidden story end-to-end by trying candidate pads and scoring by valid-English-word count — the full decoded text (the Wikipedia "Alice and Bob" article) is in results/ps4c_decoded_story.txt.
• PS5 produced real output images in results/ps5_outputs/: the four colour-deficiency simulations of image_15.png (image_15_{none,red,green,blue}.png) and the two revealed hidden images (revealed_hidden1_bw.png — a 2000×1000 BW image extracted from the single LSB; revealed_hidden2_rgb.png — a 600×398 RGB image extracted from the 3 LSBs, rescaled with n*255//7).

Implemented assignments

• PS1 — Compound Interest (ps1/): ps1a (fixed salary), ps1b (semi-annual raise), ps1c (bisection search for the savings rate).
• PS2 — Hangman (ps2/): has_player_won, get_word_progress, get_available_letters, reveal_letter, and the full hangman game loop.
• PS3 — Document Distance (ps3/): text_to_list, get_frequencies, get_letter_frequencies, calculate_similarity_score, get_most_frequent_words, get_tf / get_idf / get_tfidf.
• PS4A — Binary Trees (ps4/ps4a.py): tree1/2/3, find_tree_height, is_heap (parameterised by a compare function for min- or max-heaps).
• PS4B/C — One-Time-Pad Cipher (ps4/ps4b.py, ps4/ps4c.py): the Message class hierarchy, shift_char (wrapping printable ASCII [32,126]), apply_pad, decrypt_message, decrypt_message_try_pads, and decode_story.
• PS5 — Image Processing / Steganography (ps5/ps5.py): img_to_pix, pix_to_img, filter, extract_end_bits, reveal_bw_image, reveal_color_image.
• Finger Exercises (finger_exercises/): lectures 1–23, one per lecture.

Project structure

mit-6100l/
├── ps1/                     # Compound interest (+ course tester & wrapper)
├── ps2/                     # Hangman  (hangman.py, words.txt, tester)
├── ps3/                     # Document distance (+ tests/student_tests/ data)
├── ps4/                     # Trees (ps4a) + one-time-pad cipher (ps4b, ps4c)
├── ps5/                     # Image processing + LSB steganography
├── finger_exercises/        # Per-lecture finger exercises + pytest suite
├── results/                 # Captured tester outputs + real run artefacts
│   ├── ps*_tester_output.txt
│   ├── ps4c_decoded_story.txt
│   ├── finger_exercises_test_output.txt
│   └── ps5_outputs/*.png    # filtered + revealed images
├── requirements.txt
├── LICENSE
└── README.md

How to run

# Python 3.11 (repo uses the shared csdiy venv):
#   D:\Project\_csdiy\.venv-ml\Scripts\python.exe
python -m pip install -r requirements.txt   # only ps5 needs Pillow + numpy

# Problem-set testers are run directly (they are the course's own graders):
cd ps1 && python ps1_tester.py               # 8/8
cd ps2 && python test_ps2_student.py         # 5/5
cd ps3 && python test_ps3_student.py         # 5/5
cd ps4 && python test_ps4a_student.py        # 100%
cd ps4 && python test_ps4bc_student.py       # 3.5/3.5
cd ps5 && python test_ps5_student.py         # 3/3

# Real runs that produce artefacts:
cd ps4 && python -c "import ps4c; print(ps4c.decode_story())"
cd ps5 && python -c "import ps5, PIL.Image as I; \
  im=ps5.reveal_image('hidden1.bmp'); im.save('revealed.png')"

# Finger exercises (pytest):
cd finger_exercises && python -m pytest test_finger_exercises.py -v   # 21/21

Verification

Each problem set was graded by its official student tester shipped with the Fall 2022 skeleton (these are unittest-based graders that print a point score). The captured stdout of every run is under results/:

results/ps1_tester_output.txt          -> "You have passed 8 out of 8 tests."
results/ps2_tester_output.txt          -> "Points for these tests: 5/5"
results/ps3_tester_output.txt          -> "Points: 5/5"
results/ps4a_tester_output.txt         -> "100% done with part A"
results/ps4bc_tester_output.txt        -> "Points: 3.5/3.5"
results/ps5_tester_output.txt          -> "Points: 3/3"
results/finger_exercises_test_output.txt -> "21 passed"

PS5's reveal scaling was reverse-engineered from the staff's own reference outputs (ps5/tester_bw_img.obj, ps5/tester_rgb_img.obj): the BW image maps a single LSB to {0,255}, and the RGB image maps 3 LSBs (0..7) to {0,36,72,109,145,182,218,255} via n*255//7. The tester compares the produced images pixel-for-pixel against those references and passes.

Tech stack

Python 3.11 (standard library for ps1–ps4 and the finger exercises); Pillow and NumPy for ps5 image processing. Testing via each course tester (unittest) and pytest for the finger exercises.

Key ideas / what I learned

• Bisection search as a numeric root-finder (ps1c) and as an integer guessing strategy (finger ex. 6) — logarithmic convergence over a bounded interval.
• Frequency statistics & TF-IDF for measuring document similarity, reusing a single get_frequencies over both characters and words (ps3).
• Recursion over trees and nested structure: tree height / heap validation (ps4a), recursive flatten and sum_str_lengths with error handling.
• OOP with inheritance and operator overloading: a Message class hierarchy where decryption is just encryption by the negated pad (ps4b/c); overloaded __add__/__str__ on a Circle (finger ex. 17/18).
• Modular arithmetic on ASCII for a wrap-around one-time-pad cipher, and bit-masking / LSB steganography to hide and reveal images (ps5).
• Asymptotic complexity: reducing a sum of terms to its dominant Big-Theta class (finger ex. 22/23).

Credits & license

Based on the assignments of 6.100L Introduction to CS and Programming using Python (MIT OpenCourseWare, Fall 2022; Ana Bell, Eric Grimson, John Guttag, et al.). This repository is an independent educational reimplementation; the problem-set skeletons, test data, and specifications belong to their original authors at MIT. Original solution code in this repo is released under the MIT License. Course materials: https://ocw.mit.edu/courses/6-100l-introduction-to-cs-and-programming-using-python-fall-2022/ · csdiy guide: https://csdiy.wiki/编程入门/Python/MIT6.100L/