CMPUT 396: Algorithmic Problem Solving
Check often. If you have clarification questions
send a message to the forum (link below). I am not using eClass in
this course, except for the forum and for submitting assignments. In
particular, due dates will NOT appear in your eClass
calendar!
Fall 2017,
Instructor: Michael Buro
Lectures: TR 8:00-9:20 TL 11 (starting Sep. 5)
Office hours MB: TR 9:30-10:00, R 12:30-13:30 (ATH 337)
Office hours TAs: send email to TA to arrange a meeting
TAs: Dylan Hyatt-Denesik (hyattden@...), Joshua Sirota (sirota@...) [UAlberta accounts]
News
- [Dec 6] Final exam section expanded, final reading assignment added
- [Nov 30] R12 released
- [Nov 23] R11 released
- [Nov 20] A6 released
- [Nov 18] p3 output corrected for A5
- [Nov 16] R10 released
- [Nov 6] A5 released (note the non-standard submission dates)
- [Nov 1] R9 released
- [Oct 24] R8 released
- [Oct 23] LQ2 moved to Nov. 7
- [Oct 23] Link to R7 added for tomorrow. It's been sitting in material/ since Friday...
- [Oct 20] A4 update: runtime environments restricted to Java 8,
Python 3, and g++ 5.4 using -std=c++14.
- [Oct 18] A4 released
- [Oct 14] R6 released (for Oct 17)
- [Oct 2] R5 released (for Oct 10)
- [Oct 1] A3 updated: added hints, adjusted problem parameter
limits, added a harder problem for part 3d)
- [Sep 30] A3 released
- [Sep 29] R4 released
- [Sep 27] exercise session material (ex01,ex02,ex03) released
- [Sep 23] LQ1 date moved to Oct. 5!
- [Sep 21] R3 released
- [Sep 19] A2 problem 2 updated
- [Sep 18] In case there are broken links to some material, follow the course material link below to see a list of available files
- [Sep 17] A2 and SQ1 results released.
- [Sep 15] Reading assignment R2 released. Study it to prepare for a potential quiz on Tuesday Sep. 19.
- [Sep 7] Reading assignment R1 released. Study it to prepare for a potential quiz on Tuesday Sep. 12.
- [Sep 6] Added induction to toolbox document
- [Sep 5] BG Questionnaire Results
- [Sep 3] CS Background Quiz is live on eClass. Please complete it soon!
- [Sep 3] Welcome to the course!
Resources
Prerequisites
Important: registration is open to anyone who has passed a CMPUT 2xx
course. Students lacking the prerequisite will be withdrawn from the
course without notice. Also helpful is the knowledge of fundamental
algorithms and data structures (e.g., CMPUT 175, 204, 304, or 275)
and coding skills in either C++, Java, or Python.
Tentative Schedule
Lecture Assign. Lecture
Week of Tues.(+1) Thurs.(+3)
(Monday) | 8:00 8:00
1. Sep.04 | L1 A1r L2 R1
2. Sep.11 | SQ? L3 L4 SQ? R2
3. Sep.18 | SQ? L5 A1d/A2r L6 SQ? R3
4. Sep.25 | SQ? L7 L8 SQ? R4
5. Oct.02 | SQ? L9 A2d/A3r L10 LQ1 R5
6. Oct.09 | SQ? L11 L12 SQ? R6
7. Oct.16 | SQ? L13 A3d/A4r L14 SQ? R7
8. Oct.23 | SQ? L15 L16 SQ? R8
9. Oct.30 | SQ? L17 A4d/A5r L18 SQ? R9
10. Nov.06 | LQ2 L19 L20 SQ? R10
-- Nov.13 | ====== Reading Week ======== ===
11. Nov.20 | SQ? L21 A5d/A6r L22 SQ? R11
12. Nov.27 | SQ? L23 L24 SQ? R12
13. Dec.04 | SQ? L25 A6d L26 SQ? REX
Legend: Li : lecture i
Ajr/Ajd : assignment j released / due (Thursdays 8:00)
LQi : long quiz i about previous 4 weeks' content (Tuesdays)
SQ? : short quiz about previous week's content (randomized)
Final Exam : Dec-21-2017 9-11am, Main Gymnasium Rows 1,3, CLOSED BOOK FORMAT
Purpose
This course presents fundamental search algorithms and their
applications to decision problems and optimization.
(Tentative) Topics
- Uninformed Search (data structures, Breadth-First Search,
Depth-First Search, Uniform Cost Search, iterative deepening)
- Informed Search (A*, Branch-and-Bound, IDA*)
- Adversarial Search and Sampling Based Methods (MiniMax, α-β, MCTS, UCT)
- Constraint Satisfaction Problems and Optimization (Constraint
Propagation, Local Search, Hill Climbing, Swarm Optimization)
Course Work
There will be 6 assignments, 8 quizzes, and a final exam.
Grading
- 30% assignments (best 5 of 6, 6% each)
- 10% short quizzes (best 5 of 6, 2% each)
- 20% long quizzes (2, 10% each)
- 40% final exam
Please visit
this page to learn about our interpretation of letter grades.
In this course grades will not be curved, they are absolute
- closely following these cut points:
≥ 95% A+ ≥ 90% A ≥ 85% A-
≥ 80% B+ ≥ 75% B ≥ 70% B-
≥ 65% C+ ≥ 60% C ≥ 55% C-
≥ 50% D+ ≥ 45% D < 45% F
subject to this important condition:
if the result of the final exam is less than 40%, the final
course grade can't be better than D+.
Quizzes
There will be 8 in-class quizzes in this course: 2 long (~40 minutes)
and 6 short (~10 minutes). After each lecture week students are
expected to go over the covered material at home and answer sample
questions that will be provided. In the Tuesday meeting the following
week there might be a short quiz that checks whether students actually
did their homework. The 6 short quizzes are scheduled randomly
throughout the term and we will only consider the best 5. Missed
short exams will receive 0 marks.
Long quizzes are scheduled ~4 weeks and ~8 weeks into the term (see
schedule). They function as "midterm exams light" covering the recent
~4 weeks of course content. All quizzes will commence 8:03 sharp.
The weight of missed long quizzes will be moved to the final exam.
Assignments
Assignments are comprised of small programming tasks and exercises
related to recently covered course material. Solutions have to be
handed in by 08:00 on the due dates electronically via eClass. We
will allow groups up to *2* students working on one assignment.
Each student will be allowed AT MOST ONE assignment submission that is
late by at most 24 hours. For such late assignments 30% of the
achievable marks will be deducted. Any subsequent late submission will
receive 0 marks - as will submissions that are late by more than 24
hours. Assignment marking related questions will be addressed by the
TAs. You need to contact them within 2 days after you the marked
assignments have been returned. Later inquiries will be ignored.
Program Input/Output
Please ensure that the following invocation of your submitted programs
works on the ugrad machines:
./prog < inputfile > outputfile
where < and > are redirection operators. Your programs are supposed
to communicate via the standard input and output streams, rather
than reading from files or writing to files.
Also, your code is not supposed to ask for inputs or to print
anything beyond what's described. Quite a few marks will be
deducted if I/O doesn't work.
Final Exam
The final 2h exam will cover all course material:
- Lectures
- Assignments
- Readings
- Quizzes
The exam question format will be similar to that of the long quizzes,
including multiple-choice and bonus questions. To prepare for the
exam, read the lecture material and then try to answer all
reading/assignment/quiz questions *before* looking up solutions (see
the "final" reading assignment for
additional questions relating to the last lecture week). Forming study
groups is highly recommended.
Deferred final exam date: Monday, Jan. 8, 2018, 14:00 to
16:00 (ATH 332)
Academic Integrity
The University of Alberta is committed to the highest standards of
academic integrity and honesty. Students are expected to be familiar
with these standards regarding academic honesty and to uphold the
policies of the University in this respect. Students are particularly
urged to familiarize themselves with the provisions of
the
Code of Student Behaviour and avoid any behaviour which could
potentially result in suspicions of cheating, plagiarism,
misrepresentation of facts and/or participation in an
offence. Academic dishonesty is a serious offence and can result in
suspension or expulsion from the University. (GFC 29 SEP 2003)
Copying and cheating on assignments will be penalized with a mark of 0
(see the standard handouts for academic dishonesty and copying and
cheating),
and Section
30.3.2 Inappropriate Academic Behaviour.
Course Policies
Unless otherwise noted,
the CS Department Policies are in effect.
Collaboration
In this course we use the "Consultation" model: students are
encouraged to discuss and solve problem sets in small groups to speed
up learning and stimulate idea exchange. In the end, however, students
must write down their own solutions and be able to solve similar
problems independently.
Regardless of the collaboration method allowed, you must always
properly acknowledge the sources you used and people you worked with.
Failure to give proper credit is considered plagiarism. In general,
academic dishonesty is a serious offence and can result in suspension
or expulsion from the University.
Your professors reserve the right to give you an exam (oral, written,
or both) to determine the degree that you participated in the making
of the deliverable, and how well you understand what was
submitted. For example, you may be asked to explain any code that was
submitted and why you choose to write it that way. This may impact the
mark that you receive for the deliverable.
Note that this potential additional questioning about your deliverable
is part of the assessment process, both summative (for marks) and
formative (for feedback to you and us). It is intended to give us
additional information about what you have learned. So, whenever you
submit a deliverable, especially if you collaborate, you should be
prepared for an individual inspection/walkthrough in which you explain
what every line of your code, assignment, design, documentation
etc. does and why you chose to write it that way.
last modified on
; you are visitor #
since Aug/8/2017