Menu:
Behrooz Parhami's ECE 1 Course Page for Spring 2011
Ten Puzzling Problems in Computer Engineering
Enrollment code: 10678
Prerequisite: Open to (pre-)computer engineering students only
Class meetings: M 9:30-10:45, North Hall 1006
Instructor: Professor Behrooz Parhami
Open office hours: M 11:00-12:30, W 12:00-1:30, 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)
Course Announcements
2011/06/19: The spring 2011 offering of ECE 1 is officially over and there will be no further updates to this page. Four students who had 2 class absences took oral final exams on F 6/3 and T 6/7; students with no absence or 1 explained absence were given "pass" grades. Course grades have been reported to the Registrar's office. Have a pleasant summer!
2011/05/23: Please read this final announcement very carefully. The class attendance record near the end of this page is now in its final form, with all 9 lectures already recorded. Lecture 10 has been cancelled and there will be no make-up assignment in its stead. If you have had 0 absence, or 1 absence which has been explained, you will be assigned a "pass" grade. If you have had an unexplained single absence, please e-mail me an explanation for your absence no later than May 31. If you have had 2 or 3 absences, please send me your availability from now to F 6/3 so that I can schedule a final oral exam for you in which the contents of the lectures you missed will be discussed. Please provide as many days and time slots as possible. If your specified schedule does not fit mine, I will reply to your e-mail asking for additional time slots. If you have had 4 or more absences, 2-3 absences and you do not contact me by 5/31 for an oral exam, or a single unexplained absence, you will be assigned a "not pass" final grade.
2011/04/04: The attendance record (further down this page) has been updated to reflect today's class session. Please check the attendance record regularly to ensure accuracy.
2011/03/09: Welcome to the ECE 1 Web page for spring 2011. Please read the grading scheme below very carefully to ensure that you can earn a "pass" at the end of the quarter. ECE 1 requires no textbook and has no homework assignments or exams. A handout sheet is given out at the beginning of each lecture and lecture slides are made available on-line.
Grading Scheme
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 "Fail."
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 Calendar
Course lectures have been scheduled as follows. PowerPoint presentations (up to 2+ MB), and equivalent PDF files, are updated periodically. Note that any animation in PowerPoint presentations is lost in the PDF versions. When a particular presentation or handout file has been updated for spring 2011, you will see a 2011 date in front of it; otherwise, it is from a previous offering of the course and may have slight differences with this year's version.
Day & Date (Lecture slides, ppt + pdf, and ppt handout) Lecture topic [Lead puzzle]
M 03/28 (ppt, pdf, handout, last updated 2011/03/24) Easy, Hard, Impossible! [Collatz's conjecture]
M 04/04 (ppt, pdf, handout, last updated 2011/03/30) Placement and routing [Houses and utilities]
M 04/11 (ppt, pdf, handout, last updated 2011/04/06) Satisfiability [Making change]
M 04/18 (ppt, pdf, handout, last updated 2011/04/12) Cryptography [Secret messages]
M 04/25 (ppt, pdf, handout, last updated 2011/04/18) Byzantine generals [Liars and truth-tellers]
M 05/02 (ppt, pdf, handout, last updated 2011/04/25) Binary search [Counterfeit coin]
M 05/09 (ppt, pdf, handout, last updated 2011/05/05) Task scheduling [Sudoku]
M 05/16 (ppt, pdf, handout, last updated 2011/05/05) String matching [Word search]
M 05/23 (ppt, pdf, handout, last updated 2011/05/24) Sorting networks [Rearranging trains]
M 05/30 (ppt, pdf, handout, last updated 2010/05/20) Malfunction diagnosis [Logical reasoning]
* No lecture on M 05/30 due to the Memorial Day observance. There will be no make-up lecture or substitute assignment for this topic.
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
Some applications of the Fibonacci series (thinkquest.org)
Another application of Fibonacci numbers in nature: family trees for bees (BP's Math + Fun page, MS Word doc file)
Wikipedia article on Collatz's conjecture
Feinstein, C. A., "The Collatz 3n + 1 Conjecture is Unprovable," 2006
Lecture 2: Placement and Routing
Houses-and-utilities puzzle
Nineteen Proofs of Euler's Formula: V - E + F = 2
Lecture 3: Satisfiability
Making $5 Using 50 Coins
Roussel, O., "The SAT Game"
Lecture 4: Cryptography
Gutmann, P., "Cryptography and Security Tutorial"
Sale, T., "The Enigma Cipher Machine"
Lecture 5: Byzantine Generals
Saka, P., How to Think About Meaning, Springer, 2007
Montalban, A., and Y. Interian, "Liars and Truth-Teller Puzzles"
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
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
Lecture 8: String Matching
Website with free online tools for creating word-search and other puzzles
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
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
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
Eppstein, D., "The Geometry Junkyard," website devoted to discrete and computational geometry
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
Wikipedia article on secret sharing
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)
Wikipedia article on Amdahl's law
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
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
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 "Merp" is the first few digits of the reversed Perm Number. For example, a student with the Perm Number 9876543 will have a Merp 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 Σ Merp
0 0 0 0 0 0 0 1 0 0 1 00 Absence in Lecture 8 has been explained.
0 0 0 0 0 0 0 0 0 0 0 015
0 0 0 0 0 1 0 0 0 0 1 018 Absence in Lecture 6 has been explained.
0 0 0 0 0 0 0 0 0 0 0 05
0 0 0 0 0 1 0 0 0 0 1 062 Absence in Lecture 6 has been explained.
0 0 0 1 0 0 0 0 0 0 1 065 Absence in Lecture 4 has been explained.
0 0 0 1 0 0 0 0 1 0 2 092 Oral final exam held on T 6/7, 1:00 PM, HFH 5155.
0 0 0 1 0 0 0 0 0 0 1 094 Absence in Lecture 4 has been explained.
0 0 1 0 0 0 0 0 0 0 1 111 Absence in Lecture 3 has been explained.
0 0 0 0 0 0 1 0 0 0 1 119 Absence in Lecture 7 has been explained.
0 0 0 0 0 0 1 0 0 0 1 12 Absence in Lecture 7 has been explained.
0 0 0 0 0 0 0 0 0 0 0 15
0 0 0 0 0 1 0 0 0 0 1 17 Absence in Lecture 6 has been explained.
1 0 0 0 0 0 0 0 0 0 1 183 Absence in Lecture 1 has been explained.
0 0 0 1 0 0 0 0 0 0 1 187 Absence in Lecture 4 has been explained.
1 0 0 0 0 0 0 0 0 0 1 188 Absence in Lecture 1 has been explained.
0 0 0 0 0 0 1 0 0 0 1 20 Absence in Lecture 7 has been explained.
0 0 0 1 0 0 0 0 0 0 1 23 Absence in Lecture 4 has been explained.
0 0 0 0 0 1 0 0 0 0 1 24 Absence in Lecture 6 has been explained.
0 0 0 0 0 0 1 0 0 0 1 266 Absence in Lecture 7 has been explained.
1 1 1 1 1 1 1 1 1 0 9 269
0 0 0 0 0 0 0 0 1 0 1 270 Absence in Lecture 9 has been explained.
0 0 0 0 1 0 0 0 0 0 1 272 Absence in Lecture 5 has been explained.
0 0 0 0 0 1 0 0 0 0 1 30 Absence in Lecture 6 has been explained.
0 0 0 0 1 0 0 0 0 0 1 32 Absence in Lecture 5 has been explained.
0 0 0 0 0 0 0 0 0 0 0 38
0 0 0 1 0 0 0 0 0 0 1 391 Absence in Lecture 4 has been explained.
1 0 1 0 0 1 0 0 1 0 4 396
0 0 0 1 0 0 0 0 0 0 1 398 Absence in Lecture 4 has been explained.
0 0 0 1 0 0 0 0 0 0 1 403 Absence in Lecture 4 has been explained.
0 0 0 0 0 0 0 0 1 0 1 406 Absence in Lecture 9 has been explained.
1 0 0 0 0 0 0 0 0 0 1 440 Absence in Lecture 1 has been explained.
0 0 1 0 0 0 0 0 0 0 1 443 Absence in Lecture 3 has been explained.
0 0 0 0 0 0 0 0 0 0 0 45
0 0 0 0 1 0 0 0 0 0 1 51 Absence in Lecture 5 has been explained.
0 0 0 0 0 0 0 0 0 0 0 577
0 0 0 0 0 0 0 0 0 0 0 578
0 0 0 0 0 0 0 0 0 0 0 58
1 0 0 0 0 0 0 0 0 0 1 60 Absence in Lecture 1 has been explained.
0 0 0 0 0 0 0 0 0 0 0 61
0 0 0 1 0 0 0 0 0 0 1 624 Absence in Lecture 4 has been explained.
0 0 0 0 0 0 0 1 0 0 1 629 Absence in Lecture 8 has been explained.
0 0 0 0 0 0 0 1 0 0 1 63 Absence in Lecture 8 has been explained.
0 0 0 0 0 0 1 0 0 0 1 650 Absence in Lecture 7 has been explained.
0 0 1 0 0 0 0 0 0 0 1 657 Absence in Lecture 3 has been explained.
0 0 0 0 0 0 0 0 0 0 0 700
1 0 0 0 0 0 0 0 0 0 1 72 Absence in Lecture 1 has been explained.
0 0 0 1 0 1 0 0 0 0 2 73 Oral final exam held on F 6/3, 10:00 AM, HFH 5155.
0 0 0 0 0 0 0 0 1 0 1 78 Absence in Lecture 9 has been explained.
0 1 0 0 0 0 0 1 0 0 2 790 Oral final exam held on F 6/3, 3:00 PM, HFH 5155.
0 0 0 0 0 1 0 0 0 0 1 791 Absence in Lecture 6 has been explained.
0 1 0 0 0 0 0 0 0 0 1 817 Absence in Lecture 2 has been explained.
0 0 0 0 1 0 0 0 0 0 1 819 Absence in Lecture 5 has been explained.
0 0 0 0 0 0 0 0 1 0 1 82 Absence in Lecture 9 has been explained.
0 0 0 0 0 0 0 0 1 0 1 84 Absence in Lecture 9 has been explained.
0 0 0 0 0 0 0 0 0 0 0 85
0 0 0 0 0 0 0 0 0 0 0 862
0 0 0 0 0 0 0 0 0 0 0 883
0 0 0 0 1 0 0 0 0 0 1 888 Absence in Lecture 5 has been explained.
1 1 0 0 0 0 0 0 0 0 2 91 Oral final exam held on F 6/3, 3:30 PM, HFH 5155.
0 0 0 0 0 0 0 0 0 0 0 92
0 0 0 0 0 0 0 1 0 0 1 98 Absence in Lecture 8 has been explained.
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: 1. Ten Puzzling Problems in Computer Engineering. (1) PARHAMI. Prerequisite: Open to pre-computer engineering only. 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 incoming students to challenging computer engineering problems, faced by practicing engineers and research scientists, in a way that is both entertaining and motivating. 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.
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)