CS 611: Announcements Archives

September 28, 2006

Schedule change and homework question answered

I've posted the new schedule which shows the epistemology paper due friday not today. I've also posted a homework question and answer section over on the wiki. Feel free to add to the questions or answers.

Posted by jones at 04:39 PM | Comments (0)

September 25, 2006

The new wiki

Students in the class have created a Wiki for our enjoyment. Please find it at: Main Page - 611 Notes Wiki

I'll post things primarily to the wiki but place announcements here for a while.

Posted by jones at 06:23 PM | Comments (0)

September 18, 2006

Where to email your homework and other things

Neha has created an email address for CS 611 homework. That address is cs611ta@gmail.com. Please send your homework and other things to that address rather than her personal address.

Posted by jones at 02:16 PM | Comments (0)

September 12, 2006

No office hours at 10 am today

I need to be at a department meeting at 10 am. I will be in my office from about 9:10 am to 10 am and then from 1:30 pm til class starts if you want to come by then.

Posted by jones at 02:39 PM | Comments (0)

September 02, 2006

Welcome to CS 611 for Fall 2006

After taking (and passing) CS 611 you should be able to confidently read and write mathematically dense publications in the CS literature. You should also know theoretical computer science more deeply, but the primary goal is to improve your reading and writing skills through the study of logic, computability and complexity.

The textbooks are available in the BYU Bookstore. There are two texts: Computability and Complexity Theory by Homer and Selman and How to Prove it (Second Edition, it matters) by Velleman.

I've posted the syllabus and schedule for this semester. The schedule is rather detailed. However, I feel free to adjust the schedule based on class interest. They can be found under "Links" on the right side of this page.

The blog cotains entries from previous editions of CS 611. I hope you will find them useful. If not, we'll delete them and move on.

See you in class.

Posted by jones at 10:04 PM | Comments (2)

December 02, 2005

Grades and complexity evaluation

I've posted your grade estimates through today. Go to blackboard and see what you think.

also, don't forget to do your "evaluate the value of complexity theory" little papers.

I'll get reviews mailed out tonight or tommorow am depending on when they come in.

Posted by jones at 07:00 PM | Comments (0)

November 22, 2005

Course ratings for 611 worth a homework.

If you complete the course evaluation for 611 and allow me to see your name (not on the evaluation, but on the list of people that have completed an evaluation) then I will give you credit for one homework.

Have fun with it and please tell me what you think about 611 in your review.

Posted by jones at 09:53 PM | Comments (0)

November 10, 2005

Change in allocation of points on the final grade

The syllabus lists monthly exams as 30% with 10% per exam. We are having only two exams so there needs to be a change to the allocation of points.

Here's the deal: you can choose to have 30% of your grade as monthly exams with 15% per exam or you can choose to have 20% of your grade in monthly exams and allocate the extra 10% to the semester project. If you make no choice, then you will get 30% in monthly exams.

Posted by jones at 06:05 PM | Comments (0)

September 28, 2005

Draft version of my book available

The best way for me to prepare for class is to work on a book I am writing about logic, computability and complexity theory. The book is incomplete because I don't always have time to write before class, but on days which I do I usually get about 3/4 of what I want written.

I thought what I have might be useful for you to study and so I posted a link under "links" on the class webpage. Feel free to point out errors, confusing things or whatever you like about it. I want to finish the book in 1 to 2 years.

Posted by jones at 05:02 PM | Comments (0)

September 15, 2005

CS department announcements, including free food on 9/22

These come from Debi B. on the grads list. You should pay particular attention to the department pizza party.

1.Career Planning Seminar: Thursday, September 22nd, 11 am-12 pm, 1170 TMCB
The seminar will feature presentations on different computer career tracks and how to prepare to enter the field, resume writing by Bill Brady of the Business Career Center, and finding a job in the tech industry by Lloyd Hawkins, Coordinator for Career Placement from our college. Donuts served.

2. The Perfect Interview and Resume: Tuesday, September 27th, 12 pm--1:30 pm, 1170 TMCB
This presentation will be by Darrel Whitney from Lawrence Livermore. Mr. Whitney will also stay after the presentation to help individual students with their resumes. Donuts, again.

3. Technology Career Fair: Thursday, September 29th, 9 am-3:30 pm, Crabtree and Clyde Buildings
The following companies are interested in CS students and will be taking resumes and interviewing at the fair for jobs and internships: Amazon.com, Exxonmobil, Lawrence Livermore, Lockheed Martin, Micron, Microsoft, National Instruments, Rincon Research, Symantec, UDOT, US Navy Officers, Dow Chemical, Intel, IBM, Hewlett Packard, NextPage, Omniture, Boeing, Southwest Gas and Electric, Navair, Raytheon, US Navy Officers, Washington Group, CIA, Applied Signal, Northrop Grumman, Washington Department of Transportation.

CS Fall Opening Social: Thursday, September 22nd, 6-8 pm, Edgemont South Stake Park (2950 N. Canyon Road--See a map at http://cs.byu.edu.)
Free for all CS students and their families. The social will feature a pizza dinner w/dessert, volleyball, ultimate frisbee, THE jumbo slide, and a raffle. Come and get to know your professors too. To attend please pick up your tickets in the department offices in 3361 TMCB on the west side of the Talmage Building top floor.

Posted by jones at 10:21 PM | Comments (0)

August 30, 2005

More copies of H2P sections 1.1 and 1.2 available at my office

The pdf scanner in the office hasn't been fixed, so I put a few more paper copies of hte reading in the envelope by the door in my office. It was empty this morning, so I assume a few of you got the reading. If you still need a copy, come on by. Note that I was unable to figure out how to correctly align the paper to get the copier's stapler to staple the reading in a sensible place, so you'll have to cope a little.

Posted by jones at 04:31 PM | Comments (0)

August 29, 2005

Textbooks and the bookstore

It turns out that the second book didn't make it onto the textbook order for this semester. And that's unfortunate because "second" means "second book to arrive on the order and first book to be used in the class."

The bookstore is going to get copies of "How to Prove It" in 7-10 days. We need that book for the next few weeks. I will make copies of the reading available on a day to day basis on BlackBoard so that the copies will not be publically available. Note: the cs mail server is down (2:06 pm Monday) I will post the pdf to blackboard once the server is back and I am here to scan it. I've got 3 copies of the reading for wednesday in my office. Come get them. They are in a folder by the door. Make a copy if you get the last one. Once the books have arrived at the bookstore, you will be on your own.

You can order the book online at various places. If you all are so inclined, you can pool an order for several copies, get it shipped overnight, split the shipping and still probably come out under the bookstore cost. Use the comment space here to coordinate your efforts if you like.

I don't know why the bookstore ran out of "Computability and Complexity Theory" I assume it will be in stock in a week or two by the time we need it. Alternatively, you can order that book online as well and further amortize your shipping costs in one big order.

Posted by jones at 08:37 PM | Comments (0)

August 18, 2005

Textbooks for Fall 2005

If you are taking 611 in the fall of 2005, then you will need these two textbooks for sure:

Computability and Complexity Theory by Homer and Selman
How to prove it: a structured approach by Velleman

You are, of course, free to get other books to use for references during the semester. One valuable lesson to learn during your PhD (or MS) is that if you are stuck with the resources you have, then its not a bad idea to go look for more resources. Most people go to google and call it good, that works sometimes. But a good book can go a long way.

Posted by jones at 03:16 AM | Comments (2)

December 08, 2004

Gradebook online is updated

The gradebook on blackboard is up to date. I even weighted the items so that you can see approximately what your grade is. I say "approximately" for the following reasons...

1. I can't make each of the 31 homeworks worth 0.483710 % that they should be worth to total 15% for the total grade. When I do, I end up with a total of 100.00004 points possible in the weighted grade. Blackboard wants exaclty 100 points. Unfortunately, I can only use 3 digits of precision to describe the percentage weight of each grade. So you can draw two conclusions: first, blackboard has a rounding error somewhere and two, I can't fix it.

2. I can't make optional assignments optional. Right now, they are worth nothing. I will drop them into a spreadsheet and calculate those grades after the fact.

Posted by jones at 05:14 PM | Comments (0)

December 02, 2004

Third evaluation paper is optional

As you may or may not recall, there's a third "evaluation" paper due on the last day of class. Its the paper that requires you to find a complexity result in your research literature then find a paper that presents an algorithm for that problem.

I am going to make that optional. If you turn it in, I will grade it and include it in your grade. The probability of getting a very good grade on it is high, so it will pull up your average. If you don't turn it in, I will drop it from your grade and your average will be unchanged.

Posted by jones at 04:46 PM | Comments (0)

December 01, 2004

The rest of the semester

Is going to go something like this: You should turn in your reviews of the two assigned proofs, via the website, on or before Monday morning December 6.

You should turn in your final draft of your proof project on or before midnight of December 9 (meaning on or before midnight on December 9. As explained in the syllabus, nothing will be accepted after the last day of class).

There will be 1 or 2 more homework assignments.

The final exam will be in class at the appointed date and time which is Wednesday Dec 15 from 230 to 530. I know that's a bit of a disapointment perhaps, but the exam needs to be given in a controlled settting because it replaces the qualifying exam. It will be open book with 3 pages of notes. Those might be the 2 pages from the first two exams plus one more.

we will do the polynomial heirarchy today and friday. Then PSPACE on Monday then review on Wednesday. Bring questions for the review.

Posted by jones at 05:48 PM | Comments (0)

November 21, 2004

correction for the midterm

The question about Savitch's theorem should say the S(n) is space constructable not time constructable.

Remember that you should answer 4 of the first 5 questions and the sixth question.

Posted by jones at 04:47 AM | Comments (0)

October 19, 2004

Exam 2 is Wednesday and Thursday

The second exam will be in the testing center wednesday and Thursday. I extended the time limit to 3 hours. Last time, there was basically one challenging question (the one that used diagonalization) out of 6. This time, there are 2 or maybe 3 challenging questions out of 6.

Posted by jones at 10:35 AM | Comments (0)

October 13, 2004

Re-email homework for October 13

The CS department mail server seemed to have a problem with at least my account this morning and maybe others. You will probably need to resubmit your homework for today.

Posted by jones at 09:52 AM | Comments (0)

September 29, 2004

What I expect in the first paper

The quote from the syllabus about the first paper is in the body of this post. What I am looking for in the first paper is three things: 1. a paper from you research area that contains a proof. 2. Scratch work for the proof and 3. Your critique of whether or not that proof contributed to the paper or not, and, your evaluation of how well they defined the stuff that appeared in their proof. (I guess that's just a summary of the syllabus, let me try again...)

More specifically, I am looking for a copy of the paper, scratch work and about 1-2 pages of critique.

The purpose here is to take you to the top of Bloom's taxonomy of learned skills.

Paper 1: Find a paper from your research topic that includes a proof . Reverse engineer the proof into its scratch work. Critique the proof and the definitions used to state the theorem. Critique the presentation of the proof. Evaluate the utility of the proof in the paper (was it neccesary? was it useful?) Defend the inclusion of the proof in the paper, or, defend the removal of the proof from the paper. Turn in the original paper with your evaluation of the proof. Due October 1

Posted by jones at 01:08 PM | Comments (0)

September 20, 2004

My IM location

If you want to get in touch with me to ask a question etc., you can reach me on whatever instant messenger software you use as long as you can connect to me at the address: senojekim@mac.com I think it works on AIM. If you figure it out, post a comment so nobody else has to go through the trauma. My address may change in November when my .mac account expires, but I'll post the new address.

You can IM me anytime you see me online.

Posted by jones at 02:52 PM | Comments (0)

Study List for First Monthly exam

The following topics are fair game for the first exam. Post questions or comments in the comments section (note that I've removed the requirement that you have to include your email address in a comment).

1. Determining the truth value of a statement using a formally defined semantics (like using truth tables to define the truth values of boolean formulae).
2. Derriving proof rules in the sequent calculus. These are the low-level justifications for the proof strategies in the how to prove it book.
3. Finding and fixing errors in proofs.
4. Russell's paradox.
5. Kinds of functions, like, computable, onto, etc.
6. Proof by diagonalization.
7. Turing machine concepts (but not extensions to Turing Machines)
8. Proof of the Halting problem.

Posted by jones at 10:33 AM | Comments (0)

Changes to Scratchwork for Proofs

I am going to make the following changes to scratch work for the homework. This will make it easier to grade, and, hopefully, make it a more meaningful excercise. I am open to feedback about the changes so send them on over as you begin to experience it.

Change 1: Your scratchwork should be in a three column format with "givens", "goals" and "notes"--like in the How to Prove it Book.

Change 2: Include at least one place in your scratchwork where you got lost or had a question.

Change 3: If you have no questions or problems with a proof, then write "I understand this proof well enough to present it and answer questions in class" and be ready to do just that. This is after all a graduate class and its very appropriate to have you all teach eachother.

Posted by jones at 09:39 AM | Comments (0)

September 18, 2004

First Paper Coming Up

The first paper is due in two weeks. The purpose of this paper is to evaluate a proof from a paper in your research area. A more detailed description can be found in the body of this entry.

Posted by jones at 10:20 PM | Comments (0)

August 05, 2004

Textbooks for Fall 2004 are Unlikely to be in the Bookstore

[How to Prove It : A Structured Approach, Computability and Complexity ] For various administrative reasons that I am not qualified to either explain or understand. So you'll probably need to buy your textbooks for this class somewhere else. I've ordered them at the bookstore and they might get here by the time class starts if all goes well. I hope it will, but just in case, here are the texts for the class. Note that you will need both texts on the first day of class

Computability and Complexity by Homer and Selman published by Springer 2001

How to Prove it: A structured approach by Velleman published by CAmbridge University press.

Links to the texts at amazon.com are given above.

Posted by jones at 04:48 PM | Comments (0)

December 08, 2003

on line evaluation for 1 hwk credit

Don't forget that you can fill out the online course evaluation for 1 extra homework score. You will need to chose to be identified to get the point. Not filling out the form will not hurt your homework score.

Posted by jones at 08:55 AM | Comments (0)

December 02, 2003

Final Paper

The final paper includes: finding a paper that gives a complexity result for a problem in your field, finding a paper that gives an algorithm for that problem and writing one page in which you evaluate the role of the complexity result in the given algorithm.

Due the last day of classes and no later.

Posted by jones at 10:17 AM | Comments (0)

November 15, 2003

Worksheet for Video

[Richard Karp Video] Fill this worksheet out as you watch the guest speaker, I mean video, on Monday. We'll discuss it Friday. Have a good week and don't forget to sing up for your proof reviews.

Posted by jones at 04:14 PM | Comments (0)

November 13, 2003

Office hours from 10-1030 today

I will need to leave my office hours at 1030 today. If you'd like to see me this afternoon, send me an email: jones@cs.byu.edu