Queen's School of Computing CISC/CMPE-365* - Fall 2016 Title
CISC-365*
and
 
CMPE-365*

Algorithms I

Fall 2016


Image by rekapalli, used under Creative Commons licence

Internal LinksAnnouncements

Personnel

Course Information

Schedule

Course Plan and Record

Labs

Practice Problems

Recommended Readings

Sample Tests

Academic Integrity in CISC 365


External_Links
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






Announcements

Announcements
Date Subject Text
16/9/15
Note-taker Request
Please consider volunteering to be a note-taker for another student in this class.  See this link for more information.











Return to top



Personnel

Personnel
Instructor
Dr. Robin W. Dawes
RWD
Goodwin 537 
dawes AT cs DOT queensu DOT ca
http://sites.cs.queensu.ca/dawes/
533-6061 (but e-mail is a much better idea)
Office Hours: TBA

TAs
Name
Email 
Office Hours
Picture

Zach Baum
zac.baum


Wenjie Li
liwenjie@cs.queensu.ca

Wenjie
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






Return to top



Course Information

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.
Class Choice (three or more topics will be proposed, the class will choose one by vote)
Marking Scheme
For CISC-365: There will be five 50-minute tests.  The lowest of the five marks will count for 12%, and the other four will each count for 22%

For CMPE-365:
There will be five 50-minute 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 (CMPE-380)
The lab problems are intended for independent work.  TAs will be present in the labs to assist with the lab problems.



Return to top



Schedule

Schedule_Table
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





Return to top



Course Plan and Record

Record Table

Week 1 Tuesday, September 13
Plan: Intro and Review
PDF of Intro Material
PDF of Dijkstra's Algorithm
Wednesday, September 14
Plan: NP-Completeness
PDF of Dijkstra's Algorithm Complexity Analysis

Friday, September 16
Plan: NP-Completeness
PDF of Dijkstra's Algorithm Correctness Proof, and Variations of the Algorithm
Week 2 Tuesday, September 20
Plan: NP-Completeness

Wednesday, September 21
Plan:  NP-Completeness

Friday, September 23
Plan: NP-Completeness
PDF of Complete Notes for the Week (or should that be NP-Complete Notes)
Week 3 Tuesday, September 27
Plan: CNF-SAT to k-Clique

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 NP-Completeness, 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




Return to top



Labs

Labs
Week Lab Problem My Solution

no lab

Connecting Flights

Instructions for Completing the Assignment

Data Set





The purest and most thoughtful minds are those which love colour the most.

Graph1
Graph2
Graph3
Graph4
Graph5





Making Big Data a Bit Smaller

Data for part a) :  Sam McGee.txt

Data for part b) :  Dictionary.txt
                              Mystery.txt





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




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 





Return to top



Practice Problems

Practice Problems Table
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



























Return to top



Recommended Readings

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







Here are some of the sources I used when preparing the lectures on Genetic Algorithms:

https://svn-d1.mpi-inf.mpg.de/AG1/MultiCoreLab/papers/ebook-fuzzy-mitchell-99.pdf

We covered some of Chapter 1 of Mitchell's book.  There are some practice questions at the end of the chapter, but many relate to material we did not cover.

http://www.iitg.ernet.in/rkbc/CE602/CE602/Genetic%20Algorithms.pdf

The pdf listed above contains many examples but they are not very well explained.

http://www.slideshare.net/paskorn/simulated-binary-crossover-presentation

This set of slides gives a fairly good explanation of simulated binary cross-over.  The formulas are slightly different from the ones we used in class but the result is identical.
































Return to top



Sample Tests

365 Sample Tests
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



Return to top



Academic Integrity in CISC 365

Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).

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.



Return to top