Menu:
Behrooz Parhami's ECE 1B Course Page for Spring 2025
Ten Puzzling Problems in Computer Engineering
Page last updated on 2025 June 11
Note: ECE 1B used to be ECE 1 (see history at the end of this page)
Enrollment code: 13268
Prerequisite: Open to computer engineering students only
Class meetings: M 5:00-6:15, Buchanan 1920
Instructor: Professor Behrooz Parhami
Office hours: MW 1:15-1:45 PM, Phelps 1431
Course announcements: Listed in reverse chronological order
Grading scheme: Pass/Fail grade is assigned based on attendance
Course calendar: Schedule of lectures and links to lecture slides
The ten lectures: Lecture summaries and references
Additional topics: Possible replacements for current lectures
Attendance record: Please check regularly for possible errors
Miscellaneous information: Motivation, catalog entry, history
Note: The design and goals of this innovative freshman seminar are described in a brief article, a short paper, and a full paper:
- IEEE Computer, Vol. 42, No. 3, Mar. 2009 (PDF file)
- IEEE Trans. Education, Vol. 52, No. 3, Aug. 2009 (PDF file)
- Computer Science Education, Vol. 18, No. 4, Dec. 2008 (PDF file)
Course Announcements
2025/06/11: The spring 2025 offering of ECE 1B is officially over and course grades have been submitted to the Registrar. I hope you enjoyed this course and learned much from it. Wishing you a wonderful summer break!
2025/06/05: Five students have oral final exams scheduled for Friday 6/06. Four students cannot get a "Pass" grade unless they send me e-mails to acknowledge their single unexplained absences. See the attendance record at the bottom of this page.
2025/06/02: Please check the final version of the attendance record at the bottom of this page for your grade (Pass or Not Pass) and Schedule of your oral final exam (in my office, Ellison 1816), if you need one. To scehdule your oral final exam, please e-mail me all of your available time slots on Friday 6/06, between 10:00 AM and 7:00 PM. Once I receive information about your availability, I will get back to you with an assigned half-hour time slot.
2025/05/19: Please check the attendance record for the first 8 lectures and report any problems to the instructor. Only one lecture (M 6/02) is left for the course. As soon as attendance record for that last lecture has been posted, those with 2 absences should contact the instructor right away, providing all their available times on F 6/06, when we will schedule our oral final exams. Your final exam schedule will be e-mailed to you in response to your availability e-mail.
2025/04/15: Please check the attendance record up to yesterday's lecture (Lecture 3, April 14) and report any problems to me immediately. There were a few errors in the previous version which were caused by illegible attendance slips. Always write your name and Perm Number legibly to avoid future errors.
2025/04/09: Attendance record for the first two lectures (3/31 & 4/4) has been posted at the end of this page. Please check for accuracy and report any problems to me immediately.
2025/02/09: Welcome to the ECE 1B Web page for spring 2025. We expect to have 100+ students. Please read the grading scheme very carefully, so you can earn a "pass" grade at the end of the quarter. ECE 1B requires no textbook and has no homework assignments or exams. The objective is to provide you with amazing learning experiences in a stress-free atmosphere.
[Please report any broken hyperlinks and other problems on this page to the instructor.]
Grading Scheme
Pass/Not-Pass grading is based on attendance* and class participation. There will be no homework or exam.
0 absence: Automatic "Pass."
1 absence: "Pass" if you submit a written statement to explain the absence. Any explanation is acceptable.
2 absences: Can earn a "Pass" grade by taking an oral final exam covering the two missed lectures.
3 or more absences: Automatic "Not-Pass."
Attendance is taken as follows. Attendance slips are distributed at the beginning of each class session, with additional slips supplied to those arriving up to 10 minutes late. Students write their names and perm numbers on the slips and turn them in before leaving the classroom at the end of the lecture. You have to turn in your attendance slip in person, not through another student.
Course Calendar
Course lectures have been scheduled as follows. PowerPoint presentations (up to 2+ MB), and equivalent PDF files, are updated periodically. Please note that any animation in PowerPoint presentations is lost in the PDF versions.
Should slides be updated during the current quarter, the "last updated" information shown next to the links will change. This is unlikely, given that the slides have been fully tested and debugged.
Day & Date (Lecture slides ppt+pdf, Lecture video, Last updated) Lecture topic [Lead puzzle]
M 3/31 (ppt, pdf, lecture 1, last updated 2020/03/20) Easy, Hard, Impossible! [Collatz's conjecture]
M 4/07 (ppt, pdf, lecture 2, last updated 2020/04/02) Placement and routing [Houses and utilities]
M 4/14 (ppt, pdf, lecture 3, last updated 2020/04/08) Satisfiability [Making change]
M 4/21 (ppt, pdf, lecture 4, last updated 2020/04/15) Cryptography [Secret messages]
M 4/28 (ppt, pdf, lecture 5, last updated 2020/04/23) Byzantine generals [Liars and truth-tellers]
M 5/05 (ppt, pdf, lecture 6, last updated 2020/04/27) Binary search [Counterfeit coin]
M 5/12 (ppt, pdf, lecture 7, last updated 2020/05/03) Task scheduling [Sudoku]
M 5/19 (ppt, pdf, lecture 8, last updated 2020/05/12) String matching [Word search]
M 5/26 Memorial Day observance: No lecture during spring 2025 (ppt, pdf, lecture (N/A), last updated 2016/05/26) Malfunction diagnosis [Logical reasoning]
M 6/02 (ppt, pdf, lecture 9, last updated 2020/05/19) Sorting networks [Rearranging trains]
F 6/06, 12:00-7:00 PM (Half-hour oral final exams, to be scheduled for those with 2 absences)
T 6/17 (Course grades due by midnight)
Summary and References for the Ten Lectures
A one-page summary for each of the ten lectures is included in the following paper; additional print and on-line references are given below.
Parhami, B., "A Puzzle-Based Seminar for Computer Engineering Freshmen," Computer Science Education, Vol. 18, No. 4, pp. 1-17, Dec. 2008. (PDF file)
Lecture 1: Easy, Hard, Impossible
Fun with Fibonacci numbers, by Gareth E. Roberts [Seminar slides]
Fibonacci numbers: family trees for bees (BP's Math+Fun page) [Word file]
More on Collatz's conjecture [Wikipedia article]
On the unprovability of Collatz's conjecture, by C. A. Feinstein [Article]
Lecture 2: Placement and Routing
Houses and utilities puzzle [The Math Forum @ Drexel]
Euler's Formula: V – E + F = 2 [Twenty Proofs]
Lecture 3: Satisfiability
Making $5 Using 50 Coins [Ask Dr. Math]
Interactive game, by O. Roussel [The SAT Game]
Lecture 4: Cryptography
Web-based tutorial by P. Gutman [Cryptography and Security]
Web page maintained by T. Sale [The Enigma Cipher Machine]
The Enigma explained [12-minute video]
The fatal flaw in Enigma [11-minute video]
NSA Mathematician David Pery's 65-minute talk on Enigma (cryptography)
Introduction to Cryptography, by John Mason (thebestvpn)
Khan Academy 10-minute video on the Enigma: Part of the module "Journey into Cryptography"
Lecture 5: Byzantine Generals
Saka, P., How to Think About Meaning, Springer, 2007
Resource Web page by A. Montalban and Y. Interian [Liars and Truth-Teller Puzzles] (Link broken?)
Lecture 6: Binary Search
Du, D.-Z., and F.K. Hwang, Combinatorial Group Testing and Its Applications, 2nd ed., World Scientific, 2000 (See Chapter 16, pp. 295-318)
Programs for solving counterfeit-coin problems [Coding resources and hints]
Lecture 7: Task Scheduling
Aaronson, L., "Sudoku Science: A Popular Puzzle Helps Researchers Dig into Deep Math," IEEE Spectrum, Vol. 43, No. 2, pp. 16-17, February 2006
Online Sudoku and other interesting logic puzzles [Logic Games Online]
Lecture 8: String Matching
Website with free online tools for creating word-search and other puzzles [Puzzlemaker]
Lecture 9: Sorting Networks
Hayes, B., "Trains of Thought: Computing with Locomotives and Box Cars Takes a One-Track Mind," American Scientist, Vol. 95, No. 2, pp. 108-113, March-April 2007 [Read on-line]
Parhami, B., Introduction to Parallel Processing: Algorithms and Architectures, Plenum Press, 1999 (See Chapter 7, pp. 129-147, for an introduction to sorting networks)
Lecture 10: Malfunction Diagnosis
Logic problems [Expand Your Mind] (Link broken?)
Somani, A. K., V. K. Agarwal, and D. Avis, "A Generalized Theory for System Level Diagnosis," IEEE Trans. Computers, Vol. 36, No. 5, pp. 538-546, May 1987
Additional Lecture Topics for Possible Future Use
The following additional topics are being considered for inclusion as future lecture topics:
Topic A: Computational Geometry
Puzzles based on visual tricks and optical illusions
Web site devoted to discrete and computational geometry [The Geometry Junkyard]
See lectures 7 and 8 in the fall 2016 offering of the freshman seminar INT 94TN
Topic B: Loss of Precision
Puzzles based on logical paradoxes and absurdities
Parhami, B., Computer Arithmetic: Algorithms and Hardware Designs, Oxford University Press, 2000 (See Problems 1.1-1.3)
Topic C: Secret Sharing
Puzzles based on anonymous complainers and whistle blowers
Shamir, A., "How to Share a Secret," Communications of the ACM, Vol. 22, No. 11, pp. 612-613, 1979
Secret sharing [Wikipedia article]
Topic D: Amdahl's Law
Puzzles on river and bridge crossings
Parhami, B., Computer Architecture: From Microprocessors to Supercomputers, Oxford University Press, 2005 (See Section 4.3)
Amdahl's law [Wikipedia article]
Topic E: Predicting the Future
Puzzles based on determining the next term in a series
Sloane, N.J.A., "Find the Next Term," J. Recreational Mathematics, Vol. 7, No. 2, p. 146, Spring 1974 [GIF]
Sloane, N.J.A., Online Encyclopedia of Integer Sequences [Access on-line]
See lectures 1 and 2 in the fall 2016 offering of the freshman seminar INT 94TN
Topic F: Circuit Value Problem
Puzzles based on parallelization of hopelessly sequential problems
Greenlaw, R., H.J. Hoover, and W.L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory, Oxford University Press, 1995 (See Section 4.2, pp. 75-76)
Topic G: Maps and Graphs
Puzzles based on map/graph coloring and graph properties
Feeman, T.G., Portraits of the Earth: A Mathematician Looks at Maps, American Mathematical Society, 2002
See lectures 9 and 10 in the fall 2016 offering of the freshman seminar INT 94TN
Topic H: Device Variability
Puzzles based on detecting differences in two nearly identical images
Tutorial sources about nanoelectronics device variability and design under variability to be located
Topic I: Cellular Automata
Conway's Game of Life
Wikipedia article on Conway's Game of Life
Martin Gardner's Scientific American article on Conway's Game of Life
Eric Weisstein's Treasure Trove of the Life Cellular Automaton
Topic J: Recommender Systems
Puzzles based on finding similarities or differences among a series of images
Fingerprint matching; Google's page-rank algorithm
Mining massive datasets (YouTube videos) [See in particular video 5.1]
See lectures 3 and 4 in the fall 2016 offering of the freshman seminar INT 94TN
Topic K: 3D Models from 2D Images
Puzzles based on deducing the shapes of 3D objects from 2D projections
3D illudion in 2D drawings (sidewalk art)
Architecrtural visualization; preserving models of historical sites in danger or collapse/destruction;
Modeling industrial parts and assemblies; layered models (3D printing)
See lectures 5 and 6 in the fall 2016 offering of the freshman seminar INT 94TN
Student Attendance Record
In the following table, absence is marked with a "1" and presense with a "0". The first ten columns correspond to Lectures 1-10, the next column, Σ, is the total number of absences, and "Mrep" is the first few digits of the reversed Perm Number. For example, a student with the Perm Number 9876543 will have a Mrep code of 3, 34, 345, 3456, ... , depending on whether other students have Perm Numbers with the same ending.
Attendance slips are distributed at the beginning of class session and turned in at the end by each student (returning the slip by another student isn't allowed).
Due to one of our class sessions coinciding with the Memorial Day observance on 5/26, Lecture 10 has been cancelled and attendance will be assessed based only on Lectures 1-9.
A letter to my students
As we near the end of the 2024-2025 academic year, I want to congratulate you for another year of academic progress under difficult circumstances. The American system of higher education is under attack. An incompetent administration is gleefully cutting a tree that holds up our country’s social progress and economic prosperity. Many of you are experiencing uncertainties in sources of financial aid or academic salaries. Others are facing the prospects of visa revocation for their studies or practical training. As xenophobia spreads and anti-science officials take control of our government, the UC faculty and staff are doing everything in their power to protect you against shortsighted social and economic policies. Let’s maintain open lines of communication. We are in this together.
1 2 3 4 5 6 7 8 0 9 Σ Mrep Notes about attendance, oral final exam, and grade
0 0 0 0 0 1 0 0 0 0 1 002 Pass
0 0 0 0 0 0 0 0 0 0 0 00M Pass
0 0 0 0 0 0 0 0 0 0 0 01 Pass
0 0 0 0 0 0 0 0 0 0 0 026 Pass
0 0 0 0 0 0 0 0 0 0 0 02C Pass
0 0 0 0 0 0 0 0 0 0 0 031 Pass
0 0 0 0 0 0 0 1 0 0 1 039 Pass
0 0 0 0 0 0 0 0 0 0 0 046 Pass
1 1 0 0 0 0 0 0 0 0 2 049 Pass, based on oral final exam on F 6/06, 3:30 PM
0 0 0 0 0 0 0 0 0 1 1 05 Pass
0 1 0 0 0 0 0 0 0 0 1 067 Pass
0 0 0 0 0 0 0 0 0 0 0 06W Pass
0 0 0 0 0 0 0 0 0 0 0 07 Pass
0 0 0 0 0 0 0 0 0 0 0 08 Pass
0 0 0 0 0 0 1 0 0 0 1 105 Pass
0 0 0 0 0 1 0 0 0 0 1 10H Pass
0 0 0 0 0 0 0 0 0 0 0 110 Pass
0 0 0 0 0 0 0 0 0 0 0 11U Pass
0 0 0 0 0 0 0 0 0 0 0 12 Pass
0 0 0 0 0 0 0 0 0 0 0 142 Pass
0 0 1 0 0 0 0 0 0 0 1 14R Pass
0 0 0 0 0 0 0 0 0 0 0 14Y Pass
0 0 0 0 0 0 0 0 0 0 0 160 Pass
0 0 0 0 1 0 0 0 0 0 1 167 Pass
0 0 0 0 0 0 0 0 0 1 1 16J Pass
0 0 0 0 0 0 0 1 0 0 1 17 Pass
0 0 0 0 0 1 0 0 0 0 1 204 Pass
0 0 0 0 0 1 0 0 0 0 1 20E Pass
1 0 0 0 0 0 0 0 0 0 1 20J Pass
0 0 0 0 0 0 0 0 0 0 0 213 Pass
0 0 0 0 0 0 0 0 0 0 0 21H Pass
0 0 0 0 0 0 0 0 0 1 1 22 Pass
0 0 0 0 0 0 0 0 0 0 0 232 Pass
0 0 0 0 1 0 0 0 0 0 1 23T Pass
0 0 0 0 0 0 0 0 0 0 0 26 Pass
0 1 0 0 0 0 0 0 0 0 1 28 Pass
0 0 0 0 0 0 0 0 0 0 0 309 Pass
0 0 0 0 0 0 0 0 0 0 0 30A Pass
0 0 0 0 0 1 0 0 0 0 1 34N Pass
0 0 0 0 0 0 1 0 0 0 1 34T Pass
0 0 0 1 0 0 0 0 0 0 1 35 Pass
0 0 0 0 0 0 0 0 0 0 0 362 Pass
0 0 0 0 0 0 0 0 0 1 1 365 Pass
0 0 0 0 0 0 0 0 0 0 0 372 Pass
1 0 0 0 0 0 0 0 0 0 1 37Y Pass
0 0 0 0 0 0 0 0 0 0 0 38 Pass
0 0 0 0 0 0 0 0 0 0 0 40 Pass
0 0 0 0 0 0 0 0 0 0 0 42 Pass
0 0 0 0 0 0 0 0 0 0 0 431 Pass
1 1 0 0 0 0 0 0 0 0 2 439 Pass, based on oral final exam on F 6/06, 12:30 PM
0 0 0 0 0 1 0 0 0 0 1 43A Pass
0 0 0 0 0 0 0 0 0 0 0 43F Pass
0 0 0 0 0 0 0 0 0 1 1 443 Pass
0 0 0 0 0 0 0 0 0 1 1 44F Pass
0 0 0 0 0 0 0 0 0 1 1 44K Pass
0 0 0 0 0 0 0 0 0 0 0 45 Pass
1 0 0 0 0 0 0 1 0 0 2 47 Pass, based on oral final exam on F 6/06, 12:00 PM
0 0 0 0 0 0 0 0 0 0 0 49 Pass
0 0 0 0 0 0 0 1 0 0 1 503 Pass
0 0 0 0 0 0 0 0 0 0 0 507 Pass
0 0 0 0 1 0 0 0 0 0 1 50E Pass
0 0 0 0 0 0 0 0 0 0 0 50U Pass
0 0 0 0 0 0 1 0 0 0 1 54F Pass
0 0 0 0 0 0 0 0 0 0 0 54J Pass
0 0 0 0 0 0 0 0 0 1 1 54K Pass
0 0 0 0 0 0 0 0 0 0 0 57 Pass
0 0 0 0 0 0 0 1 0 0 1 58 Pass
0 1 0 0 0 0 0 0 0 0 1 59 Pass
0 0 0 0 0 0 0 0 0 1 1 646 Pass
0 0 0 0 0 0 0 0 0 1 1 64A Pass
0 0 0 0 0 0 0 0 0 1 1 64E Pass
0 0 0 0 0 0 0 0 0 0 0 66F Pass
0 0 0 0 0 0 0 0 0 0 0 66U Pass
0 0 0 0 0 0 0 0 0 0 0 670 Pass
0 0 0 0 0 0 0 0 0 0 0 68P Pass
0 0 0 0 0 0 0 0 0 0 0 68R Pass
0 0 0 0 0 0 0 0 0 0 0 70J Pass
0 0 0 0 0 0 0 0 0 0 0 70U Pass
0 0 0 0 0 0 1 0 0 0 1 71 Pass
0 0 0 0 0 0 0 0 0 1 1 723 Pass
0 0 0 0 0 0 0 0 0 0 0 72W Pass
0 0 1 0 0 0 0 0 0 0 1 73 Pass
0 0 0 0 0 0 0 0 0 1 1 74 Pass
0 0 0 0 0 0 0 0 0 0 0 75 Pass
0 0 0 0 0 0 0 0 0 0 0 761 Pass
0 0 0 0 0 0 0 0 0 0 0 763 Pass
0 0 0 0 0 0 0 0 0 1 1 77 Pass
0 0 1 0 0 0 0 0 0 0 1 78 Pass
0 0 0 0 0 1 0 0 0 0 1 800 Pass
0 0 0 0 0 0 0 0 0 1 1 808 Pass
0 0 0 0 0 0 0 0 0 0 0 80M Pass
0 0 0 0 0 0 0 1 0 0 2 82 Pass
0 0 0 0 0 0 0 0 0 0 0 83 Pass
0 0 0 0 0 0 0 0 0 1 1 85 Pass
0 0 0 0 0 0 0 0 0 1 1 86J Pass
0 0 0 0 0 0 1 0 0 0 1 86X2 Pass
0 0 0 0 0 0 0 0 0 0 0 86X9 Pass
0 0 0 0 1 0 0 0 0 0 1 86Y Pass
0 0 0 0 0 0 0 0 0 0 0 874 Pass
0 0 0 0 0 0 1 0 0 0 1 87F Pass
1 0 0 0 0 0 0 0 0 0 1 88 Pass
0 0 0 0 0 0 0 0 0 0 0 89 Pass
0 0 0 0 0 0 0 0 0 1 1 91 Pass
0 0 0 0 0 0 0 0 0 0 0 923 Pass
0 0 0 0 0 0 0 0 0 0 0 926 Pass
0 0 0 0 1 0 0 0 0 0 1 944 Pass
0 0 0 0 0 0 0 0 0 1 1 94A Pass
0 0 0 1 0 0 0 0 0 0 1 94M Pass
1 0 0 0 0 0 1 0 0 0 2 94R Pass, based on oral final exam on F 6/06, 11:30 AM
0 0 0 0 0 0 1 0 0 0 1 95H Pass
1 0 0 0 0 0 0 0 0 0 1 95N Pass
0 0 0 0 0 0 0 0 0 1 1 968 Pass
0 0 0 0 0 0 0 0 0 0 0 96N Pass
1 1 0 0 0 0 0 0 0 0 2 96V1 Pass, based on oral final exam on F 6/06, 3:00 PM
0 0 0 0 0 0 0 0 0 0 0 96V7 Pass
0 0 0 0 0 0 0 0 0 0 0 99 Pass
Miscellaneous Information
Motivation: Whether they work in the industry or in academic research settings, computer engineers face many challenges in their quest to design or effectively employ faster, smaller, lower-energy, more reliable, and cost-effective systems. Most computer engineering students do not begin tackling such problems, and more generally are not exposed to specific challenges of their field of study, until they enroll in upper-division major courses. Meanwhile, during their freshman- and sophomore-year experiences with foundational courses in mathematics, physics, electrical circuits, and programming, they wonder about where they are headed and what types of problems they will encounter as working professionals. This course is intended to provide an introduction to day-to-day problems and research endeavors in computer engineering via their connections to familiar mathematical and logical puzzles.
Catalog entry: 1B. Ten Puzzling Problems in Computer Engineering. (1) PARHAMI. Seminar, 1 hour.
Prerequisite: Open to computer engineering majors only.
Repeat comments: Not open for credit for those who have taken ECE 1.
Gaining familiarity with, and motivation to study, the field of computer engineering, through puzzle-like problems that represent a range of challenges facing computer engineers in their daily problem-solving efforts and at the frontiers of research.
History: This 1-unit freshman seminar (offered since 2007) was proposed and developed by Professor Parhami. The main goal of the seminar is to expose students to challenging computer engineering problems, faced by practicing engineers and research scientists, in a motivating and entertaining way. The course is useful because CE students have very limited exposure to key concepts in their chosen major during their initial studies that involve mostly foundational, basic science, and general-education courses. Beginning with the AY 2013-2014, the seminar was renamed from ECE 1 to ECE 1B to accommodate another freshman seminar, ECE 1A, that exposes students to a roadmap for their studies at UCSB, their career choices, and leading-edge research topics. During fall 2016 and fall 2018, a similar freshman seminar, INT 94TN, was offered at the campus level to introduce science and technology topics to students from different (non-science/engineering) disciplines.
Offering of ECE 1B in spring 2024
Offering of ECE 1B in spring 2023
Offering of ECE 1B in spring 2021
Offering of ECE 1B in spring 2020
Offering of ECE 1B in spring 2019
Offering of ECE 1B in spring 2018
Offering of ECE 1B in spring 2017
Offering of ECE 1B in spring 2016 (PDF file)
Offering of ECE 1B in spring 2015 (PDF file)
Offering of ECE 1B in spring 2014 (PDF file)
Offering of ECE 1 in spring 2013 (PDF file)
Offering of ECE 1 in spring 2012 (PDF file)
Offering of ECE 1 in spring 2011 (PDF file)
Offering of ECE 1 in spring 2010 (PDF file)
Offering of ECE 1 in spring 2009 (PDF file)
Offerings of ECE 1 in 2007 and 2008 (PDF file)