VERY IMPORTANT: ALL students SHOULD HAVE THEIR TEXTBOOKS BY DAY 1 of classes!!!
Course Description: The purpose of this course is to present the student with the mathematical techniques used for analyzing the time and space performance of computer algorithms. The focus will be on the practical application of these techniques to designing efficient algorithms. The following topics will be covered: asymptotic notation, recurrences, lower bounds for worst case and average case, dynamic programming, searching algorithms, sorting algorithms, graph algorithms, and if time allows, parallel algorithms, string matching algorithms.
Textbooks:
It is very important that ALL students have their books from Day 1.
- “Mathematical Logic for Computer Science”, by Lu Zhongwan, Second Edition, World Scientific Publishing.
- “Logic in Computer Science: Modeling and Reasoning about Systems”, by Michael Huth, Cambridge University Press.
Additional recommended reading:
- Introduction to Mathematical Logic, by Elliott Mendelson, Fifth Edition, CRC Press.
- Sets, Logic and Maths for Computing (Undergraduate Topics in Computer Science), by David Makinson
- The Nuts and Bolts of Proofs, Third Edition: An Introduction to Mathematical Proofs, by Antonella Cupillari
- How to prove it: a structured approach, by Daniel Velleman
Exams: There will be two tests, some written assignments, quizzes (announced and unannounced), a project and a presentation. For the presentation, students will individually present an algorithm research paper from a journal or conference, preferably recent.
Grades:
Test 1 20%
Test 2 25%
Presentation 10%
Quizzes and Assignments 15%
Project 25%
Class participation 5%
Announcements:
- Week 5: the office hours of Tuesday will be moved to Tuesday morning: 10am to 11:30am and Wednesday morning from 11am to noon.
- No class on February 1st: an assignment will be given in replacement of the class / to be posted later
- Midterm exam on March 8th! topics are everything we have covered since the start of the semester. The exam will be an hour and 20 minutes long. If you cannot make it, you should let me know BEFORE March 8th and reschedule the exam by March 15th at the latest.
- No class on March 22nd: an assignment will be given in replacement of the class / to be posted later
- No class on Cesar Chavez day (March 31)
- Don’t forget that April 25 is the deadline for you to pick your project option (presentation or deliverables only)
- Final examination on April 28!!! topics to be covered are everything we covered since the start of the semester. If you cannot make it, you should let me know BEFORE April 28th and reschedule the exam by May 5th at the latest.
What to expect — some of this semester’s milestones:
- Semester-long projects:
- List of projects
- Projects will be proposed during week 3: see below for the list of projects / also sent as email to all students enrolled in the class
- Students need to have chosen a project by the end of the last course of Week 5 (i.e., February, 17 at 3pm) Week 6 (i.e., February, 24 at 7pm): extension due to severe weather early February
- Week 15 and week of the finals: project presentations
- First midterm exam during week 8, on Tuesday March 8st.
- Article presentations: week 12.
- Final exam on Thursday April, 28th
Material:
- CS5303 Syllabus
- Copy of the daily grading form
- Outline of the semester Lectures and activites: to come
- The list of projects for this semester will be available during week 4
- Some notes on sets and functions
- Some notes on induction
- Online guide to programming in Prolog.
- Solutions to some exercises on sets and functions, more exercises on propositional logic, solutions of exercises on Quine method
- List of major assignments / activities and corresponding deadlines after week 11
Assignments:
- Week 11:
- Reading assignment: Chapter 3, Sections 4, 5, and 6, as well as Chapter 5 from Mathematical Logic for Computer Science
- Homework assignment, due April 14:
- exercises 3.4.2 [3,4], 3.4.3 [1,2,5,6], and 3.6.1, from Mathematical Logic for Computer Science
- Project assignment #2, due April 18: write a tutorial-type document about the topic of your project; to be done in team; here are detailed guidelines for assignment #2
- Week 10:
- Homework assignment: due April 8, prolog programming assignment.
- Week 9:
- Reading assignment: predicate logic, chapter 3 of Mathematical Logic for CS and chapter 2 (2.1 and 2.2) of Logic in Computer Science
- Homework assignment:
- exercise 2.1 [1,2,3] p. 157 of Logic in Computer Science
- exercises 2.6.3 [1,4] and 2.6.5 [3], p. 57, from Mathematical Logic for CS
- Week 8:
- Reading assignment: predicate logic, chapter 3 of Mathematical Logic for CS and chapter 2 (2.1 and 2.2) of Logic in Computer Science
- No homework assignment: week of midterm exam
- Project: description (both individual description and group questions) are due on March 11th at 7pm
- Week 7:
- Reading assignment: pages 42 to 65 of Mathematical Logic for CS
- Homework: exercises 2.5.3 [3,4] and 2.5.2 [2,6] of Mathematical Logic for CS
- Week 6:
- Reading assignment: same as for week 5, more specifically pages 42 to 65 of Mathematical Logic for CS
- Homework:
- Exercises 2.3.1, 2.4.1, 2.4.4, 2.4.5, from Mathematical Logic for Computer Science
- Week 5:
- Reading assignment:
- Chapter 2 of Mathematical Logic for CS
- Chapter 1, sections 1.1, 1.3, 1.4, 1.5 of Logic in CS
- Homework will be given in class: due Feb. 22
- Quiz on Thursday!
- Reading assignment:
- Week 4:
- Reading assignment: propositional logic (introduction, description, use)
- Projects: brainstorm about a CS project that involves logic; write a paragraph describing it, due on Feb. 15 (Tuesday of week 5)
- Quiz on Thursday!
- Week 3:
- Reading assignments: sets and functions (Chapter 1 of the first textbook, or notes posted on this website)
- Homework due on Thursday February, 3:
- exercises 8 and 11 of the list of exercises titled “Exercises on Induction”
- exercise 2 of the list of exercises titled “Induction”
- exercises 3 and 4 of the list of exercises titled “Exercises on Sets and Functions“
- Assignment for February, 1: a prolog assignment due on February, 8 !!! Now due on Feb. 15 !!!.
- To be completed by February 3rd, week 3: This assignment will not be graded but if I do not hear from you, I will assume it went well and you are (by 02/03) now familiar with prolog: if you are not yet familiar with prolog, get yourself familiar asap
- install swiprolog: http://www.swi-prolog.org/
- read the manual: http://www.swi-prolog.org/pldoc/refman/
- do exercises:
- Week 2:
- Homework due on Thursday January, 27:
- List of exercises titled “Induction“: exercise 1 and 3
- List of exercises titled “Exercises induction“: exercises 1 through 5
- Homework due on Thursday January, 27:
- Week 1: due on Thursday January, 20
- Review sets and functions
- Homework [DUE and randomly checked]: List several (at least 3) applications of these in computer science: detail and justify each item of your list.
Note: More information (such as assignments, reminders for due dates, quizzes, exams) will be posted on this page as the semester goes.
