|
CMPE-365* and CISC-365* Algorithms I
Fall 2019 |
 Image by fdecomite, used under Creative Commons license. |
| Internal Links | Announcements | |
| Personnel | ||
| Course Information | ||
| Schedule | ||
| Course Plan and Record | ||
| Labs | ||
| Practice Problems | ||
| Recommended Readings | ||
| Sample Tests | ||
| Academic Integrity in CISC 365 | ||
| Change Log | ||
Announcements
| Date | Subject | Text |
| 20 190920 |
CSearch Registration
Sponsorship Contest |
You may be interested
in this.
It's time for my annual CSearch Conference Registration Sponsorship
Contest. |
Return to menu
Personnel
| Instructor |
Dr. Robin W. Dawes |
 |
| Goodwin 537 |
||
| dawes
AT cs DOT queensu DOT ca |
||
| http://sites.cs.queensu.ca/dawes/ |
||
| Office Hours: Monday : none Tuesday : 1:30 - 2:30 Wednesday : 2:30 - 3:30 Thursday : 10:30 - 11:30 Friday : 1:30 - 2:30 |
| TAs |
Name |
Email |
Office Hours |
|
| Karen Chen |
13kc10@queensu.ca |
|||
| Omar El Zarif |
omar.elzarif@gmail.com |
|||
| Tyler Mainguy |
tyler.mainguy@queensu.ca |
|||
| Ashiqur Rahman |
rahman@cs.queensu.ca |
|||
| Alex Salgo |
alex.salgo@live.ca |
|||
| Yinchen Shi | 15yx56@queensu.ca | |||
| Jarvis Xu | 15gx3@queensu.ca | |||
| Leonard Zhao | 16lz1@queensu.ca | |||
Return to menu
Course Information
| Calendar
Description |
Principles of design, analysis and implementation of efficient algorithms. Case studies from a variety of areas illustrate divide and conquer methods, the greedy approach, branch and bound algorithms and dynamic programming. |
| Text |
Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms (3rd Edition) |
| Syllabus |
- Complexity of
algorithms and Complexity of problems: Reducibility, P, NP,
NP-Completeness, etc. - Divide and Conquer Paradigm: Quicksort, Median, Closest Pair of Points, etc. - Principle of Optimality - Dynamic Programming Paradigm: Longest Common Subsequence, Chained Matrix Multiplication, etc. - Greedy Paradigm: Huffman Coding, Activity Selection, Minimum Weight Spanning Trees, etc. - Branch-and-Bound Paradigm: 15-Puzzle, Travelling Salesperson Problem, etc. |
| Marking Scheme |
There will be four
50-minute tests (20% each) and four programming
assignments (5% each). |
Return to menu
Schedule
| Class
Schedule |
Tuesday 9:30 - 10:20 Thursday 8:30 - 9:20 Friday 10:30 - 11:20 |
All classes are in Stirling Auditorium |
||
| Lab Schedule | Monday 11:30 - 1:20 Tuesday 3:30 - 5:20 Wednesday 11:30 - 1:20 Thursday 9:30 - 11:20 Friday 12:30 - 1:20 |
All labs are in Jeffery 155 | ||
| Quiz
Schedule |
Date |
Locations |
Material |
Solutions |
| Quiz 1 |
Friday September 27, 10:30 am |
Stirling Aud, Ellis Aud |
Divide and Conquer Algorithms |
Solutions |
| Quiz 2 |
Tuesday October 22, 9:30 am |
Stirling Aud, Ellis Aud | Greedy Algorithms |
Solutions |
| Quiz 3 |
Friday November 8, 10:30 am |
Stirling Aud, Ellis Aud | Dynamic Programming |
Solutions |
| Quiz 4 |
Friday November 29, 10:30 am |
Stirling Aud, Ellis Aud | Branch and Bound P and NP Problems |
Solutions |
| Lab Assignment Due Dates | Date | |||
| Assignment 1 | Saturday September 21, 11:59 PM | Travel
Planning |
Sample
Solution (Python) |
|
| Assignment 2 | Saturday October 12, 11:59 PM | Subset
Sum |
||
| Assignment 3 | Monday November 4, 11:59 PM | Huffman
Coding Please download the data files from the "Labs" section of this page |
||
| Assignment 4 | Saturday November 23, 11:59 PM | Agree
to Differ Data_Files.zip |
||
Return to menu
Course Plan and Record
| Week 0 | Thursday, September 5 Plan: Introduction The Most Important Algorithm in the World? Notes : Intro |
Friday, September 6 Plan: Basic Complexity Analysis Notes : Dijkstra's Algorithm |
|
| Week 1 | Tuesday, September 10 Plan: Complexity Notes: Old notes on Complexity Part 1 Old notes on Complexity Part 2 |
Thursday, September 12 Plan: Divide and Conquer Algorithms Notes : Revised and updated notes on analyzing the complexity of recursive algorithms |
Friday,
September 13 Plan: Divide and Conquer Algorithms Notes: Divide and Conquer Algorithms |
| Week 2 | Tuesday, September 17 Plan: Divide and Conquer Notes: Closest Pair of Points |
Thursday, September 19 Plan: Divide and Conquer Notes: Convex Hull |
Friday,
September 20 Plan: Divide and Conquer Notes: Subset Sum (start) |
| Week 3 | Tuesday, September 24 Plan: Divide and Conquer Notes: All Finished with Divide and Conquer |
Thursday, September 26 Plan: Greedy Algorithms Notes: See October 1 |
Friday,
September 27 Plan: Quiz 1 Solutions |
| Week 4 | Tuesday, October 1 Plan: Greedy Algorithms Notes: Road Trip |
Thursday, October 3 Plan: Greedy Algorithms Notes: Alternatives Exclude |
Friday,
October 4 Plan: Greedy Algorithms Notes: Time for a Change |
| Week 5 | Tuesday, October 8 Plan: Greedy Algorithms Notes: Hang Your Knapsack Where You Can Reach It |
Thursday, October 10 Plan: Greedy Algorithms Notes: Putting the Squeeze On |
Friday,
October 11 Plan: Dynamic Programming Algorithms Notes: Change is in the Air |
| Week 6 | Tuesday, October 15 Plan: Dynamic Programming Notes: Grid Lock |
Thursday, October 17 Plan: Dynamic Programming Notes: Something in Common |
Friday,
October 18 Plan: Dynamic Programming Notes: Summing Subsets Swiftly Notes: See October 29 |
| Week 7 | Tuesday, October 22 Plan: Quiz 2 Solutions |
Thursday, October 24 Plan: no class |
Friday,
October 25 Plan: no class |
| Week 8 | Tuesday, October 29 Plan: Branch and Bound Notes: End of Dynamic Programming: Subset Sum and Chessboard Problem |
Thursday, October 31 Plan: Branch and Bound Notes: See November 1 |
Friday,
November 1 Plan: Branch and Bound Notes: Mummy! |
| Week 9 | Tuesday, November 5 Plan: Advanced Complexity Analysis Revised Plan: Branch and Bound continued Notes: Task Assignment |
Thursday, November 7 Plan: Complexity Revised Plan: More Branching, More Bounding Notes: B&B Validity and Implementation |
Friday,
November 8 Plan: Quiz 3 Solutions |
| Week 10 | Tuesday, November 12 Plan: Complexity Revised Plan: Enough Already, Stop all This Branch and Bound Stuff! Notes: One last B&B application: the Traveling Salesperson Problem |
Thursday, November 14 Plan: Complexity Notes: See November 15 |
Friday,
November 15 Plan: Approximation Algorithms Revised Plan: Complexity Notes: P, NP and the Big Question |
| Week 11 | Tuesday, November 19 Plan: Approximation Algorithms Revised Plan: Complexity Notes: Proving k-Clique is NP-Complete |
Thursday, November 21 Plan: Approximation Algorithms Revised Plan: Complexity Notes: See November 19 |
Friday,
November 22 Plan: Probabilistic Algorithms Revised Plan: Complexity Notes: Proving k-Vertex Cover is NP-Complete |
| Week 12 | Tuesday, November 26 Plan: Probabilistic Algorithms Revised Plan: The Kuhn-Munkres Algorithm: Opening a New Door |
Thursday, November 28 Plan: Mystery |
Friday,
November 29 Plan: Quiz 4 Solutions |
Return to menu
Labs
| Week | Lab Problem | Marking Scheme | My Solution |
| 1 |
Dijkstra's
Algorithm Dijkstra_Data_6.txt Dijkstra_Data_100.txt Dijkstra_Data_200.txt Dijkstra_Data_400.txt Dijkstra_Data_800.txt Dijkstra_Data_1600.txt |
none | Solution (Python 2.7) I was asked for the "furthest from 0" solutions for the other graphs - here are the results I found: Data_100: Vertex 85 at a cost of 33 Data_200: Vertex 188 at a cost of 26 Data 400: Vertex 366 at a cost of 31 Data 800: Vertex 790 at a cost of 30 Data 1600: Vertex 1528 at a cost of 35 You may find different vertices, but hopefully the maximum cost will be the same. |
| 2 |
Travel
Planning I/O Specifications 2019_Lab_2_flights_test_data.txt 2019_Lab_2_flights_real_data.txt |
Marking | Sample
Solution (Python 3) |
| 3 |
Divide
by 2 or Divide by 3 |
none |
Sample
Solution (Python 3) |
| 4 & 5 | Subset
Sum |
TBA |
|
| 6 |
Stop
and Smell the Roses |
none |
|
| 7 & 8 |
Huffman
Coding Please re-download these files. The versions now posted have been purged of all non-ASCII characters. File1ASCII.txt File2ASCII.txt Canonical Collection 1 20191031.zip Canonical Collection 2 20191031.zip Canonical Collection 3 20191031.zip Data 20191031.zip |
||
| 9 |
Stringing
You Along DataFiles.zip |
none |
|
| 10 & 11 |
This is Assignment 4: Making a Difference Data_Files.zip |
||
| 12 |
Return to menu
Practice Problems
| Source |
Page | Exercise
Set |
Exercises |
| Text | 11 | 1.1 | 1, 2, 4, 5 |
| 29 | 2.2 |
1, 2, 4 |
|
| 37 | 2.3 |
3, 4, 5, 6, 7 |
|
| 39 | Chapter 2 Problems |
2-3 a, b 2-4 a, b, c, d |
|
| 52 | 3.1 | 1, 2, 3 | |
| 60 | 3.2 |
1, 8 |
|
| 61 | Chapter 3 Problems |
3-2 3-4 a, b, d, e |
|
| 107 | Chapter 4 Problems |
4-1 a, b, g 4-2 |
|
| 1101 | Chapter 34 Problems |
34-1 d 34-2 a 34-3 a |
|
| 369 | 15.1 |
2, 3 |
|
| 389 | 15.3 | 5 | |
| 396 | 15.4 |
1, 5, 6 (hard) |
|
| 404 | Chapter 15 Problems |
1, 2, 3, 4 |
|
| 421 | 16.1 |
1, 2, 3, 4 |
|
| 427 | 16.2 |
3, 7 |
|
| 436 | 16.3 |
2, 6 |
|
| 446 | Chapter 16 Problems |
1 |
|
| course website |
B&B
Practice Problems |
||
| 1111 | 35.1 | 1, 3 (hard) | |
| 1116 | 35.2 | 1, 5 | |
| 1127 | 35.4 |
1 | |
| Parberry & Gasarch |
30 |
3.2 True or False |
108, 109, 110, 111, 112, 113, 114,
115, 116, 117, 118, 119, 120 |
| 31 |
3.3 Proving Big-O |
133, 134, 140, 143, 144, 147 |
|
| 37 |
4.1 Simple Recurrences |
202, 203, 204, 205, 206, 207 |
|
| 67 |
7.1 Maximum and Minimum |
315 |
|
| 74 |
7.4 Binary Search |
337, 338, 341, 342, 343 |
Return to menu
Recommended Readings
| Source | Chapter |
Details |
Target
Date |
| Text |
1 |
should be familiar ideas | |
| Text |
2 |
scan this |
|
| Text |
3 |
the essential ideas here are the "big
O", "omega" and "theta" definitions and applications |
|
| Text |
4 |
- review the substitution method and
the recursion-tree method (not covered in class) - you are not required to learn the master method, but it is a very powerful tool - study it if you have time |
|
| Electronic Enterprises Laboratory | http://lcm.csa.iisc.ernet.in/dsa/node216.html a brief but clear introduction to NP-Completeness, very similar to the approach we will take in class |
||
| Wikipedia |
http://en.wikipedia.org/wiki/List_of_NP-complete_problems Just as it says, this is a big list of NP-complete problems |
||
| Wikipedia |
http://en.wikipedia.org/wiki/P_%3D_NP_problem A reasonably good summary of the problem classes P and NP and the relationship between them. Much easier to read than our text on this subject. |
||
| mathreference.com |
http://mathreference.com/lan-cx-np,intro.html This collection of pages takes the same approach to the topic as we did (concentrating on problems and algorithms, rather than on formal languages) but it strays into error quite quickly. In fact, it contains some oversimplifications and some blatant errors that you should be able to spot. Good hunting! |
||
| Text |
15 |
Intro, 15.1, 15.3, 15.4 |
|
| Text |
16 |
Intro, 16.1, 16.2, 16.3 |
|
| The internets |
Branch and Bound sources: http://www.imada.sdu.dk/Courses/DM85/TSPtext.pdf http://www.lpds.sztaki.hu/pgrade/nagy_miklos/index.html http://www.cs.berkeley.edu/~demmel/cs267-1995/assignment5.html CMSC 132 Lecture |
||
| The intertubes |
Problems
on Algorithms (2nd Edition), by Parberry and Gasarch This is a fantastic book full of problems directly related to the material covered in CMPE/CISC-365. I strongly recommend downloading a copy of this free pdf version. Professors have been known to use this book as a source for test questions. The licensing agreement prohibits posting a direct link to the pdf, so the link given here takes you to the result of Google searching for the pdf version of the book. The link you want is the first suggestion - it contains the string "home.cse.ust.hk" |
||
Return to menu
Sample Tests
Return to menu
Academic Integrity in CISC 365
Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their actions conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1 on the Arts and Science website).
Departures from academic integrity include plagiarism, use of
unauthorized materials, facilitation, forgery and falsification, and are
antithetical to the development of an academic community at Queen's. Given
the seriousness of these matters, actions which contravene the regulation
on academic integrity carry sanctions that include but are not
limited to
- a warning
- loss of grades on an assignment or test
- failure of a course
- requirement to withdraw from the university
Any violation of Academic Integrity in CISC-365 will result in a final grade of 0 in the course.
The preceding text on academic integrity is based on a document written by Prof. Margaret Lamb and is used here with her permission.
Return to menu
Change Log
| Date | Log Entry |
| 20190907 |
Notes for Week 0 posted |
| 20190908 | Lab 1 posted |
| 20190911 |
Notes for Week 1 (partial) posted |
| 20190912 | Lab 2 posted |
| 20190915 |
Notes for Week 1 complete |
| 20190917 |
Indirect link to "Problems on Algorithms" free pdf posted under
"Recommended Reading" Lab 1 Solution posted Lab 2 (Assignment 1) Marking Scheme posted |
| 20190920 |
Practice Problems from "Problems on Algorithms" posted Notes on "Closest Pair of Points" posted |
| 20190921 |
Notes on "Convex Hulls" posted |
| 20190922 |
First notes on "Subset Sum" posted Lab 3 posted |
| 20190923 |
Sample Test 1 posted Office hours updated |
| 20190924 | Complete notes on "Subset Sum" and Horowitz/Sahni algorithm posted; end of Divide and Conquer unit |
| 20190925 |
Sample Test 1 error corrected Sample Test 1 solutions posted |
| 20190929 |
Lab 4&5 posted (This is Assignment 2 - due October 12) Sample Solution for Lab 2 (Assignment 1) posted Sample Solution for Lab 3 posted |
| 20191003 |
Notes up to and including October 1 posted |
| 20191006 |
Complete notes for this week posted |
| 20191014 |
Lab 6 posted (not for handing in) Notes for 20191008 posted |
| 20191015 |
Notes for 20191010 posted Notes for 20191011 posted Notes for 20191015 posted Sample Quiz 2 posted |
| 20191016 |
Quiz 1 Solutions posted |
| 20191018 |
Sample Quiz 2 Solutions posted |
| 20191021 |
Assignment 3 posted (this is also the lab problem for Weeks
7 and 8) |
| 20191027 |
Notes on LCS posted |
| 20191028 |
Assignment 3 data files corrected |
| 20191031 |
Assignment 3 data files corrected again! Final notes for Dynamic Programming posted Quiz 2 solutions posted Practice Quiz 3 posted |
| 20191104 |
Week 9 lab posted (not for handing in) |
| 20191105 |
First notes on Branch & Bound posted Practice Quiz 3 solutions posted |
| 20191107 |
Minor errors in LCS notes corrected - thanks to eagle-eyed
students! |
| 20191110 |
Assignment 4 posted (this is also the lab problem for Weeks
10 and 11) |
| 20191113 |
Full notes for Week 9 posted Quiz 3 solutions posted |
| 20191116 | Final Branch and Bound notes posted |
| 20191117 | Full notes for Week 10 posted |
| 20191122 | Practice Quiz 4 posted |
| 20191124 | Notes on proving k-Clique is NP-Complete posted Notes on proving k-Vertex Cover is NP-Complete posted |
| 20191125 | Practice Quiz 4 solutions posted (to both practice quizzes) |
| 20191127 | Typo corrected in k-Vertex Cover notes - thanks to MC who spotted the error! |
Return to menu
557 Goodwin Hall
Queen's University
Kingston, Ontario, Canada
K7L 2N8
Phone: (613) 533-6050
Fax: (613) 533-6513
