CMPE365* and CISC365* 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  
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. 
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 
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,
NPCompleteness, 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.  BranchandBound Paradigm: 15Puzzle, Travelling Salesperson Problem, etc. 
Marking Scheme 
There will be four
50minute tests (20% each) and four programming
assignments (5% each). 
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 
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 kClique is NPComplete 
Thursday, November 21 Plan: Approximation Algorithms Revised Plan: Complexity Notes: See November 19 
Friday,
November 22 Plan: Probabilistic Algorithms Revised Plan: Complexity Notes: Proving kVertex Cover is NPComplete 
Week 12  Tuesday, November 26 Plan: Probabilistic Algorithms Revised Plan: The KuhnMunkres Algorithm: Opening a New Door 
Thursday, November 28 Plan: Mystery 
Friday,
November 29 Plan: Quiz 4 Solutions 
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 redownload these files. The versions now posted have been purged of all nonASCII 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 
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 
23 a, b 24 a, b, c, d 

52  3.1  1, 2, 3  
60  3.2 
1, 8 

61  Chapter 3 Problems 
32 34 a, b, d, e 

107  Chapter 4 Problems 
41 a, b, g 42 

1101  Chapter 34 Problems 
341 d 342 a 343 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 BigO 
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 
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 recursiontree 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 NPCompleteness, very similar to the approach we will take in class 

Wikipedia 
http://en.wikipedia.org/wiki/List_of_NPcomplete_problems Just as it says, this is a big list of NPcomplete 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/lancxnp,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/cs2671995/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/CISC365. 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" 

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
Any violation of Academic Integrity in CISC365 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.
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 eagleeyed
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 kClique is NPComplete posted Notes on proving kVertex Cover is NPComplete posted 
20191125  Practice Quiz 4 solutions posted (to both practice quizzes) 
20191127  Typo corrected in kVertex Cover notes  thanks to MC who spotted the error! 