Day 10 — Gate I

Day 10 — Gate I

Stage I · gate day
Goal: Demonstrate fluent number sense across Days 1–9 without notes: integers and precedence, fractions, decimals/percent/sci, primes/gcd/lcm, div/mod, binary/hex, two’s complement, exponents/logs, and error.

Why this matters

Gates exist for retention, not theater. Stage II algebra assumes you can evaluate, convert, reduce, and estimate without re-deriving grade-school rules mid-proof. Treat this as a diagnostic: misses become a short repair list, not a moral failure.

Theory

What Gate I owns

Days	Must be automatic
1	Precedence, associativity, signs, parity proofs, \(|a+b|\le|a|+|b|\)
2	\(\mathbb{Q}\) ops, equality \(ad=bc\), reduce, complex fractions
3	Fraction/decimal/percent, scientific notation, compound \(\%\)
4	Primes, gcd/lcm, FTA use, Euclid infinite primes
5	Division algorithm, floor/ceiling, signed mod conventions
6	Base \(2\)/\(16\) conversions, nibbles, Horner
7	Binary add, two’s complement range & negation, overflow idea
8	Exponent/log laws, \(\log_2\) bit counts
9	Absolute vs relative error, cancellation awareness

How to sit the gate

1. Closed book first pass (timer optional: \(90\)–\(120\) minutes).
   
2. Mark unsure items; do not peek yet.
   
3. Check answers; log each miss: symptom → correct idea → one similar redo.
   
4. Repair day: only the weak topics, then retest those items cold within a week.

Definitions to write from memory (warm-up)

Before problems, write on blank paper:

• Division algorithm statement
  
• \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|\)
  
• Two’s complement range for width \(n\)
  
• \(\log_b x = y \Leftrightarrow b^y=x\)
  
• Absolute and relative error formulas
  
• Triangle inequality for \(|\cdot|\)
  
• Even/odd definitions

If you cannot write them, review the matching day before speed work.

Mixed strategies

• Simplify fractions before multiplying.
  
• For mods, reduce intermediates; state remainder convention.
  
• For bases, prefer nibble groups over giant decimal detours when going binary↔︎hex.
  
• For signed bits, state width first.
  
• For error, always ask “relative to what?”
  
• For parity, write \(2k\) / \(2k+1\), not examples alone.

Section map (timed-feel)

Section	Focus	Suggested time
A	Arithmetic, fractions, decimals, percent	\(25\) min
B	Primes, gcd/lcm, div/mod, floor	\(25\) min
C	Bases, binary, two’s complement, bits	\(25\) min
D	Exp/logs, error; short proofs	\(30\)–\(40\) min

Worked examples (calibration)

Example 1 — Arithmetic & fractions

Evaluate \(\dfrac{3}{4}\div\dfrac{9}{10}-\dfrac{1}{6}\) and reduce.

\(\dfrac{3}{4}\cdot\dfrac{10}{9}=\dfrac{30}{36}=\dfrac{5}{6}\), then \(\dfrac{5}{6}-\dfrac{1}{6}=\dfrac{4}{6}=\dfrac{2}{3}\).

Example 2 — gcd/mod

\(\gcd(252,90)\) by Euclid: \(252=2\cdot 90+72\), \(90=1\cdot 72+18\), \(72=4\cdot 18+0\) → \(18\).
\(100\bmod 7=2\); \(-100\) as \(7q+r\) with \(r\ge 0\) → \(r=5\).

Example 3 — Bases & two’s complement

\((2A)_{16}=(101010)_2=42\).
\(8\)-bit two’s complement of \(-5\): start from \(5=00000101\), invert \(11111010\), add \(1\) → \(11111011\).

Example 4 — Logs & bits

\(\log_2 64=6\); values \(0..63\) need \(6\) bits; values \(0..64\) need \(7\) bits.
\(\log_2(2^3\cdot 2^5)=\log_2(2^8)=8\).

Example 5 — Error

Approximate \(\pi\approx 22/7\). Absolute error \(|22/7-\pi|\approx 0.00126\); relative \(\approx 0.0004\).

Example 6 — Parity proof

Sum of two odds is even: \((2k+1)+(2\ell+1)=2(k+\ell+1)\).

Example 7 — Compound percent

\(200\times 1.1\times 0.9=198\).

Example 8 — Scientific notation

\((3\times 10^{-2})(4\times 10^{5})=1.2\times 10^{4}\).

Exercises — Section A (Arithmetic, \(\mathbb{Q}\), decimals)

Answer key sketches provided for starred items.

A1.* Evaluate \(8-3\times 2+12\div 4\) and \((8-3)\times(2+12)\div 4\).

A2. Evaluate \(-3^{2}\), \((-3)^{2}\), and \(-(-3)^{2}\).

A3.* Prove: product of two odd integers is odd.

A4. Compute \(\dfrac{5}{12}+\dfrac{7}{18}\) as a reduced fraction.

A5.* Simplify \(\dfrac{\frac{2}{3}-\frac{1}{4}}{\frac{5}{6}}\).

A6. Convert \(0.\overline{12}\) to a reduced fraction.

A7. A price goes \(80\to 100\to 80\). Percent change each step? Final vs original?

A8.* Write \(0.00045\) and \(450000\) in scientific notation; compute their product in scientific notation.

A9. Does \(\dfrac{7}{28}\) terminate as a decimal? Justify with the \(2\)–\(5\) criterion after reducing.

A10. Verify \(|{-6}+4|\le|{-6}|+|4|\) and compute the slack.

Exercises — Section B (Primes, gcd, div/mod)

B1.* Factor \(840\) into primes; count positive divisors.

B2. Compute \(\gcd(180,48)\) and \(\operatorname{lcm}(180,48)\); verify \(\gcd\cdot\operatorname{lcm}=|ab|\).

B3. State Euclid’s infinite primes proof in \(\le 6\) sentences.

B4.* Find \(q,r\) for \(a=-45\), \(d=7\) with \(0\le r<7\).

B5. Evaluate \(\lfloor -17/5\rfloor\), \(\lceil -17/5\rceil\), \(\lfloor 17/5\rfloor\).

B6. How many pages of size \(12\) for \(100\) items? Items on last page?

B7.* Compute \(17\bmod 5\) and explain what Python vs C might do for \((-17)\%5\).

B8. Prove: \(n\) and \(n+1\) are coprime.

B9. \(\operatorname{lcm}(12,18,30)\) via prime maxima.

B10. List residue classes of \(0,1,2,3,4\) as canonical remainders mod \(5\); which class contains \(47\)?

Exercises — Section C (Bases, binary, two’s complement)

C1.* Convert \((1101011)_2\) to decimal and to hex.

C2. Convert \(200_{10}\) to binary and hex.

C3. Convert (3F2)\(_{16}\) to binary by nibbles.

C4.* Write \(8\)-bit two’s complement for \(-20\) and for \(20\).

C5. State the two’s complement range for \(n=8\) and for \(n=16\).

C6. Add the \(8\)-bit patterns for \(100\) and \(50\); interpret as signed; did overflow occur?

C7.* Compute \(25\;\&\;13\), \(25\|13\), \(25\hat{}13\).

C8. What is \(11\ll 2\) and \(40\gg 2\) (nonnegative logical)?

C9. Why is negating 10000000 in \(8\)-bit two’s complement special?

C10. Horner-evaluate (2B)\(_{16}\).

Exercises — Section D (Exp/logs, error, short proofs)

D1.* Simplify \(2^{5}\cdot 2^{-2}\) and \((2^{5})^{2}\); solve \(2^{x}=64\).

D2. Evaluate \(\log_2 32\), \(\log_5 125\), and \(\log_9 27\).

D3. How many bits to represent IDs \(0..999\)?

D4.* Prove \(\log_b(xy)=\log_b x+\log_b y\) from definitions.

D5. True \(x=2.5\), approximation \(2.4\): absolute and relative error.

D6. Explain catastrophic cancellation with a one-line numeric story at \(6\)-digit precision.

D7.* Prove the triangle inequality \(|a+b|\le|a|+|b|\) for integers (or reals).

D8. Change of base: write \(\log_8 2\) using \(\log_2\).

D9. Machine epsilon: define in one sentence; why is it not “smallest positive float”?

D10. Prove: sum of an even and an odd is odd. (Full write-up.)

Answer key sketches (starred + half of unstarred)

A1. \(8-6+3=5\); \((5)\times(14)/4=70/4=17.5\) or \(\frac{35}{2}\).
A3. \((2k+1)(2\ell+1)=4k\ell+2k+2\ell+1=2(\cdots)+1\).
A5. Num \(\frac{8-3}{12}=\frac{5}{12}\); divide by \(\frac{5}{6}\): \(\frac{5}{12}\cdot\frac{6}{5}=\frac{1}{2}\).
A8. \(4.5\times 10^{-4}\), \(4.5\times 10^{5}\), product \(2.025\times 10^{2}\).

B1. \(840=2^3\cdot 3\cdot 5\cdot 7\); divisors \((3+1)(1+1)^3=32\).
B4. \(-45=7(-7)+4\) because \(7(-7)=-49\), \(r=4\).
B7. \(17\bmod 5=2\); Python-like floored \((-17)\%5=3\); C-like toward-zero remainder \(-2\).

C1. \(64+32+8+2+1=107\); hex 6B.
C4. \(20=(00010100)_2\); \(-20\) invert 11101011 add \(1\) → 11101100.
C7. \(25=(11001)_2\), \(13=(01101)_2\); AND 01001 \(=9\); OR 11101 \(=29\); XOR 10100 \(=20\).

D1. \(2^{3}=8\); \(2^{10}=1024\); \(x=6\).
D4. \(b^{m}=x\), \(b^{n}=y\) \(\Rightarrow\) \(xy=b^{m+n}\).
D7. From \(-|a|\le a\le|a|\) and same for \(b\), add; deduce bound on \(|a+b|\).

Additional half-key (selected):
A6. \(0.\overline{12}=\frac{12}{99}=\frac{4}{33}\).
A7. \(+25\%\), then \(-20\%\); product of factors \(1.25\times 0.8=1\), back to \(80\).
B2. \(\gcd=12\), \(\operatorname{lcm}=720\), \(12\cdot 720=8640=180\cdot 48\).
B5. \(\lfloor -3.4\rfloor=-4\), \(\lceil -3.4\rceil=-3\), \(\lfloor 3.4\rfloor=3\).
C5. \(-128..127\); \(-32768..32767\).
C6. \(150>127\): signed overflow; bit pattern of \(150\) as unsigned has MSB \(1\).
D2. \(5\), \(3\), \(\frac{3}{2}\).
D3. \(\lceil\log_2 1000\rceil=10\).
D5. abs \(0.1\), rel \(0.1/2.5=0.04\).
D8. \(\frac{\log_2 2}{\log_2 8}=\frac{1}{3}\).

Optional rapid-fire (untimed polish)

RF1. \(|{-3}|+{-3^{2}}+(-3)^{2}=?\)
RF2. \(\gcd(84,30)\) and \(\operatorname{lcm}(84,30)\).
RF3. \((-17)\bmod 5\) (math remainder \(\ge 0\)).
RF4. (F0)\(_{16}\) in binary.
RF5. \(8\)-bit two’s complement range and pattern for \(-1\).
RF6. \(\log_2(1/8)\) and \(\lceil\log_2 100\rceil\).
RF7. Relative error of \(99\) approximating \(100\).
RF8. Is subtraction associative? One counterexample.
RF9. \(\frac{2}{3}\div\frac{4}{9}\).
RF10. \(2^{10}\) vs \(10^{3}\) order comparison.

RF answers: \(1+(-9)+9=1\); \(6\) and \(420\); \(3\); 11110000; \(-128..127\), 11111111; \(-3\) and \(7\); \(0.01\); no, e.g. \((5-3)-1\neq 5-(3-1)\); \(\frac{2}{3}\cdot\frac{9}{4}=\frac{3}{2}\); \(1024>1000\).

Repair schedule template

Weak day	Symptom	Redo (closed book)	Date done
		5 problems + 1 proof

Time-box strategy

• Skip and star hard proofs on first pass; return if time.
  
• Arithmetic mistakes: re-evaluate with a second method (e.g. fraction and decimal).
  
• Base conversion: prefer binary↔︎hex shortcuts.
  
• Never spend \(>8\) minutes on one item in timed mode.

Self-score rubric

Score band	Meaning
\(\ge 85\%\)	Stage II ready; spot-repair only
\(70\)–\(84\%\)	Repair weak days \(1\)–\(2\) sessions each
\(50\)–\(69\%\)	Re-work failed sections with notes, then retest
\(<50\%\)	Restart Stage I with emphasis on A/B foundations

Count a multi-part item wrong if any critical subpart fails. Proofs: full credit for correct structure even if arithmetic side-check slips.

CS connection

Gate I is the numeric literacy layer under parsing, hashing, bitwise flags, complexity logs, and floating-point skepticism. Stage II will still use every skill here inside algebra.

Common pitfalls (exam mode)

Pitfall	What to do instead
Rushing precedence	Rewrite in steps
Wrong signed remainder	State convention explicitly
Hex without padding nibbles	Pad left to \(4k\) bits
Relative error with wrong base	Divide by true \(|x|\)
Proof by single example	Use definitions
Forgetting overflow on signed add	Check range \(-2^{n-1}..2^{n-1}-1\)

Checkpoint

• Warm-up definitions written closed-book
  
• Sections A–D attempted under time
  
• Starred answers checked; miss log started
  
• Repair plan dated within one week
  
• One parity proof and one \(\log\) or triangle proof written cleanly

Write two takeaways and your three weakest topics.

Deep dive — mixed Gate I drills with sketches

G1 — Fraction + percent + sci in one chain.
Compute \(\dfrac{3}{8}\) of \(2.4\times 10^{3}\), then express the result as a percent of \(10^{3}\).
\(\frac{3}{8}\cdot 2.4\times 10^{3}=0.9\times 10^{3}=9.0\times 10^{2}\).
As percent of \(10^{3}\): \(\frac{900}{1000}=0.9=90\%\).

G2 — gcd, mod, floor together.
\(\gcd(252,90)=18\). Math remainder \((-45)\bmod 7=4\) because \(-45=7(-7)+4\).
\(\lfloor -17/5\rfloor=-4\), \(\lceil -17/5\rceil=-3\).

G3 — Bases + two’s complement.
\((1101011)_2=107=(6B)_{16}\).
\(8\)-bit \(-20\): \(20=(00010100)_2\), invert 11101011, +1 → 11101100.
Range \(n=8\): \(-128..127\); pattern for \(-1\) is 11111111.

G4 — Exp/log + bits.
\(\log_2 32=5\); \(\log_9 27=\frac{3}{2}\); bits for IDs \(0..999\): \(\lceil\log_2 1000\rceil=10\).
\(\log_b(xy)=\log_b x+\log_b y\) via \(b^{m+n}=b^m b^n\).

G5 — Error + triangle inequality.
Approx \(2.4\) for true \(2.5\): abs \(0.1\), rel \(0.04\).
\(|a+b|\le|a|+|b|\) from \(-|a|\le a\le|a|\) and same for \(b\).

G6 — Parity proof template (must-pass).
Odd \(\times\) odd: \((2k+1)(2\ell+1)=4k\ell+2k+2\ell+1=2(\cdots)+1\).
Even + odd: \(2k+(2\ell+1)=2(k+\ell)+1\) odd.

Extra rapid-fire (second pass)

RF11. \(\frac{5}{6}-\frac{1}{4}\) reduced.
RF12. \(\operatorname{lcm}(12,18,30)\) via max exponents.
RF13. (F0)\(_{16}\) binary; \(8\)-bit meaning as unsigned.
RF14. \(2^{x}=64\); \(\log_2(1/8)\).
RF15. Relative error of \(99\) approximating \(100\); machine epsilon in one sentence.

RF answers (11–15): \(\frac{10-3}{12}=\frac{7}{12}\); \(2^2\cdot 3^2\cdot 5=180\); 11110000 \(=240\); \(x=6\), \(-3\); \(0.01\); gap between \(1\) and next representable above \(1\).

Timed second-pass strategy

1. Re-do only starred misses cold.
   
2. Write one full parity proof and one log law proof without notes.
   
3. Convert one hex↔︎binary pair and one signed \(8\)-bit value under \(2\) minutes.
   
4. Update the repair table with dates—Gate I is diagnostic, not a trophy.

Tomorrow

Day 11 — Variables & expressions. Atoms vs expressions, evaluation, like terms, algebraic identities preview, free vs bound analogy—algebra begins in earnest (Stage II).