Page last updated on 2015 May 21

*Note:* ECE 1B used to be ECE 1 (see history at the end of this page)
*Enrollment code:* 12260

*Prerequisite:* Open to computer engineering students only

*Class meetings:* M 3:30-4:45, Chem 1171

*Instructor:* Professor Behrooz Parhami

*Open office hours:* M 9:30-11:00, W 3:30-5:00, HFH 5155

**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 lecture topics:** May replace some current topics in future

**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, as follows:

- *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)

**2015/05/18:** There will be no ECE 1B lecture on M 5/25 due to Memorial Day observance. Please check your attendance record after the last lecture on M 6/1. If you have no absence or 1 absence that has already been explained, you need to take no action to get a P grade. A single unexplained absence must be explained to avoid an NP grade. If you have 2-3 absences, you must e-mail the instructor no later than T 6/2 a list of all your available time slots, from 8:00 AM to 8:00 PM, for an oral final exam to be held on R 6/4 or F 6/5. I will then get back to you with your half-hour exam time slot. It is your responsibility to monitor your attendance record and to take appropriate action. Any unresolved problem will lead to an NP grade (I will not come chasing you to resolve them).
**2015/05/11:** Attandance records for the first seven lectures (up to 5/11) are now up to date. Many of the absences still remain unexplained.
**2015/04/27:** Attandance records for the first five lectures (up to 4/27) are now up to date. More than half of the absences remain unexplained at this point. Please check the record frequently to ensure accuracy and send your explanations in a timely fashion to avoid being assigned an NP grade for the course.
**2015/04/06:** Attandance records for the first two lectures on 3/30 and 4/6 have been posted below on this page. Please check the record frequently to ensure accuracy.
**2015/03/26:** Welcome to the ECE 1B Web page for spring 2015. Please read the grading scheme below very carefully to ensure that you can earn a "pass" grade at the end of the quarter. ECE 1B requires no textbook and has no homework assignments or exams. A worksheet handout is given out at the beginning of each lecture and complete lecture slides are made available on-line. Please report any broken hyperlink to the instructor.

Pass/Fail 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.

2 absences: "Pass" if you submit a written explanation and had prior instructor approval for your 2nd absence; strong participation in class or via e-mail will work in lieu of prior approval. Otherwise, taking an oral final exam covering the two missed lectures is required.

3 absences: Can earn a "Pass" grade by taking an oral final exam covering the three missed lectures.

4 or more absences: Automatic "Not Pass."

Attendance will be 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.

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. Before downloading the slides, check the "last updated" date to make sure you have the latest files for 2015. As of this posting (March 26, 2015), the topics listed for May and June are tentative.

**Day & Date (Lecture slides, ppt + pdf, and ppt handout) Lecture topic [Lead puzzle]**

M 03/30 (ppt, pdf, handout, last updated 2015/03/28) Easy, Hard, Impossible! [Collatz's conjecture]

M 04/06 (ppt, pdf, handout, last updated 2015/04/05) Placement and routing [Houses and utilities]

M 04/13 (ppt, pdf, handout, last updated 2015/04/12) Satisfiability [Making change]

M 04/20 (ppt, pdf, handout, last updated 2015/04/19) Cryptography [Secret messages]

M 04/27 (ppt, pdf, handout, last updated 2015/04/26) Byzantine generals [Liars and truth-tellers]

M 05/04 (ppt, pdf, handout, last updated 2015/05/02) Binary search [Counterfeit coin]

M 05/11 (ppt, pdf, handout, last updated 2015/05/07) Task scheduling [Sudoku]

M 05/18 (ppt, pdf, handout, last updated 2015/05/16) String matching [Word search]

M 05/25 (ppt, pdf, handout, last updated 2015/05/16) Sorting networks* [Rearranging trains]

* No lecture on M 05/25 due to the Memorial Day observance. This topic will be covered on Monday 06/01.

M 06/01 (ppt, pdf, handout, last updated 2012/05/17) Malfunction diagnosis** [Logical reasoning]

** This topic is removed for spring 2015 ("Sorting networks," listed under M 05/25 will be covered instead). There will be no make-up lecture or substitute assignment for "Malfunction diagnosis."

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]

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

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]

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

Sloane, N.J.A., *Online Encyclopedia of Integer Sequences* [Access on-line] (Broken link?)

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

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.

__1 2 3 4 5 6 7 8 9 0 Σ Mrep__

0 0 0 0 0 0 0 0 - -

0 0 0 1 0 1 1 1 - -

0 0 0 0 0 1 0 0 - -

0 0 0 1 0 0 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

1 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 1 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 1 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 1 - -

1 0 0 0 1 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 1 1 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 1 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 1 - -

0 1 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 0 1 0 0 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 1 0 0 0 0 0 - -

0 0 0 1 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 1 0 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 0 0 0 0 0 1 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 1 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 1 0 0 - -

0 0 0 0 0 0 0 0 - -

1 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 1 0 0 - -

0 0 0 0 1 0 0 0 - -

0 0 1 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 1 0 0 1 - -

0 1 1 0 0 0 0 0 - -

1 0 0 1 0 1 1 1 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 1 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 0 0 1 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 1 0 - -

0 0 0 0 0 1 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 0 1 0 0 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 1 0 0 0 0 0 - -

0 0 1 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 1 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 1 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 1 0 - -

0 0 0 0 1 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

0 0 0 0 0 0 0 0 - -

** 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.

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 for the first time in spring 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 academic year 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.

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)