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

Instructor: Zvonimir Rakamaric
Mondays, Wednesdays 11:50am-1:10pm
MEB 1225
Office hours: Catch me after class; find me in my office; email me.
Mailing list: fcs@list.eng.utah.edu (everyone enrolled must subscribe)

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

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.

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:

Presentation advice:

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.