# Teaching : CS 5100/6100 – Foundations of CS | Spring 2013

** Instructor:** Zvonimir Rakamaric

**Mondays, Wednesdays 11:50am-1:10pm**

Time:Time:

**MEB 1225**

Location:Location:

**Office hours**: Catch me after class; find me in my office; email me.

**Mailing list:**fcs@list.eng.utah.edu (everyone enrolled must subscribe)

**Disclaimer**

This is a tentative course syllabus and subject to potential tweaks and updates.

**Course Topics**

This course is intended to cover theoretical foundations of computer science. As this is a broad area impossible to cover in one semester, we will primarily focus on topics related to one’s ability to understand and design correctly functioning complex systems, and clearly describe the workings of these systems. These include:

- Mathematical logic
- Propositional (syntax, semantics, SAT, BDD)
- First-order (syntax, semantics, theories, decision procedures, SMT)

- Model checking
- Basic automata theory
- Temporal logics

- Concurrency
- Proofs
- Shared memory consistency models

- Specifying systems
- Operational semantics

**Prerequisites**

I intend to make the course fairly self-contained, but familiarity with mathematical logic, decision procedures, and model checking will be helpful. You should also be familiar with a programming language of your choice since some homework assignments and projects might involve coding.

**Grading and Policies**

The final grade will be based on class participation (10%), homework assignments (40%), and course project (50%). There will be 4-5 homework assignments covering various topics presented in class. Each student in the class will also be responsible for completing a course project of their choice.

Academic misconduct: Please read the School of Computing Policy Statement of Academic Misconduct.

Late policy: Late homework assignments and project deliverables will not be accepted unless you contact me before the deadline and have a good reason.

Collaboration and cheating: I encourage discussing homework assignments and projects with others since that’s often a good way to learn the material. However, all students must independently write their own code and write-ups. Discussing solutions at high-level is fine. Basing your code/write-up on any other code/write-up is cheating. So, do not copy solutions from another student, do not copy solutions from the internet, do not even look at solutions from another student, do not ask for solutions on online forums (e.g., Stack Overflow). Make sure you acknowledge appropriately any outside materials you used or rely on. This includes papers, books, websites, personal communication, source code, etc.

Students with disabilities: Reasonable accommodation will gladly be provided to students with disabilities. Please let me know the situation as soon as possible. If you wish to qualify for exemptions under the Americans with Disabilities Act (ADA), you should also notify the Center for Disability Services.

**Textbook**

The Calculus of Computation: Decision Procedures with Applications to Verification by Aaron R. Bradley and Zohar Manna. We will be somewhat following this book in the first several lectures. You should have free access at the department to an electronic version through SpringerLink.

**Course Projects**

Your project can take one of these two forms:

1) Mini research project: This is your “traditional” course project. Come up with an interesting topic related to the course. Ideally it should also overlap with your research area. Study related work. Explore new directions and invent and implement new approaches. Implement existing algorithms and evaluate them. Write a project report in the end (at most 5 pages).

2) Literary review: Pick a course-related topic that you are interested in, and thoroughly read, analyze, evaluate, and summarize research materials related to the topic. Write a critical summary of your findings (at most 10 pages).

If you have an idea for a project that doesn’t fit into the listed categories, come and talk to me and I’ll try to accommodate it. If you don’t have an idea for a project, stop by my office and we’ll brainstorm a nice project for you.

Team work: I will allow at most 2 students working as a team on mini research projects. Of course, the project size should scale accordingly. Furthermore, it should be quite clear who did what and how you split up the work on the project; otherwise, points will be equally distributed among team members.

Project deliverables, presentations, grading, and deadlines:

1) Project topic (5 points, due: Feb 6 at 11:59pm): Email me a brief one paragraph description of your project topic. *Absolutely make sure you discuss your project idea with me before the project topic due date.*

2) Project proposal (5 points, due: Feb 11 at 11:59pm): Write at most 1 page *per team* describing your project plan. The proposal should include: project title, list of team members, short description of related work, and proposed work with basic milestones. It doesn’t have to be too detailed.

3) Project proposal presentation (10 points, Feb 13 in class): Present your project idea and basic related work in class. One presentation per team. Please find below some resources on how to give a good presentation. The exact format is yet to be determined.

4) Project one-on-ones (10 points, Mar 8 and Apr 18 instead of class): Show up prepared to discuss your progress and ask questions. Having a demo would be great, but is not a requirement.

5) Final presentation (20 points, Apr 24 in class): Present your project in class. One presentation per team. Presentation length: 10 minutes for one-person teams, 15 minutes for two-person teams.

6) Final report (50 points, due: May 6 at 11:59pm): Page limits for final reports listed under project types (double them if working as a team) exclude references and appendices, but note that appendices won’t influence grading and will be read at instructor’s discretion. *It should be very clear from the report exactly who did what on the project since otherwise all team members will get the same score.* Please find below some resources on writing.

Notes: All written deliverables should be single-columned single-spaced with an 11 point font and 1 inch margins, and should be submitted as **PDF** files.

Writing advice:

- Common Errors in Technical Writing, J. Owens
- Writing Technical Articles, H. Schulzrinne
- Common Bugs in Writing, H. Schulzrinne
- The Science of Scientific Writing, G. D. Gopen and J. A. Swan
- How to Write a Great Research Paper, S. P. Jones
- Academic Writing Check (automatically checks text for common pitfalls), D. Akhawe

Presentation advice:

- How to Present a Paper, L. Lamport
- How to Prepare for a Paper Presentation in a Seminar, S. Venkatasubramanian
- How to Give a Good Research Talk, S. P. Jones
- How to Give an Academic Talk, P. N. Edwards
- Presentation Zen: Simple Ideas on Presentation Design and Delivery, G. Reynolds

**Calendar (tentative):**

Date |
Topic |
Notes |

Mon, Jan 7 | Course Overview & Introduction | Lecture 1 |

Wed, Jan 9 | Propositional Logic | Lecture 2 |

Mon, Jan 14 | SAT | Lecture 3 |

Wed, Jan 16 | Using a SAT Solver | Homework 1 |

Mon, Jan 21 | Martin Luther King Day | |

Wed, Jan 23 | First-Order Logic | Lecture 5 |

Mon, Jan 28 | First-Order Theories I | Lecture 6 |

Wed, Jan 30 | First-Order Theories II | Lecture 7, Homework 1 deadline |

Mon, Feb 4 | Cancelled | |

Wed, Feb 6 | SMT Solvers I | Lecture 8, Project topic due |

Mon, Feb 11 | SMT Solvers II | Lecture 9, Project proposal due |

Wed, Feb 13 | Project Proposal Presentations | Homework 2 |

Mon, Feb 18 | Presidents’ Day | |

Wed, Feb 20 | Turing Machine & Computability | Lecture 10 |

Mon, Feb 25 | The Halting Problem | Lecture 11 |

Wed, Feb 27 | Complexity I | Lecture 12, Homework 2 deadline |

Mon, Mar 4 | Complexity II | |

Wed, Mar 6 | Binary Decision Diagrams | Lecture 13 |

Mon, Mar 11 | Spring Break | Homework 3 |

Wed, Mar 13 | Spring Break | |

Mon, Mar 18 | Project One-on-Ones | |

Wed, Mar 20 | Introduction to Model Checking | Lecture 14 |

Mon, Mar 25 | Model Checking CTL I | Lecture 15, Homework 3 deadline |

Wed, Mar 27 | Model Checking CTL II | Lecture 16, Homework 4 |

Mon, Apr 1 | Class Cancelled (Travel) | |

Wed, Apr 3 | Class Cancelled (Travel) | |

Mon, Apr 8 | Project One-on-Ones | |

Wed, Apr 10 | Guest Lecture by Prof. Ganesh Gopalakrishnan | |

Mon, Apr 15 | Symbolic Model Checking I | Lecture 17, Homework 4 deadline |

Wed, Apr 17 | Symbolic Model Checking II | Lecture 18 |

Mon, Apr 22 | Course Summary | Lecture 19 |

Wed, Apr 24 | Final Project Presentations |

Comments are closed.