Baase emphasizes the development of algorithms through a step-by-step process, rather than merely presenting the end result. Three chapters on modern topics are new to this edition: adversary arguments and selection, dynamic programming, and parallel algorithms. Computer Algorithms, Third Edition. Solutions to Selected Exercises. Allen Van Gelder. February 25, 2000.
Allen Van Gelder's research interests include development of algorithms for propositional satisfiability and quantified boolean formulas, methods for verifiable software, theorem proving, analysis of algorithms, parallel algorithms, computer graphics, and scientific visualization. He received a National Science Foundation Presidential Young Investigator Award in 1989 to investigate the use of logic programming for problems in database and artificial intelligence systems.
Office Hours, Winter 2020: Mon 4:15-5:15, Wed 4:15-5:15, plus drop-in or appt.
CSE102 Winter20-02 web page
Introduction to Analysis of Algorithms
CSE102 Fall 2019 web page
Introduction to Analysis of Algorithms
NOTE: Earlier classes use CMPS not CSE.
CMPS 102 Spring 2019 web page
Introduction to Analysis of Algorithms
CMPS 101-01 Spring 2017 web page
Algorithms and Abstract Data Types
CMPS 132/W Winter 2017 web page
Computational Complexity and Computability
CMPS 101-02 Fall 2016 web page
Algorithms and Abstract Data Types
Send email if you need to see: CMPS 101-02 Fall 2015 web page
Algorithms and Abstract Data Types
Send email if you need to see: CMPS 101 Spring 2015 web page
Algorithms and Abstract Data Types
CMPS 211 Winter 2015 web page
Combinatorial Algorithms
CMPS 130 Fall 2014 web page
Computational Models
CMPS 132 Spring 2014 web page
Computational Complexity and Computability
CMPS 217 Winter 2014 web page
Logic for Computer Science
Send email if you need to see: CMPS 101 Fall 2013 web page
Algorithms and Abstract Data Types
Global Warming and Extreme Weather,A Quick Tutorial
Papers by Allen Van Gelder Papers by Title
Review-Period Papers by Title by Allen Van Gelder
indexPapersPdf.html by Allen Van Gelder
Various software (ftp)
ColorSat misc files related to graph coloring with SAT
CarefulRanking documentation and coderelated to SAT 2011 paper.
ProofChecker documentation and code
WildBenches2009 has 20 benchmarks from the Application sectionof the SAT 2009 competition, phase 2.
The reason these are called wild is that their behavior seems to be ratherunpredicatable. It might be that solver A solves instance 1 in a minute or sowhile solver B times out at 5 hours, and at the same time, solver B solvesinstance 2 in a minute or so while solver A times out at 5 hours.In some cases, slightly jiggling an instance or a parameter of the solverchanges the time by a large factor.I am talking about good solvers that did well in this competition and/orearlier competitions.
The selection is heuristic, not scientific.My intention is to have a set of benchmarks that a researcher can conceivablysolve completely without ANY timeouts.Some instances are SAT, some are UNSAT.
Also see the main web pagehttp://www.satcompetition.org.
The reason these are called wild is that their behavior seems to be ratherunpredicatable. It might be that solver A solves instance 1 in a minute or sowhile solver B times out at 5 hours, and at the same time, solver B solvesinstance 2 in a minute or so while solver A times out at 5 hours.In some cases, slightly jiggling an instance or a parameter of the solverchanges the time by a large factor.I am talking about good solvers that did well in this competition and/orearlier competitions.
The selection is heuristic, not scientific.My intention is to have a set of benchmarks that a researcher can conceivablysolve completely without ANY timeouts.Some instances are SAT, some are UNSAT.
Also see the main web pagehttp://www.satcompetition.org.
purse-poster.pdf SAT 2005 and 2007 Competition Scoring Rules
purse-poster.ps and some 2005 results
purse-poster.ps and some 2005 results
JSAT System Description Papers
Call (unofficial)
Proposal and Motivation
Allen Van Gelder and Daniel LeBerre
Call (unofficial)
Proposal and Motivation
Allen Van Gelder and Daniel LeBerre
CMPS201, Analysis of Algorithms, Fall 2009:
Fall 2009 web page
Fall 2009 web page
1ST CALL FOR WORKSHOPS, COMPETITIONS, AND TUTORIALS
Sixteenth International Conference onTHEORY AND APPLICATIONS OF SATISFIABILITY TESTING --- SAT 2013
Also see the main web pagehttp://sat2013.cs.helsinki.fi/.
Sixteenth International Conference onTHEORY AND APPLICATIONS OF SATISFIABILITY TESTING --- SAT 2013
Also see the main web pagehttp://sat2013.cs.helsinki.fi/.
DataStructures and Analysis of Algorithms
Section 1
Teaching Assistant: | |
Instructor: Jana Kosecka | Brendan Drew |
Office hours: Tuesday 3-5pm | Office hours: |
Contact: Office 417 ST2, [email protected], 3-1876 | Monday 4-6pm, Wednesday 7:20-9pm |
Course web page: http://www.cs.gmu.edu/~kosecka/cs483.html | Office: 365 ST2 |
Prerequisites:
CS 310 and CS 330 Calculus (MATH 113, 114, 213) and MATH 125
CS 310 and CS 330 Calculus (MATH 113, 114, 213) and MATH 125
Required Textbook:
Sara Baase, Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, Third Edition, Addison-Wesley, 1990
Sara Baase, Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, Third Edition, Addison-Wesley, 1990
Course Requirements, Grading and Policies:
There will be a midterm examination, several practice homework assignments and a comprehensive final examination.
There will be a midterm examination, several practice homework assignments and a comprehensive final examination.
All required assignments must be completed by the stated due date and time. There will be absolutely noextensions for the homeworks (not even in the case of emergency). Your lowest homework grade will not be counted towards your finalgrade.
Please note that all coursework is to bedone independently. Plagiarizing the homeworks will be penalized bymaximum
negative credit and cheating on the exam will earn you an F in the course. See the GMU HonorCode System and Policies at http://www.gmu.edu/catalog/acadpol.html and http://www.cs.gmu.edu/honor-code.html.
You are encouraged to discuss the material BEFORE you do the assignment. Asa part of the interaction you can
discuss a meaning ofthe question or possible ways of approaching the solution. Thehomework should be written strictly
by yourself. In caseyour solution is based on the important idea of someone else please acknowledge that in your solution,
to avoid any accusations.
negative credit and cheating on the exam will earn you an F in the course. See the GMU HonorCode System and Policies at http://www.gmu.edu/catalog/acadpol.html and http://www.cs.gmu.edu/honor-code.html.
You are encouraged to discuss the material BEFORE you do the assignment. Asa part of the interaction you can
discuss a meaning ofthe question or possible ways of approaching the solution. Thehomework should be written strictly
by yourself. In caseyour solution is based on the important idea of someone else please acknowledge that in your solution,
to avoid any accusations.
Grading:
Quizes 30% (about every 2-3 weeks)
Midterm 30%
Final Exam 40%
Quizes 30% (about every 2-3 weeks)
Midterm 30%
Final Exam 40%
You will be allowed to have onesheet of (8.5 x 11) of notes for the midterm and two sheets
for the final. No copying of anything from the textbook or another person is allowed. You can
write some things verbatim. You can also writeyour notes on the computer and print them.
The notes sheet will be handed in with the exam. Thequiz will be a closed book exam - no notes
will be allowed.
for the final. No copying of anything from the textbook or another person is allowed. You can
write some things verbatim. You can also writeyour notes on the computer and print them.
The notes sheet will be handed in with the exam. Thequiz will be a closed book exam - no notes
will be allowed.
Important Dates:
Exam 1 - October 21st (in class), Review session Monday Oct 13th in ENT 276 and 7pm.
Exam 2 - December 9 (in class)
Tentative List of Topics:
- Introduction, Recurrences,
- Sorting; Divide and Conquer, Insertion Sort, Quicksort, Merge Sort, Heapsort
- Sorting in Linear Time, Selection
- Dynamic sets,Hash Tables, Binary Search Trees, Red-Black Trees
- Dynamic Programming, Greedy Algorithms
- Graph Algorithms - BFS, DFS, Connected Components
- Optimization problems, Greedy Algorithms, Minimum Weight Spanning Trees
- Shortest Path, All pairs Shortest Path, Transitive Closure
- Dynamic Programming
- NP-completness
1. Analysis algorithm, asymptotic growh rate, function comparison
(reading chapter 1, handout1 (.pdf)), read/be familiar with chapter 2 - Abstract data types
Practice problems 1.23 (a,b,d), 1.26, 1.27, 1.28, 1.30, 1.31 a. 1.41 - sample solutions
2. Optimality, Decision Trees (finish chapter 1).
Recursion and Induction (chapter 3.3-3.4, 3.6)
3. Recursion and Induction continued - recurrence trees, types of recurrences, solving recurrences. 3.7 - up to 3.7.1 - handout2 (.pdf)
Practice problems 3.6, 3.8, 3.10 (b,c,e)
4. Quiz, Master's Theorem, Sorting Algorithms - Quicksort handout3 (.pdf)
3.7.1-3.7.3, 4.4 (read also the average case)
5. Merging Sequences, Heapsort, Decision Trees (Lower bound for worst case)
4.5- 4.7 (up to 4.7.3),4.8 (up to 4.8.6), 4.9. handout4 (.pdf)
Practice Problems (4.6, 4.12, 4.15, 4.19, 4.29, 4.34, 4.35) - sample solutions
6. Radix Sort (4.11), Selection Problem (Chapter 5 - all except 5.3.3, 5.6, proofs
of theorems are optional e.g. Th 5.1. ). sample problems and solutions
Practice problems (4.51 (except c and g),4.55, 4.46, 5.4., 5.6a)
7. Quiz (Oct 7th) Dynamic Sets - Red-Black Trees, Hashing, Union-Find (6.6, 6.5, 6.6)
8. No Class - Columbus Day break
9. Midterm exam (Oct 21st) Practice problems 4.58
10. Graphs, Graph traversal algorithms (chapter 7 except 7.5 and 7.7)
Practice problems 7.1. 7.2, 7.4-7.5. 7.8 ,7.9, 7.11a
11. Minimum Spanning Trees chapter 8, homework (.pdf)
hw solutions (.pdf) Practice problems 8.1, 8.2, 8.6 , 8.8
12. Shortest path algorith (8.3), Transitive closure, All pairs shortest path
chapter 9 reading: 9.1-9.4. Practice problems 9.2, 9.3, 9.8 slides (.pdf)
13. Dynamic Programming: Introduction chapter 10:10.1-10.2 - slides (.pdf)
homework (.pdf)
14. Tractable and Intractable problems, chapter 13.1-13.3slides (.pdf)
Additional sample probles with solutions, which may help you to study
Problems1 (.pdf)
Sample exams and quizes
Sample Midterm (.pdf) , Practice Final (.pdf)
, Sample Quiz (.pdf)