ECE 1: Ten Puzzling Problems in Computer Engineering

      

Behrooz Parhami: 2008/05/07  ||  E-mail: parhami at ece.ucsb.edu  ||  Other contact info at: Bottom of this page

Go up to: B. Parhami's course syllabi or his home page

Link to  history and previous offerings of ECE 1

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.

Short article about the course philosophy and design, including description of 2 sample lectures (pdf file, forthcoming)

Long paper about the course, along with one-page description of each of the 10 course lectures (pdf file, forthcoming)

Spring quarter 2008 offering of ECE 1

This area is reserved for important course announcements:  2008/04/30: The first five class presentations have now been updated for spring 2008.

2008/04/10: Please check the attendance record at the end of this page to ensure that discrepancies or errors are detected promptly.

2008/04/07: Updated forms of Lectures 1 (Easy, Hard, Impossible!) and 2 (Placement and Routing) have been posted below.

2008/03/20: Welcome to the ECE 1 website. Because pass/not-pass grades  will be assigned based on attendance, please make sure that you read and fully understand the evaluation  policy described below.

Course:   

ECE 1 – Ten Puzzling Problems in Computer Engineering, University of California, Santa Barbara, Spring Quarter 2007, Enrollment Code 09852

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.

Instructor:   

Behrooz Parhami, Room 5155 HFH (Engineering I), Phone 805-893-3211, E-mail parhami at ece.ucsb.edu

Meetings:   

W 5:00-6:15, in Phelps 1260

Consultation:   

Open office hours, held in Room 5155 HFH (Engineering I) – T 9:00-10:30, R 10:00-11:30

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, and more 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.

Prerequisite:   

Open to pre-computer engineering and computer engineering majors only.

References:   

Textbook (required or recommended) – None.

Presentations – All lectures will be posted in PowerPoint and PDF formats to this website.

Handouts – A handout/worksheet (also available on the website) will be distributed in class.

Evaluation:   

Pass/Fail grading is based on attendance and class participation. There will be no homework or exam.

0 or 1 absence: Automatic “Pass.”
2 absences: “Pass” if you had prior approval for your 2nd absence or else had strong participation in class or out of class (via e-mail).
3 absences: Can earn a “Pass” by taking a final oral exam covering the three missed lectures.
4 or more absences: “Fail.”

Attendance will be taken as follows. Single-sheet handouts will be distributed at the beginning of each class session (additional sheets will be supplied to students who arrive no more than 10 minutes late). Students are to write their names and perm numbers on the sheets and hand them in before leaving the classroom at the end of the lecture.

Calendar:

Topics for class discussion have been scheduled as follows.

Day/Date

Topic of Discussion

Lead Puzzle

Special Notes

W 4/2 

Easy, hard, impossible! 

Collatz's conjecture 

http://en.wikipedia.org/wiki/Collatz_conjecture

W 4/9

Placement and routing

Houses and utilities

http://mathforum.org/dr.math/faq/faq.3utilities.html

W 4/16

Satisfiability

Making change

http://mathforum.org/library/drmath/view/68609.html

W 4/23

Cryptography

Secret messages

http://www.antilles.k12.vi.us/math/cryptotut/intro.htm

W 4/30

Byzantine generals

Liars and truth-tellers

http://www.math.uchicago.edu/~antonio/MEC/liars.html

W 5/7 

Binary search

Counterfeit coin

http://www.delphiforfun.org/Programs/counterfeitcoin.htm

W 5/14

 Task scheduling

Sudoku

http://www.websudoku.com
W 5/21 String matching Word search http://puzzlemaker.school.discovery.com/

W 5/28 

Sorting networks

Rearranging trains

http://www.americanscientist.org/template/AssetDetail/assetid/54774

W 6/4   

Malfunction diagnosis

Logical reasoning

http://www.expandyourmind.com/logicproblems/

Presentations

The following PowerPoint presentations (up to 2+ MB each), and equivalent PDF files, are updated periodically by the instructor. Note that any animation in the PowerPoint presentations is lost in the pdf versions. When a particular presentation/handout file has been updated for spring 2008, you will see a 2008 date in front of it; otherwise, the presentation is from last spring's offering of the course.

The following additional topics may be included in future:

  • Computational geometry

  • Loss of precision

  • Secret sharing

  • Amdahl's law

  • Predicting the future

  • Circuit value problem

  • Maps and graphs

Record of student absence (1) and presence (0); "Merp" is the first few digits of the reversed Perm #

Merp 1 2 3 4 5 6 7 8 9 10 All   Merp 1 2 3 4 5 6 7 8 9 10 All
                                                 
01 0 0 0 1 0 0 - - - - -   60 0 0 0 0 0 0 - - - - -
07 0 0 0 0 0 0 - - - - -   6371 0 0 0 0 1 0 - - - - -
080 0 0 0 0 0 1 - - - - -   6378 0 0 0 0 0 0 - - - - -
083 0 0 0 1 0 0 - - - - -   65 0 1 0 0 0 1 - - - - 2
101 0 0 1 0 0 0 - - - - -   68 0 0 0 0 1 0 - - - - -
105 0 0 0 0 0 0 - - - - -   70 0 0 0 0 0 0 - - - - -
15 0 1 0 0 0 0 - - - - -   75 0 0 0 0 0 0 - - - - -
22 0 0 0 0 0 0 - - - - -   800 0 0 0 0 0 0 - - - - -
27 0 0 0 0 0 0 - - - - -   804 0 0 0 0 1 0 - - - - -
41 0 0 0 0 0 0 - - - - -   805 0 0 0 0 0 1 - - - - -
48 0 0 0 0 0 0 - - - - -   81 0 0 0 0 0 0 - - - - -
50 1 0 0 0 0 0 - - - - -   83 0 0 0 0 0 0 - - - - -
51 0 0 0 0 0 0 - - - - -   84 0 0 0 0 0 0 - - - - -
54 0 0 0 0 0 0 - - - - -   880 0 0 0 0 0 0 - - - - -
55 0 0 1 0 0 0 - - - - -   888 0 0 0 0 0 0 - - - - -
57 0 1 0 0 0 0 - - - - -   9 0 1 0 0 0 0 - - - - -

 

Return to: Top of this page  ||  Go up to: B. Parhami's course syllabi or his home page

      

Dr. Behrooz Parhami, Professor Office phone: +1 805 893 3211
Dept. Electrical & Computer Engineering Departmental fax: +1 805 893 3262
University of California, Santa Barbara Office: Rm 5155 Harold Frank Hall
Santa Barbara, CA  93106-9560  USA Deliveries: Rm 4155 Harold Frank Hall
http://www.ece.ucsb.edu/~parhami/ E-mail: parhami at ece.ucsb.edu