CISC365* and CMPE365* Algorithms IFall 2016 
Image by rekapalli, used under Creative Commons licence 
Internal Links  Announcements  
Personnel  
Course Information  
Schedule  
Course Plan and Record  
Labs  
Practice Problems  
Recommended Readings  
Sample Tests  
Academic Integrity in CISC 365  
External Links 
Queen's School of Computing 
Computing
Students'
Association 

Class
Photo Gallery 

Learning
 Your First Job (Paper by Dr. R. Leamnson)  ESSENTIAL READING 

Academic
Integrity 

Date  Subject  Text 
16/9/15 
Notetaker Request 
Please consider
volunteering to be a notetaker for another student in this
class. See this
link for more information. 
Instructor 
Dr. Robin W. Dawes 

Goodwin 537 

dawes
AT cs DOT queensu DOT ca 

http://sites.cs.queensu.ca/dawes/ 

5336061 (but email is a much better
idea) 

Office Hours: TBA 
TAs 
Name 
Email 
Office Hours 
Picture 
Zach Baum 
zac.baum 

Wenjie Li 
liwenjie@cs.queensu.ca 

Kainoa Lloyd 
13krl1 

Mareena Mallory 
12mmm13 

Melissa Mangos 
12mfm5 

Mariam El Mazour 
mariam.el.mezouar 

Blake Pyman 
pyman@cs.queensu.ca 

Matthew Sherar  12mds7  
Anastasiya Tarnouskaya  12at59 
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. Class Choice (three or more topics will be proposed, the class will choose one by vote) 
Marking Scheme 
For CISC365: There
will be five 50minute tests. The lowest of the five marks
will count for 12%, and the other four will each count for 22% For CMPE365: There will be five 50minute tests. The lowest of the five marks will count for 10%, and the other four will each count for 20% There will be two graded lab problems, worth 5% each. 
Labs (CMPE380) 
The lab problems are intended for independent work. TAs will be present in the labs to assist with the lab problems. 
Class
Schedule Labs 
Tuesday 2:30  3:20 Wednesday 4:30  5:20 Friday 3:30  4:20 

Test
Schedule 
Date 
Location 
Material 
Solutions 
Test 1 
Friday October 7 
TBA 

Test 2 
Friday October 21 
TBA 

Test 3 
Friday November 4 
TBA 

Test 4 
Friday November 18 
TBA 

Test 5 
Friday December 2 
TBA 

Lab Assignment 1 
Week 6 

Lab Assignment 2  Week 12 
Week 1  Tuesday, September 13 Plan: Intro and Review PDF of Intro Material PDF of Dijkstra's Algorithm 
Wednesday, September 14 Plan: NPCompleteness PDF of Dijkstra's Algorithm Complexity Analysis 
Friday,
September 16 Plan: NPCompleteness PDF of Dijkstra's Algorithm Correctness Proof, and Variations of the Algorithm 
Week 2  Tuesday, September 20 Plan: NPCompleteness 
Wednesday, September 21 Plan: NPCompleteness 
Friday,
September 23 Plan: NPCompleteness PDF of Complete Notes for the Week (or should that be NPComplete Notes) 
Week 3  Tuesday, September 27 Plan: CNFSAT to kClique 
Wednesday, September 28 Plan: Subset Sum 
Friday,
September 30 Plan: Dividing and Conquering PDF of Notes for the Week (but definitely not notes for the weak  this week covered more NPCompleteness, a clever algorithm for Subset Sum, and an even more clever algorithm for finding the longest path in a tree) 
Week 4  Tuesday, October 4 Plan: Closest Pair of Points 
Wednesday, October 5 Plan: Road Trip! @#! Points on a #@&&! Plane! Let's Drive 
Friday,
October 7 TEST 1 Solutions 
Week 5  Tuesday, October 11 Plan: Greedy Algorithms 
Wednesday, October 12 Plan: Greedy Activity Selection 
Friday,
October 14 Plan: Huffman Coding All Greedy, All the Time 
Week 6  Tuesday, October 18 Plan: Knapsacks and Trees Packed with Greed 
Wednesday, October 19 Plan: Nine Walkers 
Friday,
October 21 TEST 2 
Week 7  Tuesday, October 25 Plan: Dynamic Programming 
Wednesday, October 26 Plan: Dynamic Programming 
Friday,
October 28 Plan: Dynamic Programming Lots of Dynamic Programs 
Week 8  Tuesday, November 1 Plan: The End of Dynamic Programming ... ENOUGH Already with the Dynamic Programming 
Wednesday, November 2 Plan: Search for Tut's Tomb 
Friday,
November 4 TEST 3 
Week 9  Tuesday, November 8 Plan: Branch and Bound The Basics Road to Tut's Tomb.pdf 
Wednesday, November 9 Plan: More Branching Best First is Best 
Friday,
November 11 Plan: More Bounding Task Assignment ("He tasks me; he heaps me!") as LibreOffice spreadsheet ... as pdfs : Sheet 1 Sheet 2 Sheet 3 
Week 10  Tuesday, November 15 Plan: End of Branch and Bound 
Wednesday, November 16 Plan: The Beginning of Genetic Algorithms 
Friday,
November 18 TEST 4 
Week 11  Tuesday, November 22 Plan: Class Choice 
Wednesday, November 23 Plan: Class Choice 
Friday,
November 25 Plan: Another Week of Genetic Algorithms Demo Programs: Genetic Algorithm for Knapsack  small example  permit clones Genetic Algorithm for Knapsack  small example  defeat the clones Genetic Algorithm for Knapsack  large example  defeat the clones Genetic Algorithm to maximize an unknown function Genetic Algorithm to Optimize a Cylinder  permit clones Genetic Algorithm to Optimize a Cylinder  defeat the clones 
Week 12  Tuesday, November 29 Plan: Class Choice Last words about Genetic Algorithms 
Wednesday, November 30 Plan: Mystery 
Friday,
December 2 TEST 5 
Week  Lab Problem  My Solution 
1 
no lab  
2 
Connecting
Flights Instructions for Completing the Assignment Data Set 

3 

4 
The
purest and most thoughtful minds are those which love colour the
most. Graph1 Graph2 Graph3 Graph4 Graph5 

5 

6 
Making
Big Data a Bit Smaller Data for part a) : Sam McGee.txt Data for part b) : Dictionary.txt Mystery.txt 

7 

8 
Strange
Things Done in the Midnight Sun Test Data File 1 Test Data File 2 Test Data File 3 Test Data File 4 

9 

10 
Qooqle
Rising Test Data File 1 Test Data File 2 Test Data File 3 Test Data File 4 Test Data File 5 Test Data File 6 

11 

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  
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 



Test 1  Test 1 from 2015  Solutions 
Test 2  Test
2 from 2015 
Solutions 
Test 3  Test
3 from 2015  with solutions 

Test 4  Test
4 from 2015  with solutions 

Test 5  A
Very Good Sample Question for Test 5 
Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments 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) and from the instructor of this course.
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 can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.
The preceding text on academic integrity is based on a document written by Prof. Margaret Lamb and is used here with her permission.