CISC365*Algorithms I
Fall 2017 

Internal Links  Announcements  
Personnel  
Course Information  
Schedule  
Course Plan and Record  
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 
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 
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 
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% 
Class
Schedule 
Tuesday 2:30  3:20 Wednesday 4:30  5:20 Friday 3:30  4:20 

Test
Schedule 
Date 
Location 
Material 
Solutions 
Test 1 
Wednesday October 4, 4:30  5:20 
TBA 
Everything up to and including
September 29 
Solutions 
Test 2 
Friday October 20 
TBA 
Solutions 

Test 3 
Tuesday November 7 
TBA 
Solutions 

Test 4 
Friday November 17 
TBA 
Solutions 

Test 5 
Friday December 1 
TBA 
Solutions 
Week 1  Tuesday, September 12 Plan: Intro and Review PPT Slides Dijkstra's Algorithm 
Wednesday, September 13 Plan: NPCompleteness Problems  some solvable, some not 
Friday,
September 15 Plan: NPCompleteness Magical Computers and Classes of Problems 
Week 2  Tuesday, September 19 Plan: NPCompleteness 
Wednesday, September 20 Plan: NPCompleteness 
Friday,
September 22 Plan: NPCompleteness Reductions and Transformations (notes for the week) 
Week 3  Tuesday, September 26 Plan: CNFSAT to kClique Notes for Tuesday 
Wednesday, September 27 Plan: Subset Sum 
Friday,
September 28 Plan: Dividing and Conquering Notes for Wednesday and Friday 
Week 4  Tuesday, October 3 Plan: Closest Pair of Points 
Wednesday, October 4 TEST 1 Test and Solutions 
Friday,
October 6 Plan: Road Trip! Notes for the week 
Week 5  Tuesday, October 10 Plan: Greedy Algorithms 
Wednesday, October 11 Plan: Greedy Activity Selection 
Friday,
October 13 Plan: Knapsacks Notes for the week 
Week 6  Tuesday, October 17 Plan: Huffman Coding What's the Frequency, Kenneth? 
Wednesday, October 18 Plan: Nine Walkers 
Friday,
October 20 TEST 2 
Week 7  Tuesday, October 24 Plan: Dynamic Programming 
Wednesday, October 25 Plan: Dynamic Programming 
Friday,
October 27 Plan: Dynamic Programming Notes on Dynamic Programming ... so far 
Week 8  Tuesday, October 31 Plan: The End of Dynamic Programming Dynamic Programming for Subset Sum 
Wednesday, November 1 Plan: Search for Tut's Tomb 
Friday,
November 3 Plan: Branch and Bound 
Week 9  Tuesday, November 7 TEST 3 
Wednesday, November 8 Plan: More Branching 
Friday,
November 10 Plan: More Bounding Notes on Branch and Bound Slides for Search for Tut's Tomb PDF of spreadsheets showing iterations 
Week 10  Tuesday, November 14 Plan: End of Branch and Bound 
Wednesday, November 15 Plan: 
Friday,
November 17 TEST 4 
Week 11  Tuesday, November 21 Plan: Class Choice 
Wednesday, November 22 Plan: Class Choice 
Friday,
November 24 Plan: 
Week 12  Tuesday, November 28 Plan: Class Choice Complete Notes on Genetic Algorithms Demo programs in Python: Genetic algorithm to find x that maximizes an objective function Same, but with clone removal Minimize the surface area of a cylinder, using standard crossover, with clone removal. Same, with range crossover. Same, but with deliberately bad initial population 01Knapsack, small example Same, but with clone removal 01Knapsack, large example, with comparison to optimal solution found by Dynamic Programming Button object, used in visualization of the "cylinder" solution space 
Wednesday, November 29 Plan: Mystery 
Friday,
December 1 TEST 5 
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 2016 
Solutions 
Test 2  Test
2 from 2016 
Solutions 
Test 3  Test
3 from 2016 
Solutions 
Test 4  Test
4 from 2016 
Solutions 
Test 5  Test
5 from 2016 
Solutions 
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.